[Math] Puzzle : Truant List of Statements

logicparadoxes

I was working my way through some puzzles in Discrete Maths by Rosen, when I came across the following question:

The $n^{th}$ statement in a list of 100 statements is : "Exactly $n$ of the statements in this list are false"

  • What conclusion can you draw from these statements ?

  • Answer the first part if the $n^{th}$ statement is : "At least $n$ of the statements in this list are false" ?

  • Answer the second part assuming that the list contains 99 statements ?

My Solution (Inadequate):

  • The 99th Statement is True and the rest are false

  • I am all thumbs for the next two parts

Book solution:

  • The 99th Statement is True and the rest are false
  • Statements 1 through 50 are all true and statements 51 through 100 are all false
  • This cannot happen; it is a paradox, showing that these cannot be statements.

My question:

Why is this so?

Best Answer

For the first part, "Exactly $n$ of the statements are false", note that they all contradict each other, so at most one is true, so at least $99$ are false. This guarantees that $1-98$ are false. You can have $99$ being true and $100$ false and all is consistent. If $99$ if false as well we cannot assign a consistent truth value to $100$, so the only assignment is number $99$ true and all others false.

For $100$ sentences saying "At least $n$ of these are false" we cannot have $1$ be false because its negation is all of these are true, so it would have to be true, in conflict with our assumption that it is false, so $1$ is true and at least one of the statements is false. Now we know that statement $100$ is false because one of the statements is true. Statement $2$ cannot be false, because its falsity would require at most one true statement, which is $1$, which would make it true. We continue back and forth, showing the high statement numbers are false and the small ones true until we show $1-50$ are true and $51-100$ are false.

If there were $99$ sentences of the form "At least $n$ of these are false" we proceed just like the $100$ case until we have $1-49$ true and $51-99$ false. Then if $50$ is true there are only $49$ false statements and if it is false there are $50$. Either way is a contradiction and we conclude there is no consistent truth assignment.

Related Question