deutsche Version

How many liars?

          Solution: See lower part of this page.

Everybody lies.
Our figures are a total mess.
Our statistics are less reliable than the horoscopes in the yellow press.

Authentic quotation from a letter, written by the director of the Italian national statistics authority just before he committed suicide in his office.


A central part of the following problem was suggested by Mr Georg Arends who received his diploma in mathematics from University of Applied Sciences Giessen-Friedberg in 1992.


The Ministry for Truth of the Kingdom of Veritania has got problems with the subjects, too. A certain quarter of the capital attracts special attention: From there come an exorbitant number of wrong tax returns, fraudulent insurance claims, untrue census informations etc. The minister wants to make an example of the  210  inhabitants of the quarter and gives instructions to his officers. They have to choose  N  houses, and  N  floors in each of the chosen houses, and  N  persons living in each of the chosen floors. All these persons have to be brought to the ministry for questioning.

The subjects chosen by the officers gather in the ministry, but their examination is delayed a little. As these people know each other well they use the delay for discussing the imminent examination. There are two groups: One group will give in and speak the truth in the examination, the other group will resist and make untrue statements only.

The interviews reveal to the officers the behaviour of the two groups  -  the truth-tellers and the liars. They decide to ask each of them how many liars are in the sample of people chosen to be examined. Here are the records of the first answers given:

"At least four."
"More than seven."
"Not only one."
"At least six."
"All are liars."
...
...

After having finished the interviews the officers realize that all answers are different - no two of them meant the same. A sorted list of the answers (brought into a mathematical form with  L  the number of liars) would read like this:

L ≥ 1
L ≥ 2
L ≥ 3
...
...
L = "all"

How many persons were interviewed? How many of them lied?

Solution

The number  M  of all people examined is a cubic number,  M = N³, but this will turn out to be important only in the last part of this solution.

Let's start with an example,  M = 100.  100  statements have been given:

A_n :  "There are at least  n  liars."

E.g.,  A_n = A₃₇  then cannot have been a liar's statement. Why? If  A₃₇  were wrong at least  64  truth-tellers would have been examined. Among these must be some who truthfully state  A_k  with  k ≥ 51 . But there are at most  36  liars, so we have got a contradiction.

This reasoning applies for all  n ≤ 50.

On the other hand, e.g.,  A_n = A₅₃  cannot have been said by a truth-teller. Why? If  A₅₃  were true there would exist at least three untrue statements  A_k  with  k ≤ 50 which was disproved above.

This reasoning applies for all  n ≥ 51.

Let's pause for a warning. We proved that  A₃₇  is not a liar's statement. But that does not imply it is a truth-teller's statement. Maybe that would lead to a contradiction, too. In fact, we will learn that it is possible for the statements  A₁  to  A_M  to be logically inconsistent - meaning all or some of them are neither true nor untrue.
Our example  M = 100 , however, does not lead us into such a logical trap. If we consider  A₁  to  A₅₀  true and  A₅₁  to  A₁₀₀  false this set of statements yields no contradiction. This is easily checked, and our introductory reasoning shows that this must be the only solution.

This example allows a straightforward generalization to all even numbers  M  of people:

The statements  A_n  for  n ≤ ^M/₂  are said by truth-tellers and for  n > ^M/₂  by liars. So there are exactly as many truth-tellers as there are liars.

For odd  M  there is no such equal division. So the middle position  n = ^M + 1/₂  suggests itself for closer inspection. (In what follows take  M = 101, n = 51  as an example for checking.) Suppose  A_n  to be true. Then  A_k  would be true for all  k < n .  So there would be at least  n  truth-tellers. But on the other hand,  A_n  just means that there are at least  n  liars. In total we get  2n = M + 1  people, so we get a contradiction. -  Now let's assume  A_n  being a lie. Then  A_k  would be false for all  k > n .  So there would be at least  n  liars. But on the other hand,  A_n  being false just means that there are at least  n  truth-tellers. Again, in total we get  2n = M + 1  people, so here too we get a contradiction.

We proved that in our original problem the number  M  of people chosen to be questioned must be even. Thus  N  must be even. As  M = N³ ≤ 210  only  M = 8  and  M = 64  remain.  M = 8  can be ruled out because the meaning of the answers given by the  M  subjects are all different from each other, and for  M = 8  the statements "More than seven" and "All are liars" would have the same meaning.

4  houses were chosen and in each of them  4  floors and in each of the floors  4  persons. Of these  64  persons exactly  32  lied.