MathDB
Sasha guessing X <= 100 in 7 questions

Source: All-Russian MO 2000

December 30, 2012
ceiling functionlogarithmsmodular arithmeticnumber theory unsolvednumber theory

Problem Statement

Tanya chose a natural number X≤100X\le100, and Sasha is trying to guess this number. He can select two natural numbers MM and NN less than 100100 and ask about gcd⁡(X+M,N)\gcd(X+M,N). Show that Sasha can determine Tanya's number with at most seven questions.
Back to ProblemsView on AoPS