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.

## Saturday, July 23, 2011

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

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

Labels:
induction,
inverse modulo,
modulo,
Number Theory,
sequence

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

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.

Labels:
color,
colored,
coloring,
Combinatorics

Subscribe to:
Posts (Atom)