Competition problem — Number theory

Library / /365 of 520

Number theory Difficulty 5.6 AIME, harder Prove it

7.5. The computer's screen displays the number 1. Every second, the computer performs the following operation: if the number on the screen is divisible by $2^k$ , it adds any positive integer from 1 to $k+1$ . Prove that any power of 2 will eventually appear on the screen.

Solution

7.5. Since $1=2^{0}$ , the first operation is to add 1, thus, $2=2^{1}$ immediately appears on the screen. Assume that $2^{n}(n>1)$ never appears on the screen. Since the numbers on the screen are monotonically increasing, there must be a moment when the number on the screen is $m2^{n}$ . Since $l2^{n}-m \geqslant 2^{l}>l+1$ , this is a contradiction.

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.