Pages

Monday, December 19, 2011

Having fun with infinite series

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

Solution

Problem 1

This is a standard textbook proof of the divergence of harmonic series, but the point here is to prepare the reader for the subsequent proofs $$\frac{1}{3} + \frac{1}{4} > \frac{1}{4} + \frac{1}{4} = \frac{1}{2}$$ $$\frac{1}{5} + \dots + \frac{1}{8} > \frac{1}{8} + \dots + \frac{1}{8} = \frac{1}{2}$$ and so on. So the original series clearly diverges to infinity. The main crux of the proof here is this assertion: $$\frac{1}{2^n+1} + \dots + \frac{1}{2^{n+1}} > \frac{1}{2^{n+1}} + \dots + \frac{1}{2^{n+1}} = \frac{1}{2}$$ for each $n$.

Problem 2

Similar to the proof above, for each $n$ we have: $$a_{2^n+1} + \dots + a_{2^{n+1}} < 4^{n+1}$$ So by AM-HM we have: $$\frac{1}{a_{2^n+1}} + \dots + \frac{1}{a_{2^{n+1}}} > \frac{4^n}{a_{2^n+1} + \dots + a_{2^{n+1}}} > \frac{1}{4}$$ So the original series is greater than $1/4 + 1/4 + \dots = \infty$

Problem 3

Similar to the proof above, for each $n$ we have: $$a_{2^n+1} + \dots + a_{2^{n+1}} < 4^{n+1} \log (2^n) = n . 4^{n+1}.\log 2$$ So by AM-HM we have: $$\frac{1}{a_{2^n+1}} + \dots + \frac{1}{a_{2^{n+1}}} > \frac{4^n}{a_{2^n+1} + \dots + a_{2^{n+1}}} > \frac{1}{4 \log 2 n}$$ So the original series is greater than $\frac{1}{4 \log2} (1 + \frac{1}{2} + \frac{1}{3} + \dots)$ which is also divergent.

Monday, October 10, 2011

Fibonacci Series: Introduction

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.

Wednesday, August 17, 2011

Are you smarter than a 6th grader?

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 dollar and each orange costs 1.01 dollar. Johnny has 101 dollars. How many ways are there for him to buy fruits, including possibly not buying anything? Sarah has 99 dollars. 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 dollars. Clearly he can buy 101 apples or 100 oranges, but these are the only two cases.

Case 2: If Johnny spends less than 101 dollars. 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 dollar x 101 + 1.01 dollar x 100 = 202 dollars. So if Johnny spends less than 101 dollars, the total amount goods left in the store is greater than 101 dollars. We can’t reverse this situation, that is, Johnny can never spend more than 101 dollars so that the total amount left in the store is less than 101 dollars.

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

Sunday, August 14, 2011

General Recursion

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

Saturday, July 23, 2011

a,b,c fraction integer

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.

Thursday, July 21, 2011

Sequence modulo 2011

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

Wednesday, July 13, 2011

Colored chessboard

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.

Sunday, June 26, 2011

liars and honest villagers

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$

Tuesday, June 21, 2011

Inequality

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.

Sunday, June 12, 2011

Supersum

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.

Wednesday, May 18, 2011

Circular Locker Problem

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

Monday, May 16, 2011

Magician and cards

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

Thursday, May 5, 2011

Function from N to N

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}^{*} $

Wednesday, April 27, 2011

Floor And Ceiling

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

Thursday, April 21, 2011

Shuffling Card

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.

Friday, April 8, 2011

Functional Equation

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

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

Wednesday, April 6, 2011

Function Composition

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

Tuesday, April 5, 2011

Symmetric Function in 3 Variables

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$

Wednesday, March 23, 2011

Sequence of natural numbers

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

Tuesday, March 8, 2011

Technology Review March/April 2011 Problem 3


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

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

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.

Tuesday, March 1, 2011

Coins in equilateral lattice

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

Thursday, February 3, 2011

Find angle C

From AMC12 1999:

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

Find $\angle C$