Maths Olympiad Prep

Library / /4 of 8

Number theory Difficulty 4.4 AIME Find the answer Italy

A goblin chooses two odd numbers x,yx, y such that 0<y<x<20120 < y < x < 2012, computes x2y2x^{2} - y^{2} and writes the result on a sheet of paper. Every morning (starting from the following day) he wakes up, reads the number written on the sheet and, if this number is even, replaces it with its half and goes to play a prank on someone.
On the day he reads an odd number for the first time, he disappears, returning to the world of fairies.
What is the maximum number of pranks the goblin can play?

Pick one

Solution

The answer is (B)\mathbf{(B)}. x2y2x^{2} - y^{2} can be factored as (x+y)(xy)(x + y)(x - y). It is not possible for x+yx + y and xyx - y to both be multiples of 44, because otherwise (x+y)+(xy)=2x(x + y) + (x - y) = 2x would also be, but this is twice an odd number. We have that max{x+y,xy}2011+2011<212\max\{x + y, x - y\} \leq 2011 + 2011 < 2^{12}, therefore the maximum power of 22 obtainable in the factorization of x2y2x^{2} - y^{2} is 2122^{12}; this is achieved for example by setting x+y=211=2048x + y = 2^{11} = 2048 (the next power is too large) and xy=2x - y = 2, that is x=1025x = 1025 and y=1023y = 1023.

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 translated into English from it; metadata (topic, difficulty) added by this project.