Logic puzzle with 100 statements

In summary, the conclusion that can be drawn about the truth values of the statements is that some are true and some are false.
  • #1
Mr Davis 97
1,462
44

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?
 
Physics news on Phys.org
  • #2
Mr Davis 97 said:
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?
 
  • #3
haruspex said:
... 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?
 
  • #4
Mr Davis 97 said:
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 ?
 
  • #5
Mr Davis 97 said:
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?
 
  • #6
Stephen Tashi said:
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.

haruspex said:
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.
 
  • #7
Mr Davis 97 said:
"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.
 
  • #8
haruspex said:
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?
 
  • #9
Mr Davis 97 said:
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.
 
  • #10
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?
 
  • #11
Mr Davis 97 said:
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.
 
  • #12
haruspex said:
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?
 
  • #13
Mr Davis 97 said:
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.
 
  • #14
haruspex said:
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?
 
  • #15
Mr Davis 97 said:
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
 
  • #16
haruspex said:
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?
 
  • #17
Mr Davis 97 said:
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?
 
  • Like
Likes Mr Davis 97
  • #18
Mr Davis 97 said:
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 ai=1 if the ith 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.
 
  • #19
haruspex said:
As I mentioned in post #13, an algebraic approach might work.
In the present case, let ai=1 if the ith 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)?
 
  • #20
Mr Davis 97 said:
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.
 

Related to Logic puzzle with 100 statements

1. How do I approach solving a logic puzzle with 100 statements?

The best way to approach solving a logic puzzle with 100 statements is to carefully read and analyze each statement, identifying any logical relationships between them. It may also be helpful to create a chart or diagram to organize the information.

2. Are there any strategies or tips for solving a logic puzzle with 100 statements?

Yes, there are a few strategies that can be helpful when solving a logic puzzle with 100 statements. One approach is to start with the statements that provide the most information and work backwards to fill in the gaps. Another strategy is to look for any statements that contradict each other, as these can often lead to a solution.

3. Can I use a process of elimination to solve a logic puzzle with 100 statements?

Yes, a process of elimination can be a useful strategy when solving a logic puzzle with 100 statements. By ruling out statements that are known to be false or impossible, you can narrow down the possibilities and get closer to a solution.

4. How can I check my solution for a logic puzzle with 100 statements?

Once you have completed a logic puzzle with 100 statements, it is important to double check your solution for accuracy. One way to do this is to go through each statement and make sure it aligns with the information provided in the puzzle. You can also ask someone else to look over your solution to catch any mistakes or errors.

5. Are there any online resources or tools for solving a logic puzzle with 100 statements?

Yes, there are several websites and apps that offer tools and strategies for solving logic puzzles with 100 statements. Some of these resources include step-by-step guides, practice puzzles, and forums where you can discuss and get help with solving difficult puzzles.

Similar threads

Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
3
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
10
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
54
Views
4K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Precalculus Mathematics Homework Help
Replies
1
Views
648
  • Precalculus Mathematics Homework Help
Replies
6
Views
2K
  • Precalculus Mathematics Homework Help
Replies
7
Views
2K
  • Special and General Relativity
Replies
17
Views
669
Back
Top