Pages

Bookmark and Share

Tuesday, December 7, 2010

a,b,c,d odd powers

If $a,b,c,d$ are integers such that $a+b+c+d = 0$ then show that for any odd number $n$,

$$X_n = a^n + b^n + c^n + d^n$$

is divisible by $Y = \sqrt{-(a+b)(a+c)(a+d)(b+c)(b+d)(c+d)}$

And that if $n$ is prime, then $X_n$ is divisible by $n$ as well

First Solution

First, it is straightforward to show that $Y$ is indeed an integer.
$a+b = -(c+d)$
$a+c = -(b+d)$
$a+d = -(b+c)$
Multiplying all three, we have that $Y = |(a+b)(b+c)(c+a)|$
If $Y=0$, then $X_n = 0$ as well. So now we're going to assume that $Y > 0$. For proving divisibility purposes, we can also assume that $Y = (a+b)(b+c)(c+a)$.

Let $f(t) = (t-a)(t-b)(t-c) = t^3 - Pt^2 + Qt - R$ be a polynomial with roots $a,b,c$

We have that $Y=(a+b)(b+c)(c+a) = (P-a)(P-b)(P-c) = f(P) = PQ-R$.

Let's also define $S_n = a^n + b^n + c^n$. All we have to show is that $S_n - P^n$ is divisible by $Y$ for $n$ odd.

Now we assert the following, and prove by induction:
If $n$ is odd, then $S_n - P^n$ is divisible by $Y$
If $n=2m$ is even, then $S_n - P^n - 2(-Q)^m$ is divisible by $Y$.

We readily obtain that $S_1 = P$ and $S_2 = P^2 - 2Q$, so the assertions above are true for $n=1,2$.

Now for higher values of $n$, we have the following:
$a^{n-3}f(a) = a^n - Pa^{n-1} + Qa^{n-2} - Ra^{n-3} = 0$
similarly we can do the same for $b,c$ and add them, so that we have:
$S_n = PS_{n-1} - QS_{n-2} + RS_{n-3}$

If $n=2m$ is even, then $n-1$ is odd, $n-2 = 2(m-1)$ is even, and $n-3$ is odd. So from induction hypothesis, we can write:
$S_{n-1} = P^{n-1} + YZ_1$
$S_{n-2} = P^{n-2} + 2(-Q)^{m-1} + YZ_2$
$S_{n-3} = P^{n-3} + YZ_3$

where $Z_1, Z_2, Z_3$ are integers
So:
$$S_n = P^n + PYZ_1 - P^{n-2}Q + 2(-Q)^m -QYZ_2 + RP^{n-3} + RYZ_3$$
$$= P^n + 2(-Q)^m + P^{n-3}(PQ-R) + Y(PZ_1 - QZ_2 + RZ_3)$$
$$= P^n + 2(-Q)^m + Y(P^{n-3} + PZ_1 - QZ_2 + RZ_3)$$

which proves our induction assertion that $S_n - P^n - 2(-Q)^m$ is divisible by $Y$. For $n$ odd, we can do the same.

So $S_n - P^n = X_n$ is divisible by $Y$ for $n$ odd.

Second Solution

We have $d = -(a+b+c)$, then
$$X_n = a^n + b^n + c^n - (a+b+c)^n$$ if $n$ is odd.

For fixed values of $b,c$, let $f(a) = a^n + b^n + c^n - (a+b+c)^n$ by a polynomial of degree $n-1$ in $a$.
Note that $f(-b) = 0$ and $f(-c) = 0$. That means $X_n = f(a)$ is divisible by $(a+b)(a+c)$.

Write $f(a) = (a+b)(a+c)P(a)$ for $P$ some integer polynomial.
Now note that $f(a) = a^n - (a+b+c)^n + (b^n + c^n)$
$a^n - (a+b+c)^n$ is divisible by $(b+c)$ in a polynomic manner (not just integer divisibility), and so is $b^n + c^n$ (since $n$ is odd).

So $f(a)$ is divisible by $(b+c)$ in a polynomic manner, which means $P(a)$ is divisible by $(b+c)$.

Thursday, November 18, 2010

Triangular (and tetrahedral) lattice

An equilateral triangle $ABC$ with side $n$ a positive integer is divided into triangular lattice consisting of unit triangles.

Each point on the lattice is colored red, white, or blue such that:
1. No point on $AB$ is colored red
2. No point on $BC$ is colored blue
3. No point on $AC$ is colored white

Prove that there exists a unit triangle whose vertices are colored with 3 different colors.

Challenge problem: Same problem but for tetrahedron and four colors.

Solution

We first state the one-dimensional version of this problem:

Given a sequence of points on a line colored red or blue, and the first point must be colored red, and the last point must be colored blue, then we have an ODD number of segments that has two differently-colored end points.

This one-dimensional version is trivial to prove.

Now we turn to the 2-dimensional version as stated in the problem.
For each side that has both red and blue endpoints, we "mark" that side.
Then for each unit triangle, we give it a score based on how many marked sides it has. Now, if we consider the "outside" area as another "surrogate unit triangle", then we can also give it a score based on how many marked sides are facing the outside.

First, note that the total score of all areas must be even, since any marked side contribute one score to two areas.

Now, applying the 1-dimensional version of the problem, we know that side AC has an odd number of marked sides. Side AB and BC does not have any marked sides. So the outside area has an odd score. Thus, there is an odd number of unit triangles that has an odd score. In order for a unit triangle to have an odd score, it must have three differently-colored vertices.

Monday, October 25, 2010

Number of black cells

Each cell on an $n \times n$ checkerboard is to be painted black or white.

How many ways are there to paint the board such that each column and each row contains an even number of black cells?

How many ways are there to paint it such that each column and row contains an odd number of black cells?

Saturday, September 25, 2010

Completable Paintings

