7
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ It seems that you are looking for a mathematical proof. If that is the case, this question should be moved to math.SE $\endgroup$ – dmg Feb 2 '15 at 7:58
  • $\begingroup$ Actually , @dmg - this is given in the section of puzzles and not mathematical proofs ;) $\endgroup$ – pranav Feb 2 '15 at 8:24
  • 2
    $\begingroup$ You ask "why is this so?". The only proper way to explain it is through proving it. I would suggest that you try proving it by contradiction. Assume n < 99 and n = 100 for the first example and you will find your contradictions :) $\endgroup$ – dmg Feb 2 '15 at 8:29
  • $\begingroup$ @pranav What have you tried? (In true math.SE style, I think you'd learn more if we led you through the process than if we fed you the answer.) $\endgroup$ – Lopsy Feb 2 '15 at 12:43
5
$\begingroup$

For the second part, "At least $n$ of the statements in this list are false," you have some number $k$ of false statements, and $100-k$ true statements. It should be clear that the $n^{th}$ statement is true whenever $n\le k$, and false otherwise, which means that there also $k$ true statements. So, you have $k=100-k$, which means that $k=50$. There are $50$ true and $50$ false statements, which means the first $50$ statements are true and the rest are false.

This method should make it clear that there is something wrong with the third problem, since it tells you that there should be $49.5$ true statements, and how can you have a (logical) half-truth? To see the paradox, suppose that statements 1 through 49 are true, and the rest are false. Then there are $50$ false statements, so the $50^{th}$ statement is true. But the $50^{th}$ was one of the false statements. Now there are only $49$ statements that are false, so "At least $50$ of the statemnets in this list are false" is false. This gives $50$ false statements again, so we're back where we started.

An odd number of statements in a list like that produces a version of the Liar's Paradox.

$\endgroup$
1
$\begingroup$

Answer the second part assuming that the list contains 99 statements:

Assume that exactly $x$ statements are false. Then every statement $n$ with number $n\ge x+1$ is false, and every statement $m$ with number $m\le x$ is true. There are exactly $99-x$ statements with $n\ge x+1$, and they coincide with the $x$ false statements. Therefore $x=99-x$. This is impossible, and the problem has no solution.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.