Problem:
Let be an integer greater than . Prove that the binary representation of has at least three consecutive identical digits ( or ).
Solution
Solution:
We consider three cases:
- is odd. Then and are consecutive even integers, and thus one of them must be divisible by , the other only by . So is divisible by ; since , has four or more digits, the last three of which are 's.
- is even but is odd. By the same reasoning, for some integer , so
Since , this number has six or more digits, the last five of which are . Thus we also get three consecutive zeros in this case.
- and are both even, that is, is divisible by . Then is divisible by . Since , has at least four digits, the last four of which are 's.
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.