Maths Olympiad Prep

Library / /293 of 520

Combinatorics Difficulty 5.3 AIME, harder Find the answer

4. Let the sequence {an}\left\{a_{n}\right\} satisfy a1=0,a2=1a_{1}=0, a_{2}=1, and for all n3,ann \geqslant 3, a_{n} is the smallest positive integer greater than an1a_{n-1} such that there is no subsequence of a1,a2,,ana_{1}, a_{2}, \cdots, a_{n} that forms an arithmetic sequence. Find a2014a_{2014}.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

4. First, prove a lemma using mathematical induction.

Lemma A non-negative integer appears in the sequence if and only if its ternary expansion contains only 0 and 1.
Proof It is obvious that the proposition holds for 0.
Assume the proposition holds for all non-negative integers less than N N , and consider N N .

If the ternary expansion of N N contains the digit 2, replace all occurrences of 2 with 0 to get the number N0 N_{0} ; replace all occurrences of 2 with 1 to get the number N1 N_{1} . Thus, the ternary expansions of N0 N_{0} and N1 N_{1} do not contain the digit 2.
By the induction hypothesis, the numbers N0 N_{0} and N1 N_{1} are in the sequence.
Since N0 N_{0} , N1 N_{1} , and N N form an arithmetic sequence, N N does not appear in the sequence. If the ternary expansion of N N does not contain the digit 2, then we need to prove that N N must appear in the sequence. If not, then there exist terms N0 N_{0} and N1 N_{1} in the sequence such that N0 N_{0} , N1 N_{1} , and N N form an arithmetic sequence. Let the common difference be d d , and 3kd 3^{k} \| d . Then the ternary expansions of these three numbers have the same lowest k1 k-1 digits, and the k k -th digit is different for each pair, so one of the numbers must have a 2 in the k k -th digit, which contradicts the assumption.
Returning to the original problem.
We only need to find the 2014th non-negative integer whose ternary expansion does not contain the digit 2.

Notice that under this restriction, the ternary carry-over method is equivalent to binary, so we just need to write 2013 (note a1=0 a_{1}=0 ) in binary (11111011101)2(11111011101)_{2} and then convert it to ternary a2014=88327 a_{2014}=88327 .

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.