A primer for mathematics competitions - Section 1.2 - Appetizer Problem

Problem:

Solution:

Here I present my solution. The book's solution is MUCH simpler but that is not mine.

We know $ BX : XC = 2:3 $, so let $ \vec{BX} = 2\vec{p} $. $ \vec{XC} = 3\vec{p} $.
Similarly, $ \vec{CY} = \vec{q} $, $ \vec{YA} = 2\vec{q} $.

Let $ \vec{AB} = \vec{r} $, our goal is to compute the length ratios.

$ \vec{AX} = \vec{AB} + \vec{BX} = \vec{r} + \vec{2p} $.
$ \vec{AX} = \vec{AC} + \vec{CX} = (-3\vec{q}) - \vec{3p} $.

Therefore: $ \vec{AX} = \frac{1}{5}(3\vec{r} - 6\vec{q}) $ (Just eliminate $ \vec{p} $ from the equations above)

$ \vec{BY} = \vec{BA} + \vec{AY} = -\vec{r} - 2\vec{q} $

Observe that we have two ways to get to $ O $, either starting from $ A $ or $ B $.

Let $ \vec{AO} = \alpha \vec{AX} $
Let $ \vec{BO} = \beta \vec{BY} $

Now $ \alpha ( \frac{1}{5}(3\vec{r} - 6\vec{q})) = \alpha \vec{AX} = \vec{AO} = \vec{AB} + \vec{BO} = \vec{r} + \beta \vec{BY} = \vec{r} + \beta(-\vec{r} - 2\vec{q}) $

Now the amazing thing happens, we can solve $ \alpha $ and $ \beta $ at the same time by equating coefficients.

$ \alpha ( \frac{1}{5}(3\vec{r} - 6\vec{q})) = \vec{r} + \beta(-\vec{r} - 2\vec{q}) $

$ \frac{3}{5}\alpha = 1 - \beta $ (matching coefficients of $ \vec{r} $)
$ -\frac{6}{5}\alpha = -2\beta $ (matching coefficients of $ \vec{q} $)

Solving, get $ \alpha = \frac{5}{6} $, $ \beta = \frac{1}{2} $.

So $ AO : OX = 5 : 1 $, $ BO : OY = 1 : 1 $.

Next, we tackle the $ CO:OZ $ and $ AZ : ZB $. To do that, we compute $ CO $ in two ways.

Let $ \vec{CO} = \gamma \vec{CZ} $
Let $ \vec{AZ} = \delta \vec{AB} $

$ \vec{CO} = \vec{CB} + \vec{BO} = \vec{CA} + \vec{AB} +  \frac{1}{2}\vec{BY} = 3\vec{q} + \vec{r} + \frac{1}{2}(-\vec{r} - 2\vec{q}) = \frac{1}{2}(\vec{r} + 4\vec{q}) $

$ \vec{CZ} = \vec{CA} + \vec{AZ} = \vec{3q} + \delta \vec{AB} = \vec{3q} + \delta\vec{r} $.

Now $ \frac{1}{2}(\vec{r} + 4\vec{q}) \vec{CO} = \gamma \vec{CZ} = \gamma(\vec{3q} + \delta\vec{r}) $

Now we equate coefficients again and get

$ \frac{1}{2} = \gamma \delta $ (matching coefficients of $ \vec{r} $)
$ 2 = 3\gamma $

Solving, get $ \gamma = \frac{2}{3} $, $ \delta = \frac{3}{4} $.

So $ CG : GZ = 2 : 1 $, $ AZ:ZB = 1 : 3 $.

Now at this point, we have all the length ratios we wanted. For triangles with opposite angle, we know triangle area is $ \frac{1}{2}ab\sin\theta $, so the length ratio give us triangle area ratios.

Since we do not need to vectors anymore, abusing the notation, we reuse $ P Q R S T U $ to mean the triangle areas of $ \triangle AOZ, \triangle AOY, \triangle ZOB, \triangle YOC, \triangle BOX, \triangle XOC $.

The length ratios give us these equations:

$ 2P = 5U $
$ R = 2S $
$ 5T = Q $

