Maths Olympiad Prep

Library / /2 of 7

Combinatorics Difficulty 4.8 AIME Prove it Hong Kong

In a school there are 20232023 students, numbered 11 to 20232023. The teacher met the students one by one in the order of their numbers, and gave a candy to each student except if that would mean three students whose numbers form an arithmetic sequence all got candies. In this way, the teacher would give a candy to students 11 and 22, but not student 33 (as 1,2,31, 2, 3 form an arithmetic sequence), then to students 44 and 55, but not to students 66 and 77 (as both 4,5,64, 5, 6 and 1,4,71, 4, 7 are arithmetic sequences), and so on. How many students got candies in the end?

Solution

Answer: 128128

With some initial trials, we can list the numbers of the students who get candies:
1,2,4,5,10,11,13,14,28,29,1, 2, 4, 5, 10, 11, 13, 14, 28, 29, \ldots

The base 33 representation of the numbers are
1,2,11,12,101,102,111,112,1001,1002,1, 2, 11, 12, 101, 102, 111, 112, 1001, 1002, \ldots,
and if we subtract 11 from each number, they become the following
0,1,10,11,100,101,110,111,1000,1001,0, 1, 10, 11, 100, 101, 110, 111, 1000, 1001, \ldots,
which are precisely those whose base 33 representations consist of the digits 00 and 11 only. Indeed, we can easily prove by induction that student nn gets a candy if and only if the base 33 representation of n1n-1 consists of the digits 00 and 11 only (call such a positive integer nn 'good'). This statement holds for the numbers we have listed. Now suppose nn is larger than 2929 and the statement holds for smaller nn.

* Suppose nn is good. If student nn does not get a candy, there exist students \ell and mm who both got candies (where <m<n\ell < m < n) and such that ,m,n\ell, m, n form an arithmetic sequence. Consider the numbers 1,m1,n1\ell - 1, m - 1, n - 1 (in base 33, same for below). They all consist of the digits 00 and 11 only, and 2(m1)=(1)+(n1)2(m - 1) = (\ell - 1) + (n - 1). This is impossible, since each digit on the left is 00 or 22, while at least one digit on the right is 11 (there is no carry in the addition, and there must be at least a place which gives 0+10+1 since 1n1\ell - 1 \neq n - 1). This contradiction establishes the fact that student nn gets a candy.

* Suppose nn is not 'good'. Then n1n - 1 consists of at least one digit 22. Suppose the place values of all the digits 22 are 3k1,3k2,,3kd3^{k_1}, 3^{k_2}, \dots, 3^{k_d} respectively. Then student nn cannot get a candy since students n2(3k1+3k2++3kd)n - 2 \cdot (3^{k_1} + 3^{k_2} + \dots + 3^{k_d}) and n(3k1+3k2++3kd)n - (3^{k_1} + 3^{k_2} + \dots + 3^{k_d}) both get candies. (For example, if n=74n = 74 then n1n - 1 has base 33 representation 22012201. Both students 22 and 3838 got candies since the base 33 representations of 11 and 3737 are 11 and 11011101 respectively. As 2,38,742, 38, 74 form an arithmetic sequence, student 7474 cannot get a candy.)

This completes the induction. Note that 202310=220222132023_{10} = 2202221_3. So the largest nn which is 'good' has the property that the base 33 representation of n1n - 1 is 11111111111111. The answer is thus 27=1282^7 = 128.

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.