Register to reply 
Mathematical Induction 
Share this thread: 
#1
Jul2904, 04:43 AM

Sci Advisor
HW Helper
P: 2,002

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 (31n). 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 (31k) through January 31. Then January (31k1) 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
Jul2904, 12:54 PM

Sci Advisor
HW Helper
P: 2,537

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.



#3
Jul2904, 03:12 PM

Astronomy
Sci Advisor
PF Gold
P: 23,271

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?) 


#4
Jul2904, 04:02 PM

Sci Advisor
HW Helper
P: 2,002

Mathematical Induction
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 this paradox. It's in the book to convince us of how right our our system is 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. 


#5
Jul2904, 06:20 PM

P: 1,367

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.



#6
Jul2904, 06:47 PM

Astronomy
Sci Advisor
PF Gold
P: 23,271

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. 


#7
Jul3004, 02:56 AM

Sci Advisor
HW Helper
P: 2,002

"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. 


#8
Jul3104, 09:38 AM

P: 646




#9
Jul3104, 01:44 PM

Sci Advisor
HW Helper
P: 2,002

I really can't find any error in his logic. (That doesn't mean there isn't one) 


#10
Jul3104, 05:43 PM

P: 1,367




#11
Aug104, 03:26 AM

Sci Advisor
HW Helper
P: 2,002

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


#12
Aug204, 12:49 PM

Sci Advisor
HW Helper
P: 2,537

In the scenario, either the judge is fallible, or the situation is selfcontradictory. 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 selfcontradictory is rather obvious. 


#13
Aug204, 09:26 PM

P: 646

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 


#14
Aug304, 10:03 PM

P: 83

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. 


#15
Aug504, 12:38 PM

Sci Advisor
HW Helper
P: 2,537

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. 


Register to reply 
Related Discussions  
Mathematical induction  Math & Science Software  2  
Mathematical Induction  Math & Science Software  3  
Mathematical Induction  Math & Science Software  4  
Mathematical Induction  Math & Science Software  9  
Mathematical induction  Math & Science Software  2 