Dharmath Vader

A Divided Kingdom

2012-02-08T13:07:00.000-08:00

A kingdom has the shape of a convex $n$-sided polygon $A_1 \dots A_n$. The King owns a castle at point $O$ in the interior of the kingdom, and he has $n$ princes, $P_1, \dots P_n$. They are each given a castle at the vertices of the polygon, so that prince $P_i$ has a castle precisely at $A_i$. The area $OA_iA_{i+1}$ is called the province $i$.

One day, a strife breaks out in the kingdom and each prince declares independence from the King. As a result, each province is divided into one or more vassals, each of which is shaped like a triangle. (Note that each province is a triangle to begin with, so some of the more stable province do not necessarily break apart into multiple vassals). At the vertices of these triangles, a citadel (a smaller castle) was erected.

Each castle and fort then declares an allegiance to King or one of the princes while following these rules:
1. Each castle declares allegiance to its original owner. That is, castle at $O$ keeps its allegiance to the King and castle at $A_i$ keeps its allegiance to prince $P_i$.

2. Each citadel that lies in the province border declares allegiance to either one of the owner of the castles at the endpoints of the province border. For example, a citadel that lies in the line $A_1 A_2$ may declare allegiance to prince $P_1$ or $P_2$, and a citadel that lies in the line $OA_3$ may declare allegiance to either the King or prince $P_3$.

3. Each citadel that lies in the interior of a province declares an allegiance to either one of the owner of the castles at the vertices of the province. For example, a citadel that lies in the province 1 may declare allegiance to either the King, prince $P_1$, or prince $P_2$ (because province 1 is the triangle $OA_1A_2$).

Now, with all citadels and forts having declared allegiance, each vassal's ownership is resolved as follows. Note that each vassal is shaped like a triangle, so it has precisely three citadels or castles on the vertices. If two or more of those citadels or castles declare allegiance to an entity, then the vassal is owned by that entity. For example, if a vassal has vertices declaring allegiance to $P_1, P_2, P_1$, then that vassal is owned by prince $P_1$.

A vassal whose vertices declare allegiance to three different entities is then left in a constant state of war. Prove that the number of such vassals is $n+2k$ where $k$is a non-negative integer.

Successive reflection

2012-01-30T10:36:00.000-08:00

Given 2012 points on the plane: $A_1, \dots, A_{2012}$, and a point $P$. Suppose $B_1, \dots, B_{2012}$ is a permutation of the $A_i$s, we determine the shadow of $P$ as follows:

Reflect $P$ with respect to $B_1$ to obtain $P_1$. Reflect $P_1$ with respect to $B_2$ to obtain $P_2$, and so on, to arrive with $P_{2012}$. We call this last point the shadow of $P$.

Obviously, depending on the permutation of $B_i$s, one may arrive at different shadows of $P$. Find the maximal numbers of shadows of $P$ over all possible permutations.

Graph with degree 3

2012-01-28T22:18:00.000-08:00

A graph where each vertex has degree 3 has all of its edges colored with red, green, or blue. How many colorings are there such that every 3 edges that meet in a vertex are either of the same color or have 3 different colors?

Replacing number on the board

2012-01-28T22:09:00.000-08:00

In a blackboard, the number 2012 is initially written. On each turn, the student can choose on of the three numbers: 6, 1006, 1509, and multiply it with the existing number on the board. The existing number is then erased and replaced with the new product.

The teacher has a specific integer $k > 1$ in mind, and the goal for the student is to get the number of the board to have form $n^k$ where $n$ is an integer.

Determine all values of $k$ such that, after a finite number of turns, the number of the board will have the desired form.

Having fun with infinite series

2011-12-19T10:03:00.000-08:00

1. Warm-up problem: show that
$$1 + \frac{1}{2} + \frac{1}{3} + \cdots = \infty$$

2. Suppose $a_1, a_2, \cdots$ is a sequence of positive numbers such that
$$a_1 + a_2 + \cdots + a_n \leq n^2$$
for all $n$, show that
$$\frac{1}{a_1} + \frac{1}{a_2} + \cdots = \infty$$

3. Suppose $a_1, a_2, \cdots$ is a sequence of positive numbers such that
$$a_1 + a_2 + \cdots + a_n \leq n^2 \log n$$
for all $n$, show that
$$\frac{1}{a_1} + \frac{1}{a_2} + \cdots = \infty$$

Fibonacci Series: Introduction

2011-10-10T12:18:00.000-07:00

Based on popular requests, I'm going to start a new series of posts called the Fibonacci Series (HA!)

It will explore a number of combinatorial interpretations of the Fibonacci series, and the elegance with which we could prove some Fibonacci-related theorems, using purely combinatorial arguments and minimal algebra.

Definition

A sequence $F_n$ is defined by $F_0 = 1, F_1 = 1$ and $F_{n+2} = F_{n+1} + F_n$. This sequence is called the Fibonacci sequence. The first few terms of the sequence is (starting with $F_0$): 1,1,2,3,5,8,13,21,...

Suppose there is a stair with $n$ steps, and one can climb it using "steps" or using "hops" where each step ascends the person by 1 step of stair, and each hop ascends the person by 2 steps.

For a stair with 2 steps, there are 2 ways one can climb it. By using 2 steps, or a hop. For a stair with 3 steps, there are 3 ways: step-hop, hop-step, or step-step-step. For 4 steps, there are 5 ways: 4 steps, step-step-hop, step-hop-step, hop-step-step, hop-hop.

Theorem: In general, for a stair with $n$ steps, there are exactly $F_n$ ways to climb it.

Proof:
Proof by induction.

The first action that one can take could be a step or a hop. If the first action is a step, then the climber must ascend the remaining $n-1$ steps with combinations of steps and hops. There are $F_{n-1}$ such ways.

If the first action is a hop, then the climber must ascend the remaining $n-2$ steps, and there are $F_{n-2}$ ways to do so.

These two cases are mutually exclusive, so in total there are $F_{n-1} + F_{n-2}$ ways to climb. This is exactly the recursive equation for the Fibonacci series, and since the first few terms agree, we conclude that in general the number of ways to climb an $n$-step stair is $F_n$.

Exercise:

There are many more possible combinatorial interpretations of the Fibonacci sequence. For the rest of the series, we are going to use the stair-climbing interpretation, but the following interpretations are just as useful.

1. Prove that $F_{n+1}$ is the number of binary numbers with $n$ digit such that there are no two consecutive zeroes.

2. Prove that $F_{n+1}$ is the number of subset from the set $\{ 1, 2, \dots, n \}$ without two consecutive numbers.

3. Prove that $F_{n-2}$ is the number of ways to tile a $1 \times n$ board with tiles of length 2 or longer.

4. Prove that $F_{n-1}$ is the number of ways to tile a $1 \times n$ board with tiles that have odd length.

5. Prove that $F_n$ is the number of permutation $(a_1, \dots, a_n)$ of $\{ 1, \dots, n \}$ such that for each $i$, $|a_i - i| \leq 1$.

6. Prove that $F_{2n+1}$ is the number of ternary numbers with $n$ digits where a 0 is never followed by a 2.

Are you smarter than a 6th grader?

2011-08-17T14:41:00.001-07:00

This problem was proposed to a math olympiad for 6th graders. The solution doesn't require any algebra nor any more advanced tools, other than simply logic.

Problem

Each apple costs $1 and each orange costs $1.01. Johnny has $101. How many ways are there for him to buy fruits, including possibly not buying anything? Sarah has $99. How many ways are there for her to buy fruits, including possibly not buying anything?

Solution

First we make an observation that 100 and 101 are relatively prime. So suppose Johnny buys X apples and Y oranges and spends exactly Z amount of money. If he wants to spend EXACTLY Z amount of money with a different combination of fruits, he would have to decrease X by 101 and increase Y by 100, or increase X by 101 and decrease Y by 100.

For Johnny,

Consider case 1: If Johnny spends exactly $101. Clearly he can buy 101 apples or 100 oranges, but these are the only two cases.

Case 2: If Johnny spends less than $101. Now, pretend that the store only has 101 apples and 100 oranges (since Johnny can’t buy more apples or more oranges than these).

Consider all the combinations of apples and oranges that Johnny can buy, and consider what’s left at the store. The total amount of goods in the store are $1 x 101 + $1.01 x 100 = $202. So if Johnny spends less than $101, the total amount goods left in the store is greater than $101. We can’t reverse this situation, that is, Johnny can never spend more than $101 so that the total amount left in the store is less than $101.

This means, in all the possible combinations of x apples (x is from 0 to 101 inclusive) and y oranges (from 0 to 100 inclusive), for each combination that Johnny can buy, there is precisely one combination that Johnny couldn’t buy. The combinations that Johnny couldn’t buy represent the amount that would be left in the store if Johnny had bought the “complement” combination instead.

The total number of combinations is 102 x 101 = 10302, (because we go from 0 apples to 101 inclusive, 0 oranges to 100 inclusive) but we have to subtract two combinations from case 1, so we have 10 300, split evenly between what Johnny could buy and couldn’t buy. So Johnny could buy 5150 combinations.

Together from Case 1 and Case 2, Johnny could buy fruits in 5152 ways.

For Sarah,

Case 1: She spends exactly $99. She can buy 99 apples. She couldn’t buy any oranges because if she wants to buy any oranges she’d have to increase it in increments of 100 and decrease the apples in increments of 101, again because 101 and 100 are relatively prime.

Now, consider the story of Johnny. Out of 5150 ways he could buy fruits, categorize them according to his spending:
Category 1: He spends $0 to $98.99
Category 2: He spends $99 exactly
Category 3: He spends $99.01 to $100.99
Category 4: He spends $101

Suppose he buys a certain number of apples and oranges. In order to keep the spending amount intact and changes the number of apples or oranges, as we’ve noted above, he would have to change the number of apples and oranges in increments of 101 and 100 respectively. The total amount of goods being changes (from apples to oranges or vice versa) is already $101. This is why in category 4 he has two ways of buying good. But this means, in category 1, 2, and 3, for each spending amount, there’s at most one (possibly zero) way to buy fruits with that spending amount.

Now, we show that $98.99 spending amount is unattainable. Johnny could achieve that amount by buying 100 apples and –1 oranges, or –1 apples and 99 oranges. Neither one are reasonable.

Next, for each amount in category 1, we pair them up. We pair up X with $98.99 – X. For example, $0 and $98.99 is paired up. $0.01 and $98.98 is paired up, etc.

We claim that within each pair, at most one value is attainable, possibly zero. If both values are attainable, say if Johnny could buy A apples and B oranges with X dollars and C apples and D oranges with $98.99 – X dollars, then he could buy (A+C) apples and (B+D) oranges with $98.99 dollars, a contradiction since we’ve shown that $98.99 is unattainable. So since there are 9900 values, and thus 4950 pairs of values, so there are at most 4950 ways to buy fruits in category 1.

But then there is 1 way in category 2, and total of 5150 ways in category 1,2,3 altogether. So there are at least (5150 – 1 – 4950) = 199 ways to buy in category 3. But notice that there are exactly 199 values (amounts) in category 3, each of which can correspond to at most one way to buy fruits. Thus we must have that each value in category 3 is attainable by exactly one way of buying, and each pair of values in category 1 is attainable by exactly one way of buying.

So in total, when Sarah spends her money, she can spend it from category 1 or 2, and there are 4950 + 1 = 4951 ways of buying.

General Recursion

2011-08-14T21:34:00.001-07:00

Given a recursive formula with $a_{n+1} = 2a_n -1$ and $a_1 = a$, find a general formula for $a_n$.

a,b,c fraction integer

2011-07-23T03:41:00.000-07:00

Given positive integers $a,b,c$ such that
$$\frac{a}{b} + \frac{b}{c} + \frac{c}{a}$$
is also an integer, show that
$$\frac{a^2b^2}{c},\frac{b^2c^2}{a}, \frac{c^2a^2}{b}$$
are all cubic numbers.

Sequence modulo 2011

2011-07-21T07:23:00.000-07:00

A sequence of integers $a_1, \dots, a_{2010}$ satisfy the following properties:

$a_1 - 1$ is divisible by 2011
$a_k a_{k-1} - k$ is divisible by 2011 for $k = 2, 3, \dots, 2010$

Show that $a_{2010} + 1$ is divisible by 2011.

Solution

First we prove the following assertion:

For $k$ odd, then $a_k.2.4.6. \cdots.(k-1) - 1.3.5.\cdots.k$ is divisible by 2011.
For $k$ even, then $a_k.1.3.5. \cdots .(k-1) - 2.4.6.\cdots.k$ is divisible by 2011.

Proof by induction. It can easily be seen for $k=1$ it's true. For $k=2$, we have $2011 | a_2a_1 - 2 = a_2(a_1-1) + (a_2-2)$ So $2011 | a_2 - 2$

