# Find a number based on lies about divisibility

A teacher writes a positive integer n < 50000 on the blackboard.
The first student claims, that n is divisible by 2.
The second student claims, that n is divisible by 3.
The third student claims, that n is divisible by 4.
This logic continues up to the twelfth student and
the twelfth student claims that n is divisible by 13.
Now 10 of those student said the truth, the other two students did lie. Both liars made their claim next to each other.

Which number was written by the teacher on the blackboard?

## 3 Answers

I think the answer is

$$25740$$

Reasoning

Only two consecutive students lie which means that $$n$$ must be divisible by either $$4$$ or $$8$$ (hence is divisible by $$4$$). Similarly, it is divisible by either $$3$$ or $$9$$ (hence it is divisible by $$3$$) and either $$5$$ or $$10$$ (hence divisible by $$5$$).

This means that $$n$$ is divisible by $$2, 3, 4, 5, 6, 10$$ and $$12$$ at the very least and since the lying students are consecutive they must be lying about divisibility by either $$7$$ and $$8$$ or $$8$$ and $$9$$. This means that $$n$$ is also divisible by $$11$$ and $$13$$.

If the student who claimed divisibility by $$9$$ is lying, then $$n$$ is divisible by at least $$4 \times 3 \times 7 \times 5 \times 11 \times 13 = 60060 > 50000$$.

Hence, the student who claimed divisibility by $$9$$ is telling the truth and the student who claimed divisibility by $$7$$ is lying. This means that $$n$$ must be divisible by $$4 \times 9 \times 5 \times 11 \times 13 = 25740$$ which is the only multiple of itself less than $$50000$$

• You just pipped me to it! I totally agree with all of this logic - it's the same answer I had. +1 – Stiv Jan 31 '20 at 14:36
• @Stiv, thanks, apologies for pipping you. – hexomino Jan 31 '20 at 14:39
• Perfect answer. – ThomasL Jan 31 '20 at 15:43

Hexonimo has a good correct answer and he was first.

I came about it in a slightly different way, eventually arriving at the same final trial answers. I'm answering because I believe my solution is a little easier to follow.

Seeing as my mathjax skills are infinitesimal, I'll use !/ to mean "not divisible"

N !/ 2 → N !/ (2*2, 2*3, 2*2*2, 2*5, 2*2*3) (4,6,8,10,12 - not consecutive)
N !/ 3 → N !/ ( 3*3, 2*2*3) (6, 12 - not consecutive)
N !/ 4 → N !/ (2*2*2, 2*2*3) (8, 12, - not consecutive)
N !/ 5 → N !/ (2*5) (10 - not consecutive with 5)
N !/ 6 → N !/ (2*2*3) (12 - not consecutive with 6)
N !/ 7 → no conflict.
N !/ 8 → N !/ (2 * 2 * 2) * (possible)
N !/ 9 → no conflict
N !/ 10 → (eliminates 2 or 5) (not consecutive)
N !/ 11 → no conflict
N !/ 12 → (eliminates 2*2 or 3) (not consecutive)
N !/ 13 -> no conflict
2-6 all imply the invalidity of higher numbers (more than 2 away). This gives us a minimal set of (2*2*3*5) as a starting point.
10 and 12 are both out as they can be formed from our starting set.
This eliminates 11 and 13 as they don't form consecutive pairs. We are left with trial numbers (2*2*3*5*11*13) * (7 or 3) (seeing as there's already a >! 3 in there, we don't need (3*3) to make it divisible by 9)
If we pick 7, we get 600060. <- Too Big If we pick 3, we get 25740. <- answer

• Preceding a symbol with \not puts a slash through it. So \not | gives $\not |$. – Acccumulation Feb 2 '20 at 18:22

I got the same answer...in a very different way. Is this cheating?

for(i in 13:50000){
non_divis_n <- 0
consec_non_divis <- 0
for(j in 2:13){
if(i%%j != 0){
non_divis_n <- non_divis_n+1
if(i %% (j-1) != 0){consec_non_divis <- consec_non_divis+1}
}
}
if(non_divis_n==2 && consec_non_divis == 1){
print(i)
}
}

• I don't think it is cheating but I also don't think it is an elegant answer to the question. – Surb Feb 1 '20 at 20:11