The $n$th statement in a list of $100$ statements is "Exactly $n$ of the statements in this list are false".

Question

I was going through "Discrete Mathematics and its Applications - 7th edition" by Konneth H Rosen when I stumbled 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".

1. What conclusion can you draw from the statement?

2. Answer (1) if the $nth$ statement is "At least $n$ of the statement in this list are false".

3. Answer (2) assuming that the list contains $99$ questions.

How to conclude from the given data? If $n$ statements are false is the $n$th statement, then maybe the first statement states that exactly $1$ statement is false. This is possible because maybe some statement from the remaining $99$ statements can be false.

But, the answer given is "99th statement is true and the rest are false". How was this concluded?

Also, for part (2) and (3), how to proceed?

Answer 1

Your list is:

• Exactly 1 statement in this list is false.
• Exactly 2 statements in this list are false.
• $\vdots$
• Exactly $n$ statements in this list are false.
• $\vdots$
• Exactly 100 statements in this list are false.

Consider: Can all the statements be false? Can more than one statement be true?

Answer 2

I have seen a good YouTube video explaining a problem of this sort (it can be found here by MindYourDecisions)

Essentially, consider the $100^{th}$ statement for the exact case. If it's true, then all the statements, including itself, must be false. This leads to a contradiction and it must be false. We now know that least one statement is false

All these statements are mutually exclusive, and therefore only one of them can be true at a time. So that would mean $99$ of them would be false. Hence, $99^{th}$ statement must be true.

I'll let you now use this to try and figure out the "at least" case.

Credits to MindYourDecisions for the video solution

Answer 3

See, first of all, given any finite list of statements, there is exactly a fixed $n$ number of them which are false and some which are true, because all statements have a truth value.

All the statements in the list given to us are attempting to assert how many statements of the list are incorrect. Applying the logic of the previous paragraph, since we know that there is precisely one fixed number which is the answer to this question, exactly one of these statements saying "$n$ of the statements is incorrect" must be correct, whereas all the other $99$ must be false.

It is then clear that precisely $99$ of the $100$ statements are false, and that the statement saying "$99$ of the statements in this list are false" must be the true statement.

---

If, now, exactly changes to "atleast", then there is a possibility of more than one statement being correct, because if, say at least two statements are incorrect, then of course "at least one statement is incorrect" is true as well.

Now, let us assume that exactly $n$ statements are false, where $n > 0$. Then, exactly all the statements saying "at least $k$ statements are false" for $ 1 \leq k \leq n$ are all true, and all others are false. Now, how since every statement is true or false, we add the number of true statements, which is $n$, to the number of false statements, which is $n$, to get $2n = 100$, so $n = 50$. In other words, "at least $k$ statements are false" for the first $50$ and false for the other $50$.

---

Now, if we had $99$ statements, then the previous logic has a small glitch : $2n = 99$ causes problems. Try to figure out how you would get around this.

Answer 4

For a different perspective, let $c_i$ be a propositional variable that stands for "the $i$-th claim is true," and let $\DeclareMathOperator{\card}{card}\card(l,u)$ stand for "between $l$ and $u$ of the $c_i$ variables are true." Then variant (1) translates into

$$ \bigwedge_{1 \leq i \leq n} c_i \leftrightarrow \card(n-i,n-i) \enspace, $$

while variant(2) translates into

$$ \bigwedge_{1 \leq i \leq n} c_i \leftrightarrow \card(0,n-i) \enspace. $$

Give these formulae to your favorite propositional reasoning tool, and you'll get the conclusions more or less explicitly given in the other answers, for both odd and even values of $n$.

Answer 5

Firstly let's understand what the question is really saying:

-> nth statement in a list of 100 statements state's that "Exactly n statements in this list are false".

so the list looks like this:

exactly 1 statement in this list is false

exactly 2 statement in this list is false

exactly 3 statement in this list is false

              .
              .
              .

exactly 99 statement in this list is false

exactly 100 statement in this list is false

Let's try and think:

if let's say statement '1' is True it states that "exactly 1 statement in this list is false".

Now we wanna know which statement in the list is the above statement talking about. Let's make an assumption that it is talking about 2nd statement which states that "Exactly 2 statements in this list are false".

Now if it is the case, then all other statements must be true hence we have a contradiction as 3rd statement says "exactly 3 are false" whereas 4th says "exactly 4 are false" but it can be only one of them as they use the word "exactly" in them.

The only member of the list that does not produce this contradiction is the 99th statement in this list which states that "exactly 99 statements in this list are false". It doesn't give contradiction as there are no statements left to contradict as only 99th statement remains true.

Hope it clears the confusion. In case of "at least", multiple statements can be true as it is not strict on an exact amount. Like, if the statement "at least 9 statements in this list are false" is true then all the statements 1-9 are true.