4
$\begingroup$

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!

Source

$\endgroup$
7
  • $\begingroup$ Hey with the info from the replies to first question, how did the third student know a prime factor ? $\endgroup$
    – AgentS
    Commented Aug 17, 2019 at 8:21
  • $\begingroup$ Obviously one of the people who doesn't see the units digit has 0 and 5 as their two digits so they can conclude that the number must be even. $\endgroup$
    – user694818
    Commented Aug 17, 2019 at 9:30
  • 1
    $\begingroup$ @MatthewDaly Not so, just needs $5$ ... $\endgroup$ Commented Aug 17, 2019 at 10:02
  • $\begingroup$ Agreed. And that has to be either the tens or ten thousands digit because otherwise two extra people would have noticed. $\endgroup$
    – user694818
    Commented Aug 17, 2019 at 10:26
  • $\begingroup$ As for the next step, if the number was ???52 or ???56, two people would know that it was divisible by 4, and if it was ????0, two people would know that it was divisible by 10 (although it couldn't be ???50 because then two people would know that it had more than two composite factors). $\endgroup$
    – user694818
    Commented Aug 17, 2019 at 14:59

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .