Teacher, teacher on the wall, Who's the dumbest of them all?

Question

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 1

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.

Answer 2

The consecutive numbers need both be powers of primes.

Why? First consider this:

If ($a\mid x$) and ($b\mid x$) and ($a$ and $b$ are coprime) then ($ab\mid x$)

I'm not sure if this a well known Lemma but I think it is so I don't need to prove it.

Now assume one of the consecutive numbers (call it $x$) is not a power of a prime. you can then always write $x=pq$ where $p$ and $q$ are coprime meaning that according to my Lemma that $x$ also divides the number, CONTRADICTION.

Knowing that one of the numbers is divisible by 2 we now know that that number is actually always of the form $2^x$.

And because of Catalan's conjecture we know that the other number is $3^2$ or a prime number.

This answers which two pupils were wrong. What's left to determine is what this means for $n$. Unfortunately I don't know this (yet)

Also nice to know that if these consecutive numbers are $x$ and $x+1$ then the number on the board is divisible by $LCM(1,2,...,x-2,x-1)$

Answer 3

One of the two pupils that are wrong could be a prime. The other one cannot be prime unless $n<3$, it has to be an even number. So it has to have more occurrences of at least one prime factor than every number smaller than it. This requires it to be the highest number of the form $2^x$ that you have in the sequence.

As an example, consider the students saying: 2, 3, 4, 5, 6, 7. In this case, it has to be 4,5 that are wrong, every other combo makes other students wrong as well.

This also means there are $n$s that are impossible - like 15 students (15,16 -> 15 is not prime). 16 students works again, 17 being prime. Likewise, between 63 and 127 there's a huge gap, because 64 has no adjacent prime.

On the other hand, some instances of $n$ have two possibilities.

2,3,4,5,6,7,8,9

Here it could be 7,8 that are wrong, or 8,9. Why 8,9, there's no prime in it? Because it has two numbers with more occurrences at least one prime factor than every number smaller than it. ($3\times 3$ and $2\times 2\times 2$). Such edge cases should be really few.

EDIT: To generalize, you need any two adjacent numbers that only have exactly one prime factor, and have more occurrences of it than any other number in the list. This means that you can limit your search to the upper half of the list, but including the middle element, if available.

Answer 4

First, for each incorrect pupil, the number he said is a power of a prime. Otherwise its factors were already mentioned and were correct.

One of those two said an even number, so one of the incorrect numbers is a power of 2. It is also the largest power of 2 smaller than n, otherwise next power of 2 would be incorrect as well. So the incorrect number $2^t$ is greater than $\frac n 2$.

The other pupil named a number of either $2^t + 1$ or $2^t - 1$ and that number has to be a power of a prime. Probably any power. For example a group of 14 pupils where pupils 7 and 8 are wrong (number is not divisible by 8 and 9).

Answer 5

• If at least one of them is a prime, then that prime can't be found among the others' divisors as a factor more than once.

• If at least one is a compound (which is true), that compound's divisors can be found separately, but not at once. For that, this number must be a power of a prime.

The compound prime power is a power of 2, and the other is an odd prime (or they're 8 and 9). Both can't be non-trivial prime powers unless they're 8 and 9, because:

• If $n, m > 1, p > 2$ and $p^n-1 = 2^m$, $n$ is either odd and so is $(p^n-1)/(p-1)$, making $n=1$ (contradiction), or $n$ is even and both $p$^$(n/2)$-1 and $p$^$(n/2)$+1 are powers of 2, making them 2 and 4 respectively.

• If $n, m > 1, p > 2$ and $p^n+1 = 2^m$, then $p^n = 2^m-1$, so $m$ is odd (contradiction otherwise), and $p^n - 1 = 2^m-2 = 2* [2$^$(m-1)] = 2* [2$^$((m-1)/2) + 1] * [2$^$((m-1)/2)-1]$. Since $p^n - 1$ shouldn't be divisible by 4, $n$ is also odd. $p+1$ is a power of 2. $p^n+1$/($p+1$) is odd, so it must be 1, which is a contradiction.

In short, the wrong number duo can be 4-5, 7-8, 8-9, 16-17 or 31-32 if there're fewer students than 100 and more than 3 (3 < $n$ < 100), but both have to be greater than $n/2$ no matter what $n$ is.

In addition, if the prime is the smaller out of the two, the other's power value must be a prime, and if it's bigger, the power must be a power of 2 (respectively Mersenne and Fermat primes), both of which can be proven when the relevant expression is expanded. So the greatest such possible duo can be the wrong divisors, because other candidates would be too small.

The most obvious answers would be 2-3 (for 2 students), 3-4 (3 to 4 students) and 4-5 (4 to 6 students). In addition, 8-9 would be feasible for 8 to 14 students. The generalized rule above applies to all the other solutions.

Answer 6

I am not quite sure if I am correct, but lets see.

My guess is: It has sth. to do with the primes.

I started with the number x, lets say x = 5 (it doesn't really matter, if its small enough). Then I iterate through the pupils and check if x can be divided by the number said. If not I mutliply it with the number.

#1 pupil has number = 2
  can't be divided so x = 10  (x*2)
#2 pupil has number = 3
 can't be divided so x = 30
#3 pupil has number = 4
 can't be divided so x = 120
#4 pupil has number = 5
 can be divided, so x stays at 120
.
.
.

With this scheme every prime would not be a divisor of x. So my idea was to find a pupil number which is not a prime an still no divisor AND is directly before a prime.

The number 16 is one of them, followed by the prime number 17. With this method x =1081080 until pupil #15 and this value for x can't be divided by 16 or 17.

So the last two pupils are wrong, and the very last said number must be a prime.

Edit:

And I have found a sequence: This happens every $y = 2^z$ for z = the previous y

z=2;   y=4
z=4;   y=16
z=16;  y=256
z=256; y=65536
.
.

All these y values are followed by a prime!

Answer 7

Because the two pupils are consecutive one of those is divisible by 2. Let's call that pupil $x$. This means that $x/2$ also can't be a divisor because if $x/2$ is a divisor and $2$ is a divisor then $x$ is also a divisor, contradiction. This either means that the consecutive number are $x$ and $x/2$ or that the number is not divisible by $2$. Since the next number can never be double the previous number it must automatically mean that the number is not divisible by $2$ and, because it needs to be consecutive with another, also not divisible by $3$. This also means that the only valid $n$ is when $n=2$ because a number not divisible by $2$ can't be divisible by $4$ also giving more incorrect statements

Answer 8

The incorrect students are any two students adjacent to each other who each hold a number which is the highest power of a prime of all students.

Of course, it is trivial that one of those students must hold a power of two. Two odd numbers can't be adjacent to eachother.

After that, it is clear that any number adjacent to the highest power of two held which is a power of a prime must be the highest power of that prime. We would hit a higher power of two before we would hit a higher power of any other prime.

Knowing this, n can be arbitrarily high. Sure there are ranges n can't be, such as from 65 to 127 or so ( I haven't done the exact math here but anywhere where the highest power of 2 is not next to an included power of a prime) but we will always eventually find a power of a prime next to a power of 2.

Answer 9

I'm kind of late (almost 3 years late!), but I solved this without looking at others' answers. I found two abstract conditions necessary to qualify a candidate n value, and two specific conditions sufficient to disqualify one.

Two integers in a row will always contain one odd and one even - that is, a number that has 2 as a factor. In order for both to not be factors of the number written on the board, and all the rest to be factors, both must be powers of prime numbers. Because one is divisible by 2, it must be a power of 2; otherwise, there will be a higher power of 2 in the range of interest. Likewise, the odd number must be a power of another prime, so that there are no equal or higher powers of its factors in the range 2 to n+1.

Therefore, if n is legitimate for this scenario to play out, then

1. one of the "dumb students" will be the student who named the highest power of 2
2. the other "dumb student" will be one who named a power of an odd prime, either 1 less or 1 greater than the greatest power of 2
3. both of these numbers will be greater than n/2
4. if n+1 is a power of 2, then n must be a power of an odd prime, and
5. if n/2+1 is a power of 2, then n/2+2 must be a power of an odd prime

Answer 10

Nice puzzle.

The maximum number of pupils in the class is

14

We can argue that certain pupils must be correct. The argument goes this way: Say 2,3,6 are called. If 6 was wrong, 2 or 3 must also be wrong. But that's impossible since the two wrongs must be consecutive. Hence, 6 must be correct, and also 2 and 3.

A variation of this argument applies to square numbers: If 2 and 4 are called, we know that 2 must be correct. (but not necessarily 4).

Another observation is that once a divisor is proven correct via the argument above, it can never be false again, regardless how many pupils call something later.

Now we can play a reverse Sieve of Eratosthenes until no two consecutive wrongs are possible:

• n=2: Both wrong :-)

• n=3: 2 must be correct

• n=4: nothing new. Two solutions exist.

• n=5: 2,3 must be correct, hence 6 also.

...

• n=7: 8 is called, so 4 must be correct. 5 also because both neighbors are already correct.

