Maths Olympiad Prep

Library / /27 of 37

Number theory Difficulty 5.9 AIME, harder Find the answer Italy

Problem:

A goblin lives in the world of fairies. One day it chooses 12 pairs of positive numbers: those of the first pair are odd, those of the second give remainder 1 when divided by 3, those of the third give remainder 1 when divided by 4, and so on up to the twelfth. Then it computes the difference of the squares of the numbers of each pair and writes on a blackboard the product of all the differences obtained.

Starting from the next morning, it divides by 12 the number on the blackboard and, if the result is an integer, it writes this result in place of the number that was on the blackboard; if it is not an integer, it erases everything and moves to the human world to play pranks. For how many days (excluding the initial day on which the goblin chooses the numbers) are we certain that we will have no problems in our world?

Pick one

Solution

Solution:

The answer is (B). The difference of the squares of two numbers that give the same remainder when divided by kk is a multiple of kk: indeed if the two numbers are a=nk+ra = n k + r and b=mk+rb = m k + r,
a2b2=(ab)(a+b)=(nm)k(nk+mk+2r) a^2 - b^2 = (a - b)(a + b) = (n - m) k (n k + m k + 2 r)
(in our case we have r=1r = 1 for all kk from 2 to 13).

As a consequence, the product written by the goblin on the blackboard is certainly divisible by 13!=21035527111313! = 2^{10} \cdot 3^{5} \cdot 5^{2} \cdot 7 \cdot 11 \cdot 13, which is a multiple of 12512^{5}; therefore the goblin will certainly be able to divide by 12 for at least 5 days in a row always finding an integer result. But if the goblin were to choose for example the pairs (2k+1,k+1)(2k+1, k+1) for k=4,7,10,13k = 4, 7, 10, 13 and the pairs (k+1,1)(k+1, 1) for the remaining kk's, the differences of the squares (respectively 3k2+2k3k^2 + 2k and k2+2k=k(k+2)k^2 + 2k = k(k+2)) would contain in all exactly 5 factors of 3, therefore their product would turn out to be divisible by 12 no more than 5 times. But then in that case on the sixth day the division would produce a non-integer number; therefore we can count on 5 days, but no more.

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.