Posted on May 2, 2010June 13, 2010 in Mathematics

Random Math Problems (1)

Probably any of these problems would be too small to include in a blog post on their own, so it might be more efficient (?) to put several of them together into one post.

The problems are not mine, and the solutions are not mine. They are just interesting problems I’ve come across when studying for math olympiads.

I hope to publish more collections of these random math problems in the future. That’s why I’m appending (1) to this post.

Problem 1

(From the 2010 Fermat contest)

Spheres can be stacked together into a tetrahedron (triangular pyramid). Here’s a visual (not created by me, from Wikipedia):

Each of the spheres in the tetrahedron has a number written on it. The top sphere is 1, and the number of any sphere is the sum of the numbers on the spheres in the layer above.

An internal sphere is defined as a sphere that is not on the outside, or in other words, touching exactly three spheres in the layer above.

In a tetrahedron with 13 layers, what is the sum of the numbers on all of the internal spheres?

Solution

Let’s draw out a few layers of the tetrahedron.
Hosted by imgur.com

Look for patterns.

There’s a few things that can be noticed-

The numbers at the three corners of a layer are 1
Any layer is highly symmetrical: in the last diagram the sequence (1 4 6 4 1) appears in the bottom row, as well as the left and right diagonals. We can rotate the tetrahedron and the numbers would still be the same.
The numbers on the outside form Pascal’s triangle. The sequence (1 3 3 1) is the 4th row of Pascal’s triangle; (1 4 6 4 1) is the 5th, and so on.

The most important thing to look for is the fact that Pascal’s triangle appears in the tetrahedron.

Each row of Pascal’s triangle is one longer than the previous row. To calculate a row, overlap the previous row with the new row, like this:
Hosted by imgur.com

Here the number in a purple box is the number to the top-right of it plus the number to the top-left of it:
Hosted by imgur.com

Simple.

Notice that each number in the top gets added into exactly two boxes at the bottom.

Therefore the sum of the numbers in the bottom is twice the sum of the numbers in the top. $1 + 3 + 3 + 1 = 8$ , and $1 + 4 + 6 + 4 + 1 = 16$ .

This applies to any two rows. The sum of any row is twice the sum of the previous row.

Since the sum of the first row is 1, the sum of the second is 2, the sum of the third 4, and so on. We can even express this as a formula. The sum of the nth row is:

$2^{n-1}$

A similar idea applies to the layers of the tetrahedron.

In Pascal’s triangle, each number gets added to two places in the next row.

The tetrahedron is like Pascal’s triangle, in three dimensions. Each sphere in the tetrahedron sits on top of three spheres in the layer under it. So each number gets added to three different numbers in the next row.

Thus the sum of the numbers in any layer of the tetrahedron is 3 times the sum of numbers in the previous layer.

A formula for the sum of the nth layer of the tetrahedron:

$3^{n-1}$

What we really want is a formula for the middle numbers, or internal spheres. The internal spheres are the spheres that are not on the outer layer.

We know the formula for the sum of the whole layer, and we know the formula for any of the three ‘sides’ of a layer.

Hosted by imgur.com

The internal numbers would be the sum of the entire layer minus three times the sum of a side. To cover up for the three 1’s we’ve counted more than once, we add 3 to the result.

The formula for the sum of the internal numbers on the nth layer:

$3^{n-1} - 3 \cdot 2^{n-1} + 3$

The problem asks for the sum of the first to the thirteenth layer. Well, the first three layers don’t have any internal spheres so we start from the forth:

$\begin{array}{l} \displaystyle\sum_{n=4}^{13} 3^{n-1} - 2^{n-1} + 3 \\ = (3^3 + 3^4 + \cdots + 3^{12}) \\ \quad - 3(2^3 + 2^4 + \cdots + 2^{12}) + 3 \cdot 10 \end{array}$

We can use the sum of geometric series formula, or more easily calculate it by brute force. The answer would be 772626.

Problem 2

(From the 2008 Canadian Math Olympiad)
Hosted by imgur.com

In quadrilateral $ABCD$ , $CM$ splits the quadrilateral into two parts of equal area. $AN$ also splits the quadrilateral into two parts of equal area. $AB$ is the longest side of the quadrilateral.

Prove that $MN$ bisects $DB$ .

Solution

I’m going to use the equal sign to mean two figures with equal areas, not two figures that are congruent.

The triangles $\triangle ANB$ and $\triangle MCB$ are both half of $ABCD$ , so their areas are equal. Then $\triangle ANB = \triangle MCB$ .

$\triangle ANB$ can be split into $\triangle ANM + \triangle MNB$ , and similarly $\triangle MCB$ can be split into $\triangle MCN + \triangle MNB$ .

