100 people on island; some honest, some liars.... How many tell the truth?

Steven G

Elite Member
Joined
Dec 30, 2014
Messages
14,364
There are 100 people on an island; some people always tell the truth, and the others always lie.




A visitor asks them, "How many of you tell the truth?"



For n=1,2,3,...100 the nth person replies, "f(n) of us tell the truth," where f(n) is the last two digits of n2




How many of them always tell the truth? Note that all 100 islanders replied.
 
Hm. A very interesting math puzzle. At first I was completely stymied and thought maybe the trick was that there wasn't an answer. But then I carefully re-read the problem and saw that f(n) is the last two digits of n^2, which made the puzzle solvable.

The answer is: ***4 villagers always tell the truth. Specifically, villagers #2, #48, #52, and #98***
 
I have been messing around with this on and off for the last few days. I have not looked at it since ksdhart responded so this answer may not be timely.

Anyway, it is a great puzzle.

i have realized that my original answer was very maundering. Consequently, I am editing it to make it more concise and comprehensible because I think such a superior puzzle deserves an appropriate answer.

EDITED

Arithmetic background first.

With respect to the first 24 positive integers, what are their squares?

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400, 441, 484, 529, 576.

Note that each of those squares can be expressed as 100g + h, where g and h are non-negative integers. Let's call the various values of h the residuals. So the residuals of the first 24 positive integers are:

1, 4, 9, 16, 25, 36, 49, 64, 81, 0, 21, 44, 69, 96, 25, 56, 89, 24, 61, 0, 41, 84, 29, 76, 25, 76.

Let's order those residuals.

0, 0, 1, 4, 9, 16, 21, 24, 25, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84, 89, 96.

Of the twenty-four residuals, twenty are unique, but 0 is a residual twice as is 25.

First algebra background:

We define f(n) as having as its domain the positive integers and as equaling

\(\displaystyle f(n) = n^2 - 100 * \left \lfloor \dfrac{n^2}{100} \right \rfloor.\)

In other words, f(n) gives the residual of n^2.

The following result is given without proof.

\(\displaystyle n^2 = 100g + y^2 \implies f(n) = f(y).\)

Second algebra background:

\(\displaystyle y \in \mathbb Z \text { and } 1 \le y \le 24 \implies\)

\(\displaystyle (0 + y)^2 = y^2,\ (50 - y)^2 = 2500 - 100y + y^2 = 100(25 - y) + y^2,\)

\(\displaystyle (50 + y)^2 = 100(25 + y) + y^2,\ \text { and } (100 - y)^2 = 100(100 - 2y) + y^2 \implies\)

\(\displaystyle f(0 + y) = f(y) = f(50 - y)= f(50 + y) = f(100 - y).\)

For example f(8) = 64, f(42) = 1764 - 1700 = 64, f(58) = 3364 - 3300 = 64, and
f(92) = 8464 - 8400 = 64.

Logical solution.

Each person on the island is indexed from 1 through 100. Each person when asked how many truth tellers are on the island gives as an answer the residual of that person's index squared. Of course, the liars answers are lies, but the truth tellers' answers are true.

For indices 1-24, our arithmetic showed that we had residuals of 0 and 25 twice and 20 other distinct numbers once each. Our algebra showed that we have the exact same residuals for indices 26-49, 51-74, and 76-99. So, for all those indices we have as residuals 0 eight times, 25 eight times, and each of the 20 others four times each. That gives just 96 residuals, but we left out the residuals of the squares of indices 25, 50, 75, and 100. They are 25, 0, 25, and 0. So all told, we have 0 ten times, 25 ten times, and the other 20 numbers 4 times each.

Now all the truth tellers have to give the same response. If any truth teller says 0, then he is denying his own existence, which is absurd. If any truth teller says 25, then we would have at least 24 more answers of 25, which is impossible because the residuals of only ten indices are 25. Thus there are only four truth tellers. So they must have indices such that f(index) = 4. Therefore, the four of them are indexed as #2, #48, #52, and #98.
 
Last edited:
\(\displaystyle f(y + 0) = f(y) = f(50 - y)= f(50 + y) = f(100 - y).\)

Now all the truth tellers have to give the same response. If any truthteller says 0, then he is denying his own existence, which is absurd. If any truthteller says 25, then we would have at least 24 more answers of 25, which is impossible because there can be only 10. Thus there are only four truthtellers. So they must have indices such that f(index) = 4. Therefore the four of them are indexed as #2, #48, #52, and #98.
Yes, you got it. Very nicely done.
 
Top