4. Let the sequence satisfy , and for all is the smallest positive integer greater than such that there is no subsequence of that forms an arithmetic sequence. Find .
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 , and consider .
If the ternary expansion of contains the digit 2, replace all occurrences of 2 with 0 to get the number ; replace all occurrences of 2 with 1 to get the number . Thus, the ternary expansions of and do not contain the digit 2.
By the induction hypothesis, the numbers and are in the sequence.
Since , , and form an arithmetic sequence, does not appear in the sequence. If the ternary expansion of does not contain the digit 2, then we need to prove that must appear in the sequence. If not, then there exist terms and in the sequence such that , , and form an arithmetic sequence. Let the common difference be , and . Then the ternary expansions of these three numbers have the same lowest digits, and the -th digit is different for each pair, so one of the numbers must have a 2 in the -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 ) in binary and then convert it to ternary .