Liars!

Logic Level 4

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, ..., 100,$ the $n^\text{th}$ person replies, " $f(n)$ of us tell the truth," where $f(n)$ is the last two digits of $n^2.$

How many of them always tell the truth?

Note: All 100 islanders replied. For example, the $3^\text{rd}$ person replied, "9 of us tell the truth" because $3^2={\color{#D61F06}09}.$ and the $17^\text{th}$ person replied, "89 of us tell the truth" because $17^2=2{\color{#D61F06}89}.$

The answer is 4.

11 solutions

X X
May 6, 2018

Relevant wiki: Truth-Tellers and Liars

$(25m+n)^2$ and $(25m-n)^2$ has the same last two digits,because $(25m+n)^2-(25m-n)^2=100mn$ .

So,for $a$ smaller than 25, $f(a)=f(50-a)=f(50+a)=f(100-a)$ .

If $a$ is not a multiple of 5,then there are 4 people saying, " $f(a)$ of us tell the truth."So, $f(a)=4$ .

If $a$ is a multiple of 10,they say, "none of us tell the truth." which is definitely a lie.

If $a$ is a multiple of 5,but not a multiple of 10(there are 10 $a$ s like this),they say, "25 of us tell the truth",which is also a lie.

Hence,4 people(the 2nd,48th,52nd,98th person) tell the truth.

(You actually do this, but just not explicitly) A better way to present it is to let $g(x)$ be the number of times that $f(n) = x$ . Then, we want to show that $g(a) = a$ if and only if $a = 4$ .

Calvin Lin Staff - 3 years ago

Great solution! Beutiful approach!

Rotem Peri-Glass - 3 years ago

what if the nth person asked is a liar

Be Humble & Sit Down - 3 years ago

XX, I am not able to fill in a step (or two) in your solution. Specifically, I am unable to get from the first line, to the second. Perhaps you, or another, would be willing to give me some help. Thanks. P.S. I used Excel.

Ian Leslie - 3 years ago

$f(25m+n)=f(25m-n)$

Place $m=1,n=25-a$ will get $f(25+25-a)=f(25-25+a),f(50-a)=f(a)$ .

Place $m=2,n=a$ will get $f(50+a)=f(50-a)$ .

Place $m=3,n=25-a$ will get $f(100-a)=f(50+a)$

X X - 3 years ago

Thank you.

Ian Leslie - 3 years ago

Beautiful proof!

Paul-Boer Putter - 3 years ago

You have not shown that all of the f (a) with a <25 , other than multiples of 5, are different.

Matt McNabb - 3 years ago

Let $0<a<b<25$ ,if $b^2-a^2=(b+a)(b-a)$ is a multiple of $100(=2\times50=10\times10)$ ,then $b+a,b-a$ are both multiples of 10(because $a+b$ can't be a multiple of 50),so $a,b$ are both multiples of 5.

X X - 3 years ago

How do you deduce the third line ? Please explain...

Ariijit Dey - 3 years ago

X X - 3 years ago

How tremendously elegant!

Divyanshu Vadehra - 3 years ago

P.S from the 3rd line There are $20$ $a$ 's $< 25$ and not a multiple of $5$ which satisfies your 2nd equation $f(a)=f(50-a)=f(50+a)=f(100-a)$ so this means 20 people say "4 of us tell the truth"; How can then this be true?

Ariijit Dey - 2 years, 11 months ago

I didn't mean to increase the font size using "#" Please don't take this on a harsh note

Ariijit Dey - 2 years, 11 months ago

Out of the 20 $a$ 's $< 25$ and not a multiple of 5, how many of them satisfy $f(a) = 4$ ?

Calvin Lin Staff - 2 years, 11 months ago

Fabricio Kolberg
May 20, 2018

My solution takes a computational approach (this is one of those moments where computers really feel like bicycles for our brains).

Notice that the set of people who tell the truth has two necessary conditions:

They all say the same number (two different numbers can't be true at the same time).
The size of the set is equal to the number the people in the set say (if they say a different number, then it is not the size of the set of truth-tellers, meaning they're not telling the truth).

I made a simple program in C that calculates, for the first 100 positive integers, the remainder of the division of their squares by 100, and then lists the number of occurrences of each value. The output was the following:

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

The only set that satisfies both conditions we previously mentioned are the four people who said 4, making 4 the right answer.

The code itself is pretty simple, but if you want it, I can post it.

I tried to do this in excel, but didn't find any easy way. I really would like to see this code.

Inksa Inkeroinen - 3 years ago

You can do this in Excel with two columns.

Column A:

=NUMBERVALUE(MID(POWER(ROW(),2),IF(LEN(POWER(ROW(),2))<3,1,LEN(POWER(ROW(),2))-1),2))

Column B:

=COUNTIF($A$1:$A$100,ROW())

Though, this excludes a count of the people that said 0.
You can account for 0 with an adjustment to the formulas in column B, by changing ROW() to ROW()-1. You are then counting how many times people have said a number equal to 1 less than the row number.

But there's an argument for excluding 0 altogether - because it's impossible for a liar to say it, and for it to be the truth.

Jonathan Quarrie - 3 years ago

Here’s the C program I used to find the amount of people saying each number:

import math

values = [];
for x in range(0, 100):
    values.append(0);
for x in range(0, 100):
    y = math.pow(x, 2);
    while y >= 100:
        y = y % 100;
    values[int(y)] += 1;
for x in range(0, 100):
    if values[x] != 0:
        print(str(x) + ": " + str(values[x]));

Calvin Osborne - 3 years ago

How do I upvote a comment?

Fabricio Kolberg - 3 years ago

@Fabricio Kolberg – You can't anymore. Brilliant took the ability to upvote comments away.

Jonathan Quarrie - 3 years ago

Fill col 1 with numbers 1 to 100

Fil col 2 with the square of [col 1 ]

Fill col 3 with 100* int( [col 2]/100)

Sort according to col 3

Count the number responses manually

Laszlo Mihaly - 3 years ago

case 4 was the step I didn't realize... :)

Inksa Inkeroinen - 3 years ago

I actually did that manually!

Aatman Supkar - 3 years ago

I did this manually with a list of squares but realizing the count was going to be 10 or fewer, so I only made the first 4 rows of your table.

Jeremy Galvagni - 3 years ago

I did this with excel.

Paul Sommer - 3 years ago

I did it with excel, too.

Laszlo Mihaly - 3 years ago

I've got to admit I just don't get this one at all. I guess we assume that the islanders all know how many liars there are. The restrictions on what liars say I just don't get. The math rules on what the honest ones say doesn't make much sense, either. I can't tell if there's something in the wording I don't get, or something in the math that resticts true values. Would someone please clarify this for me? Complicated is fine, but this is total fog

Bill Weihmiller - 3 years ago

It is hard to explain better than the solution that has been posted. However, it may help if you try to solve it yourself. Here is my recommendation:

Open an excel spreadsheet.

Fill col 1 with numbers 1 to 100

Fil col 2 with the square of [col 1 ]

Fill col 3 with 100* int( [col 2]/100) (this will be the last two digits of the numbers in col 2)

Sort all of the data according to col 3

Starting at the top, look at the numbers and try to decide if the statement can be true.

Laszlo Mihaly - 3 years ago

I agree with you. The wording of the question was not enough for me to actually figure out what it was asking!

Matt Shisler - 3 years ago

Eric Schneider
May 20, 2018

Let $g(n)$ be a function that lists the number of occurrences of $n$ on $\text{Im}_f([100])$ . Then we're looking for some $n=g(n)$ . We can do this with math and critical thinking, but why do that when we can write seven lines of python?

arr = []
for i in range(1, 101):       # for each i from 1 to 100
    arr.append(i**2 % 100)    # add f(i) to the array arr
for i in arr:                 # for each value in arr
    if i == arr.count(i):     # if i occurs i times in arr
        print(i)              # we found our answer
        break                 # we don't have to keep going

I did the same but why did you put a "break" then you are assuming that there's a single answer. It would be better to check it by eraseing this break. (You could also simplify the first 3 lines using list comprehension just to notice it)

Pau Cantos - 3 years ago

Oooh, you're right. If we're trying to golf this down:

for x in range(1,101):
    if x == [i**2%100 for i in range(1,101)].count(x): print(x)

Eric Schneider - 3 years ago

Malcolm Rich
May 21, 2018

This is a fairly simple exercise in recognising patterns in square numbers. Apart from the more frequent occurrence of 25 and 00 every ten numbers, the remaining numbers follow a cycle 01,04,09,...09,04,01 every 50 square numbers.

0 can't be correct as 10 people say zero 10 people say 25 so they must be lying Every other possible answer is repeated 4 times which is also one of the answers given by the islanders

Bhaskar Pandey
May 23, 2018

#include<iostream>

using namespace std;

int main()
{
    int truth[101];
    truth[0]=-1;
    for(int i=1;i<=100;++i)
    {
        truth[i]=(i*i)%100;
    }
    for(int i=1;i<=100;++i)
    {
        int a=0;   //a is initialised with zero every time i increments
        for(int j=1;j<=100;++j)
        {    
            if(truth[i]==truth[j])
            {
                a++;    // whenever we find a match that means they have same opinion
            }
        }
        if(a==truth[i])   //for all truth tellers 
        {                 // "number of truth tellers they say there are" = "actual number of truth tellers"
            cout<<a;
            return 0;
        }
    }
}

Arsenio Meneses
May 25, 2018

Using an Excell spreadsheet create 2 columns, side-to-side, from 1 to 100 and a third one with the correspondent product of the first two. Look for the number that has exactly the same number of persons saying that number. You will see that 04 is the only number that has 4 people saying the number 4.

This will become tough for 1000people.

Debasish Roy - 1 year ago

Eshan Balachandar
Jul 11, 2018

While you could write a code, here's my solution using inspection.

Look at the last digit of squares.

1, 9 --> 1 [20]

2, 8 --> 4 [20]

3, 7 --> 9 [20]

4, 6 --> 6 [20]

5 --> 5 [10]

0 --> 0 [10]

The bracket indicates how many numbers fall into that group. Clearly, the answer can be almost 20. But the answer is also a square. Possibilities are 01, 04, 09, 16. Notice that 1, and 51 both square with ends 01, and hence it cannot be the answer (why?). Inspecting the squares, 9 and 16 are clearly too frequencies for ends of squares. Elimination leaves 4 as the answer.

Himank Kansal
May 27, 2018

I tried for a simple approach. I realized that last two digits after squaring starts repeating after 50. So search among 1 to 50 and twice the number of digits found. Now 1 cannot be there since the number has to be even since same squares will appear after 50. 4^2 is 16, that means 8 numbers whose squares end up with 16 which is not possible in 1 to 50. So since oddXodd is odd, look for even numbers. 2 gives 4, look numbers which have a chance to end up with 4 will give 48. Remaining digits will not give the answer since 6X6=36 (18 in 1 to 50, not possible).

Similar in 50 to 100. Total numbers become 4.

Xu Liangjun
May 26, 2018

The last digits of n^2 can only be 1,4,9,6,5.

It's clear that n^2 share the same last two digits with (100-n)^2 ,when positive interger n <100.

So there must be 2x(x is an interger) people telling the truth.

Now the last digit of n^2 can only be 4 and 6.

And you can try three times.Emmmm, just for joking.

Now you should think about a more precise principle.

It's natural to find out that (25m-n)^2,(25m+n)^2 share the same last two digits.

Now the last digit of n^2 is 4.

And 4 itself is right.

Will McKnight
May 22, 2018

If 0 people are telling the truth, then everyone is a liar, including those who say 0 people are telling the truth. This immediately implies that there is at least one truth-teller. Additionally, there were 10 who said there are 0 truth tellers, which places an upper inclusive bound of 90 truth tellers. Filtering the truth teller counts for between 1 and 90 inclusive gives 86 truth tellers, filtering again gives 82, and so on until it bottoms out at an upper inclusive bound of 70. The number of truth tellers must be matched by the number of people giving that number, and the only number for which this holds among the between-1-and-70 filtered list is 4 (4 people each claim 1, 9, and 16 truth tellers, for instance, which is an obvious contradiction).

E Sch
May 22, 2018

@Inksa Inkeroinen

i know this is lame but sigh ...

in spreadsheet 4 columns down 100 rows

A=n	B=f(n)	C=count	D=verifiy
1	mod(A1^2,100)	Countif(B$1:B$100,B2)	if(C1=B1)
A1+1	mod(A2^2,100)	Countif(B$1:B$100,B2)	if(C2=B2)

then sum on column $D=\boxed{4}$ , because only rows n=2,48,52,98 are true

Liars!

The answer is 4.

11 solutions

0 pending reports