Suppose it's true for $k-1$ odd, then for $k$ even:
$2011 | a_k a_{k-1} - k$ which means
$$2011 | 2.4.\cdots.(k-2) (a_k a_{k-1} - k) = 2.4.\cdots.(k-2)a_k a_{k-1} - 2.4.\cdots.(k-2).k$$
$$2011 | a_k (2.\cdots.(k-2)a_{k-1} - 1.3.\cdots.(k-1)) + (a_k.1.3.\cdots.(k-1) - 2.\cdots.(k-2).k)$$
And since 2011 divides the first term by induction hypothesis, then it also divides the second term, which completes the induction step. The proof for $k-1$ even and $k$ odd is similar.

Now, that means for $k=2010$, let $X = a_{2010}$ we have:
$$2011 | X.1.3. \cdots .2009 - 2.4.\cdots.2010$$

We now prove the following assertion for $i = 1,2,\dots,1005$
$$2011 | X.1.3. \cdots. (2011-2i) + (-1)^i (2i) (2i+2)\cdots.2010$$

For $i = 1$ it is true by definition. Now suppose it's true for $i-1$, then for $i > 1$:
$$2011 | X.1.3. \cdots. (2011 - 2i).(2011-2i+2) +(-1)^{i-1} (2i-2) (2i)\cdots.2010$$
if $2011 | a(2011+b) + c$ then $2011 | ab+c$
$$2011 | X.1.3. \cdots. (2011 - 2i).(-2i+2) + (-1)^{i-1} (2i-2) (2i)\cdots.2010$$
if $2011 | a$ then $2011 | -a$.
$$2011 | X.1.3. \cdots. (2011 - 2i).(2i-2) + (-1)^{i} (2i-2) (2i)\cdots.2010$$
$$2011 | 2(i-1)(X.1.3. \cdots. (2011 - 2i).+ (-1)^{i} (2i)\cdots.2010)$$
if $2011 | 2(i-1)a$ then $2011 | a$ since 2011 is prime and $i > 1$.

So the assertion holds for $i = 1,\dots, 1005$. Particularly, for $i = 1005$ we have:
$$2011 | X - 2010$$
$$2011 | X + 1 - 2011$$
$$2011 | X + 1$$

Colored chessboard

2011-07-13T14:25:00.000-07:00

An $n \times n$ chessboard is put on the table such that its sides are facing the North, East, South, and West. Each cell is then colored either with red, green, blue, or yellow paint such that:
1. The North-most cells are colored only with red or green
2. The East-most cells are colored only with green or blue
3. The South-most cells are colored only with blue or yellow
4. The West-most cells are colored only with yellow or red

Prove that there is a point that serves as a vertex to at least three squares of different colors.

Solution

For each cell that has color red, green, blue, and yellow, give it a rank of 1,2,3, and 4 respectively.

Then for each "side" (a segment of line between two cells), mark it if:
1. It delineates two cells. That is, sides that coincides with the sides of the large chess board cannot be marked.
2. Those two cells have a rank differing by exactly 1.

Now, for each vertex, give it a score as follows:
1. The score of each vertex is the number of marked sides that border it. Thus, each cell might have a score of 0, 1, 2, 3, or 4.
2. Vertices that lie on the sides of the large chess board also get their own score. These vertices cannot have a score of 4 of course, but give it a score regardless. Call these vertices the "border vertices" as opposed to "inner vertices"

We assert the following: if an inner vertex has an odd score, then it serves as a vertex to at least three squares of different colors. In other words, an inner vertex with an odd score is the vertex whose existence we seek to prove.

Indeed, it is impossible to form an inner vertex with a score of 1 or 3 with merely one or two colors. For example, if the four squares surrounding the vertex has colors R,G,G,R, then the squares would have ranks of 1,2,2,1, and there are two marked sides. The other combinations are left to the reader as an exercise.

Now, let $A$ be the sum of scores among the inner vertices, and $B$ be the total number of scores among the border vertices. $A+B$ must be even since each marked side contributes two points of score to that total.

We will show that $B$ is odd. The Northwest (NW) corner must be colored red, and the NE corner must be colored green, and the North side must be colored only red or green. Thus, the North side changes color an odd number of times, and each change of color is between a red and a green, producing an odd number of marked sides in the process. These marked sides contribute 1 point each to $B$.

The same argument can be made to the East side and the South side, but not the West side. In fact, none of the color changes on the West side contribute to $B$ at all since they're between a cell of rank 1 and rank 4. So in total, $B$ is a sum of three odd numbers, which means $B$ is odd.

Since $A+B$ is even, then $A$ is odd. That means there must be at least one inner vertex that has an odd score, showing the existence of our desired vertex.

liars and honest villagers

2011-06-26T00:04:00.000-07:00

In a village, there are $n$ people who each has an ID number from 1 to $n$. Each person is either completely honest or a total liar. One day, a detective came to visit and interviewed them. This is what they told him:

If a person had an ID number $x$ where $x$ is even, he said:
"The person whose ID number is $x/2$ is honest"

If a person had an ID number $x$ where $x$ is odd and greater than one, he said:
"The person whose ID number is $(x-1)/2$ is a liar"

Person with ID number of 1 did not say anything.

If $L$ is the number of liars and $H$ is the number of honest villagers, find all possible values of $L-H$

Inequality

2011-06-21T10:18:00.000-07:00

If $x_1,\dots,x_n$ are real numbers such that $0 \leq x_i \leq 1 \forall i$, and satisfies $x_1 + \dots + x_n = m+r$ where $m$ is an integer and $0 \leq r < 1$, show that:

$$(1+x_1)(1+x_2)\dots(1+x_n) \geq (1+r)2^m$$

Determine the conditions under which equality is achieved.

Solution

For each $i$ such that $x_i = 0$ or $x_i = 1$, we can safely eliminate them from the problem without changing neither the condition nor the inequality. So without loss of generality, we can assume that $0 < x_i < 1$ for all $i$.

Now, we prove by induction on $n$. It is trivial for $n=1$. For $n=2$, we have two cases:
1. The simple case, $x_1 + x_2 = r < 1$ then the inequality also holds trivially
2. The overflowing case, where $1 < x_1 + x_2 = 1 + r$, then:
$$(1-x_1)(1-x_2) \geq 0$$
$$\iff 1+x_1x_2 \geq x_1+x_2 = 1+r$$
$$\iff 1+x_1+x_2+x_1x_2 \geq 2+2r$$
$$\iff (1+x_1)(1+x_2) \geq 2(1+r)$$

Now, for a larger value of $n$, suppose that the inequality is established for $n-1$, and suppose that $x_1 + \dots + x_{n-1} = m + r$. Again we have two cases,

1. The simple case, if $x_n + r < 1$ then $x_1 + \dots + x_n = m+ (r+x_n) < m+1$
$$(1+x_1)\dots(1+x_{n-1})(1+x_n) \geq (1+x_n)(1+r)2^m \geq (1+r+x_n)2^m$$
which follows from the simple case for $n=2$ above.

2. The overflowing case, if $1 < x_n + r = 1 + r_2$ then $x_1 + \dots + x_n = (m+1) + r_2$

$$(1+x_1) \dots (1+x_{n-1})(1+x_n) \geq (1+x_n)(1+r)2^m$$
$$ \geq (1+r_2)2^{m+1}$$
which is similar to the overflowing case from $n=2$ above.

The equality cases can be determined as follows:
If all $x_i$s are zeros or ones, then the equality follows trivially. We assert then at most one of the $x_i$s are strictly between zero and one. Because if there are two of them, then both the simple case and the overflowing case in $n=2$ will never reach equality. The inductive step in the proof also depends on these two cases.

Supersum

2011-06-12T13:21:00.000-07:00

For a natural number $n$, the supersum of $n$ is defined as the sum of possible combinations that we can obtain by deleting digits of $n$, calculated as modulo 9. For example, the supersum of 1234 is:

No deletions: 1234 +
Deleting 1 digit: 123 + 134 + 234 + 124
Deleting 2 digits: 12 + 13 + 14 + 23 + 24 + 34 +
Deleting 3 digits: 1 + 2 + 3 + 4

$ = 8 \mod 9$

If $n$ is a 2011-digit number, and $s$ is its supersum, show that $s-n$ is divisible by 9.

Circular Locker Problem

2011-05-18T17:58:00.000-07:00

From a friend's brother:

There are 1000 lockers and 1000 students. The lockers are arranged in a circle, all closed. The 1st student opens all the lockers. The 2nd student closes every other locker. The 3rd student goes to every 3rd locker. If it’s open he closes it, if it’s closed, he opens it. When he gets to locker #999, he continues to locker #2 and continues until he reaches a locker that he has already touched. The 4th student goes to every 4th locker: again, if it’s closed, he opens it, if it’s open, he closes it. Every student after that does the same, until student #1000, who will obviously just open or close locker #1000. After they are all finished, which lockers will be open?

Solution

First, let's think about what happens when student $n$ does his turn.

If $n$ is relatively prime to 1000, that is, $n$ does not contain any factor of 2 or 5, then $n$ will touch all the lockers exactly once. For example, student #3 will go touching lockers 3,6,...,999,2,5,...,998,1,4,7,...,997,1000. In this case student $n$ behaves exactly like student #1.

If $n$ is a multiple of $2$ or $5$, then let $d = \gcd(1000,n)$ Student $n$ touches locker $m$ if and only if $d$ divides $m$. For example, if $n=16$, then $d = 8$. Student #16 will go touching lockers 16,32,...,992,8,24,...,1000, which are exactly all multiples of 8. In this case, student $n$ behaves exactly like student #8.

Now, how many students have numbers that are NOT relatively prime to 1000? Such students must have numbers in the form of $n = 2^a 5^b$ We can enumerate the possibilities:

If $b=0$, then the student numbers are: 2,4,8,16,32,64,128,256,512, for a total of 9 students. Remember that students #16,32,...,512 behave exactly like student #8,and there are 6 of them, so it's equivalent to student #8 going 6 extra times. Their effects cancel out pairwise. So we only need to consider the effects of students #2,4,8.

If $b=1$, then the student numbers are: 5,10,20,40,80,160,320,640, for a total of 8 students. Remember that students #80,...,640 behave exactly like student #40,and there are 4 of them, so their effects cancel out pairwise. So we only need to consider the effects of students #5,10,20,40.

If $b=2$, then the student numbers are: 25,50,100,200,400,800, for a total of 6 students. Remember that students #400,8000 behave exactly like student #200, so their effects cancel out. So we only need to consider the effects of students #25,50,100,200.

If $b=3$, then the student numbers are: 125,250,500,1000.

If $b=4$, then the student number is: 625, which behaves like student #125, and thus cancels the effect of student #125.

So in total, there are 9+8+6+4+1 = 28 numbers that are not relatively prime to 1000, so there are an even numbers of students that are relatively prime. Each of these students touches all lockers exactly once, so their effects again cancel out pairwise. Thus, the student numbers that we need to consider are: (grouped by their largest factor of 2):
5,25
2,10,50,250
4,20,100,500
8,40,200,1000

In order to determine if locker $n$ is closed or open, find all numbers above that divides $n$. If there are even such numbers, then the locker is close, otherwise it's open.

For example, 120 = 3 x 5 x 8, so 120 is divisible by 2,4,8, 5,10,20,40. That means locker #120 is open.

For a more explicit list of open lockers, the following are the open lockers:
1. Lockers with numbers (not divisible by 5 or divisible by 25), and (divisible by 2 but not by 4, or divisible by 8).
2. Lockers with numbers divisible by 5 but not 25, and (divisible by 4 but not by 8).

Magician and cards

2011-05-16T15:12:00.000-07:00

From IMO 2000, problem 4:

A magician has one hundred cards numbered 1 to 100. He puts them into three boxes, a red one, a white one and a blue one, so that each box contains at least one card. A member of the audience draws two cards from two different boxes and announces the sum of numbers on those cards. Given this information, the magician locates the box from which no card has been drawn.

How many ways are there to put the cards in the three boxes so that the trick works?

Solution

There are 12 possible ways to divide the card:
1. RWWW...WWWB (Card 1 goes to red box, card 2 to 99 go to white box, and card 100 goes to blue box) and all of its permutations, for a total of 6 ways.
2. RWBRWBRWB... and all of its permutations, for a total of 6 ways.

We now show that there are no other ways to put the cards. Consider the placement string (RWB string as in the example above). We will divide into two major cases: those with repeating characters, and those without repeating characters.

First, note that if there is a substring "RW" anywhere in the string, we don't allow substring "RB," for otherwise we can have an ambiguous sum of W+R versus R+B. Likewise, if there is a substring "RW" then we don't allow "BW."

Now, suppose there is a repeating substring "WW." Then we can't have a "RB" or "BR" anywhere in the string because there would be an ambiguous sum of R+W versus B+W.

Note that if we already have a "WW" then we can't have a "BB" because "BB" would mean that no "RW" or "WR" can exist, but we already established that no "RB" or "BR" can exist. So combination of "WW" and "BB" altogether would make it impossible for any "R" to exist in the string, a contradiction.