We wanted $ R + T $, but we do not know $ Q $, so even more is required. Here is another observation, $ \triangle ABX : \triangle ACX = 2:3 $ because they share the same height but with different base, that gives $ 3(P + R + T) = 2(Q + S + U) $, at this point, we can solve $ Q = \frac{5.5U + 4S}{1.4} $, and therefore $ R + T = 2a + \frac{16.5b + 4a}{7} $.

Even then, it is not enough, because we have no matching answer, now we pull in one more equation with the observation that $ \triangle CAE : \triangle CBE = 3:1 $ using the similar argument, now we get 5 equations:

$ 2P = 5U $
$ R = 2S $
$ 5T = Q $
$ 3(P + R + T) = 2(Q + S + U) $
$ P + Q + S = 3(R + T + U) $,

We know these equations will not give an exact answer because it is simply up to scaling. We arbitrarily set $ U = 1 $ and solve these equations (with a solver, coz I am lazy), we finally get our answers.

P = 2.500
Q = 4.722
R = 0.556
S = 0.278
T = 0.944
U = 1.000

So R + T = 1.5 and that is $ \frac{9}{2}\frac{1}{3} = \frac{9b}{2} $

So finally, that's our answer! Phew.

UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 6

Problem:

Solution:

It is simply reversing the variable order.

Suppose a set of polynomial is invlex ordered with respect to the variable order $ x > y > z $, then it is lex ordered with respect to the variable order $ z > y > x $, this is obvious to see from the definition.

A primer for mathematics competitions - Section 1.1 - Appetizer Problem 3

Problem:

Solution:

We know the method for computing the radius for the inscribed circle. Now let's think about the radius of the circumscribed circle.

The key observation is that it is a right angled triangle inside a circle, so the hypotenuse must be the diameter, and therefore $ R = \frac{c}{2} $, in our previous case, that would be $ \frac{5}{2} $.

To avoid the algebra, we can simply test the options and see which one gives $ 1 : 2.5 $. That gives option (A) right away.

Knowing the answer is (A), working backwards, we know the radius of the inscribed circle is $ \frac{ab}{a + b + c} $.

This is a particularly good looking formula. Let's see why.

Using exactly the same computation we had in the last problem, we have

$ \frac{d}{a} = \frac{1 - \frac{a}{c}}{\frac{b}{c}} = \frac{c - a}{b} $.

The equation of the angle bisector is

$ \frac{x}{a} + \frac{y}{\frac{a(c-a)}{b}} = 1 $.

Solving for $ x $ by subsituting $ y = x $, we get

$ x = \frac{a}{1 + \frac{b}{c-a}} = \frac{a (c - a)}{b + c - a} $ and that is our representation for the radius of the inscribed circle.

I claim that the two representations are equal, to see that, we write

$ \begin{eqnarray*} \frac{a (c - a)}{b + c - a} &=& \frac{ab}{a+b+c} \\ a (c - a)(a + b + c) &=& (ab)(b + c - a) \\ a^2c + abc + ac^2 - a^3 - a^2b - a^2c &=& ab^2 + abc - a^2b \\ abc + ac^2 - a^3 - a^2b &=& ab^2 + abc - a^2b \\ ac^2 - a^3 &=& ab^2 \\ ac^2 - a^3 &=& a(c^2 - a^2) \\ ac^2 - a^3 &=& ac^2 - a^3 \end{eqnarray*} $

Reading backwards, now we have shown the both representations are equal (of course, the given one look much better)

A primer for mathematics competitions - Section 1.1 - Appetizer Problem 2

Problem:

Solution:

There must be a lot of different ways to approach this problem, but personally, I like to address geometric problem analytically, or even better, algebraically.

First, we recall the fact that an inscribed circle's center is at the intersections of the angle bisectors. The equation of the angle bisector for the right angle is particularly easy, it is simply $ y = x $, now if we found another angle bisector's equation, then we are done.

Suppose we draw the angle bisector of the angle between the hypotenuse and the base, we get a diagram like this.

I want to find the y-intercept value $ d $ of that angle bisector, because then I can use intercept form for straight-line to find the equation of it. Now we know that $ \frac{d}{3} = \tan\frac{\alpha}{2} $, now we can use this awesome formula I found online.

$ \tan{\frac{\alpha}{2}} = \frac{1-\cos\alpha}{\sin\alpha} $

