100 Statements
Jane Street
On a sheet of paper, you have 100 statements written down. the first says, 'at most 0 of these 100 statements are true', the second says, 'at most 1 of these 100 statements are true' ... the nth says, 'at most (n-1) of these 100 statements are true. ... the 100th says, 'at most 99 of these statements are true.' how many of the statements are true?
Answer
With this kind of a question, it's best to start guessing until you spot the dynamic. Say 0 statements are true - then 1st statement would also be true, since it says 'at most 0 statements are true', so this is inconsistent. What if all 100 statements are true? Then 100th statement would have to be false, since it says 'at most 99 statements are true' - so this is inconsistent too. Okay, so the answer is somewhere in the middle.
Say 10 statements are true (denote $X=10$) - what does this imply? If $k^{th}$ statement says 'at most k statements are true', i.e. $X\leq k$ - then all statements with $k\lt 10$ are false (since we know $X=10$). It also implies all statements with $k\geq 10$ are true, since if $X=10$ then $X\leq 10$, $X\leq 11$, ..., $X\leq 99$ are all true. And this is the important bit: we just saw that if n statements are true, then all statements $k$ with $k\geq n$ are also true (of which there are $99-(n-1)$), while others are false. So if we assume $n$ statements are true, this implies $99-(n-1)$ statements are true. Then $99-(n-1)=n$ so $n=50$, i.e. 50 statements are true.