Moon area problem

Problem:

Solution:

I am an engineer, therefore I am thinking about solving this using integration. But the area defined is hard to compute using integration because the curves defining it are not functions. (For example, at the far right end, the circle has both its upper point and lower point), so I figured something else.

 The yellow area is what we wanted, note that it is super easy to calculate the red area, as well as the sum of all colored areas, which leave us the question, how to we compute the green area? Because if we can compute the green area, the problem is pretty much solved.

The red area is simply the difference between a square of side 0.5 and a quarter circle with radius 0.5), so it is $ 0.5^2 - \frac{\pi 0.5^2}{4} \approx 0.053650459 $

The sum of all colored area is simply the same shape with side doubled, so the area is four times the red area and it is approximately $ 0.053650459 \times 4 \approx 0.214601837 $

Next we focus on the green area, zooming in, we see that is a sum of two areas, the dark green and the light green one, it is now obvious that the left one can be solved by integration, it is not so obvious that the right one can be computed relatively easily with the left hand side result as we shall see.

You probably see in the diagram that the x coordinate of the intersection point is approximately 0.29, why is that?

Let's solve this:

The equation of the big circle is $ x^2 + (y - 1)^2 = 1 \implies x^2 + y^2 - 2y = 0 $.
The equation of the small circle is $ (x - 0.5)^2 + (y - 0.5)^2 = (0.5)^2 \implies x^2 + y^2 - x - y + 0.25 = 0 $

Subtracting these two equations give $ x - y - 0.25 = 0 \implies y = x - 0.25 $.

Putting this back into the first equation gives $ x^2 + (x - 0.25 - 1)^2 = 1 $, solving we get $ x = 2x^2 - 2.5x + 0.5625 = 0 $ and therefore $ x = \frac{2.5 \pm \sqrt{1.75}}{4} $, we take the smaller value $ \frac{2.5 - \sqrt{1.75}}{4} $ as this is the leftmost intersection point.

Next, we compute we find an explicit formula for the lower big circle. We already have the implicit form: $ x^2 + (y - 1)^2 = 1 $, making $ y $ the subject gives $ y = 1 \pm \sqrt{1 - x^2} $, as this is the lower half of the circle so we take the negative sign $ y = 1 - \sqrt{1 - x^2} $

Now we do the integration, the form is simply asking for trigonometric subsitution, so we are doing it.

Let $ x = \sin u $, $ dx = \cos u du $

$ \int{1 - \sqrt{1 - x^2}dx} $
$ \int{(1 - \sqrt{1 - \sin^2 u})\cos u du} $
$ \int{(1 - \sqrt{\cos^2 u})\cos u du} $
$ \int{(1 - \cos u)\cos u du} $
$ \int{(\cos u - \cos^2 u) du} $
$ \int{(\cos u - \frac{1 + \cos 2u}{2}) du} $
$ \sin u - \frac{1}{2}(u + \frac{1}{2}\sin 2u) $
$ \sin u - \frac{1}{2}(u + \sin u \cos u) + C $
$ x - \frac{1}{2}(\arcsin x + x \sqrt{1 - x^2}) + C $

This formula gives us the dark green area (note that we can just set $ C = 0 $ as the formula gives 0 when $ x = 0 $)

If we substitute the number, the dark green area is approximately $ 0.004304482 $

If we observe carefully, the light green area is actually a similar figure. If we double the image so that the small circle has radius 1, the shape of the area is exactly the same, so we can use exactly the same formula there.

The base has length $ 2 \times (0.5 - 0.29) $ long in the doubled area, we plug in the formula, and then scale it back down (so that area is divided by 4), we get the value $ 0.002980577 $

Last but not least, given all the areas, we can now compute the moon area to be $ 0.14638126 $.

Using this simple C# Monte Carlos simulation program, I verified the answer above should be correct.

namespace Moon
{
    using System;

