31 students in a row were numbered 1,2,...,31 in order. The teacher wrote down a number on the blackboard.
Student 1 said "the number is divisible by 1",
Student 2 said "the number is divisible by 2",
and so forth...until
Student 31 said "the number is divisible by 31".
The teacher remarked: "Very well pups, but two of you gave a wrong statement, and those two sit besides each other". Determine those two.
we're given a set S {1,2,3,...,31}
(1) only two numbers in S do not divide the teacher's number T
(2) these two numbers are consecutive.
(1) and (2) together imply that one of the numbers is even, call it E. Also, neither number in the answer pair can be less than 31/2 because that implies that twice that number doesnt divide T. So the pair must be one of (16,17), (17,18), . . . , (30,31).
we can eliminate all even numbers in all these pairs except 16. This is because they can all be represented as products of numbers that divide T (< 31/2) that dont have common factors. i.e,
18 = 2*9
20 = 4*5
22 = 2*11
24 = 8*3
26 = 2*13
28 = 4*7
30 = 2*15
16 = 2*8. However, knowing that 8 divides T then knowing that 2 divides T gives no additional information. Ex, 8 divides 24 and 2 divides 24 but 8*2 = 16 does not divide 24.
so you get (16,17).
same as prev - approach