Consider the last B in the string, and call this B'. There are 4 possibilities of strings that come after B':
1. B'B: contradiction because B' is the last B in the string
2. B'R: contradiction because no BR is allowed
3. B'W
4. B' is the last letter in the whole string.

Consider also the last R in the string, call it R'. As in B', we only have 2 possibilities of strings that come after R':
5. R'W
6. R' is the last letter in the whole string.

Now obviously 4 and 6 cannot both be true, so one of them (possibly both) must be false. WLOG, we can assume that 6 is false, then 5 has to be true. If there's RW, we cannot have BW, so 3 is false, which means 4 is true.

So the last R in the string is followed by a W, and B is the last letter in the whole string. Since there already is an RW, we can't have a BW in the entire string. Also, we can't have BB, or BR, so there's no other place for another B. That means B' is the last and only B in the string.

Now, R' can't be preceded by another R (because no RR is allowed), nor by a B (because no BR is allowed), nor by a W, because a WR and a WB' can't both exist. So R' is the earliest R in the string. Since it's also the last, then R' is the only R in the string.

So we have RWW...WWB (and all of its permutations) as the only solution that allows repetition between characters.

Now, suppose there's no repeated characters. We assert that we cannot have a pattern like "RWR" anywhere in the string. Because the character that comes after "RWR" cannot be B, because "RWRB" gives an ambiguous sum of R+B and W+R. We also cannot have RWRR for there's no repeating characters. So we must have either "RWRW" or the fact that RWR is the ending of the entire string. If it is the ending, then we apply the same argument forward, and conclude that the ending must be WRWR. Either way, an RWR can be extended to RWRW or WRWR. But since there is at least one B in the string, and this B cannot be adjacent to another B, and we can't have BW, WB, BR, or RB either, a contradiction. So there must not be any RWR or its permutations anywhere in the string.

Suppose card 1 goes to R, and card 2 goes to W. Card 3 can go to:
1. R, forming RWR, contradiction
2. W, forming a WW, contradiction
3. B.

So we have RWB as the beginning of the string. Now card 4 can go to:
1. R
2. W, forming a WBW, contradiction
3. B, forming a WBB, contradiction.
So card 4 must go to R.

We can continue this argument inductively to arrive that the entire string must have the form: RWBRWBRWB....

Function from N to N

2011-05-05T11:42:00.000-07:00

Find all functions $ f:\mathbb{N}^{*}\rightarrow\mathbb{N}^{*} $
such that

$f(n)+f(n+1)+f(f(n))=3n+1 (\forall)n\in\mathbb{N}^{*} $

Floor And Ceiling

2011-04-27T22:22:00.001-07:00

Show that there are positive integers $a,b,c,d$ with $b,d < 100$ such that:

$$\lfloor \frac{a}{b} k \rfloor = \lfloor \frac{73}{100} k \rfloor$$

and

$$\lceil \frac{c}{d} k \rceil = \lceil \frac{73}{100} k \rceil$$

For all $k = 1,2,\dots,99$

Note: $\lfloor x \rfloor$ denotes the floor function and $\lceil x \rceil$ denotes the ceiling function

Shuffling Card

2011-04-21T12:16:00.000-07:00

A deck of 31 cards is being shuffled, where at each point, the shuffler may perform the following operation:

1. Cut the deck in half and interleave each half to perform a new deck. The cards at position 1,2,3,...,15 now occupy position 2,4,6,...,30, and the cards at position 16,..., 31 now occupy position 1,3,...,31.

2. Similar to operation one, but with different "cut." The cards at position 1,2,3,...,16 now occupy position 1,3,5,...,31, and the cards at position 17,...,31 now occupy position 2,4,6,...,30.

3. Take $m$ cards from the top and move them to the bottom of the deck (a standard cut).

Starting from the original configuration, how many different configurations can be achieved by repeating the three operations above?

Solution

There are $5.31 = 155$ different configurations.
First, it's clear that the deck can be "rotated" in any amount along one direction, so we only consider rotational configurations.
Step 1 moves cards from position $m$ to $2m \mod 31$
Step 2 moves cards from position $m$ to $2m-1 \mod 31$
Step 3 moves cards from position $m$ to $m+k \mod 31$ for some $k$.

Now, step 3 does not change the rotational configurations. Step 1 and 2 both can be consolidated into the move from $m$ to $2m \mod 31$ and followed by a suitable number of step 3.

Thus, the number of different rotational configurations are the smallest number $n$ such that $2^n \equiv 1 \mod 31$, and that means $n=5$.

So there are 5 rotational configurations and 31 configurations within each rotational configuration, for a total of 155.

Functional Equation

2011-04-08T08:52:00.000-07:00

Find all functions $f:N \to N$ such that:

$$f(f(m+n)) = f(m) + f(n) \forall m,n \in N$$

Function Composition

2011-04-06T05:18:00.001-07:00

Are there real-valued continuous functions $f,g$ defined on real numbers such that
$$f(g(x)) = x^{2011}$$
and
$$g(f(x)) = 2011x$$

for all $x$?

Solution

Applying $g$ to both sides, we have:
$$g(f(g(x))) = g(x^{2011})$$
$$2011g(x) = g(x^{2011})$$

Let $x = 1$, we have $g(1) = 0$

Let $P(y) = g(e^y)$ defined on all $y$ real numbers.
So $P(2011y) = g(e^{2011y}) = g((e^y)^{2011}) = 2011g(e^y) = 2011P(y)$
We conjecture that $P(y) = ay$ for some $a$. Setting $x = e^y$, we have:
$$g(x) = g(e^y) = P(y) = ay = a \log x$$

Now plugging back in, our second equation becomes:
$$a \log f(x) = 2011 x$$
$$f(x) = e^{2011x / a}$$

Testing for compatibility with first equation:

$$f(g(x)) = e^{2011 a \log x / a} = e^{2011 \log x} = x^{2011}$$

Symmetric Function in 3 Variables

2011-04-05T15:33:00.000-07:00

A function $f$ is defined from a triplet of positive reals to a positive real number $f:R_+^3 \to R_+$ and satisfies the following:

1. $f$ is symmetric in all 3 variables. That is $f(a,b,c) = f(b,a,c) = f(a,c,b) = ...$
2. For any positive real $t$, $f(ta,tb,tc) = tf(a,b,c)$
3. $f(1/a, 1/b, 1/c) = 2011^2/f(a,b,c)$
4. $f(a,b,c) = f(\sqrt{ab}, \sqrt{ab}, c)$

Determine how many triplet of positive integers $(x,y,z)$ are there such that $f(1/x,1/y,1/z) = 1$

Solution

From rule 3, we have $f(1,1,1) = 2011^2/f(1,1,1)$, so $f(1,1,1) = 2011$.

Now, for any $u,v > 0$,
$f(u,v,1/(uv)) = f(\sqrt{uv}, \sqrt{uv}, 1/(uv))$ using rule 4
and
$f(uv,1,1/(uv)) = f(\sqrt{uv}, \sqrt{uv}, 1/(uv))$ using rule 4
So
$f(u,v,1/(uv)) = f(uv,1,1/(uv)) = f(uv, 1/(uv), 1) = f(1,1,1) = 2011$

Now, for any $t,u,v$, let $k = \sqrt[3]{tuv}$, then $t = k^3/uv$
$f(t,u,v) = f(k^3/uv, u, v) = kf(k^2/uv, u/k, v/k) = kf(u/k, v/k, 1/((u/k)(v/k))) = 2011k = 2011\sqrt[3]{tuv}$

Thus $f(t,u,v) = 2011\sqrt[3]{tuv}$ for all $t,u,v$.

Now we need to determine the number of positive integer triples $(x,y,z)$ such that
$$f(1/x,1/y,1/z) = \frac{2011}{\sqrt[3]{xyz}} = 1$$
$$xyz = 2011^3$$
Since 2011 is a prime, there are only the following possibilities:
1. $(1,1,2011^3)$ and all its permutations, there are three triplets.
2. $(1,2011, 2011^2)$ and all its permutations, there are six triplets.
3. $(2011,2011,2011)$, there is one triplet.

So in total, there are ten triplets that satisfy the condition.

The above conditions could be tailored to fit any symmetric functions. For example, for $f = a^2 + b^2 + c^2 + k$ one can have the following conditions:

1. $f$ is symmetric
2. $f(\sqrt{a^2+t},b,c) = f(a,b,c) + t$
3. Any condition that would determine $f(0,0,0)$
4. $f(a,b,c) = f(\sqrt{(a^2+b^2)/2},\sqrt{(a^2+b^2)/2},c)$

Likewise, for $f = ab+bc+ca$ one can have the following conditions (really hard):
1. $f$ is symmetric
2. $f(a+t,b,c) = f(a,b,c) + t(b+c)$
3. Any condition that would determine $f(0,0,0)$
4. $f(a,b,c) = f(k,k,c)$ where $k = \sqrt{(a+c)(b+c)}-c$

Sequence of natural numbers

2011-03-23T05:46:00.001-07:00

Suppose $a_1,a_2,\dots, a_n,\dots$ is a sequence of natural numbers that satisfy:

$$a_{a_n} = 6n - a_n$$

for all $n$. Find $a_{2011}$.

Solution

For a fixed $n$, let $x_0 = n$
$$x_1 = a_n$$
$$x_2 = a_{x_1}$$
$$x_3 = a_{x_2}$$
$$\cdots$$
$$x_n = a_{x_{n-1}}$$

Then:
$$x_2 = a_{x_1} = a_{a_n} = 6n - a_n = 6x_0 - x_1$$
$$x_3 = a_{x_2} = a_{a_{x_1}} = 6x_1 - a_{x_1} = 6x_1 - x_2$$
In general:
$$x_{n+2} = a_{x_{n+1}} = a_{a_{x_n}} = 6x_n - a_{x_n} = 6x_n - x_{n+1}$$
$$x_{n+2} + x_{n+1} - 6x_n = 0$$

This is a second order recursion with characteristic equation $t^2 + t - 6 = 0$ with solutions $t = -3, t = 2$.

So the general term for $x_n$ is:
$$x_n = P.2^n + Q.(-3)^n$$.
However, for $x_n$ to be positive for all $n$, then $Q$ must be zero, otherwise with large enough $n$, $x_n$ could eventually be negative. Thus $x_n = P.2^n$ for some $P$.

$a_n = x_1 = 2P = 2.P = 2x_0 = 2n$

After substituting back, we find that $a_n = 2n$ satisfies all the constraints, so we have $a_n = 2n$ for all $n$.

Technology Review March/April 2011 Problem 3

2011-03-08T06:34:00.000-08:00

The figure contains three semicircles and one circle. The semicircles all have horizontal diameters, and their centers are shown. Their radii are $R, r_1, r_2$ with $r_1 + r_2 = R$. The circle is constructed tangent to the three semicircles. Find $p$ the radius of the circle, and show that the distance from its center to the baseline is $2p$.

