Maths Olympiad Prep

Library / /73 of 105

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:
Find all the ways which one can assign an integer to each vertex of a 100100-gon subject to the following condition: among any three consecutive numbers written down, one of the numbers is the sum of the other two.

Solution

Solution:
The answer is that all the numbers must be zero. (Clearly, this works.)

We now prove this is the only solution. Call the numbers x1,x2,,x100x_{1}, x_{2}, \ldots, x_{100}. Then the sum x1+x2+x3x_{1}+x_{2}+x_{3} must be even, since it is either 2x12x_{1}, 2x22x_{2}, or 2x32x_{3}. Similarly, x2+x3+x4x_{2}+x_{3}+x_{4} must be even.

In this way, x1x_{1} and x4x_{4} have the same parity. By the same reasoning, x4x_{4} and x7x_{7} have the same parity, and so on—the numbers xkx_{k} and xk+3x_{k+3} have the same parity. Since 33 doesn't divide 100100, that means all the numbers have the same parity. Clearly then all the numbers are even (rather than all odd).

We may now employ infinite descent: if (x1/2,,x100/2)(x_{1}/2, \ldots, x_{100}/2) is a working assignment, then so is (x1/2,x2/2,,x100/2)(x_{1}/2, x_{2}/2, \ldots, x_{100}/2), and then so is (x1/4,x2/4,,x100/4)(x_{1}/4, x_{2}/4, \ldots, x_{100}/4). Such a process cannot go on indefinitely unless xk=0x_{k}=0 for all kk, completing the proof.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.