Now we can easily calculate $ d = 3\tan{\frac{\alpha}{2}} = 3\frac{1-\cos\alpha}{\sin\alpha} = 3\frac{1 - \frac{3}{5}}{\frac{4}{5}} = \frac{3}{2} $.

Therefore, the angle bisector's equation is $ \frac{x}{3} + \frac{y}{\frac{3}{2}} = 1 $, in intercept form.

Solving the intersection point of this with $ y = x $ gives $ x = y = 1 $, that is the center of our inscribed circle, and therefore the radius is also 1.

So the answer is (A) - A for appetizer?

A primer for mathematics competitions - Section 1.1 - Appetizer Problem 1

Problem:

Solution:

Letting the center of the circle $ O $, the square to have side length $ 2s $ and the circle have radius $ r $.

By Pythagoras theorem, we can get this relation. (Sorry Pythagoras, I just keep forgetting how to spell your name ... )

$ s^2 + (2s - r)^2 = r^2 $

This can easily simplify to $ 5s^2 - 4sr = 0 $, so we get $ r = \frac{5s}{4} $.

Therefore the area ratio is $ \frac{\pi r^2}{(2s)^2} = \frac{\pi (5s)^2}{4^2(2s)^2} = \frac{25\pi }{64} $.

The answer is (A).

UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 5

Problem:

Solution:

All we needed to do for this problem is to verify the three rules.

(i) > is a total (or linear order) on $ \mathbf{Z}^n_{\ge 0} $

This is simple to verify according to the definition. As long as two monomials are not the same, then either one is strictly larger than the other.

(ii) If $ \alpha > \beta $ and $ \gamma \in \mathbf{Z}^n_{\ge 0} $, then $ \alpha + \gamma > \beta + \gamma $.

This is also simple to verify. if $ \alpha $ has a total degree larger than $ \beta $, then so is $ \alpha + \gamma $ and $ \beta + \gamma $. Otherwise if the rightmost element of $ \alpha - \beta $ is negative, then so is $ \alpha + \gamma $ and $ \beta + \gamma $ as well.

(iii) > is a well ordering

For any set of $ n $ tuple, their total order is a set of non-negative integer and therefore there exist a smallest total degree, consider that subset of $ n $ tuples with smallest total degree.

For any set of $ n $ tuple with the same total order, their last element is an integer, and therefore exists a smallest first element, consider that subset of $ n $ tuples with smallest total degree and smallest last element. (*)

Repeat the above until we find the one with every element smallest. Now we have found a smallest element.

Suppose we have two elements $ \alpha $ and $ \beta $ with same total degree to compare with and $ \alpha $ has a smallest last element, then $ \alpha - \beta $ will have a negative rightmost non-zero element.

UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 4

Problem:

Solution:

All we needed to do for this problem is to verify the three rules.

(i) > is a total (or linear order) on $ \mathbf{Z}^n_{\ge 0} $

This is simple to verify according to the definition. As long as two monomials are not the same, then either one is strictly larger than the other.

(ii) If $ \alpha > \beta $ and $ \gamma \in \mathbf{Z}^n_{\ge 0} $, then $ \alpha + \gamma > \beta + \gamma $.

This is also simple to verify. if $ \alpha $ has a total degree larger than $ \beta $, then so is $ \alpha + \gamma $ and $ \beta + \gamma $. Otherwise if $ \alpha $ is lexicographically larger than $ \beta $, then so is $ \alpha + \gamma $ and $ \beta + \gamma $ as well.

(iii) > is a well ordering

For any set of $ n $ tuple, their total order is a set of non-negative integer and therefore there exist a smallest total degree, consider that subset of $ n $ tuples with smallest total degree.

For any set of $ n $ tuple with the same total order, their first element is an integer, and therefore exists a smallest first element, consider that subset of $ n $ tuples with smallest total degree and smallest first element.

Repeat the above until we find the one with every element smallest. Now we have found a smallest element.

Convex Optimization Exercise 2.1

Problem:

Solution:

The case for $ k = 1 $ is trivial. The case for $ k = 2 $ is given as definition. Using induction, we can assume $ \theta_1 x_1 + \cdots + \theta_{k-1} x_{k-1} \in C $ work for any set of $ \theta $ that sums to 1.

