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


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

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


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.


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.