(Note: I couldn't draw them as semicircles and I was too lazy to crop the image. But you get the idea).

Solution

Suppose the circle centered in $A$ has radius $r_1$, and the circle centered in $B$ has radius $r_2$. We can readily see that $BC = r_1$ and $AC = r_2$. Also because the third circle is tangent to all circles:
$OA = p+r_1$
$OB = p+r_2$
$OC = r_1 + r_2 -p$

From Stewart's Theorem:

$$OC^2 AB = OA^2 BC + OB^2 AC - AB.BC.AC$$
$$(r_1 + r_2 - p)^2 (r_1+r_2) = r_1(p+r_1)^2 +r_2(p+r_2)^2 - r_1 r_2 (r_1 + r_2)$$

The coefficient of $p^2$ on both sides of that equation is $r_1 + r_2$, thus this is not a quadratic equation, but merely a linear equation in $p$. Expanding and canceling both sides gives us:

$$ p = \frac{r_1r_2(r_1+r_2)}{(r_1+r_2)^2-r_1r_2} = \frac{r_1r_2R}{R^2-r_1r_2}$$

To compute the distance $h$ from $O$ to $AB$, first we calculate the area of triangle $OAB$. Since $OA = p+r_1, OB = p+r_2, AB = r_1+r_2$, we can use Heron's formula:

$$S_{OAB} = \sqrt{(p+r_1+r_2)pr_1r_2} = \frac{1}{2} h AB = \frac{1}{2} h R$$
$$4(p+r_1+r_2)pr_1r_2 = h^2 R^2$$
$$h^2 = \frac{4(p+r_1+r_2)pr_1r_2}{R^2}$$

Now note that $p+r_1+r_2 = p+R = \frac{r_1r_2R}{R^2-r_1r_2} + R = \frac{R^3}{R^2-r_1r_2}$

Plug this into the equation above:

$$h^2 = \frac{4(p+R)pr_1r_2}{R^2} = \frac{4}{R^2} \frac{R^3}{R^2-r_1r_2} \frac{r_1r_2R}{R^2-r_1r_2} r_1r_2 = 4 \frac{(r_1r_2R)^2}{(R^2-r_1r_2)^2}$$
$$h = 2p$$

Technology Review March/April 2011 Problem 2

2011-03-08T06:31:00.000-08:00

On an infinite chessboard an Obamaknight can move six spaces in any direction, then turn left and move one space. For example, from (5,-3) he can move to N-W to (4,3) followed by two moves E-N ending at (16,5). Place a finite number of Obamaknight on the board so that (allowing an arbitrary number of moves):
i. no one of them can reach any other one of them
ii. any position on the board can be reached by one of them

Extension: a modern Obamaknight moves six spaces in any direction, then turns left or right and moves one space. Place a finite number of modern Obamaknights with the above properties.

Solution to original problem:

We begin by noticing that the moves are commutative. When two moves are swapped, the ending position is still the same. There are only four possible moves: N-W, E-N, S-E, and W-S. Furthermore, each pair of N-W and W-S "cancel out", and so do E-N and W-S. So each sequence of moves is equivalent to $a$ moves of N-W followed by $b$ moves of $E-N$ for some integers $a,b$.

If we start at $(0,0)$, and make $a$ moves of $N-W$ + $b$ moves of $E-N$, we will end up at $(-a+6b ,6a+b)$. If we vary $a,b$ over all possible integers, we will get a grid of parallelograms, where one parallelogram has vertices at cells $(0,0), (-1,6), (6,1), (5,7)$. Any cell in this grid (that is, any cell that serves as a vertex of a parallelogram in this grid) can be reachable from $(0,0)$ with proper choice of $a$ and $b$. Conversely, the knight can only reach those cells that are part of the grid.

If we start at $(1,0)$ and repeat the process above, we get a similar grid, except everything is shifted one cell to the east.

Thus, the answer to the original problem is simply how many cells are in the one parallelogram described above. If we put the knights to fill up that parallelogram, they will all reach different cells, and collectively able to reach any cell.

I can't draw the grid and the cells here, but there are 30 such cells. You can convince yourself by drawing the grid, but the cells in the rectangle with vertices $(0,1),(5,1),(0,5),(5,5)$ cover them all. Each cell in that rectangle is not reachable from any other cell in that rectangle, and collectively those cells cover the entire board, since the rectangle can be "copied and stamped" around.

Solution to the extension problem:

One crucial fact about the original problem is that the number of elementary moves are the same as the dimensionality of the board. The board is in 2-D, while there are 2 elementary moves. In the extension problem, we now have four elementary moves (N-W, N-E, E-N, E-S). So the same analysis won't work.

Instead, we attempt to reconstruct a move of "one to the right" by using a finite number of those four moves. Indeed, we could.

$$3 \times (6,1) -3 \times(6,-1) - (-1,6) = (1,0)$$

Thus, 3 moves of E-N followed by 3 moves of W-N followed by S-E results in one move to the right. Using similar technique, one can construct a move of one to the top/left/bottom, and then reach any position on the board. Therefore, one Obamaknight is enough.

Technology Review March/April 2011 Problem 1

2011-03-08T06:30:00.000-08:00

Consider the solution of any ordinary sudoku puzzle. What is the largest number of times that any fixed integer can appear on either of the two major diagonals? Show that this number can actually occur.

Solution:

Five. The major diagonal passes through five 3x3 squares, and each of those squares can only contain any fixed integer once. Thus the theoretical maximum is 5. The figure below shows that the number 9 can appear five times along the major diagonals.

Coins in equilateral lattice

2011-03-01T23:02:00.000-08:00

$n(n+1)/2$ coins are placed on an equilateral lattice with side $n$, such that all but one coin are showing heads.

At each step, one is allowed to choose two adjacent coins $A$ and $B$, and then flip all coins on the line $AB$ (and its extension).

Characterize all starting configuration such that it's always possible to get all tails.

Find angle C

2011-02-03T09:06:00.001-08:00

From AMC12 1999:

In triangle $ABC$,
$3 \sin A + 4 \cos B = 6$
$4 \sin B + 3 \cos A = 1$

Find $\angle C$

a,b,c,d odd powers

2010-12-07T12:56:00.001-08:00

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)$.

Triangular (and tetrahedral) lattice

2010-11-18T08:11:00.001-08:00

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.

Number of black cells

2010-10-25T03:51:00.000-07:00

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?

Completable Paintings

2010-09-25T08:20:00.000-07:00

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.

Ternary Polynomial

2010-09-16T13:57:00.000-07:00

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.

Integral Inequality

2010-09-01T06:35:00.000-07:00

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}$$

Number of solutions to modular equation

2010-08-09T13:08:00.000-07:00

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.

a,b,c integers and cubic number

2010-07-23T14:26:00.001-07:00

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$.

Minimum Reciprocal Length

2010-06-28T16:03:00.000-07:00

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

2010-06-28T12:55:00.000-07:00

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$.

Three independent random variables

2010-06-24T08:32:00.001-07:00

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

Polynomial and divisibility

2010-06-15T05:58:00.000-07:00

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)$

Triangle Inequality

2010-05-31T21:29:00.000-07:00

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$$

Cannot be all negative

2010-05-20T11:51:00.000-07:00

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.

Sequence with prime number

2010-05-18T22:31:00.000-07:00

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$.

Largest k for arbitrary function

2010-05-13T14:33:00.000-07:00

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.

Solution: Passengers Boarding Airplane

2010-05-12T11:20:00.000-07:00

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

2010-05-12T09:21:00.000-07:00

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

2010-05-12T09:16:00.001-07:00

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

3 arbitrary functions

2010-05-10T13:27:00.000-07:00

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

2010-05-10T12:36:00.000-07:00

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.

Chess Board Coloring

2010-05-06T11:54:00.000-07:00

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

2010-05-06T11:51:00.000-07:00

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$

Cyclic quadrilateral

2010-05-05T10:36:00.000-07:00

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

Solution 1: Critical Height

2010-04-22T19:22:00.000-07:00

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

2010-04-22T11:51:00.000-07:00

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

Solution: Happy Saint Math Trick's Day

2010-03-23T08:35:00.000-07:00

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

2010-03-23T08:10:00.001-07:00

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

Second Solution: Osculating Circle, Ellipse, and Cone

2010-03-19T15:27:00.000-07:00

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?

2010-03-19T15:23:00.000-07:00

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?

Which stack has counterfeit coins?

2010-03-18T16:52:00.000-07:00

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

2010-03-18T14:08:00.000-07:00

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

Osculating Circle, Ellipse, and Cone

2010-03-12T11:17:00.000-08:00

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

2010-03-12T10:56:00.000-08:00

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.

Tennis tournament

2010-03-09T21:34:00.001-08:00

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

2010-03-09T21:28:00.000-08:00

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.

Drawing letters

2010-01-21T06:12:00.000-08:00

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?

Paired cards

2010-01-13T07:56:00.000-08:00

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$.

Solution

First we solve the following problem: given $n$ letters, how many strings of length $4n$ can we form such that there are no two equal adjacent letters and each letter appears exactly 4 times. For example, if $n=3$, then we wish to form a string of length 12 from the letters A,B,C each appearing 4 times such that there are no two equal adjacent letters. Some examples of legal strings are ABCABCABCABC, or ABCBACACBCBA

Infinite fractional sum

2010-01-13T01:52:00.000-08:00

Find the limit to the infinite sum:

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

Solution: Coupon drawing

2010-01-12T09:55:00.000-08:00

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?

Solution

Answer: $N + N/2 + N/3 + \cdots + N/(N-1) + 1$

Proof:

Fix $N$, and let $f(m)$ be the expected number of draws until we see all coupons, provided that we have seen $m$ coupons so far. The number that we are looking for is $f(0)$, and we know that $f(N) = 0$.

Observe that when we draw a random coupon, we have a $m/N$ chance of drawing a coupon we have seen, and thus wasting our draw. After that draw, the expected number of draws is still $f(m)$. But we also have a $1-m/N$ chance of drawing a new coupon, after which our expected number becomes $f(m+1)$.

So $f(m) = \frac{m}{N}(1 + f(m)) + (1-\frac{m}{N})(1 + f(m+1))$

which is equivalent to $f(m) = f(m+1) + \frac{N}{N-m}$

Since $f(N) = 0$, one can inductively prove that $f(m) = \frac{N}{1} + \frac{N}{2} + \cdots + \frac{N}{N-m}$

Solution to challenge problem

In order for the $M$-th draw to be the last draw, it must be the first occurrence of the last coupon needed. Let's say the last draw is $N$, then the first $M-1$ draws must be formed solely by coupons $1, \cdots, N-1$ where each coupon appears at least once.

Let $a_r$ be the number of strings with length $r$ where each letter can be one of $1, \cdots, N-1$. Then the probability in question is $Na_{M-1}/ N^M$

Also, we have the following relationship (think Exponential Generating Function):

$ \sum_{r=0}^{\infty} \frac{a_r}{r!}x^r = ( \sum_{r=1}^{\infty} \frac{1}{r!}x^r ) ^{N-1}$

so

$ RHS = (e^x - 1)^{N-1} = \sum_{k=0}^{N-1} \binom{N-1}{k} e^{kx} (-1)^{n-k-1}$

Now, the coefficient of $x^r$ in the binomial expansion is

$\sum_{k=0}^{N-1} \binom{N-1}{k}\frac{k^r}{r!} (-1)^{n-k-1}$

so that

$ a_r = \sum_{k=0}^{N-1}\binom{N-1}{k} k^r (-1)^{n-k-1}$

There is (as far as I know) no known simplification for the above form.

Coupon drawing

2010-01-11T02:30:00.000-08:00

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/

Factorial and power of 2

2010-01-09T16:51:00.000-08:00

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

2010-01-09T03:27:00.000-08:00

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} $

Average Winning Roll

2009-12-21T04:27:00.000-08:00

$n$ people are rolling a random real number between zero and one. The highest roll wins. What is the expected value of the winning roll?

Solution: Stones and Marbles

2009-12-17T04:00:00.000-08:00

Original problem: here

First, I apologize that the problem was not carefully worded. The problem statement should have been: find all initial conditions where it's always possible for Bob to empty all the three boxes.

There are 3 boxes, and 2010 stones and 2010 marbles are put arbitrarily inside those three boxes.

At each step, Bob is allowed to either:

1. take a stone from one box, a marble from another box, and put them on the third box

2. add or subtract all boxes by the same number of stones

3. add or subtract all boxes by the same number of marbles

Prove or disprove, that by repeating these steps, Bob can empty all three boxes.

Solution

Answer: If the total number of objects (stones + marbles) in each box is congruent to each other modulo 3.

Proof:

We can generalize the problem by replacing 2010 with $n$, and it is easy to see that if $n$ is not divisible by 3, then Bob will never be able to empty the boxes, since each operation does not change the total number of objects modulo 3.

Furthermore, even if $n$ is divisible by 3, and we have 2 boxes where they are not congruent to each other modulo 3, Bob will also not be able to empty the boxes. Clearly steps 2 and three does not change relative congruency mod 3, and the first step can be thought as reducing 1 object from each box and adding 3 objects to one box, which again does not change relative congruency mod 3.

Now, suppose the number of total objects in each box is congruent to each other mod 3, we will show that one can always achieve three empty boxes.

Label the boxes as 1,2, and 3. We will denote $A(x,y)$ as the operation of taking a marble from box $x$, a stone from box $y$, and putting them in the third box. We denote the configuration of the boxes at any time by a six-tuple $(m_1, s_1, m_2, s_2, m_3, s_3)$ where $m_i, s_i$ represent the number of marbles and stones in box $i$ respectively. For the time being, we shall also allow negative numbers in the boxes, because due to steps 2 and 3, we can always raise all numbers by the same amount temporarily.

We also denote the change caused by an operation as a six-tuple similar to the one above, but with a square bracket. For example, $A(1,2) = [-1,0,0,-1,1,1]$ means that the operation $A(1,2)$ reduces the number of marble in box 1 by 1, number of stones in box 2 by 1, and increases the number of marbles and stones in box 3 by 1, and leaves everything else unchanged. This is true by definition.

Now, note that:

$A(1,2) = [-1,0,0-1,1,1]$

$A(2,3) = [1,1,-1,0,0,-1]$

$A(1,3) = [-1,0,1,1,0,-1]$

So $A(1,2)+A(2,3)+A(1,3) = [-1,1,0,0,1,-1]$ which means that the composition of the above 3 operations has the effect equivalent of switching a marble in box 1 with a stone in box 3. So now we can define a new operation $B(x,y)$ as switching the marble in box $x$ with a stone in box $y$, using the algorithm described above.

