Logic puzzle with 100 statements

[Mr Davis 97]

Homework Statement

We have 100 statements, where the nth statement says that "exactly n of these statements are false." What conclusions can you draw about the truth values of the statements?

Homework Equations

The Attempt at a Solution

Immediately we see that the 100th statements can't be true, because that leads to a contradiction, since all statements would be false. Statements 1-98 are false because they all imply that there would be more than one statement true. However, only one of the statements can be true at one time (because of the word "exactly"). We have shown that statements 1-98 and 100 are false by contradiction, so that leaves us with statement 99. I am confused about how we "prove" that this statement is true. For all of the others, we assumed that they were true, and this led to a contradiction, so they became false. However, for the 99th statement, if we let it be false, it doesn't seem like a contradiction occurs where it would have to be true. Thus it seems that it can be true or false. How should I be thinking about this in order to give a definite answer to the problem?

 

[haruspex]

for the 99th statement, if we let it be false

... how many would be false in total? How does that affect the truth of other statements?

 

[Mr Davis 97]

... how many would be false in total? How does that affect the truth of other statements?

If 99 other statements were false, and since the 99th statement is false, that would mean that some other statement would have to be true, but no other statement is true, so we have a contradiction. So the 99th statement must be true. Is that the way to go?

 

[Stephen Tashi]

We have 100 statements, where the nth statement says that "exactly n of these statements are false."

What is meant by "these"? If statement 5 says "Exactly 5 of these statements are false", does "these" refer to statements 1 though 5 or to statements 1 through 100 ?

 

[haruspex]

If 99 other statements were false, and since the 99th statement is false, that would mean that some other statement would have to be true,

yes, but specifically which one?

 

[Mr Davis 97]

What is meant by "these"? If statement 5 says "Exactly 5 of these statements are false", does "these" refer to statements 1 though 5 or to statements 1 through 100 ?

"These" refers to all 100 statements.

yes, but specifically which one?

And I'm not sure what you mean. By the 99th statement being false, exactly one statement is true. But it can't be the 99th statement since we let it be false for the sake of contradiction, and it can't be any of the other 99 statements because we showed that they are all already false. Thus there is contradiction and the 99th statement must be true...

When I say "By the 99th statement being false, exactly one statement is true" it just means that no statement is true, which is a contradiction.

 

[haruspex]

"These" refers to all 100 statements.


And I'm not sure what you mean. By the 99th statement being false, exactly one statement is true. But it can't be the 99th statement since we let it be false for the sake of contradiction, and it can't be any of the other 99 statements because we showed that they are all already false. Thus there is contradiction and the 99th statement must be true...

When I say "By the 99th statement being false, exactly one statement is true" it just means that no statement is true, which is a contradiction.

You are right, that works. I was thinking of a slightly different route. If the 99th is false you have all 100 being false, making number 100 true.

 

[Mr Davis 97]

You are right, that works. I was thinking of a slightly different route. If the 99th is false you have all 100 being false, making number 100 true.

Wait, but the 100th statement can't be true because that would imply its falsehood, right? A contradiction?

 

[haruspex]

Wait, but the 100th statement can't be true because that would imply its falsehood, right? A contradiction?

Yes, that was the route I took.

 

[Mr Davis 97]

Okay, so as a final question, I would like to really understand what I have done here. It appears that to find the truth value of a particular statement, I started by assuming that the statement had one value, and derived by contradiction that it must be the other value. Is this a good strategy for these logic puzzles in general? For example, it doesn't seem clear to me how we would show that one of the particular statements is false by proving that it is false directly. It seems that it is always easier to start by assuming that the statement is true (or assuming that a statement is false if it turns out the statement is actually true) and derive a contradiction thus proving that the statement is false (or true). Is this a correct observation?

 

[haruspex]

Okay, so as a final question, I would like to really understand what I have done here. It appears that to find the truth value of a particular statement, I started by assuming that the statement had one value, and derived by contradiction that it must be the other value. Is this a good strategy for these logic puzzles in general? For example, it doesn't seem clear to me how we would show that one of the particular statements is false by proving that it is false directly. It seems that it is always easier to start by assuming that the statement is true (or assuming that a statement is false if it turns out the statement is actually true) and derive a contradiction thus proving that the statement is false (or true). Is this a correct observation?

