Tuesday, March 23, 2010

Solution: Happy Saint Math Trick's Day

Original problem: http://dharmath.blogspot.com/2010/03/happy-saint-math-tricks-day.html

This problem is inspired by this comic.

Prove that the trick in the comic always works. In other words, if $p$ is a prime number greater than 3, prove that $p^2 + 14 \equiv 3 \mod 12$

Solution

$p^2 + 14 \equiv 3 \mod 12$ means that $p^2+11$ is divisible by 12, which means that $p^2+11-12 = p^2-1$ is divisible by 12.

If $p$ is a prime number greater than 3, then $p$ is odd. This means that $p$ divided by 4 has remainder either 1 or 3. In both cases, $p^2$ divided by 4 has remainder 1, which means $p^2-1$ is divisible by 4.

If $p$ is a prime number greater than 3, then $p$ divided by 3 has remainder either 1 or 2. In both cases, $p^2$ divided by 3 has remainder 1, which again means $p^2-1$ is divisible by 3.

Since $p^2-1$ is divisible by both 3 and 4, it is divisible by 12.

Happy Saint Math Trick's Day

This problem is inspired by this comic.

Prove that the trick in the comic always works. In other words, if $p$ is a prime number greater than 3, prove that $p^2 + 14 \equiv 3 \mod 12$

Solution: http://dharmath.blogspot.com/2010/03/solution-happy-saint-math-tricks-day.html

Friday, March 19, 2010

Second Solution: Osculating Circle, Ellipse, and Cone

Original Problem: http://dharmath.blogspot.com/2010/03/osculating-circle-ellipse-and-cone.html

An osculating circle of a point on a curve is defined as a circle that:
1. passes through that point
2. whose slope at that point is the same of the slope of the curve at that point
3. whose radius is the same as the radius of curvature of the curve at that point

In other words, it is a second-degree approximation circle of the curve at that point.

http://en.wikipedia.org/wiki/Osculating_circle

Given a cone whose half-angle is $\theta$, we take a cross section with a plane whose incident angle is $\theta$. That is, the plane is perpendicular to one of the cone rays. Naturally, the cross section forms an ellipse.

If O is the intersection of the main axis of the cone and the cross section, and A is the point on the ellipse's major axis that's closest to O, then prove that a circle with center O and radius OA is an osculating circle to the ellipse at A.

Hint: for people without any knowledge of calculus, the radius of osculating circle at A is $b^2/a$ where $b$ is half the length of minor axis and $a$ is half the length of major axis (standard ellipse notation).
The rest of the problem can be done without using calculus.

Second Solution

As given in the hint, the radius of the osculating circle is $b^2/a$. And clearly the circle in the problem passes through A and its tangent at A is perpendicular to the major axis, hence coincides with the ellipse's tangent. We are left to prove that $OA = b^2/a$. However, astute readers will note that $b^2/a$ is exactly the length of semi latus-rectum of the ellipse. So suppose $D$ is the focus that's closest to $A$, and $GG_1$ is the latus rectum passing through $D$, we will show that $DG = OA$.

Let $B$ be the point on the major axis that's farthest to $O$, and let $S$ be the vertex of the ellipse. Let $x = 2 \theta$ be the angle of the cone. We also note that $AO \perp AS$.

Let $\tau$ be the plane that passes through $GG_1$ (and hence through D) and perpendicular to the cone axis. Let $E$ be the point of intersection of the axis and this plane. The cross section of the cone with $\tau$ is a circle with center $E$. Let $F$ be the point on the circle such that $EF$ passes through $D$.

Since $SO$ is an angle bisector, we have $AO:OB = SA:SB = \cos x$, thus
$$AO = \frac{\cos x }{ \cos x+1} AB = \frac{\sin x \cos x }{ \cos x+1} SB$$

Now, $D$ is the point at which the smaller Dandelin Sphere touches the ellipse. If we consider the triangle $SAB$, then $D$ is where the incenter of that triangle touches $AB$. Since $SAB$ is a right angle at $A$, then $DA$ is the radius of that incenter.
$$DA = \frac{AS.AB}{AS+AB+SB} = \frac{\sin x \cos x}{1 + \sin x + \cos x} SB$$

Thus $AO : DA = (1+ \sin x + \cos x) : (1 + \cos x) = 1 + (\sin x) / (1 + \cos x)$
Which means $DO:AD:AO = \sin x : (1 + \cos x) : (1 + \sin x + \cos x)$