An $n \times n$ checker board is painted all white except $m$ cells that are painted black. At each step, one is allowed to choose a rectangle that has three black corners, and paint the fourth corner black. A configuration is called completable if one can paint the entire board black using a sequence of steps described above.

First Question:
Find the smallest $m$ such that any configuration with $m$ black cells are always completable.

Second Question:
Find the smallest $m$ such that there is a completable configuration with $m$ black cells.

Thursday, September 16, 2010

Ternary Polynomial

A polynomial with integer coefficients is called "ternary" if its coefficients are all 1, -1, or zero.

First Question:
Find two polynomials $P(x)$ and $Q(x)$ with integer coefficients where at least one coefficient is larger than 2010, such that $P(x)Q(x)$ is ternary.

Second Question:
Does there exist a ternary multiple of $F(x) = x^2 - 3x + 1$ ?

Solution

First Question

Note that the polynomial $(x-1)(x^2-1)(x^4-1)(x^8-1) ... (x^{2^n}-1)$ is ternary. Indeed, because the coefficient of $x^k$ can only be formed in exactly one way. For digits in the binary representation of $k$ that is one, we take the $x^{2^i}$ term, and for the other digits, we take the $-1$ term.

Now, that polynomial can be factored. For example:
$$(x-1)(x^2-1)(x^4-1)(x^8-1)$$
$$=(x-1)^{4} (x+1) (x^3+x^2+x+1) (x^7+...+1)$$
$$=(x-1)^{4) (x+1) (x+1)(x^2+1) (x+1)(x^2+1)(x^4+1)$$
$$=(x-1)^4 (x+1)^3 (x^2+1)^2 (x^4+1)$$

So similarly,
$$(x-1)(x^2-1)(x^4-1)(x^8-1) ... (x^{2^n}-1)$$
$$ = (x-1)^{n+1} (x+1)^n (x^2+1)^{n-1} ... (x^{2^{n-1}}+1) $$

If we let $P(x) = (x-1)^{n+1}$ and $Q(x)$ to be the rest, we claim that we can make the largest coefficient in $P$ and $Q$ to be arbitrarily large by setting $n$ large enough. For $P$, it is clear due to binomial expansion. For $Q$, the factor $(x+1)^n$ will have a large enough coefficient, while the rest of the factors all consist of positive signs (no negative signs).

So by setting $n$ large enough, we could find $P$ and $Q$ that satisfy the desired conditions.

Second Question

We start by proving a lemma: if $s > 2$ then $s^n > s^{n-1} + ...+ s + 1$. This lemma can be proved by induction:
$s^{n+1} > 2s^n = s^n + s^n > s^n + ... + s + 1$

Now, we note that the larger root of $F$ is greater than 2, so let $r$ be this larger root. ( $r = (3 + \sqrt{13})/2 > 2$ ).

Suppose $P$ is a ternary polynomial such that $P(x) = F(x) G(x)$ for some integer polynomial $G$, then $P(r) = 0$.

But that is impossible if $r > 2$, due to the lemma above, since the largest term in $P$ cannot be offset by the rest of the terms. A contradiction.

Wednesday, September 1, 2010

Integral Inequality

Prove that:

$$\left( \int_\pi^\infty\frac{\cos x}{x}\ dx\right)^{2} < \frac{1}{{\pi}^{2}} $$

Solution

Integrate by parts:

$$\int \frac{\cos x}{x} dx = \frac{\sin x}{x} + \int \frac{\sin x}{x^2} dx$$

So
$$\int_\pi^\infty\frac{\cos x}{x}\ dx = \int_\pi^\infty \frac{\sin x}{x^2} dx$$

And
$$| \int_\pi^\infty\frac{\cos x}{x}\ dx| = |\int_\pi^\infty \frac{\sin x}{x^2} dx|$$
$$\leq \int_\pi^\infty \frac{| \sin x |}{x^2} dx$$
$$\leq \int_\pi^\infty \frac{1}{x^2} dx $$
$$= \frac{1}{\pi}$$

Monday, August 9, 2010

Number of solutions to modular equation

Prove that there are infinitely many prime numbers $p$ such that there are exactly $p^2$ integer triples $(x,y,z)$ such that $0 \leq x,y,z < p$ and $x^2+y^2 - 2010z^3$ is divisible by $p$.

Solution

We will first show that any prime that has form $p = 6k-1$ and does not divide 2010 satisfies the given condition.

First, let $p$ be such prime. Suppose there are $a,b \in \{ 1, \dots, p-1 \}$ such that $a^3 \equiv b^3 \mod p$.

Since $b^{p-1} \equiv 1 \mod p$ then let $c \equiv ab^{p-2} \mod p$, so that we have $bc \equiv a \mod p$.

Then $b^3c^3 \equiv a^3 \equiv b^3 \mod p$ which means $b^3c^3 \equiv b^3 \mod p$ which then means $c^3 \equiv 1 \mod p$ (since $(b,p) = 1$).

Because $c^{p-1} = c^{6k-2} \equiv 1 \mod p$ and $c^{6k-3} = c^{3(2k-1)} \equiv 1 \mod p$, then we must have $c \equiv 1 \mod p$, which means $a \equiv b \mod p$.

In summary, we've shown that $a^3 \equiv b^3 \Rightarrow a \equiv b \mod p$. This means that the set $\{1^3, \dots, p^3 \} \mod p$ is the same as set $\{ 1, \dots, p \} \mod p$. So given any arbitrary $x$ and $y$, we can find exactly one $z$ such that $z^3 \equiv 2010^{-1} (x^2+y^2) \mod p$. Since there are $p^2$ possible pairs for $(x,y)$, then there are also $p^2$ possible triples for $(x,y,z)$.

Now we show that there are infinitely many primes of the form $6k-1$ which would mean that there must be infinitely many primes of the form $6k-1$ that do not divide 2010.