Now consider

$ \begin{eqnarray*} & & \theta_1 x_1 + \cdots + \theta_k x_k \\ &=& \theta_1 x_1 + \cdots + \theta_{k-1} x_{k-1} + \theta_k x_k \\ &=& \frac{1 - \theta_k}{1 - \theta_k}(\theta_1 x_1 + \cdots + \theta_{k-1} x_{k-1}) + \theta_k x_k \\ &=& (1 - \theta_k)(\frac{\theta_1}{1 - \theta_k} x_1 + \cdots + \frac{\theta_{k-1}}{1 - \theta_k} x_{k-1}) + \theta_k x_k \end{eqnarray*} $

Now we know the sum inside the bracket is in $ C $ by the induction hypothesis, and therefore the point we wanted to prove is also in $ C $ because of the definition.

UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 3

Problem:

Solution:

Here is the Exercise 1 statement.

Okay, I know this is stupid, this is just an exercise!

Part (a)
lex order: $ -z^2 + z + 3y + x^3 + x^2 + 2x $
$ LM(f) = z^2 $
$ LT(f) = -z^2 $
$ multideg(f) = (2, 0, 0) $
(2, 0, 0)
(1, 0, 0)
(0, 1, 0)
(0, 0, 3)
(0, 0, 2)
(0, 0, 1)

grlex order: $ x^3 - z^2  + x^2 + z + 3y + 2x $
$ LM(f) = x^3 $
$ LT(f) = x^3 $
$ multideg(f) = (0, 0, 3) $
(0, 0, 3)
(2, 0, 0)
(0, 0, 2)
(1, 0, 0)
(0, 1, 0)
(0, 0, 1)

grevlex order: $ x^3 + z^2 - x^2 + z + 3y + 2x $
$ LM(f) = x^3 $
$ LT(f) = x^3 $
$ multideg(f) = (0, 0, 3) $
(0, 0, 3)
(2, 0, 0)
(0, 0, 2)
(1, 0, 0)
(0, 1, 0)
(0, 0, 1)

Part (b)
lex order: $ -3x^5yz^4  + xyz^3 + 2x^2y^8 - xy^4 $
$ LM(f) = x^5yz^4 $
$ LT(f) = - 3x^5yz^4 $
$ multideg(f) = (4, 1, 5) $
(4, 1, 5)
(3, 1, 1)
(0, 8, 2)
(0, 4, 1)

grlex order: $ -3x^5yz^4 + 2x^2y^8 + xyz^3 - xy^4 $
$ LM(f) = x^5yz^4 $
$ LT(f) = - 3x^5yz^4 $
$ multideg(f) = (4, 1, 5) $
(4, 1, 5)
(0, 8, 2)
(3, 1, 1)
(0, 4, 1)

grevlex order: $ 2x^2y^8 - 3x^5yz^4 + xyz^3 - xy^4 $
$ LM(f) = x^2y^8 $
$ LT(f) =  2x^2y^8 $
$ multideg(f) = (0, 8, 2) $
(0, 8, 2)
(4, 1, 5)
(3, 1, 1)
(0, 4, 1)

UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 2

Problem:

Solution:

Part (a) grlex
Part (b) grevlex
Part (c) lex

UTM Ideals Varieties and Algorithm - Chapter 2 Section 2 Exercise 1

Problem:

Solution:

It is a really simple sorting exercise, so let's do some warmup.

Part (a)
lex order: $ x^3 + x^2 + 2x + 3y - z^2 + z $
$ LM(f) = x^3 $
$ LT(f) = x^3 $
$ multideg(f) = (3, 0, 0) $
(3, 0, 0)
(2, 0, 0)
(1, 0, 0)
(0, 1, 0)
(0, 0, 2)
(0, 0, 1)

grlex order: $ x^3 + x^2 - z^2 + 2x + 3y + z $
$ LM(f) = x^3 $
$ LT(f) = x^3 $
$ multideg(f) = (3, 0, 0) $
(3, 0, 0)
(2, 0, 0)
(0, 0, 2)
(1, 0, 0)
(0, 1, 0)
(0, 0, 1)

