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 n1n-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 k1k-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 Tk1T \le k-1; for it to be false, T>k1T > k-1. Hence statement kk is true exactly when kT+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 100T100 - T. But this number must equal TT itself, because TT is the total number of true statements. Therefore:

T=100T2T=100T=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 k1k-1 are true" with k148k-1 \le 48, but 50>k150 > k-1. All statements 5252 through 100100 are true because each claims "at most k1k-1 are true" with k151k-1 \ge 51, and 50k150 \le k-1. Hence exactly 5050 statements are true, consistent with T=50T=50.

Thus the answer is 5050.

Related problems