Track / Stage 5 / 218 of 400 #818 of 2000

Problem 818

AIME late

Combinatorics Difficulty 5.5 Find the answer

Bogganov I.I.

Given an infinite supply of white, blue, and red cubes. Any \ $N\$ of them are arranged in a circle. A robot, starting at any point on the circle, moves clockwise and, until only one cube remains, repeatedly performs the following operation: it destroys the two nearest cubes in front of it and places a new cube behind it of the same color if the destroyed ones are the same, and of the third color if the destroyed ones are of different colors. We call a placement of cubes good if the color of the remaining cube at the end does not depend on the starting point of the robot. We call $\$ N \ $lucky if for any choice of $\$ N \$ cubes, all their placements are good. Find all lucky $\$ N \.

Your answer

Official solution

We will arbitrarily assign the remainders $0,1,2$ from division by 3 to colors. All operations with them will also be performed modulo 3. Then the operation performed by the robot is as follows: if cubes of colors $a$ and $b$ are destroyed, a cube of color $-a - b$ appears.

If $N=2^k$ , then after each full round, the number of cubes is halved, and their sum changes sign. Therefore, in the end, a cube of color $(-1)^k(a_1+\ldots+a_N)$ will be obtained, regardless of the starting point. Thus, powers of two are successful.

If $N=2^k+d$ , where $1 \leq d \leq 2^k-1$ , then consider an arrangement with one red cube and $N-1$ white cubes. If the robot starts before the red cube, then after $d$ moves, one blue cube and $2^k-1$ white cubes will remain. If the robot starts immediately after the red cube, then after $d$ moves, one red cube and $2^k-1$ white cubes will remain. The arguments provided for powers of two show that in these two situations, the final colors will be different, meaning that $N$ is unsuccessful.

## Answer

Powers of two.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.