Now, looking back at the triangle $SAB$ and the plane that contains it,
$$DF = \frac{AD}{\cos \theta} = \frac{1 + \cos x}{(1 + \sin x + \cos x) \cos \theta} OA$$
and
$$DE = DO \cos \theta = \frac{\sin x \cos \theta}{1 + \sin x + \cos x} OA$$
So
$$DG^2 = EG^2 - DE^2 = EF^2 - DE^2 = (DE + DF)^2 - DE^2 = DF(DF + 2DE)$$
$$= \frac{OA^2}{(1 + \sin x + \cos x)^2} \frac{1 + \cos x}{\cos \theta} \left(\frac{1 + \cos x}{\cos \theta} + 2\sin x \cos \theta \right)$$
Since $x = 2\theta$, then $1 + \cos x = 2 \cos^2 \theta$
$$(1 + \sin x + \cos x)^2 = (2 \cos^2 \theta + 2 \sin \theta \cos \theta)^2 = 4 \cos^2 \theta (\sin \theta + \cos \theta)^2$$
and
$$\frac{1 + \cos x}{\cos \theta} + 2\sin x \cos \theta = 2 \cos \theta + 2 \sin x \cos \theta = 2 \cos \theta (1 + \sin x)$$
So
$$DG^2 = \frac{OA^2}{4 \cos^2 \theta (\sin \theta + \cos \theta)^2} \frac{2 \cos^2 \theta}{\cos \theta} 2 \cos \theta (1 + \sin x)$$
$$= OA^2 \frac{1 + \sin x}{(\sin \theta + \cos \theta)^2}$$

But
$$1 + \sin x = 1 + 2 \sin \theta \cos \theta = \cos^2 \theta + \sin^2 \theta + 2 \sin \theta \cos \theta = (\sin \theta + \cos \theta)^2$$

So $DG^2 = OA^2$ which means $DG = OA$

Which jug is poisoned?

You have 1000 jugs of wine, one of which has been poisoned. You have access to rats that would die within 23 hours of drinking that poison. You need to determine which jug is poisoned within 24 hours. How many rats do you need at minimum?

Thursday, March 18, 2010

Which stack has counterfeit coins?

Credit to this problem goes to MIT Technology Review Puzzle Corner, November/December 2009 Edition.

Given thirteen stacks each containing four coins, we are told that exactly one stack contains all counterfeit coins. A counterfeit coin weighs less than a good coin by an amount not exceeding 5 grams, and all good coins weigh an integral number of grams.

We are given a precision scale with a very wide area to put the coins on. We need to answer all these three questions all in two weighings:
1. What is the weight of a good coin?
2. What is the weight of a counterfeit coin?
3. Which stack has the counterfeit coins?

Solution: Osculating Circle, Ellipse, and Cone

Original Problem: http://dharmath.blogspot.com/2010/03/osculating-circle-ellipse-and-cone.html

An osculating circle of a point on a curve is defined as a circle that:
1. passes through that point
2. whose slope at that point is the same of the slope of the curve at that point
3. whose radius is the same as the radius of curvature of the curve at that point

In other words, it is a second-degree approximation circle of the curve at that point.

http://en.wikipedia.org/wiki/Osculating_circle

Given a cone whose half-angle is $\theta$, we take a cross section with a plane whose incident angle is $\theta$. That is, the plane is perpendicular to one of the cone rays. Naturally, the cross section forms an ellipse.

If O is the intersection of the main axis of the cone and the cross section, and A is the point on the ellipse's major axis that's closest to O, then prove that a circle with center O and radius OA is an osculating circle to the ellipse at A.

Hint: for people without any knowledge of calculus, the radius of osculating circle at A is $b^2/a$ where $b$ is half the length of minor axis and $a$ is half the length of major axis (standard ellipse notation).
The rest of the problem can be done without using calculus.

Solution

As given in the hint, the radius of the osculating circle is $b^2/a$. And clearly the circle in the problem passes through A and its tangent at A is perpendicular to the major axis, hence coincides with the ellipse's tangent. We are left to prove that $OA = b^2/a$.

Let B be the point on the major axis that's farthest to O, and let C be the vertex of the ellipse. Let $x = 2 \theta$ be the angle of the cone. We also note that $AO \perp AC$.

Now the length of major axis $2a = AB = BC \sin x \iff \frac{a}{BC} = \frac{\sin x}{2}$.

Since CO is an angle bisector, then $OA/OB = CA/CB = \cos x$
$$\frac{OA}{AB-OA} = \cos x \iff OA = \frac{AB \cos x}{1 + \cos x} = \frac{2a \cos x}{1 + \cos x}$$

Now, let D be the point where the smaller Dandelin Sphere touches the cutting plane.
http://en.wikipedia.org/wiki/Dandelin_spheres

D is the focus that's closest to A. Therefore $DA = a-c$ where $c = \sqrt{a^2-b^2}$ (using the standard ellipse notation). But the center of the Dandelin sphere is also the incenter of the triangle ABC, so DA is the same as inradius of ABC. Using the inradius formula, and since $\angle BAC = \pi/2$

$$DA = \frac{AC.AB}{AC+AB+BC} = \frac{BC \cos x . BC \sin x}{BC \cos x + BC \sin x + BC} = BC \frac{\cos x \sin x}{1+\sin x + \cos x}$$