In this particular puzzle, assuming a particular statement is false still leaves open 99 possibilities for the number true statements, whereas assuming it true tells you much more. So it is natural to try the second option. In other versions it might be better to work the other way.

 

[Mr Davis 97]

In this particular puzzle, assuming a particular statement is false still leaves open 99 possibilities for the number true statements, whereas assuming it true tells you much more. So it is natural to try the second option. In other versions it might be better to work the other way.

Alright. But in general, to determine the truth value of these statements and statements in other logic puzzles, we start by assuming that the statement is either true or false and then working out the consequences?

 

[haruspex]

Alright. But in general, to determine the truth value of these statements and statements in other logic puzzles, we start by assuming that the statement is either true or false and then working out the consequences?

Mostly, yes. There might be rare occasions when an algebraic approach is manageable.
Note that they are very artificial. Self-referential statements are not really allowed in a formal study of logic.

 

[Mr Davis 97]

Mostly, yes. There might be rare occasions when an algebraic approach is manageable.
Note that they are very artificial. Self-referential statements are not really allowed in a formal study of logic.

Also, one more thing. You say that it is more natural, in this particular problem, to start by assuming that a particular statement is true, and then deriving a contradiction. However, would it be possible to start by taking one of the 100 statements, assume that it is false, and work out the consequences to solve the problem from there?

 

[haruspex]

Also, one more thing. You say that it is more natural, in this particular problem, to start by assuming that a particular statement is true, and then deriving a contradiction. However, would it be possible to start by taking one of the 100 statements, assume that it is false, and work out the consequences to solve the problem from there?

Yes, but you might have to stack up a whole sequence of suppose this is false and this is false and ... Induction might be another way

 

[Mr Davis 97]

Yes, but you might have to stack up a whole sequence of suppose this is false and this is false and ... Induction might be another way

Okay. And also, and this is truly the final thing, is there a way to logically solve this particular problem without starting by making an assumption that a statement is either true or false? Is there some other way to determine whether one of the 100 statements is either true or false?

 

[LCKurtz]

Okay. And also, and this is truly the final thing, is there a way to logically solve this particular problem without starting by making an assumption that a statement is either true or false? Is there some other way to determine whether one of the 100 statements is either true or false?

Putting it all together, how about:
1. There can't be more than 1 true. (Obvious)
2. They can't all be false. (Then statement 100 must be true, contradiction).
3. Therefore there must be exactly 1 true, meaning 99 are false and statement 99 is true.
Is that what you are looking for?

 

[haruspex]

Okay. And also, and this is truly the final thing, is there a way to logically solve this particular problem without starting by making an assumption that a statement is either true or false? Is there some other way to determine whether one of the 100 statements is either true or false?

As I mentioned in post #13, an algebraic approach might work.
In the present case, let a_i=1 if the i^th statement is true, 0 otherwise. Then we can express the given facts as $((\Sigma_1^na_i)-n+r)a_r=0$ for all r.
This looks unpromising, not least because it loses the constraint that all the values must be 0 or 1.
Perhaps the simplest line on the given problem is: no two statements agree, so at most one is true, so at least 99 are false. It remains to check whether the 99th or 100th might be true.

 

[Mr Davis 97]

As I mentioned in post #13, an algebraic approach might work.
In the present case, let a_i=1 if the i^th statement is true, 0 otherwise. Then we can express the given facts as $((\Sigma_1^na_i)-n+r)a_r=0$ for all r.
This looks unpromising, not least because it loses the constraint that all the values must be 0 or 1.
Perhaps the simplest line on the given problem is: no two statements agree, so at most one is true, so at least 99 are false. It remains to check whether the 99th or 100th might be true.

And what procedures does one go through in order to determine whether the 99th statement or the 100th statement are true (just for clarification)?

 

[haruspex]

And what procedures does one go through in order to determine whether the 99th statement or the 100th statement are true (just for clarification)?

I really don't think there's anything better than your original approach, plus what you found in post #3.
We've done this one to death.