Starting with an initial configuration of arbitrary placement, our first goal is to obtain a configuration in the form of $(a,a,b,b,c,c)$. We can first apply $B(1,2)$ or $B(2,1)$ repeatedly until number of stones and marbles in box 1 are equal or differ by 1. Then we can apply $B(2,3)$ or $B(3,2)$ repeatedly until the number of stones and marbles in box 2 are equal or differ by 1. Because the total number of stones and marbles are equal, this must mean that the number of stones and marbles in box 3 differ by at most 2. We now have 2 cases:

1. We have a configuration in the form of $(a, a+1, b+1, b, c, c)$ or its permutation. Then we apply $A(2,1) = [0,-1,-1,0,1,1]$ to arrive at $(a,a,b,b,c+1,c+1)$ which has the required form.

2. We have a configuration in the form of $(a, a+1, b, b+1, c+2, c)$ or its permutation. We apply $B(3,2) = [0,0,1,-1,-1,1]$ to arrive at $(a,a+1, b+1,b, c+1,c+1)$ which reduces us to case 1.

So now we have a configuration in the form of $(a,a,b,b,c,c)$ where $a \equiv b \equiv c \mod 3$ (by the invariance principle outlined in the beginning).

Now note that:

$A(1,2) = [-1,0,0-1,1,1]$

$A(2,1) = [0,-1,-1,0,1,1]$

$A(1,3) = [-1,0,1,1,0,-1]$

$A(3,1) = [0,-1,1,1,-1,0]$

So $A(1,2)+A(2,1) + A(1,3)+A(3,1) = [-2,-2,1,1,1,1]$, which is equivalent to taking 2 marbles and 2 stones from box 1, and putting 1 of each in box 2 and 3. Let us define $C(x)$ as the operation of taking 2 marbles and 2 stones from box $x$ and putting 1 of each in the two other boxes.

If we let $d = \max (a,b,c) - \min (a,b,c)$. If $d = 0$, then we are done, because that means all three boxes have equal content, and we can repeatedly apply steps 2 and 3 to empty the boxes. But if $d > 0$ we claim that judicious use of operation $C(x)$ will always reduce $d$. Indeed, without loss of generality, we may assume $a \leq b \leq c$. We have 2 cases:

1. If $a \leq b < c$, we apply $C(3)$, then $(a,a,b,b,c,c)$ becomes $(a+1,a+1,b+1,b+1, c-2,c-2)$. But since $c \equiv b \mod 3$, then $c-b \geq 3 \iff c-2 \geq b+1 \geq a+1$ which means now $d' = (c-2)-(a+1) = (c-a)-3 = d-3$.

2. If $a < b \leq c$, we apply $C(2) + C(3)$, then $(a,a,b,b,c,c)$ becomes $(a+2,a+2,b-1,b-1,c-1,c-1)$. But since $b \equiv a \mod 3$, then $b-a \geq 3 \iff a+2 \leq b-1 \leq c-1$ which means now $d' = (c-1)-(a+2) = (c-a)-3 = d-3$.

Thus, we can always reduce $d$ by 3 at a time until we get the configuration where $d = 0$ when all three boxes have equal content. At that point, we can repeatedly apply steps 2 and 3 to empty them.

Stones and Marbles

2009-12-16T01:23:00.000-08:00

There are 3 boxes, and 2010 stones and 2010 marbles are put arbitrarily inside those three boxes.

At each step, Bob is allowed to either:

1. take a stone from one box, a marble from another box, and put them on the third box

2. add or subtract all boxes by the same number of stones

3. add or subtract all boxes by the same number of marbles

Prove or disprove, that by repeating these steps, Bob can empty all three boxes.

Twist And Spin

2009-12-15T04:27:00.000-08:00

A matrix $M$ is skew-symmetric if and only if $M^{tr} = -M$. Let $S$ be the set of all 4x4 skew-symmetric matrices.

Twist

Suppose $F:\mathbb{R}^4 \to \mathbb{R}^4$ is a differentiable vector field in $\mathbb{R}^4$, we define the operation "twist" that maps each point in $\mathbb{R}^4$ to $S$ as follows:

If $F(x,y,z,w) = A\vec i + B \vec j + C \vec k + D \vec l$ then

$(\bold{twist} F)(x,y,z,w) = \left( \begin{array}{cccc}
0 & B_x - A_y & C_x - A_z & D_x - A_w \\
A_y-B_x & 0 & C_y - B_z & D_y - B_w \\
A_z-C_x & B_z - C_y & 0 & D_z - C_w \\
A_w - D_x & B_w - D_y & C_w - D_z & 0 \end{array} \right) $

Where $B_x$ denotes $\partial B / \partial x$ and so on. One way that makes it easier to memorize the formula is to associate the first column and row with $x$, second column and row with $y$, third with $z$, and last with $w$.

Spin

If $G : \mathbb{R}^4 \to S$ is a differentiable function that takes a point in $\mathbb{R}^4$ to a skew-symmetric matrix, we define the operation "spin" that produces a vector field in $\mathbb{R}^4$ as follows:

If $G(x,y,z,w) = \{ \sum_{i,j} G_{ij}(x,y,z,w) \}$ (where $G_{ij}$ is the entry at the $i$-th row and $j$-th column, and since $G$ is skew-symmetric, then $G_{i,i} = 0$ and $G_{ji} = -G_{ij}$)

Then

$(\bold{spin} G)(x,y,z,w) = (G_{23_w} + G_{34_y} + G_{42_z}) \vec i $

$+(G_{13_w} + G_{34_x} + G_{41_z}) \vec j$

$+(G_{12_w} + G_{24_x} + G_{41_y}) \vec k$

$+(G_{12_z} + G_{23_x} + G_{31_y}) \vec l$

where again $G_{ij_x}$ denotes $\partial G_{ij} / \partial x$ and so on.

Problems:

Prove the following:

1. $(\bold{spin}(\bold{twist} F)) = \vec 0$

2. $\bigtriangledown \cdot ( \bold{spin} G) = 0$

3. If $F$ is a conservative vector field, then $\bold{twist} F = \vec 0$

Dissecting a tetrahedron

2009-12-08T09:49:00.000-08:00

Let $T_r$ denote a regular tetrahedron whose side length is $r$.

1. Prove that it is impossible to assemble eight $T_1$ into a $T_2$.

2. Prove that a tetrahedron can be cut into four optically congruent pieces. Two solids $A$ and $B$ are considered optically congruent if either $A$ or its mirror image can be rotated into $B$.

3. Prove that a $T_2$ can be cut into four $T_1$ and a regular octahedron whose side length is 1.

Solution: Inequality

2009-12-02T03:59:00.000-08:00

Original problem: http://dharmath.thehendrata.com/2009/12/02/inequality/

For positive real number $a,b,c$ prove that

$2\sqrt{ab+bc+ca} \leq \sqrt{3} \sqrt[3]{(a+b)(b+c)(c+a)}$

First Solution

Credit for this solution goes to Sander Parawira

$!9 (a+b)(a+c)(b+c) \geq 8 (a+b+c)(ab+ac+bc) \geq 8 \sqrt{3} (ab+ac+bc)^{3/2}$

The first inequality is well-known, and the second one is equivalent to $a^2+b^2+c^2 \geq ab+bc+ca$

$! 3 \sqrt{3} (a+b)(a+c)(b+c) \geq 8 (ab+ac+bc)^{3/2}$
$! \sqrt{3} \sqrt[3]{ (a+b)(a+c)(b+c) } \geq 2 \sqrt{ab+ac+bc}$

Second Solution

Since it's homogeneous, we may assume that $ab+bc+ca=1$. We wish to minimize $(a+b)(b+c)(c+a)$.

If we let $a = \cot A, b = \cot B, c = \cot C$, then the normalization condition implies that $A,B,C$ are angles of a triangle.

$(a+b)(a+c) = a^2+ab+bc+ca = a^2+1 = \csc^2 A$

So $(a+b)(b+c)(c+a) = \csc A \csc B \csc C = 2R^2/S$ where $S$ is the area of the triangle and $R$ is the circum-radius.

Now the problem can be rewritten as: given a circle with radius 1, find 3 points $ABC$ on the circle such that the triangle $ABC$ has maximal area.

