1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Logic puzzle with 100 statements

  1. Nov 21, 2016 #1
    1. The problem statement, all variables and given/known data
    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?

    2. Relevant equations


    3. 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?
     
  2. jcsd
  3. Nov 21, 2016 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    ... how many would be false in total? How does that affect the truth of other statements?
     
  4. Nov 21, 2016 #3
    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?
     
  5. Nov 21, 2016 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    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 ?
     
  6. Nov 21, 2016 #5

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    yes, but specifically which one?
     
  7. Nov 21, 2016 #6
    "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.
     
  8. Nov 21, 2016 #7

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  9. Nov 21, 2016 #8
    Wait, but the 100th statement can't be true because that would imply its falsehood, right? A contradiction?
     
  10. Nov 21, 2016 #9

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes, that was the route I took.
     
  11. Nov 21, 2016 #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?
     
  12. Nov 21, 2016 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  13. Nov 21, 2016 #12
    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?
     
  14. Nov 22, 2016 #13

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  15. Nov 22, 2016 #14
    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?
     
  16. Nov 22, 2016 #15

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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
     
  17. Nov 23, 2016 #16
    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?
     
  18. Nov 23, 2016 #17

    LCKurtz

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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?
     
  19. Nov 23, 2016 #18

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
  20. Nov 25, 2016 #19
    And what procedures does one go through in order to determine whether the 99th statement or the 100th statement are true (just for clarification)?
     
  21. Nov 25, 2016 #20

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Logic puzzle with 100 statements
Loading...