In a school there are students, numbered to . 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 and , but not student (as form an arithmetic sequence), then to students and , but not to students and (as both and are arithmetic sequences), and so on. How many students got candies in the end?
Solution
Answer:
With some initial trials, we can list the numbers of the students who get candies:
The base representation of the numbers are
,
and if we subtract from each number, they become the following
,
which are precisely those whose base representations consist of the digits and only. Indeed, we can easily prove by induction that student gets a candy if and only if the base representation of consists of the digits and only (call such a positive integer 'good'). This statement holds for the numbers we have listed. Now suppose is larger than and the statement holds for smaller .
* Suppose is good. If student does not get a candy, there exist students and who both got candies (where ) and such that form an arithmetic sequence. Consider the numbers (in base , same for below). They all consist of the digits and only, and . This is impossible, since each digit on the left is or , while at least one digit on the right is (there is no carry in the addition, and there must be at least a place which gives since ). This contradiction establishes the fact that student gets a candy.
* Suppose is not 'good'. Then consists of at least one digit . Suppose the place values of all the digits are respectively. Then student cannot get a candy since students and both get candies. (For example, if then has base representation . Both students and got candies since the base representations of and are and respectively. As form an arithmetic sequence, student cannot get a candy.)
This completes the induction. Note that . So the largest which is 'good' has the property that the base representation of is . The answer is thus .