I was preparing for a competition, and I encountered the following problem.
In a classroom, the teacher said to five students, Alan, Bob, Carl, Dick and Eason, ‘I have
written down a five-digit number $N$ which is made up of five different digits. I will let Alan see
the ten thousands and thousands digits of $N$, let Bob see the thousands and hundreds digits, let
Carl see the hundreds and tens digits, let Dick see the tens and unit digits and let Eason see the
unit and ten thousands digits.’ The teacher then let each student know two digits of $N$ as said,
and then everybody sat in a circle and started the following conversation.‘Raise your hands if you know a prime factor of $N$,’ said the teacher, and then two
students raised their hands.‘Raise your hands if you know a prime factor of $N$,’ asked the teacher again, and this time
three students raised their hands.‘Raise your hands if you know a composite factor of $N$,’ the teacher continued, and then
two students raised their hands.‘Raise your hands if you know two composite factors of $N$,’ said the teacher, but no
student raised their hands.Then the teacher asked, ‘who knows the value of $N$?’
One student said, ‘I know. N is a multiple of $59$.’
Assuming all students to be clever (which means that deductions can be made whenever
sufficient information is given), find $N$.
I knew that $N$ is divisible by $2$ or $5$, by the first question asked by the teacher.
I knew that $N$ is divisible by $2$, and the ten thousands digit or the tens digit is $5$ by the second question asked by the teacher. (Think the reason by yourself. Actually I asked for help for this deduction.)
Then I am stuck.
Can someone help me? Any help is appreciated!
Best Answer
Indeed the answer I believe is 50268 as @Hw Chu says. The reason is as follows. Note that having 5 in the tens place doesn't give the students enough information to actually deduce the actual number (and one must know all the numbers to say with certainty it is divisible by 59). So after the teacher asks if anyone knows a prime factor and 3 people raise their hands, we have the following configuration that is known to all:
5_ _ _ [even]
Now the teacher asks if anyone knows a composite factor. The only two people that can answer and the ones that do are Dick and Carl. It is pretty clear why this is. Eason has only access to the last digit (which is not enough to answer the question, Bob has access to the thousands place and hundreds which is not enough and for similar reasons Alice cannot answer as well). Now, this means that Carl, with his knowledge of the hundreds and tens place and knowing that the last digit is even, is able to deduce with certainty that the number is divisible by 4.
So the possibilities of the last digit are as follows: 0, 2, 4, 6, 8. Now Carl must be able to reduce the possibilities with his knowledge so that no matter what the number is, the last two digit as a number itself is divisible by 4. Hence, he must be able to reduce the 5 to 3 choices. This is obvious as 4 is not enough (if this isn't clear, it will be clear in a second). Now to do so, Carl must see 2 even numbers. So let us for example say he sees 4, 6. Then in particular, he leaves 0 and 2 as possible choices for the last number. But if _0 is divisible by 4, then _2 is not. So this cannot be the case. In fact, the 3 possibilities he leaves as must be an arithmetic progression differing by 4. Hence, it must be 0, 4, 8. That is, he sees 2, 6. Now this doesn't let us know in what particular order he sees them.
But now Bob knows Carl sees {2, 6} as Bob can deduce this himself from seeing Carl raise his hand. So Bob must be able to deduce exactly what the number is from the information remaining. Carl knows the order in which the numbers appear {2, 6} but Bob knows everything Carl knows because he knows the numbers Carl sees AND knows the order by seeing the hundreds place. So let's think about how Bob can deduce the final number. He can see that the last digit must be 0, 4, or 8. But he also knows Carl cannot deduce the number is divisible by 8. Ah! But Eason also didn't raise his hand for 2 composite numbers so the last digit CANNOT be 0. So we can deduce that Bob can deduce the last 3 digits are from the following: 624, 628, 264, 268. However, since he knows the exact number, i.e. knows exactly what the last 3 numbers are, he must also see 2 even numbers to limit the choice to one possibility. But to us, he limits it to the following: 50624, 50628, 50264, 50268. Only one of these is divisible by 59, which is 50268.