• n=8: Two solutions exist, either (7,8 wrong) (8,9 wrong)

...

• n=13: 14 is called, which makes 7 correct. 14 is also correct since 2 and 7 are already correct. Only the (8,9 wrong) solution exists.

• n=15: 16 is called, which makes 8 correct. Now we have a contradiction. Let's write the number and highlight those already proven correct: 2,3,4,5,6,7,8,9,10,11,12,13,14,15,16

From now on, whenever an even number n is added, is must be correct since n/2 is already marked as correct.

(maybe this could have been formulated a bit shorter, but still, the arguments work)

Answer 11

_{(answers are highlighted with bold. (corresponds to encircling on paper). "/∶" means "not divisible by" (didn't find the proper symbol).)}

In mathematical terms, the puzzle looks like this:

The number on the blackboard is divisible by everything in the list 2,3,4...n+1 except 2 consecutive numbers (let's call them m,m+1).

What can we say about them?

1. The number is divisible by 2 but not divisible by m
   => m*2 isn't present in the list¹
2. The number is divisible by anything less than m,m+1 but not divisible by them
   => m,m+1 can't be factored by the (different) numbers in the list²
   ____specifically: one of the m,m+1 is even
   ____=> m/2|(m+1)/2 isn't present in the list _{- unless the other multiplier is 2 as well}

---

=> There are only a few possibilities for m,m+1:

• 2,3 => n+1<4 (2 students, both wrong. ha-ha) N=1 ROFLMAO
  _____________________________________all possibilities though are: N∈N, N/∶2,3
• 3,4 => n+1<6 (n<5) | => n=3 N=2 big number indeed
  _____________________________________all possibilities: N=2k,k/∶2,3
  ________________| => n=4 (2,3,4,5) => N=10
  _____________________________________all possibilities: N=10k,k/∶2,3
• 4,5 => n+1<8 => n can be at most 6 (list entry n+1 =7)

The last case requires study in more detail:

Possible values for n:
- 4 at least <= to include "4,5"
=> n=4 (2,3,4,5) => N=6k,k/∶2,5
=> n=5 (2,3,4,5,6) => same as above
=> n=6 (2,3,4,5,6,7) => multiplier=LCM(2,3,6,7)=42 =>
_________________=> N=42k,k/∶2,5

---

My, my. Big numbers these days...

---

¹_{(If the number isn't divisible by 2 (m=2), this stands, too: 4 cannot be present)}
²_{(without loss of generality, by two different numbers in the list: if e.g. (m+1)=k*k*l, k*l is also present in the list and is not m)}

Answer 12

Edited to resolve a prior issue with an incorrect solution:

So, basically, for incorrect students p and p+1, 1 <= p < n, n may lie within the range p+1 < n+1 < (p+1)*2.
Both p+1 and p+2 are either prime or have a single prime factor.
This would mean that the pair p, p+1, for n up to 100, is as follows (p,p+1)
1,2 [divisors 2,3; n=2]
2,3 [divisors 3,4; n=3 or 4]
3,4 [divisors 4,5; 3 < n < 7]
6,7 [divisors 7,8; 6 < n < 13]
7,8 [divisors 8,9; 7 < n < 27]
15,16 [divisors 16,17; 15 < n < 31]
30,31 [divisors 31,32; 30 < n <61]

Answer 13

I'm Back on a computer!

So we know the two students who claimed wrong claimed wrong consecutively. We can say that these two students claimed that the numbers $a$ and $b$ were factors of the number written on the board by the teacher, which in reality it wasn't. The first thing to note is that one of these numbers, either $a$ or $b$ must be even, and one of these numbers must be odd. The second thing to note is that both $a$ and $b$ must be factored into only one type of prime, eg they must be a prime number raised to some power. To prove this, we can assume the contrary and say that $a$ can be factored to $ppqqq$ where $p$ and $q$ are primes. $pp$ will be smaller than $a$, but we know that all numbers smaller than $a$ were accepted by the teacher as being a factor of the number on the board. Similarly, $qqq$ will be accepted by the teacher as being a factor of the number on the board. If both $pp$ and $qqq$ are accepted as being a factor, then $a$ must also be a factor, breaking our assumption. Therefore both $a$ and $b$ must be some prime raised to a power. Because one of these is even and one of these is odd, the even claim must be a power of $2$, and the odd claim must be a power of an odd prime number.

We know immediately some restrictions upon $n$. Firstly, it must be less than $2a$, and less than $2b$, because we know the number on the board is not divisible by either $a$ or $b$. But I believe this is the only restriction upon $n$.