17
$\begingroup$

This question already has an answer here:

A teacher wrote a large number on the board and asked the students to tell about the divisors of the number one by one.

The 1st student said, "The number is divisible by 2." The 2nd student said, "The number is divisible by 3." The 3rd student said, "The number is divisible by 4." . . . (and so on) The 30th student said, "The number is divisible by 31.

The teacher then commented that exactly two students, who spoke consecutively, spoke wrongly.

Which two students spoke wrongly?

Taken from here

$\endgroup$

marked as duplicate by Rand al'Thor, ffao, boboquack, Peregrine Rook, Kate Gregory Feb 19 '18 at 22:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I don't know why, but I love your puzzles. $\endgroup$ – NL628 Feb 19 '18 at 5:21
  • 2
    $\begingroup$ Answer already on that link. $\endgroup$ – Niranj Patel Feb 19 '18 at 5:27
  • $\begingroup$ Wowowowow Nice one @NiranjPatel Wasn't wasted though, good practice XD $\endgroup$ – NL628 Feb 19 '18 at 5:29
  • 3
    $\begingroup$ The title says "Can you find the two numbers?" while the question ends with "Which two students spoke wrongly?" :P And first student starts with 2. So the answer would differ. Can you change the title or the question :P $\endgroup$ – Mehravish Temkar Feb 19 '18 at 9:48
19
$\begingroup$

Okay so the first step is to realize that:

The secret numbers are consecutive so one is even and one is odd.

Also,

It can't be any two consecutive numbers if it is not divisible by 2 and 3. For example, it also wouldn't be divisible by 6 or 8 or 9, etc, which would violate the condition.

Hence,

These two numbers cannot have multiples that are less than 31. Eliminating 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, and 15.

Also, we see that

It can't be like the number 21 because if it's divisible by 3 and 7, it will be divisible by 21.

Eliminating all of those, we get that the answer is

Students number 16 & 17.

$\endgroup$
  • $\begingroup$ Congrats!!!!!!! $\endgroup$ – Lifesaving Linen Feb 19 '18 at 17:54
13
$\begingroup$

Since the actual question is: Can you find the two numbers? Which two students spoke wrongly?, technically no one has answered it! The right answer is:

Yes, the 15th and 16th students.

Solution:

Since no other student was wrong, the first inference is that these two consecutive divisors cannot have any multiples <=30.
2 being the smallest possible multiplier, that means both must be greater than 15. Clearly any two consecutive numbers have to be an even-odd pair. If that odd number had any (odd) factors, the large number would need to be indivisible by at least one of those factors. But that would have caused an earlier student to have been called wrong. So this must be a prime number. Similarly, the even number in the pair cannot have any odd factors either, so it can only be a power of 2.
The only available primes in the range are 17, 19, 23 and 29. Of the numbers adjacent to these primes only 16 is a power of 2. All the remaining numbers 18,20,22,24,28,30 have at least one odd factor.
So the consecutive numbers can only be (16,17) which were called out by the 15th and 16th students.

$\endgroup$
6
$\begingroup$

The numbers that don't divide the one on the board can't be less than 16, otherwise also their multiples won't divide it. Similarly, neither can be a non-prime with multiple distinct prime factors, as that would mean there's a smaller divisor not dividing the number on the board. Since one of the numbers must be even, it's a power of 2.

- If $2^k-1=p^r (k>3)$:

$2^k=p^r+1$ (the right hand side must be divisible by 4 - only possible if $r$ is odd)

$2^k=(p+1)(p^{r-1}-p^{r-2}+...-...-p+1)$ (the second factor is odd, so $p+1=2^k, r=1$)

However, there's no solution (Mersenne prime less than a valid power of 2) from 16 to 31.

- If $2^k+1=p^r (k>3)$:

$2^k=p^r-1$

$2^k=(p-1)(p^{r-1}+p^{r-2}+...+p+1)$ (either $r=1$ or $r$ is even)

If $r$ is even, both $p^{r/2}-1$ and $p^{r/2}+1$ are powers of 2.

However, there's no solution from 16 to 31 in this case.

In short, one must be a power of 2 and the other a prime. 16 and 17 are the only duo satisfying the conditions, which corresponds to Student 15 and 16.

$\endgroup$
  • 1
    $\begingroup$ It's NOT a duplicate, because I used elimination a lot less than others. Is it because my solution/wording happened to be similar to the one on the link? $\endgroup$ – Nautilus Feb 19 '18 at 10:59
  • 5
    $\begingroup$ I'd like to not be treated like a cheater right away, that's all. $\endgroup$ – Nautilus Feb 19 '18 at 11:06
  • 1
    $\begingroup$ Wait yes, I think this is a perfectly good solution (possibly even better than mine because there is less elimination). And obviously this solution would work better for higher values of N. +1 for the amazing solution. $\endgroup$ – NL628 Feb 19 '18 at 17:57

Not the answer you're looking for? Browse other questions tagged or ask your own question.