So
$$a-c = BC \frac{\cos x \sin x}{1+\sin x + \cos x}$$
$$c/BC = a/BC - \frac{\cos x \sin x}{1+\sin x + \cos x} = \frac{\sin x}{2} - \frac{\cos x \sin x}{1+\sin x + \cos x} = \frac{\sin x}{2} . \frac{1 + \sin x - \cos x}{1 + \sin x + \cos x}$$
Thus $$\frac{c}{a} = \frac{1 + \sin x - \cos x}{1 + \sin x + \cos x}$$

Because $a^2 = b^2+c^2$,
$$\left( \frac{b}{a} \right)^2 = 1 - \left( \frac{c}{a} \right)^2 = 1 - \frac{(1 + \sin x - \cos x)^2}{(1 + \sin x + \cos x)^2} = \frac{4(1+\sin x)(\cos x)}{(1 + \sin x + \cos x)^2}$$
But
$$(1 + \sin x + \cos x)^2 = (1 + \sin^2 x + \cos^2 x + 2 \sin x + 2 \cos x + 2 \sin x \cos x)$$
$$= 2(1+\sin x)(1+\cos x)$$
So
$$\frac{b^2}{a^2} = \frac{2 \cos x}{1 + \cos x} = \frac{OA}{a}$$

Which means $OA = b^2/a$

Alternative solution available here: Second Solution

Friday, March 12, 2010

Osculating Circle, Ellipse, and Cone

An osculating circle of a point on a curve is defined as a circle that:
1. passes through that point
2. whose slope at that point is the same of the slope of the curve at that point
3. whose radius is the same as the radius of curvature of the curve at that point

In other words, it is a second-degree approximation circle of the curve at that point.

http://en.wikipedia.org/wiki/Osculating_circle

Given a cone whose half-angle is $\theta$, we take a cross section with a plane whose incident angle is $\theta$. That is, the plane is perpendicular to one of the cone rays. Naturally, the cross section forms an ellipse.

If O is the intersection of the main axis of the cone and the cross section, and A is the point on the ellipse's major axis that's closest to O, then prove that a circle with center O and radius OA is an osculating circle to the ellipse at A.

Hint: for people without any knowledge of calculus, the radius of osculating circle at A is $b^2/a$ where $b$ is half the length of minor axis and $a$ is half the length of major axis (standard ellipse notation).
The rest of the problem can be done without using calculus.

Solution:
http://dharmath.blogspot.com/2010/03/osculating-circle-ellipse-and-cone.html

Second Solution:
http://dharmath.blogspot.com/2010/03/second-solution-osculating-circle.html

Solution: Tennis Tournament

Original problem: http://dharmath.blogspot.com/2010/03/tennis-tournament.html

In a tennis tournament of 100 people, each player plays every other players exactly once. There is no draw in a tennis game, one side always wins.

Given that no player loses all of his games, prove that there is a cycle of exactly 3 players. That is, there are players A,B, and C such that A defeats B, B defeats C, and C defeats A.

First Solution

First we prove that there exists a cycle of any length in the tournament. Indeed, take player A, "mark" him, and take any player that A defeats, say B, and also mark that player.. And take any player that B defeats, say C, mark him, and so on. At each turn, we are guaranteed to find a player that loses to that player. If we ever find a player that we have marked before, we obtain a cycle. But the number of marked players increases steadily while there is only a finite number of players in the tournament. Sooner or later, we will run out of players and we are guaranteed to return to a previously marked player.

If this cycle that we found has length 3, then we are done. Now we establish the following statement via induction:

A cycle of length at least 3 contains a cycle of length 3.

The base case is trivial. Now suppose we have a cycle of length $k: A_1, A_2, \cdots, A_k$ where $A_i$ beats $A_{i+1}$ and $A_k$ beats $A_1$.

If $A_1$ beats $A_{k-1}$ then we have a cycle of length 3: $A_1$ beats $A_{k-1}$ beats $A_k$ beats $A_1$.

If $A_{k-1}$ beats $A_1$ then we have a cycle of length $k-1: A_1, \cdots, A_{k-1}$ which also contains a cycle of length 3 by induction hypothesis.

Tuesday, March 9, 2010

Tennis tournament

In a tennis tournament of 100 people, each player plays every other players exactly once. There is no draw in a tennis game, one side always wins.

Given that no player loses all of his games, prove that there is a cycle of exactly 3 players. That is, there are players A,B, and C such that A defeats B, B defeats C, and C defeats A.

Migrated here from wordpress

Due to some mix-ups with the hosting and domain company, and since I'm not really willing to pay for it anymore, I have decided to move my math problem repository here to blogspot. This past mix-up also explains my brief hiatus for about a month and a half. Thus, when reading any post older than March 10, 2010, please keep in mind that those posts were written for wordpress and were migrated automatically, thus you might lose some layout and formatting. I'll do my best to clean them up but I might miss some.

From now on, problems and solutions will still be two separate posts. This is mainly because blogspot does not allow partial hiding or spoiler tags. Thus to prevent solutions from spoiling the problem posts, I will continue to post them separately.