    class Program
    {
        static void Main(string[] args)
        {
            Random random = new Random(0);
            int numTrials = 10000000;
            int hitTrials = 0;
            for (int i = 0; i < numTrials; i++)
            {
                double x = random.NextDouble();
                double y = random.NextDouble();
                bool outsideQuarter = (x * x + y * y) > 1;
                bool insideCircle = (x - 0.5) * (x - 0.5) + (y - 0.5) * (y - 0.5) < 0.25;
                bool insideMoon = outsideQuarter && insideCircle;
                if (insideMoon)
                {
                    hitTrials++;
                }
            }
            Console.WriteLine((hitTrials + 0.0) / numTrials);
        }
    }
}

One last problem remain though, is there a simpler solution?

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

Problem:

Solution:

It took me a good while to solve this problem, but looking in retrospect, this problem is easy. It is just that the notation tripped me up.

(a)

First, note that $ \alpha \in \mathbf{Z}_{\ge 0}^{n} $, so $ \alpha = 0 $ means it is an n-tuple of all 0, which means all the powers are 0, which means the monomial is actually 1, not 0.

With that in mind, the solution for this is not hard, we do infinity descent here as follow. Suppose the contrary, we have :

$ 0 > \beta $ for some $ \beta $
$ \beta = 0 + \beta  > \beta + \beta =2\beta $
$ 2\beta = 0 + 2\beta > \beta + 2\beta = 3\beta $

and so on.

Now we have a sequence of $ 0, \beta, 2\beta, 3\beta, \cdots $ and this is an infinitely decreasing sequence with no minimum, contradicting the well ordering property required for monomial order.

(b)

Now we know 1 as a term is the minimum monomial for all order, in particular, we know

$ 1 \le x^{\beta - \alpha} $

Multiplying $ x^{\alpha} $ on both side we get the inequality we wanted

$ x^{\alpha} \le x^{\beta} $.

The converse is not true, in particular, we know in lex order

$ x < y $.

But obviously neither divide each other.

(c)

We do a similar infinite descent for this one, support the contrary, we have

$ \alpha + \beta < \alpha $

We reach the same conclusion as above, to be more concrete, we can write

$ \alpha + \beta +k\beta < \alpha + k\beta $.

So we have the sequence $ \alpha, \alpha + \beta, \alpha + 2\beta, \cdots $. This is an infinitely decreasing sequence with no minimum, so again it contradicts the well ordering property.

The Art of Computer Programming - Section 1.2.3, First Set, Exercise 16

Problem:

Solution:

The trick is to differentiate the geometric series on both side


$ \begin{eqnarray*} \sum\limits_{j = 0}^{n}x^j &=& \frac{x^{n+1} - 1}{x - 1} \\ \frac{d}{dx}(\sum\limits_{j = 0}^{n}x^j) &=& \frac{d}{dx}(\frac{x^{n+1} - 1}{x - 1}) \\ \sum\limits_{j = 0}^{n}\frac{d}{dx}(x^j) &=& \frac{d}{dx}(\frac{x^{n+1} - 1}{x - 1}) \\ \sum\limits_{j = 0}^{n}jx^{j - 1} &=& \frac{d}{dx}(\frac{x^{n+1} - 1}{x - 1}) \\ \sum\limits_{j = 0}^{n}jx^j &=& x\frac{d}{dx}(\frac{x^{n+1} - 1}{x - 1}) \\ &=& x\frac{(x-1)(x^{n+1} - 1)' - (x^{n+1} - 1)(x-1)'}{(x - 1)^2} \\ &=& x\frac{(x-1)(n+1)x^n - (x^{n+1} - 1)}{(x - 1)^2} \\ &=& x\frac{(n+1)x^{n+1} - (n+1)x^n - x^{n+1} + 1}{(x - 1)^2} \\ &=& x\frac{nx^{n+1} - (n+1)x^n + 1}{(x - 1)^2} \\ &=& \frac{nx^{n+2} - (n+1)x^{n+1} + x}{(x - 1)^2} \\ \end{eqnarray*} $

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?