## July 02, 2006

### 100-statement question

This is for you logicians out there.

Well, all right, this is also for you illogicians out there.

I hand you a sheet of paper with 100 numbered statements on it. They read like this:
1. Exactly 1 of the statements on this sheet is false.
2. Exactly 2 of the statements on this sheet are false.
3. Exactly 3 of the statements on this sheet are false.

...

99. Exactly 99 of the statements on this sheet are false.
100. Exactly 100 of the statements on this sheet are false.
That is, statement n on the sheet reads: "Exactly n of the statements on this sheet are false."

Question: Which statements are true and which are false?

There is, of course, a bonus. Replace "exactly" with "at least" all 100 times. Try the same question. Does your answer change? Why and how and wheretofore?

There is, of course, a second bonus. Still with the 100 "at leasts", add a 101st statement. ("101. At least 101 of the statements on this sheet are false."). Try the same question. Does your answer change? Why and how and wheretofore hereunder? Anonymous said...

1. Statement 99 is true. The rest are false.
2. First 50 statements are true, the rest are false.
3. No true statements and no false statements. Anonymous said...

#3 is wrong in the previous comment. Correct answer: first 50 true, the last 50 false. 51st is neither true nor false. Anonymous said...

The previous comment corrects a mistake with another mistake. The 51st statement is simply false. The answer simply does not change.

Sailesh Ganesh said...

A formal solution here.

Case 1: The word 'exactly' is used.
All the 100 statements are disjoint statements (i.e., none of them implies any of the others, in fact, any one of them implies none of the others!), hence only one of them can be true. Which means 99 of them must be false, which means statement 99 is true, while the rest are false.

Case 2: The word 'atleast' is used.
Two observations:
1) If statement n is true (2 <= n <= 100), statement n-1 is also true.
2) If statement n is false (1 <= n <= 99), statement n+1 is also false.

Therefore, there is a number n such that statements 1 through n are all true, while statements n+1 through 100 are all false. The strongest of the true statements is statement n, which means atleast n statements are false. Also, since statement n+1 is false, atmost n statements are false. Together, they imply that exactly n statements are false. Now, we also know that 100-(n+1)+1 = 100-n statements are false. Hence, we have the equation 100-n = n, or n = 50. Thus, statements 1 through 50 are all true, while statements 51 through 100 are all false.

Case 3: The word 'atleast' is used, with 101 statements. Then the above equation becomes 101-n = n, which yields n = 50.5, which is absurd, hence in this case, the set of statements is not self-consistent, and no solution can be found.