Self-referential truth count

FreeBrainteaserEasyJane StreetSIGFive Rings

On a sheet of paper are 100100 statements. The first reads, "at most 00 of these 100100 statements are true." The second reads, "at most 11 of these 100100 statements are true." In general, the nnth statement says, "at most n−1n-1 of these 100100 statements are true." How many statements are true?

Solution

Let the statements be numbered 1,2,…,1001,2,\dots,100. Statement kk says: "at most k−1k-1 of these 100100 statements are true."

Let TT be the total number of true statements. For statement kk to be true, we must have T≤k−1T \le k-1; for it to be false, T>k−1T > k-1. Hence statement kk is true exactly when k≥T+1k \ge T+1.

Thus the true statements are those with indices T+1,T+2,…,100T+1, T+2, \dots, 100. The number of such statements is 100−T100 - T. But this number must equal TT itself, because TT is the total number of true statements. Therefore:

T=100−T⟹2T=100⟹T=50.T = 100 - T \quad\Longrightarrow\quad 2T = 100 \quad\Longrightarrow\quad T = 50.

Check: If T=50T=50, then statements 5151 through 100100 are true (50 statements). Statement 5151 says "at most 5050 are true" — true because exactly 5050 are true. Statement 5050 says "at most 4949 are true" — false because 50>4950 > 49. All statements 11 through 4949 are false because each claims "at most k−1k-1 are true" with k−1≤48k-1 \le 48, but 50>k−150 > k-1. All statements 5252 through 100100 are true because each claims "at most k−1k-1 are true" with k−1≥51k-1 \ge 51, and 50≤k−150 \le k-1. Hence exactly 5050 statements are true, consistent with T=50T=50.

Thus the answer is 5050.

Related problems