We claim that the maximal area occurs when $ABC$ is an equilateral triangle. Suppose $AB \neq BC$, then let $B'$ the midpoint of the arc $AC$ that passes through $B$. Compare the area of $ABC$ and $AB'C$. These triangles have the same base $AC$, but different heights. Since $B'$ is the midpoint of the arc, then the distance from $B'$ to $AC$ is greater than that of $B$ to $AC$. Thus $S_{ABC} < S_{AB'C}$.

This means that whenever the triangle has two unequal sides, we can always find another triangle with greater area. The process stops when all three sides are equal, and that's when $ABC$ is an equilateral triangle.

Variation: minimizing $\csc A \csc B \csc C$ can also be done with Jensen, using the function $f(x) = \log \csc x$

This is because $f'(x) = -\cot(x)$ and $f''(x) = \csc^2 x$ thus $f$ is convex.

Inequality

2009-12-02T02:21:00.000-08:00

For positive real number $a,b,c$ prove that

$2\sqrt{ab+bc+ca} \leq \sqrt{3} \sqrt[3]{(a+b)(b+c)(c+a)}$

solution: http://dharmath.thehendrata.com/2009/12/02/solution-inequality/

Solution: 3 Variable Inequality

2009-11-30T06:50:00.000-08:00

Original problem: http://dharmath.thehendrata.com/2009/11/24/3-variable-inequality/

For $a,b,c > 0$, prove that:

$! (ab(a+b) + bc(b+c) + ca(c+a))^2 \geq 4abc(a+b+c)(a^2+b^2+c^2)$

First Solution

WLOG, we assume $a \geq b \geq c$.

From AM-GM: $RHS \leq (ac(a+b+c) + b(a^2+b^2+c^2))^2$

But $ac(a+b+c) + b(a^2+b^2+c^2) \leq ab(a+b) + bc(b+c) + ca(c+a) \iff b(b-a)(b-c) \geq 0$

Second Solution

We will use the usual notation $S(k,l,m)$ to denote the symmetric sum: $S(k,l,m) = \sum a^kb^lc^m$ where the sum is over all permutations of $a,b,c$.

$ab(a+b)+bc(b+c)+ca(c+a) = \sum a^2b = S(2,1,0)$.

$4(a+b+c)(a^2+b^2+c^2) = S(1,0,0).S(2,0,0) = 2S(3,0,0) + 4S(2,1,0)$

So $RHS = abc(2S(3,0,0) + 4S(2,1,0)) = 2S(4,1,1) + 4S(3,2,1)$

And $LHS = S(2,1,0).S(2,1,0) = S(4,2,0) + S(3,3,0) + S(4,1,1)+ 2S(3,2,1) + S(2,2,2)$

So we need to prove:

$! S(4,2,0) + S(3,3,0) + S(2,2,2) \geq S(4,1,1) + 2S(3,2,1)$

By Muirhead, $S(4,2,0) \geq S(4,1,1)$, so we only need to prove

$! S(3,3,0) + S(2,2,2) \geq 2S(3,2,1)$

$! \iff S(3,3,3) (S(0,0,-3) + S(-1,-1,-1)) \geq 2S(3,3,3) S(0,-1,-2)$

$! \iff S(0,0,-3) + S(-1,-1,-1) \geq 2S(0,-1,-2)$

which is true by Schur

Solution: Integer Inequality

2009-11-30T06:02:00.000-08:00

Original problem: http://dharmath.thehendrata.com/2009/11/27/integer-inequality/

For any positive real number $t$, prove that there are integers $a,b,c,d$ such that

$! a^3b+b^3c+c^3d < tabcd$

Solution

Putting $a=b=c=d=1$, we find that the answer is trivial if $t > 3$. Now suppose $t \leq 3$.

Let $x=a/d, y=b/d, z=c/d$ be positive rational numbers, so our inequality becomes:

$! x^3y + y^3z +z^3 < txyz$

Let $f(x,y,z) = \frac{x^3y + y^3z +z^3}{xyz}$. Now, AM-GM asserts that $x^3y + y^3z + z^3 \geq 3xyz\sqrt[3]{yz}$, with equality happens if and only if $x^3y = y^3z =z^3$. In other words, when the equality conditions are satisfied, then $f(x,y,z) = 3\sqrt[3]{yz}$.

Equality conditions require that $z = y^{3/2}$ and $x = (y^2z)^{1/3} = y^{7/6}$. So, $f(y^{7/6}, y, y^{3/2}) = 3y^{5/6}$

If we want to find $y$ such that $3y^{5/6} < t$ then $y < (t/3)^{6/5}$. Which means we want to find $y$ such that $1/y > (3/t)^{6/5}$.

Now, let $N$ be an integer large enough such that $N^6 > (3/t)^{6/5}$. We can set $(x,y,z) = (1/N^7,1/N^6,1/N^9)$ which can be achieved by setting $(a,b,c,d) = (N^2, N^3, 1, N^9)$.

One can check that the assignment of $a,b,c,d$ does satisfy the condition of the problem:

$LHS = N^9 + N^9 + N^9 = 3N^9$

$RHS = t N^{14}$

$LHS < RHS \iff 3 < tN^5 \iff N^6 > (3/t)^{6/5}$, which is true by the way we chose $N$.

System Change

2009-11-30T05:56:00.000-08:00

Starting with today, I am going to change the system at which problems and solutions are posted, to avoid spoiling solutions for people who do not want to be spoiled.

For each problem post, there will be a corresponding solution post, with category Solution. The two posts will refer to each other.

The problem post will simply post the problem and a link to the solution post.

The solution post will repeat the problem, and then post the solution behind a "More" link.

Integer Inequality

2009-11-26T17:58:00.000-08:00

For any positive real number $t$, prove that there are integers $a,b,c,d$ such that

$! a^3b+b^3c+c^3d < tabcd$

Solution: http://dharmath.thehendrata.com/2009/11/30/solution-integer-inequality/

Polynomial Algorithm

2009-11-25T16:42:00.000-08:00

Credit for this problem goes to Zeke Chin

Does there exist an algorithm for the decision problem:

Given a polynomial over $n$ variables $x_1,\cdots,x_n$ with positive integer coefficients, and a positive integer $c$, is it true that $cx_1\cdots x_n \leq P(x_1,\cdots,x_n)$ for all assignments of positive integers to $x_1,\cdots,x_n$?

For example, for $P = x_1^2 + x_2^2$ and $c=2$, the algorithm should return "Yes" since $2x_1x_2 \leq x_1^2 + x_2^2$

Solution

We can rewrite the problem as follows: if $P$ is a positive integer polynomial defined over positive integers, what is the minimum value of $Q = P/x_1\cdots x_n$? Or, if the minimum value does not exist, what is the infimum of all the achievable values?

Homogeneous polynomials

We first restrict our attention to homogeneous polynomials of degree $k$ (each term in $P$ has a total degree of $k$). If $k < n$ then the infimum is zero, because when we scale up all the $x_i$ by a factor, $P$ decreases accordingly. For example, if $P = ab+b^2+ac$, then $Q = (ab+b^2+ac)/abc$. It is easy to make $Q$ arbitrarily small by multiplying $a,b,c$ by a large factor.

Homogeneous polynomials of degree $n$

If $k=n$, that means $Q$ is homogeneous of degree zero. Thus, if we scale all the $x_i$ by the same factor, $Q$ remains constant. Now, we can assume $P$ is defined over rational numbers for simplicity.

For each coefficient of $P$, we write them as sums of ones. For example, if $P = a^2b^2 + 2bc^3 + 2cd^3$, then we write it as $P = a^2b^2 + bc^3 +bc^3+ cd^3 + cd^3$ such that we can now assume that all terms in $P$ have coefficients 1, even if the terms may repeat themselves.

Then $Q = \frac{ab}{cd} + \frac{c^2}{ad} + \frac{c^2}{ad} + \frac{d^2}{ab} + \frac{d^2}{ab}$

We now define the profile number of each variable as the total number of powers in the polynomial $Q$. For example, $p_a$, the profile number of $a$ is $1-1-1-1-1 = -3$, and $p_b = -1, p_c =3,p_d=1$. Thus we write the profile numbers of $P$ as $(-3,-1,3,1)$.

Let $s = P(1,\cdots,1)$ be the number of terms in $P$. In the example above, $s=5$.

The sum of of all profile numbers $\sum p_{x_i} = 0$, because each term has a total degree of zero. This means that the average number of profile number is zero. If all profile numbers are exactly zero, then the minimum value of $Q$ is $s$. For example, if $Q = (a^2b + abc+bc^2)/abc$, then by AM-GM, $Q \geq 3$. The minimum can be achieved when all $x_i$ is 1.

Not all profile numbers are equal

If not all profile numbers are equal, then some profile numbers are positive and some others negative. Let $x_i,x_j$ be such that $p_{x_i} > 0, p_{x_j} < 0$. Write $x_i = k_1x_j$ and substitute it into $Q$. In the example (before) above, $p_c = 3, p_a=-3$. So we write $c = k_1a$, then

$! \displaystyle Q = \frac{b}{k_1d} + \frac{k_1^2a}{d}+\frac{k_1^2a}{d}+\frac{d^2}{ab}+ \frac{d^2}{ab}$

This operation has 3 effects:

1. It eliminates $c$ from the polynomial. So now the profile of $c$ is guaranteed to be zero.

2. It preserves homogeneity if we view $k_1$ as a dimensionless number. In the example above, each term is still homogeneous with degree zero. This means that the sum of profile numbers are still zero. In fact, now the profile numbers are $(0,-1,0,1)$. In general, replacing $x_i$ with $kx_j$ will cause the transformation $(p_{x_i}', p_{x_j}') = (0, p_{x_i} + p_{x_j})$

3. The "profile number" of $k_1$ in the example above is guaranteed to be positive, by the way we choose $k_1$. We say profile number in quotes because we say that $k_1$ is a dimensionless number, and thus is not given a profile number per se.

We keep doing this operation, choosing a variable with a positive profile number and one with negative profile number, and make a $k$-substitution like above. By the majorization-theorem, we are guaranteed to terminate with a condition that all profile numbers are zero. Furthermore, the "profile numbers" of all the $k_i$s are positive. We continue with the example above, substituting $d=k_2b$ to arrive with:

$! \displaystyle Q = \frac{1}{k_1k_2} + \frac{k_1^2a}{k_2b}+\frac{k_1^2a}{k_2b}+\frac{k_2^2b}{a}+ \frac{k_2^2b}{a}$

Now, according to the AM-GM theorem, if we set each term in the above equation to be equal, then $Q$ will be expressed in terms of $k_i$, all with positive powers. This means we can set $Q$ to be arbitrarily small by setting the variables accordingly. Thus, the infimum of all achievable values of $Q$ is zero.

As an example, if we set $\frac{1}{k_1k_2} = \frac{k_1^2a}{k_2b} = \frac{k_2^2b}{a}$, along with $c=k_1a, d=k_2b$ we get $ b = k_1^3a, c = k_1a, d = k_1^{5/3}a$. Substituting this value back to original expression of $Q$, we obtain $Q = 5k_1^{1/3}$.

If we want $Q$ to be really small, say $10^{-2}$, then we set $k_1 = 10^{-6}$ and $a=1$, which gives us $b=10^{-18}, c = 10^{-6}, d=10^{-10}$. For the sake of original problems that $a,b,c,d$ need to be positive integers, we multiply everything by $10^{18}$ to get$(a,b,c,d) = (10^{18}, 1, 10^{12}, 10^{8})$

Missing cases

So far, the missing cases are:

1. Non homogeneous polynomials

2. Homogeneous polynomials of degree greater than $n$. The conjecture here is that we simply test the value of $Q$ for all combinations of $x_i = 1,2$. The output is either an achievable value when all $x_i = 1$, or an infimum of zero.

Final Algorithm

The final algorithm is as follows. The final output values are italicized.

1. Is the polynomial homogeneous?

No: ??

Yes: go to step 2

2. What is the degree of homogeneity?

Less than $n$: infimum value is zero

Exactly $n$: go to step 3.

Greater than $n$: ??

3. Compute the profile numbers of each variable. Are they all zero?

Yes: the minimum values achieved when all variables are one

No: infimum value is zero

3 Variable Inequality

2009-11-24T03:56:00.000-08:00

For $a,b,c > 0$, prove that:

$! (ab(a+b) + bc(b+c) + ca(c+a))^2 \geq 4abc(a+b+c)(a^2+b^2+c^2)$

Solution: http://dharmath.thehendrata.com/2009/11/30/solution-3-variable-inequality/

Mean of Means

2009-11-23T11:16:00.000-08:00

If $a_i,b_i$ are positive numbers for $i=1,\cdots,n$, and

$! M_r (a,b) = \left( \frac{a^r+b^r}{2} \right)^\frac{1}{r}$

Prove that for $0 < r < s$,

$! \displaystyle \sum M_r(a_i,b_i) \sum M_{-r}(a_i,b_i) \leq \sum M_s(a_i,b_i) \sum M_{-s}(a_i,b_i) \leq \sum a_i \sum b_i$

Triangle Inequality

2009-11-22T03:03:00.000-08:00

Given $n$ right triangles each with sides $a_i, b_i, c_i$, with $c_i$ being the hypotenuse ($i=1,\cdots, n)$. Let $A = \sum a_i, B = \sum b_i, C= \sum c_i$.

Prove that

$\displaystyle \frac{a_1b_1}{c_1} + \cdots + \frac{a_nb_n}{c_n} \leq \frac{AB}{\sqrt{A^2+B^2}}$

Harder version: prove that

$\displaystyle \frac{a_1b_1}{c_1} + \cdots + \frac{a_nb_n}{c_n} \leq \frac{AB}{C}$

Solution

For each $i$,

$ (\frac{1}{a_i^2} + \frac{1}{b_i^2})(\frac{1}{A^2} + \frac{1}{B^2}) \geq (\frac{1}{a_iA} + \frac{1}{b_iB})^2$

and

$ (\frac{a_i}{A^3} + \frac{b_i}{B^3})(\frac{1}{a_iA} + \frac{1}{b_iB}) \geq (\frac{1}{A^2} + \frac{1}{B^2})^2$

If we let $S = 1/A^2 + 1/B^2$, then two inequalities above can be combined to form:

$ (\frac{a_i}{A^3} + \frac{b_i}{B^3})\sqrt{\frac{1}{a_i^2} + \frac{1}{b_i^2}} \geq S^{3/2}$

$ (\frac{a_i}{A^3} + \frac{b_i}{B^3}) \geq S^{3/2} \frac{a_ib_i}{c_i}$

So, when we sum the last inequality over all $i$, we have:

$ (\frac{A}{A^3} + \frac{B}{B^3}) \geq S^{3/2} \sum \frac{a_ib_i}{c_i}$

$ S^{-1/2} \geq \sum \frac{a_ib_i}{c_i}$

So $LHS \leq \frac{1}{\sqrt{S}} =RHS$

Remark

The harder version is stronger than the easier version due to Minkowski's inequality, which asserts that $C^2 \geq A^2+B^2$

Solution for harder version

We wish to prove that

$ \sum_i c_i \sum_j \frac{a_jb_j}{c_j} \leq \sum_i a_i \sum_j b_j$

Consider the expansion for both sides. If $i=j$ then the product is $a_ib_i$, which is canceled in both LHS and RHS.

If $i \neq j$, then we assert that:

$ \frac{c_ia_jb_j}{c_j} +\frac{c_ja_ib_i}{c_i} \leq a_ib_j + a_jb_i$

$ \iff c_i^2a_jb_j +c_j^2a_ib_i \leq (a_ib_j + a_jb_i)c_ic_j$

$ \iff (a_i^2+b_i^2)a_jb_j +(a_j^2+b_j^2)a_ib_i \leq (a_ib_j + a_jb_i)c_ic_j$

$ \iff (a_ib_j + a_jb_i)(a_ia_j + b_ib_j) \leq (a_ib_j + a_jb_i)c_ic_j$

$ \iff a_ia_j + b_ib_j \leq c_ic_j$

which is true by Cauchy, since $c_i = \sqrt{a_i^2+b_i^2}$

3 Sequence Inequality

2009-11-19T08:58:00.000-08:00

If $a_i, b_i, c_i$ are sequences of positive numbers for $i = 1,2,\cdots,n$, prove the following inequality:

$\sum (a_i+b_i+c_i) \sum \frac{a_ib_i + b_ic_i+ c_ia_i}{a_i+b_i+c_i} \sum \frac{a_ib_ic_i}{a_ib_i + b_ic_i+ c_ia_i} \leq \sum a_i \sum b_i \sum c_i$

where all summations are taken from $i=1$ to $i=n$. When does equality happen?

Solution

First, we prove the following lemma:

Lemma

$\sum \frac{x_iy_i}{x_i+y_i} \sum (x_i+y_i) \leq \sum x_i \sum y_i$

Proof:

Let $X = \sum x_i, Y = \sum y_i$. We first note that $(\frac{x_i}{X^2} + \frac{y_i}{Y^2})(\frac{1}{x_i} + \frac{1}{y_i}) \geq (\frac{1}{X} + \frac{1}{Y})^2$ for each $i$.

Which means

$\displaystyle \frac{x_i}{X^2} + \frac{y_i}{Y^2} \geq \frac{1}{1/x_i + 1/y_i}(1/X+1/Y)^2 = \frac{x_iy_i}{x_i+y_i}(1/X+1/Y)^2$

Then, if we let $S = \frac{XY}{X+Y} \iff 1/S = 1/X+1/Y$, then

$\displaystyle \frac{x_i}{X^2} + \frac{y_i}{Y^2} \geq \frac{x_iy_i}{(x_i+y_i)S^2}$

The above inequality holds for all $i$, so we sum them from $i=1$ to $n$ to yield:

$\displaystyle \frac{X}{X^2} + \frac{Y}{Y^2} \geq \sum \frac{x_iy_i}{(x_i+y_i)S^2}$

But the LHS is just $1/X+1/Y = 1/S$, so the last inequality is equivalent to the lemma.

Lemma Interpretation

One thing that I was amazed by is that the lemma has such a striking form. If we let $A(x_1,\cdots,x_k)$ be the arithmetic mean of $x_1,\cdots, x_k$, and $H(x_1,\cdots,x_k)$ be its harmonic mean, the lemma can be rewritten as:

$ \displaystyle A(H(x_1,y_1), \cdots, H(x_n,y_n)) \leq H(A(x_1,\cdots,x_n), A(y_1, \cdots, y_n))$

There is such a similarity between this equation and, for example, Cauchy. Because if we let $G$ to denote geometric mean, then Cauchy's inequality can be rewritten as:

$ \displaystyle A(G(x_1,y_1), \cdots, G(x_n,y_n)) \leq G(A(x_1,\cdots,x_n), A(y_1, \cdots, y_n))$.

Furthermore, if we let $M_p(x_1, \cdots, x_n)$ to be the $p$-th power mean, then $A = M_1, G = M_0, H = M_{-1}$.

Minkowski Inequality is $M_p \circ M_1 \leq M_1 \circ M_p$ for $p > 1$.

Holder (and in turn Cauchy) Inequality is $M_1 \circ M_0 \leq M_0 \circ M_1$.

But our lemma is $M_1 \circ M_{-1} \leq M_{-1} \circ M_{1}$.

In general, if $p < q$ are finite real numbers, then $M_p \circ M_q \geq M_q \circ M_p$ with equality happens when the numbers are all zeros or all proportional.

First Inequality

First we shall prove the following inequality. If we let $A = \sum a_i, B = \sum b_i, C = \sum c_i$

$\displaystyle (AB+BC+CA)\sum \frac{a_ib_ic_i}{a_ib_i + b_ic_i + c_ib_i} \leq ABC$

which can be rewritten as:

$\sum \frac{1}{1/a_i + 1/b_i + 1/c_i} \leq \frac{1}{1/A + 1/B + 1/C}$

First let's define a sequence $p_i = \frac{b_ic_i}{b_i + c_i}$ which is equivalent to $1/p_i = 1/b_i + 1/c_i$. Let $P= \sum p_i$

Then using our lemma, we have $P \leq \frac{BC}{B+C} = \frac{1}{1/B + 1/C}$.

Again, using the lemma,

$LHS = \sum \frac{1}{1/a_i + 1/p_i} \leq \frac{1}{1/A + 1/P} \leq \frac{1}{1/A+1/B+1/C}$ which proves the first inequality.

Second Inequality

Now we shall prove the following inequality.

$\displaystyle (A+B+C)\sum \frac{a_ib_i + b_ic_i + c_ib_i}{a_i+b_i+c_i} \leq AB+BC+CA$

Now let $q_i = b_i + c_i$, so if we let $Q = \sum q_i = B+C$, by the lemma:

$\sum \frac{a_ib_i + a_ic_i}{a_i+b_i+c_i} = \sum \frac{a_i q_i}{a_i + q_i} \leq \frac{AQ}{A+Q} = \frac{AB+AC}{A+B+C}$.

Similarly,

$\displaystyle \sum \frac{b_ic_i + a_ib_i}{a_i+b_i+c_i} \leq \frac{BC+AB}{A+B+C}$.

$\displaystyle \sum \frac{a_ic_i + b_ic_i}{a_i+b_i+c_i} \leq \frac{AC+BC}{A+B+C}$.

Adding three inequalities gives us the second inequality.

When we multiple first and second inequalities, we get the desired result.

Matching Binary String

2009-11-17T08:53:00.000-08:00

We are given two binary strings $A$ and $B$ each of length $2n$. Both strings contain equal number of ones and zeros to each other. We write $A$ on top of $B$, so that each element of $A$ is paired with each element of $B$ at the corresponding position.

We call the two strings a "match" if there are at least $n$ common elements where the element of $A$ at a certain position matches that of $B$ at that position.

Prove that, we can cyclically shift $B$ a number of times (and wrap around at the end/beginning) so that $A$ and $B$ form a match.

Simplifying Series

2009-11-16T06:52:00.000-08:00

Let $a_n = \binom{2n}{n}$ and $b_n = \binom{3n}{n}$. Find a more compact expression for:

$A(x) = a_0 + a_1x + a_2x^2 +\cdots + a_nx^n + \cdots$

$B(x) = b_0 + b_1x + b_2x^2 +\cdots + b_nx^n + \cdots$

Solution

We start with $A(x) = 1 + 2x + 6x^2 + 20x^3 + \cdots + \binom{2n}{n}x^n + \cdots$

Differentiate both sides,

$A'(x) = 2 + 12x + 60x^2 + \cdots + \binom{2n}{n}nx^{n-1} + \binom{2n+2}{n+1}(n+1)x^n + \cdots$

$\frac{A' - 2A}{4x} = 2 + 12x + 60x^2 + \cdots $

The coefficient of $x^{n-1}$ in $\frac{A'-2A}{4x}$ is the coefficient of $x^n$ in $\frac{A'-2A}{4}$

$= \frac{1}{4}(\binom{2n+2}{n+1}(n+1) - 2\binom{2n}{n})$

$= \frac{1}{4}\binom{2n}{n}(\frac{(2n+2)(2n+1)}{n+1} - 2) = n\binom{2n}{n}$

which is the coefficient of $x^{n-1}$ in $A'$.

Thus, $\frac{A'(x)-2A(x)}{4x} = A'(x)$.

$A'(x)(1-4x)= 2A(x) \iff \frac{dA}{dx} (1-4x) = 2A$

$\frac{dA}{2A} = \frac{dx}{1-4x}$

Integrate both sides, with the boundary condition that $A(0)=0$

$\frac{\ln |A|}{2} = \frac{\ln (1-4x)}{-4} \iff A = (1-4x)^{-\frac{1}{2}}$

So $A(x) = \frac{1}{\sqrt{1-4x}}$

To find a compact expression for $B(x)$, we temporarily use $x^2$ as the generating variable.

Let $P(x) = B(x^2) = b_0 + b_1x^2 + b_2x^4 + \cdots + b_nx^{2n} + \cdots$

By inspection, we have

$(4-27x^2)P'' - 81xP' -24P = 0$

And its correctness can be verified by comparing the coefficient of $x^n$ directly. All that's left is to simply solve the differential equation.

I wasn't able to solve the actual equation, but I did find that if we let $y = -27xP + (4-27x^2)P'$ then $y' = -3P$

ABC String

2009-11-14T18:46:00.000-08:00

How many strings of A's, B's, and C's are there that satisfy the following conditions:

1. There are $n$ A's and $2n$ total of B's and C's.

2. Every two adjacent letters are different.

Solution

In order to create such string, we could first arrange $n$ A's and $2n$ D's such that no two A's are adjacent. Then, we can color the D's with B's and C's to satisfy the problem constraint. Note that in order for the coloring to be valid, each contiguous segment of D can only be colored in two ways: BCBCBC.... or CBCBCB...

So now the question is, how many such linings of A's and D's are possible? We first lay down the A's. We then have $n-1$ spots in between that must be filled by non-empty segments of D's, and two spots at both edges that contain possibly-empty segments of D's. Further more, the sum of the length of the segments must equal $2n$, and each segment may be colored in 2 ways.

So, we claim that the number of ways is the coefficient of $x^{2n}$ in the expansion of:

$(1+2x+2x^2+....)(2x+2x^2+2x^3+...)^{n-1}(1+2x+2x^2+...)$

Each term of $x^{2n}$ in the above expansion comes from multiplication of $x^k$ terms in each factor whose sum of power is $2n$. The contribution of $x^k$ from a given factor corresponds to the length of segment corresponding to that factor. The first and last factor correspond to the outer segments which may be empty. The middle segments may not be empty, and that's why we require that they contribute at least one power of $x$. The coefficients are also set up so that each nonempty segments contribute 2 to the number of possible colorings while empty segments do not contribute.

From here, it's just a matter of algebraic manipulation. Let $y=2x+2x^2+... = \frac{2x}{1-x}$

Then $S = (1+y)^2y^{n-1} = y^{n-1} + 2y^n + y^{n+1}$

Also note that, according to Binomial Theorem:

$\frac{1}{(1-x)^k} = (1-x)^{-k} = 1 + kx +\frac{(k+1)k}{2!}x^2 + \frac{(k+2)(k+1)k}{3!}x^3 + ... = \sum_{i=0}^{\infty} \binom{k+i-1}{i} x^i$

So, the coefficient of $x^{2n}$ in $y^{n-1} = 2^{n-1} x^{n-1} \frac{1}{(1-x)^{n-1}}$ is $2^{n-1}$ times the coefficient of $x^{n+1}$ in $\frac{1}{(1-x)^{n-1}}$

that is $2^{n-1} \binom {2n-1}{n+1}$

Similarly, the coefficient of $x^{2n}$ in $2y^n$ is $2^{n+1}\binom{2n-1}{n}$

And the coefficient of $x^{2n}$ in $y^{n+1}$ is $2^{n+1}\binom{2n-1}{n-1}$

So the total coefficient is $2^{n-1} \binom {2n-1}{n+1} + 2^{n+1}\binom{2n-1}{n} + 2^{n+1}\binom{2n-1}{n-1}$

$= 2^{n-1} \frac{(2n-1)!}{n!(n-2)!} \left( \frac{1}{n+1} + \frac{4}{n-1}+ \frac{4}{n-1} \right)$

$= \binom{2n+1}{n} \frac{2^{n-2}(9n+7)}{n(2n+1)}$

Coin Toss

2009-11-14T17:37:00.000-08:00

A boy tosses a fair coin repeatedly. Every time he gets a Head, he earns 1 penny, and every time he gets a Tail, he earns 2 pennies. He starts with no money. Prove that the probability of him at one time having exactly $n$ pennies is $\frac{2+(-\frac{1}{2})^n}{3}$

Path and Parallelogram

2009-11-12T05:50:00.000-08:00

A path from $A$ to $B$ consists of several piecewise straight segments (where $b \neq A$). A flea starts from point $P$ and for each segment, it performs the following operation:

If the segment starts at $X$ and ends at $Y$, and the flea is currently at $Z$, the flea will jump to the point $Z'$ such that $XZYZ'$ is a parallelogram (in that order).

The flea starts from $P$ and performs the operation on the segments sequentially until it is done with the last segment, where the flea is now in $Q$. Prove that $APBQ$ is a parallelogram.

Integral

2009-11-08T03:59:00.000-08:00

Evaluate $ \int e^x \sec x \tan^2x dx$

Solution

Let $A = \int e^x \sec^3x dx$ and $B = \int e^x \sec x dx$, and since $\tan^2x = \sec^2x-1$, the desired integral is $A-B$.

$A = \int e^x \sec^3x dx$

Here we evaluate it using integration by parts, with

$u = e^x \sec x, du = e^x \sec x (\tan x + 1) dx$

$dv = \sec^2x dx, v = \tan x$

So

$A = uv - \int v du = e^x \sec x \tan x - \int e^x \sec x \tan^2 xdx - \int e^x \sec x \tan x dx$

$= e^x \sec x \tan x - (A-B) - \int e^x \sec x \tan x dx$

Save this equation. Now we evaluate $\int e^x \sec x \tan x dx$ using integration by parts again,

$u = e^x, du = e^x dx$

$dv = \sec x \tan x dx, v =\sec x$

So $\int e^x \sec x \tan x dx = e^x \sec x - \int e^x \sec x dx = e^x \sec x - B$

Plug this back into the saved equation:

$A = e^x \sec x \tan x - (A-B) - \int e^x \sec x \tan x dx $

$= e^x \sec x \tan x - (A-B) - (e^x \sec x - B)$

So $2A-2B = e^x \sec x \tan x - e^x \sec x$

Thus $A-B = (e^x \sec x \tan x - e^x \sec x) / 2$

Divide Colored Balls

2009-10-30T05:31:00.000-07:00

There are $2n$ balls of each color: red, green, and blue. How many ways are there to divide them into two groups such that each group has $3n$ balls?

First Solution

It is the same as the coefficient of $3n$ in the expansion $(1+x+x^2+x^3+\cdots+x^{2n})^3$. The proof is left to the readers as an exercise.

Note that $(1+x+\cdots+x^{2n})^3 = \frac{(1-x^{2n+1})^3}{(1-x)^3} = (1 - 3x^{2n+1} + 3x^{4n+2} - x^{6n+3})(1-x)^{-3}$

But $(1-x)^{-3} = (1+3x + 6x^2 + 10x^3 + \cdots + \frac{(k+2)(k+1)}{2}x^k + cdots)$

So the coefficient of $3n$ in that expansion is:

$\frac{(3n+2)(3n+1)}{2} - 3\frac{n(n+1)}{2} = 3n^2 + 3n + 1$

Second Solution

We shall prove that there are $3n^2+3n+1 = (n+1)^3 - n^3$ ways, which has striking geometrical interpretations.

Create an equilateral triangle with altitude $3n$, and mark all the points that has integer distance to all the sides. These points will form a triangular lattice

It is a well-known fact that for any point in an equilateral triangle, the sum of distances to the sides is constant. Since the altitude of the triangle is $3n$, then for any point in that triangular lattice, the sum of distance to the sides is $3n$. Furthermore, the distances are integers. Thus, these points represent the number of ways to choose $3n$ balls from 3 colors.

However, the constraint that we only have $2n$ supply of each color is not yet enforced. We examine the points in the lattice whose distance to any of the sides is greater than $2n$, and we eliminate them. So we are left with a hexagonal lattice of side $n+1$. This is the projection of a half-shell of an $n+1$-cube that has $n$-cube carved out of it.

Students in a School

2009-10-28T09:46:00.000-07:00

There are 3 schools, each of which has $n$ students. Each student knows altogether $n+1$ students from the other two schools. Prove that we can choose 3 students, each from a different school, such that they know each other.

Solution

Assign each student a score based on the higher number of students he/she knows from each school. For example, if a student knows 4 students from one school and 5 students from another school, his score is 5.

Choose student $a$ with the highest score. Since the highest score is not necessarily unique (there may be multiple highest scores), choose any one of them.

Suppose student $a$ belongs to school $A$, and let $k$ be his score. Suppose he knows $k$ students from school $B$ and $n+1-k$ students from school $C$, where $k \geq n+1-k$.

Take any student $c$ from school $C$ who knows $a$. If $c$ knows any of the $k$ students from school $B$, then we are done, since $a,c,$ and this mutual acquaintance from school $B$ form a desired trio. Thus, we may assume that $c$ knows at most $n-k$ students from school $B$, that is, the ones that $a$ doesn't already know.

But that means $c$ knows at least $(n+1) - (n-k) = k+1$ students from school $A$. Since $\max(k+1, n-k) \geq k+1 > k$, that means $c$ has a higher score than $a$, contradicting our choice of $a$.

Passengers Boarding Airplane, Part Deux

2009-10-27T02:58:00.000-07:00

2009 passengers are waiting in a line to board an airplane with 2009 seats. The seats are numbered from 1 to 2009. Each passenger has a boarding pass that has his/her seat number on it. However, these passengers are oblivious to their boarding pass and choose their seats at random, each with a uniform probability from the available empty seats.

What is the probability that everyone's actual seat number and their assigned seat number differ by at most 1? That is, no one sits more than 1 seat away from their assigned seat.

Solution

Zeke's solution in the comment is correct.

2 Variable Recursion

2009-10-23T03:55:00.000-07:00

This problem is written as an auxiliary lemma for the solution to this problem.

Suppose $f(m,n)$ is a function that is defined for non-negative integers $m,n$ where:

$f(m,n) = 0$ if $m < n$

$f(m,0) = 1 \forall m$

$\displaystyle f(m,n) = \sum_{k=1}^{n} f(k-1,k-1) f(m-k,n-k) + f(m-1,n) \forall m \geq n$

Prove that $f(m,n) = \frac{m-n+1}{m+1} \binom{m+n}{m}$

Solution

First, if $m=n$, then the recursion becomes the recursion of Catalan numbers, and the initial condition $f(0,0) = 1$ matches. So $f(n,n) = C_n = \frac{1}{n+1}\binom{2n}{n}$ is the $n$-th Catalan number.

Our recursion now becomes:

$\displaystyle f(m,n) = \sum_{k=1}^{n} C_{k-1} f(m-k,n-k) + f(m-1,n)$

Let $d = m-n$, we know that the formula holds for $d=0$. For $d>0$, we introduce $g(n,d) = f(n+d,n)$ that is defined over all non-negative $n,d$, with $g(n,0) = C_n \forall n$.

Then our recursion formula becomes:

$\displaystyle g(n,d) = \sum_{k=1}^{n} C_{k-1} g(n-k,d) + g(n,d-1)$

Due to the last term, we also define that $g(n,-1) = 0 \forall n$ to allow that recursion formula to work generally. Note that this convention does not violate the original definition of $f$.

Suppose $P(x) = C_0 + C_1x + C_2x^2 + \cdots + C_nx^n + \cdots$ be an infinite polynomial defined on a region near $x=0$ (within its converging radius). We know that $P(x)$ is the generating function for Catalan numbers, and it's known to be

$\displaystyle P(x) = \frac{1-\sqrt{1-4x}}{2x}$

Now let $Q(x,y) = \sum_{n,d \geq 0} g(n,d)x^ny^d $ also defined near zero.

Consider the coefficient of $x^n y^d $ in $P(x)Q(x,y)$. It is the sum $C_0 g(n,d) + C_1g(n-1,d) + \cdots + C_ng(0,d) = g(n+1,d) - g(n+1,d-1)$

But $\sum_{n \geq 1, d \geq 0}g(n,d)x^ny^d = Q(x,y) - (1+y+y^2 + \cdots) = Q - \frac{1}{1-y}$

Which means the coefficients of $P(x) Q(x,y)$ is identical to $\frac{1}{x}(Q - \frac{1}{1-y}}) - \frac{y}{x}(Q - \frac{1}{1-y})$

$PQ = \frac{1}{x}(Q - \frac{1}{1-y}} )- \frac{y}{x}(Q - \frac{1}{1-y})$ solving for $Q$ yields

$Q(x,y) = \frac{1}{1-y-xP(x)}$

As a sanity check, when $y =0$, all the $y$ terms vanish and $Q$ should be identical to $P$. But since $P$ is the Catalan generating function, it satisfies $P(x) = 1+xP(x)^2$, so $Q = \frac{1}{1-xP} = P$.

One possible approach here is to solve explicitly for $Q(x,y)$ and find its Taylor series to get an explicit formula for $g$ and thus $f$, but it would make you want to gouge your eyes out.

Instead, we note that $P = 1 + xP^2$, so $1-xP = 1-\frac{P-1}{P} = \frac{1}{P}$, thus

$Q=\frac{1}{1-y-xP} = \frac{1}{\frac{1}{P}-y} = \frac{P}{1-Py}$

Which means that $Q-P = yPQ$ is an identity near zero. Note that

$\displaystyle Q-P = \sum_{n \geq 0, d \geq 1}g(n,d)x^ny^d$

And that

$\displaystyle yPQ = \sum_{n \geq 0, d \geq 1}x^ny^d(g(n+1,d-11) - g(n+1,d-2))$

From there we get another identity: $g(n,d) = g(n+1,d-1) - g(n+1,d-2)$ for all $n \geq 0, d \geq 1$

In other words, $g(n,d) = g(n-1,d+1) + g(n,d-1) \forall n\geq 1, d \geq 0$

Translating back, we have $f(m,n) = f(m,n-1) + f(m-1,n)$

Suppose $s = m+n$, we can prove the desired formula by induction on $s$. First, for $m+n=1$, it must be that $m=1,n=0$, and the formula is satisfied trivially. One can also check that the formula still holds for low values of $s$. The induction step holds because:

$f(m,n-1) + f(m-1,n) = \frac{m-n+2}{m+1} \binom{m+n-1}{m} - \frac{m-n}{m} \binom{m+n-1}{m-1}$

$=\frac{n(m-n+2)}{(m+n)(m+1)} \binom{m+n}{m} + \frac{m-n}{m+n} \binom{m+n}{m} = \frac{m-n+1}{m+1} \binom{m+n}{m+1}$

Combinatorial Sum Identity

2009-10-23T01:41:00.000-07:00

For $m,n > 0$ prove that

$\displaystyle 1 + \sum_{k=1}^{m} \binom{k+n}{k} = \binom{m+n+1}{m}$

Harder version:

$\displaystyle \sum_{k=l}^{m} \binom{k+n}{k} = \binom{m+n+1}{n+1} - \binom{n+l}{n+1}$

First Solution

Note that

$\displaystyle \binom{k+n}{k} = \frac{k+n+1}{n+1}\binom{k+n}{k} - \frac{k}{n+1}\binom{k+n}{k}$

$\displaystyle = \binom{k+n+1}{n+1} - \binom{k+n}{n+1}$

So

$\displaystyle \sum_{k=l}^{m} \binom{k+n}{k} = \binom{n+m}{m} + \cdots + \binom{n+k}{k} + \cdots + \binom{n+l}{l}$

$\displaystyle = \binom{n+m+1}{n+1} - \binom{n+m}{n+1} + \binom{n+m}{n+1} - \binom{n+m-1}{n+1} + \cdots + \binom{n+l+1}{n+l} - \binom{n+l}{n+1}$

$\displaystyle = \binom{m+n+1}{m} - \binom{n+l}{n+1}$

Second Solution

For the normal version, suppose in the Cartesian lattice we walk from $(0,0)$ to $(m, n+1)$ where we can only move 1 unit to the right or to the top. There are $\binom{m+n+1}{m}$ possible paths.

Consider the last upwards motion that we make, say from $(k,n)$ to $(k,n+1)$. There is only one possible path to complete after this motion, that is, all horizontal motions. But in order to get here, we may use any possible path from $(0,0)$ to $(k,n)$. There are $\binom{k+n}{k}$ such paths. Note that $k$ can range from $0$ to $m$, so the 1 term in the LHS accounts for the case where $k=0$.

For the harder version, suppose now we limit ourselves for $k \geq l$. The LHS describes the number of paths where the last upward motion happens at or after $l$. The negative term in the RHS describes the number of paths where the last upward motion happen before $l$, because that means the path must pass through $(l-1, n+1)$.

Boys and Girls around the table

2009-10-22T14:53:00.000-07:00

$(n+1)$ boys and $n$ girls are seated around a circular table playing a game. One boy started to put a stone on the table, and they subsequently went around the table clockwise. At each child's turn, if that child is a boy, he puts a stone on the table, but if that child is a girl, she takes away one stone from the table. They're finished when everyone has had one turn. If the table ever becomes empty (except before the first boy put his stone), they all lose the game.

Prove that there is a boy such that if he starts, they can complete the round without losing.

Furthermore, prove that there is only one such boy. That is, if any other boy starts, they would lose the game.

Harder version: suppose you now have $m+n$ boys and $n$ girls, with $m$ positive. Prove that there are exactly $m$ boys who could start a non-losing game.

Solution for normal version

We prove by induction on $n$. The proof is trivial for $n=1$. Now, suppose that there is one and only one boy who could start a non-losing game in the case of $n=k-1$. We consider the case of $n=k$.

Take any boy who sits with a girl to his left, so that the girl's turn is immediately following him. Call the boy Andy and the girl Betty. Remove Andy and Betty from the table. We are now left with $k-1$ girl and $k$ boys, for which we would have exactly one boy who could start a non-losing game.

Suppose we start with that boy, then when we get to Andy, his stone would immediately be removed by Betty, and then the game proceeds exactly like it would in $n=k-1$ case. So the table would never become empty.

To prove that there is only one boy who could start a non-losing game, we only need to prove that Andy could not start a non-losing game. But it is trivial. If we start with Andy, the table would become empty right after Betty's turn. For any other boy besides Andy, the game proceeds exactly like it would in $n=k-1$ case, so there can only be one starter boy.

Solution for harder version

We fix $m$, and prove by induction on $n$. For $n=1$, it is easy to see that all the $m+1$ boys are sitting together, so the first $m$ boys could start a non-losing game.

The induction step works exactly like the normal version. We take any boy who sits immediately before a girl and remove them from the game.

Any boy who had started a non-losing game would still start a non-losing game after those two are returned to the table. The boy who was temporarily removed couldn't have been a starter boy. So there are exactly $m$ starter boys.

Circles and Coloring

2009-10-21T06:26:00.000-07:00

Several circles are drawn on a piece of paper to form several regions on the paper. We wish to color these regions such that no two regions that share a common boundary would have the same color.

(It is okay if two regions that share a common point to have the same color, but not boundary)

How many colors minimum are needed?

Solution

Two colors are sufficient.

For each circle $C$, we give a region the score of 1 if it's inside $C$ and 0 if it's outside of $C$. We go through the circles one by one and give scores accordingly, and at the end, we tally up the total scores of each region. If a region has an even score, we color it Red, and if it has an odd score, we color it Blue.

If two regions share a common boundary, that boundary must belong to a circle. One region would have to be inside that circle and another region outside. Their inside/outside-ness are identical with regard to all the other circles. Therefore, their scores differ by exactly 1, and they would have opposite color.