Maths Olympiad Prep

Library / /10 of 24

Number theory Difficulty 4.9 AIME Prove it United States

Problem:
Let xx be an integer greater than 22. Prove that the binary representation of x21x^{2}-1 has at least three consecutive identical digits (000000 or 111111).

Solution

Solution:
We consider three cases:

- xx is odd. Then x+1x+1 and x1x-1 are consecutive even integers, and thus one of them must be divisible by 44, the other only by 22. So x21=(x+1)(x1)x^{2}-1=(x+1)(x-1) is divisible by 88; since x3x \geq 3, x21x^{2}-1 has four or more digits, the last three of which are 00's.

- xx is even but x2\frac{x}{2} is odd. By the same reasoning, (x2)21=8k\left(\frac{x}{2}\right)^{2}-1=8k for some integer kk, so
x21=4(x2)21=4(8k+1)1=32k+3 x^{2}-1=4\left(\frac{x}{2}\right)^{2}-1=4(8k+1)-1=32k+3
Since x6x \geq 6, this number has six or more digits, the last five of which are 0001100011. Thus we also get three consecutive zeros in this case.

- xx and x2\frac{x}{2} are both even, that is, xx is divisible by 44. Then x2x^{2} is divisible by 1616. Since x4x \geq 4, x21x^{2}-1 has at least four digits, the last four of which are 11'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.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.