A maths teacher writes a very large number on the blackboard and asks her pupils (of whom there are $n$ in the room) about its factors.
The first pupil says, "The number is divisible by 2."
The second says, "The number is divisible by 3."
The third says, "The number is divisible by 4."
The fourth pupil says, "The number is divisible by 5."
$...$
The $n$th pupil says, "The number is divisible by ($n+1$)."
The teacher says, "You were all right except for two of you, who spoke consecutively."
Given this information, what can you say about:
- the value of $n$
- which two pupils were wrong?
If you want to list all possibilities, then we can limit $n$ to be less than $100$ to make the problem finite. However, there is a general answer for which values are possible, which works for arbitrarily large $n$.
Don't worry about what the number on the blackboard is! You could find its smallest possible value in each case using the Chinese Remainder Theorem, but that would be boring and tedious.
I'll upvote any answer which is correct and relies only on pencil, paper, and logic without resorting to computer power. The green tick will go to whichever answer gives the correct solution in the most simple and elegant way.
NB: this is a maths puzzle and not a maths problem. There's a nice 'aha!' which narrows down the possibilities considerably, and the nature of the final solution is quite surprising.
Answer
If $x$ has at least two distinct prime factors, that is $x = p^n * q^m * r$, with $p, q$ primes, $n, m \ge 1$, and $r$ not divisible by $p$ or $q$, then $(p^n * r) | z$ and $(q^m * r)|z$ implies $(p^n * q^m * r = x)|z$.
Therefore, if $x$ is a wrong answer, and all answers $< x-1$ were correct answers, $x$ cannot have two distinct prime factors; $x$ must be either a prime number or a power of a prime number. Further, if $x$ is a wrong answer, then $2x$ is also a wrong answer.
Since exactly two answers $\le n+1$ were incorrect, and the two incorrect answers were consecutive, the two incorrect numbers are $x$ and $x+1$ with $x \ge 2$, and $n \le 2x-2$, and both $x$ and $x+1$ are either primes or powers of primes.
The only two consecutive primes are $2$ and $3$; other than this at least one of $x$ and $x+1$ is a non-trivial power of a prime. So we have one number $p^k$, where $p$ is a prime and $k \ge 2$, and $p^k \pm 1$ which is a prime or a power of a prime.
Assume $p \ge 3$, which implies $p$ is odd: $p^k \pm 1$ is even, therefore it is not a prime but must be power of $2$. Therefore, one of the incorrect numbers must be a power of two: The incorrect answers are $2^k$ and $2^k \pm 1$. If $2^k \pm 1$ is a prime, then it is either a Mersenne prime or a Fermat prime; the only known Fermat primes are $3, 5, 17, 257, 65537 = 2^1 + 1, 2^2 + 1, 2^4 + 1$ and $2^{16} + 1$; the smallest known Mersenne primes are $2^k - 1$ for $k = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 1257787, 1398269, 2976221, 3021377, 6972593, 13466917, 20996011, 24036583, 25964951, 30402457, 32582657$.
If we assume that the number of students is less than the world population, the possibilities are $(4,5)$, $(16,17)$, $(256,257)$, $(65536,65537)$, $(3,4)$, $(7,8)$, $(31,32)$, $(127,128)$, $(8191,8192)$, $(131071,131072)$, $(524287, 524288)$, $(2147483647,2147483648)$, where the other number is a prime.
If the other number is a prime power, then the only pair is $(8,9)$ (Mihăilescu's theorem, better known as Catalan's conjecture but proven in 2002).
Since $3$ is also a Fermat prime, in total the possibilities are $(8,9)$, all numbers $(2^k, 2^k + 1)$ where $2^k + 1$ is a Fermat prime, and $(2^k, 2^k - 1)$ where $2^k - 1$ is a Mersenne prime.
So the first possible pairs of wrong answers and the only that are possible on earth with actual humans are $(2,3)$, $(3,4)$, $(4,5)$, $(7,8)$, $(8,9)$, $(16,17)$, $(31,32)$, $(127,128)$, $(256,257)$, $(8191,8192)$, $(65536,65537)$, $(131071,131072)$, $(524287,524288)$, $(2147483647,2147483648)$.
The possible values for $n+1$ are $[3 \ldots 15], [17 \ldots 61], [128 \ldots 253], [257 \ldots 511]$ etc. and the possible values for $n$ are $[2 \ldots 14], [16 \ldots 60], [127 \ldots 252], [256 \ldots 510]$. So we don't have a class of $15$ students, or $61$ to $126$ students, or $253$ to $255$ students, or $511$ to $8190$ students.
We could probably use the fact that the number actually fit on the board to exclude some large numbers.
No comments:
Post a Comment