Mathematical Induction

  1. Galileo

    Galileo 1,999
    Science Advisor
    Homework Helper

    Here's an unsolved problem I found in my Algebra book.
    See if you can spot where the error in reasoning lies:

    A serial killer is sentenced to be executed.
    He asks the judge not to let him know the day of the exectuion.
    The judge says: "I sentence you to be executed at 10 A.M. some
    day of this coming January, but I promise that you will not be aware
    that you are being executed that day untill they come to get you
    at 8 A.M." The killer goes to his cell and proceeds to prove, as follows,
    that he can't be executed in January.

    Let P(n) be the statement that I can't be executed on January (31-n).
    I want to prove P(n) for [itex]0 \leq n \leq 30[/itex]. Now I can't be
    executed on January 31, for since that is the last day of the month
    and I am to be executed that month, I would know that was the day
    before 8 A.M. (when they wouldn'y come to get me), contrary to the judge's sentence. Thus P(0) is true.
    Suppose that P(m) is true for [itex]0\leq m \leq k[/itex], where [itex]k\leq 29[/itex]. That is, suppose I can't be executed on January (31-k) through
    January 31. Then January (31-k-1) must be the last possible day for
    execution, and I would be aware that was the day before 8 A.M. contrary
    to the judge's sentence. Thus I can't be executed on January (31-(k+1)),
    so P(k+1) is true. Therefore I can't be executed in January.
    (Of course, the serial killer was executed on January 17.)
     
  2. jcsd
  3. NateTG

    NateTG 2,537
    Science Advisor
    Homework Helper

    If we allow for the possibility of no execution at all in January, then the entire argument fails, since on Jan 31, the serial killer still isn't sure.
     
  4. marcus

    marcus 24,894
    Science Advisor
    Gold Member
    2014 Award

    Galileo I believe that the error in reasoning is with the Judge!
    He cannot logically make such a promise to the prisoner.

    (in my humble opinion and with all due respect for the Judge)

    (also I believe that in Netherlands there is no capital punishment so
    how do you have it in your Algebra book?)
     
  5. Galileo

    Galileo 1,999
    Science Advisor
    Homework Helper

    Hehe, sounds like the logic beat common sense. There goes the system :rofl:

    The error in reasoning (if there is one) is definitely in the induction step.
    His claim that he cannot be executed on Januray 31 is true. But saying
    that he would know on January 29 that he would be executed
    on January 30 because it cannot happen on January 31 sounds fishy.
    Sounds like he's reasoning backward in time or something :confused:

    You see, the whole reason why we can't execute people is because of
    this paradox. It's in the book to convince us of how right our our system is :rofl: :rofl:

    Ok, just kidding. There are no good dutch books on mathematics in existence. Everyone here uses books that are written in english.
    This problem is from 'Linear Algebra' by Fraleigh and Beauregard.
     
  6. The basic problem is P(n) is a time dependent statement. Say it's 7:00 AM, 30 January. The killer knows they will either kill him today or tomorrow. So basically P(0) and P(1) can't be decided until 8:00 AM ON THAT DATE. Thus, the whole argument is flawed. In other words, the killer can say P(0) is true only after they didn't kill him/her on 30 January.
     
  7. marcus

    marcus 24,894
    Science Advisor
    Gold Member
    2014 Award

    the logic would be the same if the month of January had 2 days instead of 31. Indeed maybe in ancient times the fierce Dutch tribes dwelling in the marshlands and forest of Holland DID have exactly 2 days in their month of January. (It was because they had difficulty counting beyond this number.)

    So the judge told the prisoner "I promise they will come to get you at 8AM either Jan 1 or Jan 2 and that you will not know beforehand (at 7:30 AM or anytime before they appear) that they are coming that day."

    The judge has made a mistake and he cannot make good on his promise.

    This was also true among the ancient Swedes, whose month of January had always exactly 3 days.
     
  8. Galileo

    Galileo 1,999
    Science Advisor
    Homework Helper

    Hmmm. Not entirely convincing. He's simply reasoning by contradiction:
    "Suppose I will be executed on the 31st. Then I won't be picked up the 30th
    thus I would know in advance, so I can't be executed the 31st."
    He can make that conclusion beforehand.

    Although time dependancy does seem to play a role.
     
  9. Unfortunate assumption .... he thinks he will survive till jan 30 .... so his P(0) fails. (hmm what an example of circular induction :rolleyes: )
     
  10. Galileo

    Galileo 1,999
    Science Advisor
    Homework Helper

    Why can he not assume that? His supposition is that he will be executed on January 31. Then ofcourse he won't be executed on the other days so he'll survive 'till Jan 30.

    I really can't find any error in his logic. (That doesn't mean there isn't one)
     
  11. You are using P(1) to prove P(0) and this is wrong. What you are basically saying is: "Suppose P(0) = F. P(1) = T, therefore P(0) = T." Are you convinced?
     
  12. Galileo

    Galileo 1,999
    Science Advisor
    Homework Helper

    Yes :smile:

    For P(k) to be true P(m) must be true for m>k. The reasoning is indeed circular.
    Thanks :approve:
     
  13. NateTG

    NateTG 2,537
    Science Advisor
    Homework Helper

    Huh? How do you come up with any circularity. The argument the prisoner makes is not circular, and the induction is quite valid.

    In the scenario, either the judge is fallible, or the situation is self-contradictory. At that point, either the Judge's statement is invalid, or LEM does not apply.

    Let's make this a bit simpler:

    If Judge says "You will be executed tomorrow, but you won't know that you'll be executed tomorrow until they come and get you." That the statement is self-contradictory is rather obvious.
     
  14. ok i need to run to college now so i will finish this up pretty fast.

    first of all the person is assuming that he will survive till jan 30. Then using this he proves that he wont be killed on jan 31 then he uses this to prove that he wont be killed on jan 30.

    so what he has done is,
    "Question:Prove that chickens don't fly?
    Answer:Assume chickens don't fly. Since chickens don't fly QED..."
    if u think that this proof is valid, then u live in an axiomatic system way different than mine :p :D
     
  15. agreed

    This prisoner is making an assumption on a previous assumption. Even if (s)he made it to the 29th, (s)he wouldn't know if they were going to kill him/her tomorrow or the day after until 8 am on the 30th.

    This is more noticable when you say you have 10 days left. Will the prisoner die tomorrow? 3 days?

    Obviously, the prisoner did not expect to die on the 17th, yet it happened.
     
    Last edited: Aug 4, 2004
  16. NateTG

    NateTG 2,537
    Science Advisor
    Homework Helper

    No, what's going on is essentially the following:

    The judge says: 0=1.

    The prisoner says:
    The Judge knows what he's talking about so 0=1.
    Now assume (by contradiction) that I will be killed.
    But we know that 1!=0 so the assumption must be false.
    Therefore I will not be killed.
     
  17. Gokul43201

    Gokul43201 11,141
    Staff Emeritus
    Science Advisor
    Gold Member

    <recovering from severe blow to head > Whaa ??? :confused:
     
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?