Note that any prime above 3 must have form $6k+1$ or $6k-1$. If there are only finite number of primes of the form $6k-1$, say $p_1, p_2, \dots, p_n$, consider the number $N = 6p_1p_2 \dots p_n - 1$.
For each $i$, $p_i$ does not divide $N$ because otherwise $p_i$ would also have to divide 1, a contradiction. So $N$ is not divisible by any of the $p_i$s, which means all prime factors of $N$ must be of the form $6k+1$. That means, $N \equiv 1 \mod 6$, a contradiction.

Friday, July 23, 2010

a,b,c integers and cubic number

Suppose $a,b,c$ are positive integers such that $\frac{a}{b} + \frac{b}{c} + \frac{c}{a}$ is an integer. Prove that $abc$ is a cubic number.

Solution

We have $ab^2 + bc^2 + ca^2 = kabc$ for some k.

Let $d = \gcd(a,b,c)$. We can replace $a,b,c$ by $a/d, b/d, c/d$ respectively and the problem does not change. Thus, without loss of generality, we may assume that $d = 1$.

Let $p$ be a prime that divides $abc$, which means $p$ divides at least one of $a,b,c$. We also know that $p$ cannot divide all three, since $d = 1$.

If $p$ divides exactly one of $a,b,c$, for example $a$, then $ab^2, ca^2, kabc$ are all divisible by $p$, but not $bc^2$. Impossible. Thus, $p$ must divide exactly two of $a,b,c$.

Suppose $p$ divides $a$ and $b$. Furthermore, let $x$ be the largest integer such that $p^x$ divides $a$. Likewise, let $y$ be the largest integer such that $p^y$ divides $b$.

Since $ab^2, bc^2, kabc$ are all divisible by $b$, then so is $ca^2$. Thus $y \leq 2x$.

Since $ab^2, ca^2, kabc$ are all divisible by $a$, then so is $bc^2$, Thus $y \geq x$, which means $x \leq y \leq 2x$.

Now, since $ab^2, ca^2, kabc$ are all divisible by $p^{2x}$, then so is $bc^2$, which means $y \geq 2x$.

Therefore, $y = 2x$, which means that the degree of $p$ in the factorization of $abc$ is $x+y = 3x$.

For each prime $p$ that divides $abc$, it must occur as a cubic number in its prime factorization. Thus $abc$ is a cubic number.

A non-trivial example is $a=1,b=2,c=4$.

Monday, June 28, 2010

Minimum Reciprocal Length

Given a triangle $ABC$, and point $P$ in its interior. Find points $X,Y$ on $AB$ and $AC$ (or their extensions) such that $XY$ passes through $P$ and
$$\frac{1}{PX} + \frac{1}{PY}$$ is maximized.

Circumcircle and Incircle Tangency

Given a triangle $ABC$, its circumcircle $C_O$ and incircle $C_I$. Suppose $X,Y,Z$ are points on $C_O$ such that $XY$ and $XZ$ are tangent to $C_I$, prove that $YZ$ is also tangent to $C_I$.

Solution

Let us denote $R$ to be the radius of $C_O$ and $r$ to be the radius of $C_I$. Also let $O$ and $I$ to be the centers of the circle. Let also Suppose $AB$ is tangent to $C_I$ at $L$. And suppose $AI$ meets $C_O$ at $M$ and $MO$ meets $C_O$ at $N$.

Now suppose $a = \angle MAZ = \angle MAB = \angle MNC = \angle MCB$. Because $\angle ALI = \angle MCN = 90^o$ then by similarity of $\triangle ALI$ and $\triangle MNC$ we have: $$AI.MC = MN.LI = 2Rr$$

Now $\angle MIC = \angle IAC + \angle ACI = x + \angle ACI = \angle MCB + \angle ICB = \angle MCI$ so that we know $MC = MI$. Thus: $$AI.MI = 2Rr$$

Now, we draw similar figures to the triangle $X,Y,Z$. That is: $XY$ is tangent to $C_I$ at $L'$. And suppose $XI$ meets $C_O$ at $M'$ and $M'O$ meets $C_O$ at $N'$.

In our analysis above, we showed that $AI.MC = 2Rr$ but we didn't use the fact that $BC$ is tangent to $C_I$, so we can repeat the argument to claim that $$XI.M'Z = 2Rr$$.

On the other hand, $XI.IM' = AI.IM = 2Rr$ so we have $IM' = M'Z$ which means $IM'Z$ is an isosceles. $$\angle M'IZ = \angle M'ZI$$ $$\angle M'XZ + \angle IZX = \angle M'ZY + \angle YZI$$ Because $XY$ and $XZ$ are both tangent to $C_I$ then $XM$ is a bisector of $\angle YXZ$ so that $\angle M'XZ = \angle M'XY = \angle M'ZY$. So our equation above becomes: $$\angle IZX = \angle YZI$$ which means $ZI$ is also internal angle bisector, which means $YZ$ is tangent to $C_I$.

Thursday, June 24, 2010

Three independent random variables

3 independent random variables $A,B,C$ are drawn from the same distribution. Determine the correlation between $A-B$ and $B-C$.

Tuesday, June 15, 2010

Polynomial and divisibility

A sequence of polynomials $P_i(x)$ are defined as follows:
$P_1(x) = 1$
$P_2(x) = 1$
$P_{n+2}(x) = (x+2)P_{n+1}(x) - P_n(x), n=1,2,\dots$

Prove that for all $n > 1$, $P_n(x)^2 + x$ is divisible by $P_{n-1}(x)$

Monday, May 31, 2010

Triangle Inequality

Given a triangle $ABC$ and a point $M$ inside the triangle.

Let $\alpha = \angle BMC, \beta = \angle AMC, \gamma = \angle AMB$

Prove that:
$$\frac{AM}{BM.CM} + \frac{BM}{CM.AM} + \frac{CM}{AM.BM} \geq -2 \left( \frac{\cos \alpha}{AM} + \frac{\cos \beta}{BM} + \frac{\cos \gamma}{CM} \right)$$

