Number guessing

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.

(This is a contest problem)


The answer is 50268.

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Nick Kent
Feb 2, 2020

After the digits were shown only two students could know a prime factor right away: Dick and Eason. The reason is that no one besides them knows the value of the last digit, they cannot discard the possibility of value of the last digit being some i i or i + 1 i+1 (since they saw just two digits, there are eight "left" and there will always be an "adjacent" pair).

Dick and Eason were able to know a prime factor because they were shown the last digit, d 0 {d}_{0} . For them N equals 10 x + d 0 10x + {d}_{0} , where x was basically unknown for them. So, to able to find a prime factor they had to find a common divisor between 10x and d 0 {d}_{0} . But since they didn't know x, the only thing left for them was a common divisor between 10 and d 0 {d}_{0} . Number 10 has two prime divisors: 2 and 5, which means d 0 {d}_{0} (and N N too) is divisible by 2 or 5.

Since we are able to reach that conclusion, all other students were too.

After the teacher repeated the question, another student appeared, apart from Dick and Eason. That student couldn't identify any other prime factor apart Dick and Eason's - a lack information about even a single digit denies any possibility to prove a prime factor, apart from 2 and 5. So the student somehow managed to decide on one of the possible divisors: 2 and 5. Since they don't know the last digit, the only possibility too limit its possible values was to simply observe them in their digits. If they've decided on 5 as prime factor, they would need to limit d 0 {d}_{0} to 0 or 5 and discard 2, 4, 6 and 8. That's too many, since they were shown only 2 digits. That means d 0 {d}_{0} was limited to even values and 5 was discarded. So, that student was shown 5 as one of their digits. But since only one student showed up, that would mean that they "shared" the digit with either Dick or Eason. Thus, there are two possible pictures: Carl shared 5 with Dick in tens digits, or Alan shared 5 with Eason in ten thousands.

Let's consider the first possibility: Carl was the third student. That would mean that every student then knew d 1 {d}_{1} was 5 and d 0 {d}_{0} was even (0, 2, 4, 6 or 8).

Everybody identified 2 as a prime factor, but only two were able to find a composite factor. Since nobody yet knows about all the digits, student were only able to add 5 or another 2 as prime factors. So, there are, again, two possibilities: the composite factor is 4 or 10. But it couldn't be 10 because that would mean N N ended with 50 and Dick could name two composite factors in following question: 10 and 25. So the identified factor was 4, which means d 0 {d}_{0} is either 2 or 6 (since divisibility by 4 is determined by two last digits and d 1 {d}_{1} is 5). The student who identified the factor would be Dick and Eason again

After nobody answered the following question about multiple composite factors, all students would know that 5 as a divisor wasn't a possibility, so the factor identified by Dick and Eason would 4. That would also mean nobody was sure if N N was divisible by 8, since odd primes were out of question. That would student with no information about the first 3 digits. Even student like Alan and Bob would still have a "digit" missing, so nobody would be able to identify the number. We've come to contradiction.

That means it was Alan who was the third student to identify 2 as prime factor. That means that after the second question every student knew that the first digit was 5.

Again there were two possible composite factors: 4 and 10. If the identified factor was 10, then d 0 {d}_{0} = 0 and Dick and Eason were the ones to identify it. But then again that would leave with three unknown digits in the "middle", so the identified factor was 4.

As was mentioned before, divisibility by 4 is determined by last two digits, so obviously one of the student who identified the factor was Dick. The other student somehow managed to get information about those two digits. No student had information about d 1 {d}_{1} apart from Dick and Carl, so Carl was the other student. If d 1 {d}_{1} is odd, Carl would have to limit d 0 {d}_{0} to 2 and 6, meaning to discard three even values which is not possible considering one of his digits is odd, so d 1 {d}_{1} is even. That means Carl limited d 0 {d}_{0} to 4, 8 and 0 (still possibility from their POV) discarding 2 and 6 which are in fact two even numbers. Thus, all students know Carl has 2 and 6 as his digits and d 0 {d}_{0} is 4 or 8 (0 was discarded because Eason didn't raise the hand).

After the following question it was determined that N N is not divisible by 8. That means N N cannot end with 264 or 624 since these number are divisible. So, student knew that d 0 {d}_{0} couldn't be 4, then 8 was left. That means Bob knowing first and last digits, as all other students, also knew digits d 3 {d}_{3} and d 2 {d}_{2} . Digit d 2 {d}_{2} was either 2 or 6 and Bob could easily determine d 1 {d}_{1} , since everyone concluded Carl had digits 2 and 6 as his digits. So Bob was able to find N N . Other weren't able to since they didn't have any information about d 3 {d}_{3} , apart from Alan who in turn wasn't able to place 2 and 6 into Carl's digits.

All that is left is to determine N N ourselves. We know that:

  • first digit is 5

  • last digit is 8

  • ( d 2 {d}_{2} = 2 and d 1 {d}_{1} = 6) or ( d 2 {d}_{2} = 6 and d 1 {d}_{1} = 2)

  • N N is divisible by 59

After looking at all possible variants we conclude that the only valid value for N N is 50268 \boxed{50268}

P.S.: Sorry for the walltext

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...