We know that $\triangle ANB = \triangle MCB$ . By subtraction, $\triangle AMN = \triangle MCN$ .

The triangles $\triangle AMN$ and $\triangle MCN$ share a common base, $MN$ . Because their areas are equal, the perpendicular from $A$ to $MN$ is equal to the perpendicular from $C$ to $MN$ . Therefore $AC || MN$ .

Now we draw a line through $D$ , parallel to $AC$ and $MN$ . We extend $AB$ and $BC$ to meet this line (and we draw a couple of additional lines):
Hosted by imgur.com

Because $XY || AC$ , $\triangle ADC = \triangle AXC = \triangle AYC$ .

Here $\triangle MCB = ADCM$ .

We can write $ADCM$ as $\triangle ADC + \triangle ACM$ . Since $\triangle ADC = \triangle AXC$ , $ADCN = \triangle XCM$ .

It follows that $\triangle MCB = \triangle XCM$ , and $XM = MB$ .

Similarly, $ADCN = \triangle AYN$ . Then $\triangle ANB = ADCN = \triangle AYN$ , and $YN = NB$ .

Because $XM = MB$ and $YN = NB$ , the result follows that $DK = KB$ .

Problem 3

(From the 2010 USAMO)

This problem actually appears in both the junior and senior USAMO taken about a week ago from time of writing. It’s problem 4 in the senior and problem 6 in the junior.

Hosted by imgur.com

$\triangle ABC$ is a right triangle. $BD$ bisects $\angle ABC$ , and $EC$ bisects $\angle ACB$ .

Prove that the lines $[AB, AC, BI, ID, CI, IE]$ cannot all have integer lengths.

Solution

I was really surprised at how short and simple the solution can be for this problem.

Because $\angle BAC = 90$ , $\angle ABC + \angle ACB = 90$ and $\angle IBC + \angle ICB = 45$ because of the angle bisectors.

Then $\angle BIC = 180-45 = 135$ .

First we apply the pythagorean theorem:

$BC^2 = AB^2 + AC^2$

We then apply the Law of Cosines:

$BC^2 = IB^2 + IC^2 - 2 \cdot IB \cdot IC \cdot \cos 135$

Combining the two, and substituting $-\frac{1}{\sqrt{2}}$ for $\cos 135$ :

$\begin{array}{c} AB^2 + AC^2 = IB^2 + IC^2 + 2 \cdot IB \cdot IC \cdot \frac{1}{\sqrt{2}} \\ \frac{2 \cdot IB \cdot IC}{AB^2 + AC^2 - IB^2 - IC^2} = \sqrt{2} \end{array}$

This is absurd, if AB, AC, IB, and IC are all integers and nonzero.

Posted on April 3, 2010July 12, 2010 in Mathematics, Programming

Project Euler 285

Problem 285 of Project Euler was released yesterday; it requires some geometry and probability sense.

The problem goes like this:

Albert chooses two real numbers a and b randomly between 0 and 1, and a positive integer k.

He plays a game with the following formula:

$k' = \sqrt{(ka+1)^2 + (kb+1)^2}$

The result k’ is rounded to the nearest integer. If k’ rounded is equal to k, then Albert gets k points. Otherwise, he gets nothing.

Find the expected value of the total score if Albert plays this game with $k = 1, 2, \cdots , 10^5$ .

For example (from the problem statement), let k=6, a=0.2, and b=0.85.

Here the expression $\sqrt{(ka+1)^2 + (kb+1)^2}$ gives the number 6.484. When rounded to the nearest integer, it becomes 6, which is equal to k. Therefore, Albert gets 6 points.

Yup – another expected value problem. But the concept of this problem is simple:

Hosted by imgur.com

For any value of k, there are certain values of a and b where Albert will get points. Otherwise, he does not get points. Here the gray blob is the area where he does get points, and the white area is where he does not.

The red square is the sample space of the random variables a and b, since $0<a<1$ and $0<b<1$ .

The probability of Albert getting the points is the fraction of the square that’s gray.

The area of the red square is always 1. The area of the gray area varies with k. Thus the idea is to calculate the area of the gray area for each value of k from 1 to $10^5$ .

Now we can get to the details of the problem.

Notice that if $round(k') = k$ , then $k-0.5 < k' < k+0.5$ (the difference between less-equal and less is irrelevant in this problem):

Hosted by imgur.com

In a similar way, the equation of the larger circle is $(a+\frac{1}{k})^2 + (b+\frac{1}{k})^2 < (\frac{k+0.5}{k})^2$ .

These are equations of circles. A circle has the equation $(x-a)^2 + (y-b)^2 = r^2$ where $(a,b)$ is the center and r is the radius.

Thus both the smaller and the larger circles have a center at $(-\frac{1}{k},-\frac{1}{k})$ . The radii of the circles are different: the radius of the smaller circle is $\frac{k-0.5}{k}$ and the radius of the larger circle $\frac{k+0.5}{k}$ .

Plotting the inequalities:

Hosted by imgur.com

We can see now that this is a calculus problem! Indeed, the shaded area is the area of the larger circle inside the box – area of the smaller circle inside the box.

Initially I tried integrating the circles directly, but I ran into problems while integrating and I was unable to correctly integrate the equation. Instead, I integrated an equivalent problem:

Hosted by imgur.com

It’s obvious that the areas do not change with this transformation.

So now for the smaller circle the equation is $a^2 + (b+\frac{1}{k})^2 > (\frac{k-0.5}{k})^2$ . Solving for b, we get:

$b > \sqrt{(\frac{k-0.5}{k})^2-a^2} - \frac{1}{k}$

.. And this equation for the larger circle:

$b < \sqrt{(\frac{k+0.5}{k})^2-a^2} - \frac{1}{k}$

The variable of integration here is a, and k is only a constant. Therefore we can replace the radius with r and get this equation to integrate:

$b = \sqrt{r^2-a^2} - \frac{1}{k}$

With the help of an integration table, this can be integrated fairly easily.

Hosted by imgur.com

There’s one additional problem – computing the integrating ‘limits’ of the two circles. Let’s call them $L_S$ and $L_L$ for small and large respectively.

Both of them can be computed using the pythagorean theorem.

Hosted by imgur.com

The formula for $L_S$ (it should be obvious by now what $L_L$ should be):

$L_S = \sqrt{(\frac{k-0.5}{k})^2-\frac{1}{k^2}}$

Now we can get this really big formula for computing the area for any integer k:

$\begin{array}{l} \int_{\frac{1}{k}}^{\sqrt{(\frac{k+0.5}{k})^2-\frac{1}{k^2}}} (\sqrt{(\frac{k+0.5}{k})^2-a^2}-\frac{1}{k}) da \\ - \int_{\frac{1}{k}}^{\sqrt{(\frac{k-0.5}{k})^2-\frac{1}{k^2}}} (\sqrt{(\frac{k-0.5}{k})^2-a^2}-\frac{1}{k}) da \end{array}$

Also, fortunately for me, it is impossible for the upper bound to cross the circle at the top or right, I mean, we never have something like this –

Hosted by imgur.com

Anyways, here’s a Haskell implementation of the algorithm:

integral a r k = 0.5 * (a * sqrt (r^2 - a^2) + r^2 * atan (a/sqrt (r^2-a^2))) - a/k

area k = let area_1 1 = 0
             area_1 k = integral (sqrt (((k-0.5)/k)^2 - (1/k)^2)) ((k-0.5)/k) k - integral (1/k) ((k-0.5)/k) k
             area_2 k = integral (sqrt (((k+0.5)/k)^2 - (1/k)^2)) ((k+0.5)/k) k - integral (1/k) ((k+0.5)/k) k
         in  area_2 k - area_1 k

main = print . sum . zipWith (*) [1..] $ map area [1..10^5]

The code runs in about 3 seconds.

There seems to be an edge case where k=1 (probably an asymptote) so I have to specially make it be zero.

This problem was released 10 pm last night and I was tired, lol, but I still managed to solve it and get into the top 20.

Hosted by imgur.com

Posted on April 2, 2010July 12, 2010 in Mathematics

The two-circles method of proving the Pythagorean Theorem

The Pythagorean theorem, stating that the square of the hypotenuse is equal to the sum of the squares of the sides in a right triangle, is a fundamental concept in geometry and trigonometry.

There are many, many ways to prove the Pythagorean theorem. This page contains 84 different proofs, and The Pythagorean Proposition by Loomis contains another 367 proofs.

This is what I think to be an interesting proof, by the use of two circles. It is number 89 in Loomis’s book.

Starting with a right triangle, we draw two circles:

Hosted by imgur.com

Here, $\angle ACB$ is right, and A and B are the centers of circles $\Omega_1$ and $\Omega_2$ respectively.

Now we draw some additional lines, extending AB to F and G:

Hosted by imgur.com

In this diagram, we can prove that $\triangle ADC \sim \triangle ACG$ :

$\angle DCG$ is right. This is an application of Thales’ theorem since DG is a diameter.
$\angle ACB$ is right. This is given.
$\angle ACD = \angle BCG$ . Since $\angle DCG = \angle ACB$ , $\angle DCG - \angle DCB = \angle ACB - \angle DCB$ .
$\angle BCG = \angle BGC$ . This is because BC and BG are both radii of $\Omega_2$ and $\triangle BCG$ is isosceles.
$\angle ACD = \angle BGC = \angle AGC$ .
$\therefore \triangle ADC \sim \triangle ACG$ . The two triangles have two shared angles: $\angle CAG$ and $\angle ACD = \angle AGC$ .

In a similar way, we can prove that $\triangle BEC \sim \triangle BCF$ .

The rest of the proof is algebraic rather than geometric. Let’s call the side AC to be b, BC=a, and AB=c.

From the similar triangles, we have the following ratios:

$\frac{AG}{AC} = \frac{AC}{AD}$ (or, $b^2 = AG \cdot AD$ )

$\frac{BF}{BC} = \frac{BC}{EB}$ (or, $a^2 = BF \cdot EB$ )

Adding the two equations, we get:

$a^2 + b^2 = BF \cdot EB + AG \cdot AD$

The line BF can be split into AF and AB which is equal to c+b since AF = AC.

The line EB can be considered the difference between AB and AE, which is equal to c-b.

Similarly, AG = AB+BG = c+a, and AD = AB-DB = c-a. By substitution:

$\begin{array}{rcl} a^2 + b^2 &=& (c+b) (c-b) + (c+a) (c-a) \\ &=& c^2 - b^2 + c^2 - a^2 \\ &=& 2c^2 - a^2 - b^2 \\ 2a^2 + 2b^2 &=& 2c^2 \\ a^2 + b^2 &=& c^2 \end{array}$

Q.E.D.

Posted on February 22, 2010July 12, 2010 in Mathematics

A Geometry Exercise

This post was inspired by a problem I came across when studying for a math contest, namely problem 23 in the 2007 Cayley Contest.

I think this is an interesting problem because the solution is not so obvious, and there are several incorrect approaches that I’ve tried (and given up on). I’ve modified the problem slightly to make it more interesting.

Here we have a rectangle, $ABCD$ . It’s rotated to the right by $\theta$ degrees, using $A$ as the pivot. This forms $AEFG$ as the new rectangle. We are given $x$ and $y$ , we are asked to find the area of the shaded region.

Can you come up with a general formula for the area of the shaded region, using the given variables $x$ , $y$ , and $\theta$ ?

Solution

I will use the notation $(ABC)$ to denote the area of triangle $\triangle ABC$ .

The solution is to draw a line parallel to $BC$ through $E$ , the blue line. This splits the lower shaded area into two triangles: $\triangle AXE$ and $\triangle EYH$ , and a rectangle: $BCYX$ .

Since $ABCD$ is the same as $AEFG$ , the top shaded area is the same as the bottom shaded area.

Let’s find the area of triangle $\triangle AXE$ .

The angle $\angle BAE$ is equal to $\theta$ . Of course, $AE$ is equal to $y$ . Using some basic trigonometry, $AX = y \cos \theta$ , $XE = y \sin \theta$ , and $BX = y - y \cos \theta$ . Now we know the area of triangle $\triangle AXE$ :

$\begin{array}{rcl} (AXE) &=& \frac{1}{2} (y \cos \theta) (y \sin \theta) \\ &=& \frac{1}{4} y^2 \sin(2 \theta)\end{array}$

Next we find the area of $\triangle EYH$ . $EY = x - y \sin \theta$ , and using trigonometry again, $HY = \tan \theta (x - y \sin \theta)$ .

$\begin{array}{rcl} (EYH) &=& \frac{1}{2} (x - y \sin \theta) [\tan \theta (x - y \sin \theta)] \\ &=& \frac{1}{2} (x - y\sin \theta)^2 \tan \theta \end{array}$

Finally, for the rectangle $BCYX$ :

$\begin{array}{rcl} (BCYX) &=& x (y - y \cos \theta) \end{array}$

Now we add all this up and simplify ( $T$ is total):

$\begin{array}{rcl} T &=& 2[(AXE) + (EYH) + (BCYX)] \\ &=& 2[\frac{1}{4} y^2 \sin(2 \theta) + \frac{1}{2}(x - y \sin \theta)^2 \tan \theta + x (y - y \cos \theta)] \\ &=& \tan \theta (x^2+y^2) - 2xy (\sec \theta - 1)\end{array}$

It’s rather tedious to get from the second to the last step, but Wolfram Alpha could do it for me.

Notice that we assume that $EF$ intersects $DC$ . If $\theta$ is large enough, then $EF$ would intersect $AD$ , and this formula would no longer work.

Of course it would also fail if $y$ is greater than $x$ , so my formula works for only a rather limited range of values.

Lucky's Notes

Notes on math, coding, and other stuff

Tag: geometry

Random Math Problems (1)

Problem 1

Solution

Problem 2

Solution

Solution

Project Euler 285

The two-circles method of proving the Pythagorean Theorem

A Geometry Exercise

Solution