Solution In Progress

Let
$a = \frac{AM}{\sin \alpha}, b = \frac{BM}{\sin \beta}, c = \frac{CM}{\sin \gamma}$

Because $M$ is in the interior of the triangle, then $0 < \alpha, \beta, \gamma < \pi$ and thus $0 < \sin \alpha, \sin \beta, \sin \gamma \leq 1$. Thus $a,b,c > 0$. Without loss of generality, we may assume that $a \geq b \geq c$.

So we have:
$AM = a \sin \alpha, BM = b \sin \beta, CM = c \sin \gamma$

Substitute it to our inequality, and use the following shorthand:

$C_\alpha = \cos \alpha \sin \beta \sin \gamma$
$C_\beta = \sin \alpha \cos \beta \sin \gamma$
$C_\gamma = \sin \alpha \sin \beta \cos \gamma$

So our inequality becomes
$$ \iff a^2\sin^2 \alpha + b^2 \sin^2 \beta + c^2 \sin^2 \gamma +2 ( bc C_\alpha + ac C_\beta + ab C_\gamma ) \geq 0$$

Note the following identities:
$$C_\beta + C_\gamma = \sin \alpha \cos \beta \sin \gamma + \sin \alpha \sin \beta \cos \gamma = \sin \alpha \sin (\beta + \gamma) = \sin \alpha \sin (2 \pi - (\beta + \gamma)) = - \sin^2 \alpha$$

Similarly,
$$C_\alpha + C_\gamma = - \sin^2 \beta$$
$$C_\alpha + C_\beta = - \sin^2 \gamma$$

So that
$$C_\alpha = (\sin^2 \alpha - \sin^2 \beta - \sin^2 \gamma)/2$$
$$C_\beta = (\sin^2 \beta - \sin^2 \alpha - \sin^2 \gamma)/2$$
$$C_\gamma = (\sin^2 \gamma - \sin^2 \beta - \sin^2 \alpha)/2$$

Substituting back to our inequalities, we have:
$$\iff (a-b)(a-c)\sin^2 \alpha + (b-a)(b-c) \sin^2 \beta + (c-a)(c-b) \sin^2 \gamma \geq 0$$

It's also equivalent to:
$$\iff (a-b)^2 C_\gamma + (a-c)^2 C_\beta + (b-c)^2 C_\alpha \leq 0$$

Thursday, May 20, 2010

Cannot be all negative

Suppose $a_1,a_2,a_3,a_4$ and $b_1,b_2,b_3,b_4$ are eight real numbers. Prove that there is $i,j$ distinct indices such that $a_ia_j + b_ib_j \geq 0$.

Advanced version:
Suppose $a_i,b_i,c_i, 1 \leq i \leq 5$ are fifteen real numbers. Prove that there is $i,j$ distinct indices such that $a_ia_j + b_ib_j + c_ic_j \geq 0$.

General version:
Suppose $A_{i,j}, 1 \leq i \leq n, 1 \leq j \leq n+2$ is a matrix of $n \times (n+2)$ real numbers, prove that there are two columns $p,q$ such that their dot product is non-negative. That is:
$$\sum_{i=1}^{n} A_{i,p} A_{i,q} \geq 0$$

Also find an example of a $n \times (n+1)$ matrix where this property does not hold

A geometric interpretation of this problem is that, given $n+2$ vectors in $n$-dimensional space, two of them must form an angle of 90 degrees or less.

Tuesday, May 18, 2010

Sequence with prime number

Suppose $p$ is a prime number greater than 2, and $m$ is a natural number. Let $a_n$ be sequences defined by:
$a_1 = 1$
$a_2 = m$
$a_{n+2} = \frac{a_{n+1}^2 +p}{a_n}, n = 1,2,...$

Determine all values of $m$ such that $a_n$ is an integer for all $n$.

Thursday, May 13, 2010

Largest k for arbitrary function

Find the largest number $k$ that satisfies the following property:

For every real-valued function $f$ defined over $[0,1]$, there exist $a,b,c \in [0,1]$ such that:
$$|f(ab) + f(bc) + f(ca) - abc | \geq k$$

Solution

First we show that $k = 1/6$ satisfies the condition of the problem.

For $k=1/6$, suppose to the contrary that for all $a,b,c$ chosen in the interval $[0,1]$ we have:
$$|f(ab) + f(bc) + f(ca) - abc | < \frac{1}{6}$$

Let $y = f(0),y=f(1)$.
Plugging in $a=b=c=0$ we have $|3x| < 1/6 \iff |x| < 1/18$
Plugging in $a=b=c=1$ we have $|3y-1| < 1/6$
Plugging in $a=b=1, c=0$ we have $2x+y| < 1/6$

That means $y = (2x+y) - 2x < 1/6 + 2/18 = 5/18$
But also $3y-1 > -1/6 \iff y > 5/18$, a contradiction.

Thus $k= \frac{1}{6}$ satisfies the condition of the problem.

Now we show that it is the largest such constant. We choose a function $f(x) = \frac{6x^\frac{3}{2} - 1}{18}$ and prove that
$$ -\frac{1}{6} \leq f(ab)+f(bc)+f(ca) - abc \leq \frac{1}{6}$$
for all $a,b,c \in [0,1]$

Indeed, the first inequality is equivalent to
$$(ab)^\frac{3}{2} + (bc)^\frac{3}{2} + (ca)^\frac{3}{2} \geq 3abc$$ which is true by AM-GM.

The second inequality is equivalent to
$$(ab)^\frac{3}{2} + (bc)^\frac{3}{2} + (ca)^\frac{3}{2} - 3abc \leq 1$$

Now consider the LHS, and try to find its maximum value over $a,b,c \in [0,1]$
First, we try a substitution $x = \sqrt{ab}, y = \sqrt{ac}, z = \sqrt{bc}, x,y,z \in [0,1]$ and WLOG, we may assume that $x \geq y \geq z$ (which corresponds to $a \geq b \geq c$)
So now our objective function becomes $x^3 + y^3 + z^3 - 3xyz$.

