Alice thinks about a natural number in her mind. Bob tries to find that number by asking him the following 10 questions: Is it divisible by 1? Is it divisible by 2? Is it divisible by 3? ... Is it divisible by 9? Is it divisible by 10? Alice's answer to all questions except one was "yes". When she answers "no", she adds that "the greatest common factor of the number I have in mind and the divisor in the question you asked is 1”. According to this information, to which question did Alice answer "no"?
Problem
Source: Azerbaijan NMO 2024. Junior P1
Tags: number theory, AZE JUNIOR NATIONAL MO
K124659
08.07.2024 17:29
I'm not in HS but whatever
If she says "no" to only one of these questions and we gather that Alice's number and a certain number 1-10 are relatively prime. Because Alice's number is a multiple of every other number 1-10 we know that any number 1-5 cannot be the number relatively prime to alice's number considering it would then not be a multiple of the number double of it. Alice only answers no once, and so we know the remaining numbers are 6, 7, 8, 9, and 10. These numbers have no multiples within the range of 1-10, but almost all have factors within the range of numbers that Alice cannot have said no to being divisible to Alice's number.
In short, using logic, we know the only number that does not share any factors besides 1 with all of the other numbers 1-10 and does not have a multiple within the 1-10 range is 7. The answer is 7.
QueenArwen
23.07.2024 19:14
Since she only answered 'No' to one number, it cannot be 1, 2, 3, 4, or 5 as if it was one of these she would have had to answer no again to their multiples. Since the number is a multiple of 1, 2, 3, 4 and 5, it must also be a multiple of 6, 8 and 10 as these are 3x2, 4x2 and 5x2 respectively. Hence the number is either 9 or 7. However it cannot be 9 as both 9 and the number Alice thought of are both multiples of 3 so their GCD will be at least 3. Thus Alice answered no to 7
miyukina
23.07.2024 20:35
If it is only one, then it must be for the second half answers, 6 ~ 10 However, 6 = 2 × 3 , both had yesses previously, while 10 = 2 × 5 with the same concept as 6 So the no may only be 7, 8 or 9 From the additional info provided by Alice, this no must be for a prime, since the gcf(8, 4) = 4 > 1 and gcf(9, 6 or 3) = 3 > 1 (we can also use 8 and 2, 6 or 10) Answer = 7