Skip to main content
OlympiadHQ

Browse · MATH

Print

jmc

number theory senior

Problem

Zan has created this iterative rule for generating sequences of whole numbers:

1) If a number is 25 or less, double the number.

2) If a number is greater than 25, subtract 12 from it.

Let be the first number in a sequence generated by the rule above. is a "sweet number" if 16 is not a term in the sequence that starts with . How many of the whole numbers 1 through 50 are "sweet numbers"?
Solution
Consider the remainders of numbers in one of these sequences modulo 12. The first step doubles the remainder, but second step does not change it. So, if repeatedly doubling a number modulo 12 does not give , the number 16 cannot be a term in the sequence. On the other hand, if there is a term congruent to 4 mod 12 in the sequence, it must be 4, 16, or a number greater than 25. If it's 4, two steps later 16 will be in the sequence. If it's 16, then 16 is in the sequence. If it's greater than 25, then subtracting off 12 repeatedly will eventually give 16, the largest number less than 25 which is congruent to 4 modulo 12.

So, we just need to find which remainders modulo 12 will eventually give 4 when doubled modulo 12 repeatedly. We can easily see that 1, 2, 4, and 8 all give 4 modulo 12 eventually. We can also see that 3, 6, 9 and 0 will just end up at 0 (ie, multiples of 12) when doubled modulo 12, and so they will not reach 4 modulo 12. This leaves 5, 7, 10, and 11. Doubling 11 gives , , so 11 and 10 reach 4 modulo 12. Double 5 gives 10 modulo 12, and double 7 gives 2 modulo 12, so they will eventually reach 4.

Therefore, the only sweet numbers are congruent to 0, 3, 6, or 9 modulo 12, or in other words, multiples of 3. There are multiples of 3 between 1 and 50.
Final answer
16