Let $g(x) = x^3 + y^3 + z^3 - 3xyz$, and fix $y,z$.
$$g(1) - g(x) = (1-x^3) - 3yx(1-x) = (1-x)(1 + x + x^2 - 3yz)$$
Because $x \leq 1$, then $1-x \geq 0$
$1+x+x^2-3yz \geq 1 + 2x^2-3yz = (1-yz) + 2(x^2 - yz) \geq 0$
So $g(1) \geq g(x)$.

So the maximum happens when the largest of 3 variables equals to 1. But this means that $ab = 1$ which implies $a=b=1$. Then $y = z = \sqrt{c}$. Our objective function now becomes:
$$x^3 + y^3 + z^3 - 3xyz = 2y^3 - 3y^2 +1$$
Let $h(y) = 2y^3 - 3y^2 + 1$, then $h(y) - h(0) = y^2(2y-3) < 0$ because $y \geq 1$. So the maximum happens when $y = 0$

In conclusion, our maximum happens when $x = 1, y=z=0$ and that's when $a=b=1, c= 0$. At this point, the maximum value is 1, thus proving our assertion.

Another way to determine the maximum value of the function above is by observing that it is a convex function on each of its variable, and all three variables are freely chosen from the interval $[0,1]$. Thus, the maximum must happen when all of its variables are zero or one. Plugging in all permutations of $(0,0,0), (0,0,1), (0,1,1), (1,1,1)$, we find that the maximum is indeed 1.

Wednesday, May 12, 2010

Solution: Passengers Boarding Airplane

Credit goes to Ed Kao, Vallent Lee and Laurence Tai for helping with the second solution.

Original problem: http://dharmath.blogspot.com/2009/10/passengers-boarding-airplane.html

2009 passengers are waiting in a line to board an airplane with 2009 seats. Each passenger has a boarding pass that has his/her seat number on it. The first passenger, however, was oblivious and chose a random seat to sit on.

For each subsequent passenger, he/she will try to sit on his/her assigned seat first. If that seat is taken by someone else, he/she will choose a random empty seat to sit on.

What is the probability that the last passenger would sit on his assigned seat?

Answer: $\frac{1}{2}$

First Solution

We generalize the problem to $n$ passengers boarding an airplane with $n$ seats.

The probability that the first passenger sits in his seat is $1/n$. We will prove by induction that the probability that the $k$-th ($k > 1$) passenger sits in his seat is $\frac{n-k+1}{n-k+2}$

For $k=2$, it's obvious that the second passenger has probability $\frac{n-1}{n}$ of finding his seat unoccupied. As long as the first passenger chooses something other than his seat, he will find his seat unoccupied and sits there correctly.

For $k>2$, consider the time when $k$-th passenger is about to board. If he finds his seat unoccupied, he will sit there. The only way that he does NOT sit on his correct seat is if it's already occupied by a previous passenger. We will divide this into two cases, depending on who sits at his seat.

Case 1: Passenger $k-1$ sits there. The only way this could happen is if passenger $k-1$ finds her seat occupied by someone else, and then she chooses to sit at passenger $k$'s seat. The probability of passenger $k-1$ finds her seat occupied by someone else is $1-\frac{n-(k-1)+1}{n-(k-1)+2} = \frac{1}{n-k+3}$.
At that point, there are $k-2$ occupied seats total and there are $n-k+2$ empty seats on the plane. The probability that she chooses to sit at this particular seat is $\frac{1}{n-k+2}$

