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?
Answer the first part if the nth statement is : "At least n of the statements in this list are false"
Suppose the $1st$ statement is false, then it is not the case that at least $1$ of the stamenets are false. This is a contradiction as the $1st$ statement is false.
So, the first statement must be true. You can repeat this argument all the way up to (and including) 50, but what happens at 51?
If the $51st$ statement is true, there must be at least $51$ false statements. As 1-50 are true, this cannot be the case and therefore statement $51$ must be false. The same argument applies to 51-100.
Answer the second part assuming that the list contains 99 statements
You can use the same argument as before for proving that $1-49$ are true.
What about statement $50?$?