grevlex order: $ x^3 + x^2 - z^2 + 2x + 3y + z $
$ LM(f) = x^3 $
$ LT(f) = x^3 $
$ multideg(f) = (3, 0, 0) $
(3, 0, 0)
(2, 0, 0)
(0, 0, 2)
(1, 0, 0)
(0, 1, 0)
(0, 0, 1)

Part (b)
lex order: $ -3x^5yz^4 + 2x^2y^8  - xy^4 + xyz^3 $
$ LM(f) = x^5yz^4 $
$ LT(f) = - 3x^5yz^4 $
$ multideg(f) = (5, 1, 4) $
(5, 1, 4)
(2, 8, 0)
(1, 4, 0)
(1, 1, 3)

grlex order: $ -3x^5yz^4 + 2x^2y^8  - xy^4 + xyz^3 $
$ LM(f) = x^5yz^4 $
$ LT(f) = - 3x^5yz^4 $
$ multideg(f) = (5, 1, 4) $
(5, 1, 4)
(2, 8, 0)
(1, 4, 0)
(1, 1, 3)

grevlex order: $ 2x^2y^8 - 3x^5yz^4 - xy^4 + xyz^3 $
$ LM(f) = x^2y^8 $
$ LT(f) =  2x^2y^8 $
$ multideg(f) = (2, 8, 0) $
(2, 8, 0)
(5, 1 ,4)
(1, 4, 0)
(1, 1, 3)

Differential Geometry of Curves and Surfaces - Chapter 1 Section 3 Exercise 3

Problem:

Note the errata to this problem here. In particular, B should be on the line with OC and that's the half line r.

Solution:

Note that $ \angle OCA $ is a right angle.

$ \frac{CA}{2a} = \sin \theta $
$ \frac{BA}{2a} = \tan \theta $
$ CA^2 + CB^2 = BA^2 $

$ (2a \sin \theta)^2 + CB^2 = (2a \tan \theta)^2 $
$ OP^2 = CB^2 = 4a^2(\tan^2 \theta - \sin^2 \theta) $

With some trigonometry, we get

$ \sec^2 \theta = 1 + \tan^2 \theta = 1 + t^2 $
$ \cos^2 \theta = \frac{1}{\sec^2 \theta} = \frac{1}{1 + t^2} $
$ \sin^2 \theta = 1 - \cos^2 \theta = 1 - \frac{1}{1 + t^2} = \frac{t^2}{1 + t^2} $
$ \tan^2 \theta - \sin^2 \theta = t^2 - \frac{t^2}{1 + t^2} = \frac{t^4 + t^2 - t^2}{1 + t^2} = \frac{t^4}{1 + t^2} $

So we get $ OP = \frac{2at^2}{\sqrt{1 + t^2}} $

$ x = OP \cos \theta = \frac{2at^2}{1 + t^2} $
$ y = OP \sin \theta = \frac{2at^3}{1 + t^2} $

This time around I solved the problem with a good diagram and geometrical insight without using MATLAB.

Part (b) is trivial, when $ t \to \pm \infty $, $ x \to 2a $, $ y \to 0 $,

$ \alpha' = 2a\frac{1}{(1+t^2)^2}((1 + t^2)2t - t^2(2t), (1 + t^2)3t^2 - t^3(2t)) $

So $ \alpha'(t) = (0, 2a) $ as $ t \to \pm \infty $

At this point I am still confused, look like $ \alpha'(t) $ should be $ (0, 2a) $ and not $ (2a, 0) $?

Problems in Number Theory

Problem:

Solution:

The key step in this problem is to let $ n = A2^p3^q5^r $, it can be easily seen that $ A = 1 $ for minimal value in the set.

The fact that these roots are natural number give rise to these equations:

$ p - 1 = 0 \mod 2 $
$ p = 0 \mod 3 $
$ p = 0 \mod 5 $

$ q = 0 \mod 2 $
$ q - 1 = 0 \mod 3 $
$ q = 0 \mod 5 $

$ r = 0 \mod 2 $
$ r = 0 \mod 3 $
$ r - 1 = 0 \mod 5 $

By Chinese remainder theorem, we get $ p = 15 $, $ q = 10 $, $ r = 6 $, so the answer is

$ 2^15 \times 3^10 \times 5^6 = 30,233,088,000,000 $