Case 2: Passenger $i (i < k-1)$ sits there (at passenger $k$'s seat). Now we consider the moment where passenger $i$ was about to board. Passenger $k$'s seat was open.

If passenger $k-1$'s seat had been occupied by someone else before $i$, then passenger $i$'s seat would have been open, and passenger $i$ must have sit there correctly.

In order for passenger $i$ to NOT sit on his seat, both passenger $k$ and $k-1$'s seat are both open. That means, the probability that passenger $i$ sits at passenger $k$'s seat is the same as the probability that passenger $i$ sits at passenger $k-1$'s seat, since both choices are equally likely and they're always made with both choices available.

Thus the probability from case 2 is $\frac{1}{n-k+3}$

The total probability that passenger $k$ does not sit at his correct seat is:
$$\frac{1}{n-k+3} \frac{1}{n-k+2} + \frac{1}{n-k+3} = \frac{1}{n-k+2}$$
so the probability that he sits at his seat is:
$$1 - \frac{1}{n-k+2} = \frac{n-k+1}{n-k+2}$$
which completes the inductive step.

From this formula, it's clear that the probability passenger $n$ sits on his correct seat is $\frac{1}{2}$

Second Solution
We make the following observations:

1. In the beginning, both seat #1 and #2009 are both empty.
2. The moment someone chooses to sit on either seat (that is, the moment they stop being both empty), there is no more choices to be made for the rest of the boarding process. The rest of the passengers must thus sit deterministically from that point on.

Indeed, when passenger $k$ sits on seat #2009, then seat $k+1, ..., 2008$ would be empty and the subsequent passengers don't have to choose at all. Passenger #2009 has a random "choice" of 1 seat.
If passenger $k$ sits on seat #1, then the remaining vacant seats match the unboarded passengers perfectly and everyone can sit in their correct seat save for those who've already boarded.

That means, for every event that someone illegitimately sits on seat #2009, that passenger had an equally likely choice of seat #1, and vice versa. The moment this symmetry is broken, there would be no more choices to be made for the rest of the boarding process.

3. When passenger #2009 is about to board, there is only one empty seat. That empty seat is either seat #1 or seat #2009. If there is another seat $k ( 1 < k < 2009)$ empty, then one might ask: why didn't passenger $k$ sit there? A contradiction.

From the observations above, we define two events:
A: an event that passenger #2009 sits at seat #1
B: an event that passenger #2009 sits at seat #2009

These two events are mutually exclusive, and are the only two possibilities. Furthermore, they have equal probability since the moment one event becomes impossible, there is no more choices to be made by the rest of the passengers.

So the probability that passenger #2009 sits at his correct seat is $\frac{1}{2}$

Triangle Inequality

In a triangle $ABC$, let $a = BC, b = AC, c = AB$. For any point $M$ and real numbers $x,y,z$, show that

$(x+y+z)(xMA^2 + yMB^2 + zMC^2) \geq xyc^2 + xzb^2 + yza^2$

Solution
We shall show that the inequality above is equivalent to
$$(x \vec{MA} + y \vec{MB} + z \vec{MC})^2 \geq 0$$

Indeed, since:
$$2\vec{MA} \vec{MB} = MA^2 + MB^2 - c^2$$
so
$$2xy\vec{MA} \vec{MB} = xyMA^2 + xyMB^2 - xyc^2$$
$$2yz\vec{MB} \vec{MC} = yzMB^2 + yzMC^2 - yza^2$$
$$2zx\vec{MC} \vec{MA} = zxMC^2 + zxMA^2 - zxb^2$$

Adding them, we obtain:
$$RHS = \sum x(y+z)MA^2 - 2\sum xy \vec{MA} \vec{MB}$$

So
$$LHS - RHS = \sum x^2MA^2 + \sum x(y+z)MA^2 - RHS = \sum x^2 MA^2 + 2\sum xy \vec{MA} \vec{MB}$$
$$= (x \vec{MA} + y \vec{MB} + z \vec{MC})^2 \geq 0 $$

Combined Sequence

Let $A,B$ be two distinct positive integers greater than 1, and define the sequences:

$a_m = m + \frac{Bm}{A}, m = 1,2,3,\cdots, A-1$
$b_m = m + \frac{Am}{B}, m = 1,2,3,\cdots, B-1$

And combine those two sequence to form a new sequence $c_1,c_2,\cdots, c_{A+B-2}$ with $c_1 \leq c_2 \leq \cdots \leq c_{A+B-2}$.

Prove that the difference between any two consecutive $c_i$s are less than 2.

Solution

It suffices to prove that for each $a_k$, we can find another $a_i$ or $b_j$ that lies between $a_k$ and $a_k+2$, and vice versa, for each $b_l$, we can find another $a_i$ or $b_j$ that lies between $b_l$ and $b_l + 2$.
Without loss of generality, we may assume that $A > B$.
The distance between two consecutive $b_j$s are $b_{j+1} - b_j = 1 + B/A < 2$, so for each $b_l$, we're guaranteed that $b_l < b_{l+1} < b_l+2$.

Now we're left to consider $a_k$.
Fix $k$, and now take the smallest $l$ such that $b_l > a_k$. This is always possible because:
\[a_k \leq a_{B-1} = (B-1)(1+A/B) < (A-1)(1+B/A) = b_{A-1}\]
(the middle inequality is true because $A > B$.)

If $l$ is the smallest such $l$, that means
\[b_{l-1} \leq a_k \iff (l-1)(1+B/A) \leq k(1+A/B) \iff l/A - k/B \leq 1/A\]

So
\[b_l - a_k = l(1+B/A) - k(1+A/B) = (A+B)(l/A - k/B) \leq (A+B)/A < 2\]
which completes the proof

Monday, May 10, 2010

3 arbitrary functions

Suppose $f,g,h$ are functions that are defined in the closed interval $0 \leq x \leq 1$. Show that we can always find $a,b,c \in [0,1]$ such that:

$$|f(a)+g(b)+h(c) - (1-a)(1-b)(1-c)| \geq \frac{1}{3}$$

Also show that the constant $\frac{1}{3}$ cannot be replaced by a larger constant.

Finite Prime Set

Let $P$ be a finite set of primes. Define $m(P)$ as the largest number of consecutive integers each of which is divisible by a prime in $P$.
Let $|P|$ denote the size of $P$ and $\min(P)$ to be the smallest element in $P$.

Prove that:
1. $m(P) \geq |P|$
2. $m(P) = |P|$ if and only if $\min (P) > |P|$

Solution

Let $s = |P|$. We proceed by constructing $s$ consecutive integers which are each divisible by a prime in $P$. Indeed, the following system has a solution, according to Chinese Remainder Theorem:
$x+1 \equiv 0 \pmod {p_1}$
$x+2 \equiv 0 \pmod {p_2}$
...
$x+s \equiv 0 \pmod {p_s}$

Second part:
Suppose we have $s < \min(P)$ and that we have $s+1$ consecutive integers all divisible by some $p_i$: $x, x+1, x+2, ... , x+s$. Let $p_1 = \min(P)$.

For each $p_i$, it can only divide at most one of the above-mentioned integers. For if it divides $x+a$ and $x+b$ then it also divides $|a-b| \leq s < p_1$, a contradiction (since $p_1$ is the smallest prime in $P$).
So $m(P) \leq s$. But it's been shown that $m(P) \geq s$, so $m(P) = s$.

Now suppose we have $s \geq \min(P)$. We will show $s+1$ consecutive integers such that each is divisible by a prime in $P$, which then establishes $m(P) > s$.
Let $k = \min(P)$.
Again, we set up a system of equations as described above, but we choose the ordering of $p_i$s such that $p_k = k$. The rest can be arbitrary ordering. This is always possible if $s \geq k$.
According to CRT, there is a solution of $s$ consecutive integers that satisfy the above system of equations. But then we also have $x = x+k - k$ divisible by $p_k = k$. So together with $x$, they form $s+1$ consecutive integers.

Thursday, May 6, 2010

Chess Board Coloring

Each cell in an infinite chess board is colored with one of the $n$ available colors. Prove that we can always find a rectangle such that all four corners have the same color.

Advanced version: Suppose not all cells are colored, but only some of them. Furthermore, for any circle with radius R, we can always find a colored cell in that circle. Prove that we can still find a monochromatic rectangle.

Solution: Cyclic quadrilateral

Original Problem: http://dharmath.blogspot.com/2010/05/cyclic-quadrilateral.html

First Solution

Let $AB=AD=x, BC=y$ and $CD=x+z$ with $y < z$.

Let $\theta = \angle ADC$ so $\angle ABC = 180^o-\theta$. It's easy to see that because $CD > BC$ then $\angle ABC > \angle ADC$ thus $0 < \theta < 90^o$

Now $AC^2 = x^2 + y^2 + 2xy \cos \theta = x^2 + (x+z)^2 - 2x(x+z)\cos \theta$, simplify it to get:
$\cos \theta = \frac{(x+z)^2-y^2}{2x(x+y+z)} = \frac{x+z-y}{x}$

But since $\theta$ is an acute angle, $\theta < 60^o \iff \cos \theta > 1/2$
So we need to show
$x+z-y > x$ which is true because $z > y$

Second Solution



Let $R$ be a point on $CD$ such that $CB = CR$ (see the picture).

Since $AB=AD$, then $CA$ is an internal angle bisector, and thus $\triangle ABC$ are congruent to $\triangle ARC$. That means $RD = CD - CR = CD - CB > AB = AD$.
Also, $AD = AB = AR$.
So $\triangle ARD$ is an isosceles where $AD = AR$ and $RD > AD$, which means that $\angle ADR < 60^o$ and thus $\angle ABC > 120^o$

Wednesday, May 5, 2010

Cyclic quadrilateral

In a cyclic quadrilateral $ABCD$ such that $AB = AD$ and $AB+BC < CD$, show that $ABC > 120^o$

Solution: http://dharmath.blogspot.com/2010/05/solution-cyclic-quadrilateral.html

Thursday, April 22, 2010

Solution 1: Critical Height

Original problem: http://dharmath.blogspot.com/2010/04/critical-height.html

You have an infinite supply of crystal balls that you take into a building with 1000 stories.

There is a critical height at which if you drop the ball from there, the ball would break. If the ball is dropped from the floors under that critical height, it would not break, but if it's dropped from the floors above, obviously, it breaks.

How many trials minimum do you need in order to determine the critical height?

Advanced version #1: If you only have a supply of $k$ balls, how many trials minimum do you need?

Advanced version #2: What is the strategy that would minimize the expected number of trials, given that you only have $k$ balls, if we treat the critical height as a random variable drawn uniformly from (1,...,1000)?

Note that the two advanced versions are two different questions and thus beget two different strategies.

Clarification: When I say "how many trials minimum do you need in order to determine the critical height" it formally means: find the smallest integer $N$ such that it's always possible to determine the critical height within $N$ trials, regardless of where the critical height is. Naturally, this $N$ will be expressed in terms of $k$ in the case of advanced version #1.

Solution to advanced version #1

First we make an observation that we only care about the number of floors that are possible candidates, and the actual floor height is irrelevant. For example, if we know that the critical height must be in the floor 10 to 30, or if we know that it must be in the floor 510-530, we can employ the exact same strategy in both of those situations. The number of minimum trials needed to solve both scenarios are the same, and any action we do in one scenario is directly translatable to the other scenario. We consider these two scenarios as equivalent problems.

Our second observation is that the possible candidates are always in the form of one contiguous block of floors. We start with a block of 1000 floors (floor 1 to 1000). Every time we drop a ball from a certain floor, say floor $a$ either it breaks or it doesn't break. If it breaks, then our next candidate is floor 1 to $a$, and if it doesn't, then our next candidate is floor $a+1$ to 1000. Every time we drop a ball, we divide one contiguous block into two (possibly unequal) halves and we eliminate one half, so we establish an invariant that our candidates are always one contiguous block of floors.

From the two observations above, we may define a function $f(n,k)$ as the minimum number of trials needed to solve the case with $n$ floors and $k$ balls. Without loss of generality (and for notational ease), we may assume that the floors are floor 1 to $n$.

Suppose our first drop is at floor $a$. As we described above, if it breaks, then we are left with $k-1$ balls to find the critical height among floor 1 to $a$. We need at least $f(a,k-1)$ trials to do this. Otherwise, we still have $k$ balls to find the critical height among floor $a+1,...,1000$. We need at least $f(1000-a, k)$ trials. So in the worst case, we need at least $f(n,k) = \max ( f(a,k-1) , f(n-a,k) ) + 1$ if our first drop is at floor $a$. However, we can choose $a$ to minimize the number of trials.
So:
$$ f(n,k) = \min_{a} \left( \max ( f(a,k-1) , f(n-a,k) ) \right) + 1$$

For $k=1$, if we only have 1 ball, then the only possible strategy is to drop it sequentially from floor 1,2,... until it breaks. Thus $f(n,1) = n-1$ For example, if we know that the critical height is somewhere between floor 1 to 3, then we drop it at floor 1 and 2. If it doesn't break at floor 2, then we don't need to test floor 3 because it already know it breaks at floor 3.

Consider the case of $k=2$. Let $g(n) = f(n,2)$. From the recursion above, we have:
$$ g(n) = \min_{a} \left( \max ( a-1 , g(n-a) ) \right) + 1$$

Let $T(n)$ be the $n$-th triangular number. That is,
$T(0) = 0$
$T(1) = 1$
$T(2) = 1+2 = 3$
$T(3) = 1+2+3 = 6$
...
$T(n) = n(n+1)/2$
And let $T^{-1}(n)$ be the ceiling of the inverse triangular number.
That is
$T^{-1}(0) = 0$
$T^{-1}(1) = 1$
$T^{-1}(2) = T^{-1}(3) = 2$
$T^{-1}(4) = T^{-1}(5) = T^{-1}(6) = 3$
$T^{-1}(7) = T^{-1}(8) = T^{-1}(9) = T^{-1}(10) = 4$
and so on.

We claim that $g(n) = T^{-1}(n-1)$, which we shall prove by induction.
For small $n$ we can verify by hand that we can solve $n$ floors and that it's the minimal amount. In fact, for small $n$, $T^{-1}(n-1)$ agrees with $\log_2 n$ which is the information theoretic lower bound.

Now we proceed by strong induction.
$$ g(n) = \min_{a} \left( \max ( a-1 , T^{-1}(n-a-1) ) \right) + 1$$
Note that $T$ is a monotonically increasing function, which means $T^{-1}(n)$ is monotonically non-decreasing. But since the argument to the function is $n-a-1$, the second half of the max is actually non-increasing.

We wish to find $a$ that minimizes the max of two function, one of which is increasing and another non-increasing. The minimum must happen when the two functions intersect, that is when $a-1 = T^{-1}(n-a-1)$.

$$T^{-1}(n-a-1) = a-1$$
$$n-a-1 \leq T(a-1) = a(a-1)/2$$
$$n-1 \leq a+ a(a-1)/2 = a(a+1)/2 = T(a)$$
$$n-1 \leq T(a)$$
$$T^{-1}(n-1) \leq a$$

So the $a$ that minimizes is $T^{-1}(n-1)$, and for that value of $a$,
$f(n) = (a-1) + 1 = a = T^{-1}(n-1)$.

This completes our proof for $k=2$. For an example, suppose we have 11 floors and 2 balls, then our first drop should be at floor 4. If it breaks then we resort to the linear approach with our one remaining ball to discover which among floor 1,2,3,4 is the critical height. We can do it in 3 trials. If it doesn't break, then we drop it at floor 7. If it breaks at floor 7, then the critical floor must be floor 5, 6, or 7, which we can find in 2 trials. If it keeps not breaking, we drop it at floor 9, then 10. In any case, we will find it within 4 trials.

For case $k=3$, we do the same thing except we replace $T$ with $P$, the $n$ pyramidal number.
$P(0) = T(0) = 0$
$P(1) = T(1) = 1$
$P(2) = T(1) + T(2) = 4$
$P(3) = T(1) + T(2) + T(3) = 10$
...
$P(n) = n(n+1)(n+2) / 6$
The arguments in the proof still hold to establish feasibility and optimality of this strategy.

For general case $k$, we replace $P$ with $H_k$, the $n$-th hyper-pyramidal number:
$$H_k (n) = n(n+1)...(n+k-1) / k! = \binom{n+k-1}{k}$$
And the minimum number of trials is
$$f(n,k) = H_k^{-1}(n-1)$$

Critical Height

You have an infinite supply of crystal balls that you take into a building with 1000 stories.

There is a critical height at which if you drop the ball from there, the ball would break. If the ball is dropped from the floors under that critical height, it would not break, but if it's dropped from the floors above, obviously, it breaks.

How many trials minimum do you need in order to determine the critical height?

Advanced version #1: If you only have a supply of $k$ balls, how many trials minimum do you need?

Advanced version #2: What is the strategy that would minimize the expected number of trials, given that you only have $k$ balls, if we treat the critical height as a random variable drawn uniformly from (1,...,1000)?

Note that the two advanced versions are two different questions and thus beget two different strategies.

Clarification: When I say "how many trials minimum do you need in order to determine the critical height" it formally means: find the smallest integer $N$ such that it's always possible to determine the critical height within $N$ trials, regardless of where the critical height is. Naturally, this $N$ will be expressed in terms of $k$ in the case of advanced version #1.

Solution to advanced version #1:
http://dharmath.blogspot.com/2010/04/solution-1-critical-height.html

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.

Thursday, January 21, 2010

Drawing letters

A string of alphabets are randomly generated one letter at a time. Each time, one obtains the letter $A,\cdots,Z$ with probability $p(A),\cdots, p(Z)$. Given that the sum of these probabilities is 1, what is the expected number of draws before the string "DHARMATH" appears?

Wednesday, January 13, 2010

Paired cards

A standard deck of 52 cards is shuffled with uniform probability. A "pair" is defined as two numerically identical cards that are adjacent in the stack. What is the probability that the deck contains no pair?

Challenge: Find the probability that the deck contains exactly $n$ pair for $n=1,2,\cdots,26$.

Infinite fractional sum

Find the limit to the infinite sum:

$$ 1 - \frac{1}{2} +\frac{1}{3} - \frac{1}{4} + \cdots$$

Tuesday, January 12, 2010

Solution: Coupon drawing

Original problem here: http://dharmath.thehendrata.com/2010/01/12/coupon-drawing/

A container holds $N$ coupons. You draw successive coupons from the container, observe the coupon drawn, and then replace the coupon. What is the expected number of draws needed until all $N$ coupons have been seen at least once?

Challenge: what is the probability that the process ends after exactly $M$ draws?

Monday, January 11, 2010

Coupon drawing

Credit for this problem goes to Sander Parawira

A container holds $N$ coupons. You draw successive coupons from the container, observe the coupon drawn, and then replace the coupon. What is the expected number of draws needed until all $N$ coupons have been seen at least once?

Solution here: http://dharmath.thehendrata.com/2010/01/12/solution-coupon-drawing/

Saturday, January 9, 2010

Factorial and power of 2

Credit for this problem goes to Peter Macko.

If $n$ is a positive integer, prove that $(2^n)! $ is divisible by $2^{2^n-1}$ and that its quotient is an odd number.

Inequality

For positive numbers $a,b,c>0$ such that $a+b+c=3$, find the maximum value of

$\frac{1}{2+a^2+b^2} + \frac{1}{2+a^2+c^2} + \frac{1}{2+b^2+c^2} $