My Math Forum The absent minded professor

 Probability and Statistics Basic Probability and Statistics Math Forum

 July 23rd, 2017, 07:48 PM #1 Math Team     Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 233 The absent minded professor Greetings MMF members and guests! 1 physicist and 99 mathematicians are to board a 100 seater jet liner. The physicist boards first but has lost his boarding pass. Being an absent minded professor , naturally he has forgotten the number of his assigned seat. In an icredible stroke of genius , he decides to sit in a random seat. One by one the mathematicians board , each taking his/her assigned seat if it is available , if his/her seat is already taken , he/she sits in a random available seat. What is the probably that the last mathematician to board will sit in his/her assigned seat ? Thanks from jks, 123qwerty and Joppy
 July 25th, 2017, 02:17 AM #2 Math Team     Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 233 The question seems to defy our intuition yet has a simple answer if you think about it in the right way. Hint:Ask yourself , is seat number 53 available to the last mathematician? Then generalize... Thanks from Joppy
 July 27th, 2017, 11:26 PM #3 Math Team     Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 233 Well it's been a few days and no one has posted an attempt so I will give the solution. The probability that the last mathematician will have his assigned seat available is $\ \ \frac{1}{2}$ First regarding the hint , seat number 53 cannot be available unless it is assigned to the last mathematician or it is assigned to the physicist because it will be taken at random or the passenger who is assigned seat number 53 will take it since passengers take their seat one at a time and he is last to be seated. This generalizes to every seat number. The only possible seats available to the last mathematician are the physicist's assigned seat or his assigned seat (whatever that may be) Now , does that mean that the probability of availabilty for the physicist's assigned seat and his assigned seat is $\ \frac{1}{2} \ \$ each? Not necessarily but it is true in this case because each seat has been treated the same by every passenger. Here is a youtube link where I saw this problem , I changed the wording a little and attempted to give a bit more details , hope I didn't mess it up. http://www.google.com/url?q=https://...FtPHS3BWzojX7g It is worth it to look at this presentation by Peter Winkler at MOMATH , there are quite a nice variety of interesting problems discussed. Let me know if the link functions and/or if you would like further discussion about this problem. Thanks from 123qwerty and Joppy Last edited by agentredlum; July 27th, 2017 at 11:52 PM.
July 27th, 2017, 11:49 PM   #4
Senior Member

Joined: Feb 2016
From: Australia

Posts: 1,354
Thanks: 464

Math Focus: Yet to find out.
Quote:
 Originally Posted by agentredlum Well it's been a few days and no one has posted an attempt so I will give the solution.
You should have answered this post and then continued the story! Maybe all the mathematicians on the plane are flying out for Wu Gangs funeral .

July 28th, 2017, 12:02 AM   #5
Math Team

Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

Quote:
 Originally Posted by Joppy You should have answered this post and then continued the story! Maybe all the mathematicians on the plane are flying out for Wu Gangs funeral .
You are right!

Unfortunately I could not solve that problem.

By the way I edited the answer post to increase clarity , these questions are tricky in their wording ... In the answer I had the physicist assigned seat #1 but that's not necessarily the case , he boards first ... which can easily confuse someone into thinking his assigned seat is #1

 July 28th, 2017, 02:35 AM #6 Senior Member   Joined: Dec 2012 From: Hong Kong Posts: 853 Thanks: 311 Math Focus: Stochastic processes, statistical inference, data mining, computational linguistics Haha, I'll probably have to post the solution to my problem later then XD But after I attempt agent's. I was going to do this over the weekend! Now I've seen the answer, but I haven't read the detailed solution yet Thanks from agentredlum and Joppy
July 28th, 2017, 08:04 PM   #7
Senior Member

Joined: Jul 2012
From: DFW Area

Posts: 603
Thanks: 83

Math Focus: Electrical Engineering Applications
Well shoot, I've been working on the problem computationally, and I was trying to understand the answer a little more before I posted it. Oh well, I kind of cheated anyway by using a computer and by not following the line of reasoning given in the hint.

However, I do think that I have additional apparent information. I say "apparent" because I see the results computationally for $n<<100$, but of course I have not proven that it scales up to large $n$.

First of all, I did watch the video (the problem starts at 9:40), and the speaker's explanation (as well as the one given in agentredlum's post) are quite clear now but I just wasn't getting it. I guess I don't think like a mathematician and I was making the problem more complicated as explained below.

Quote:
 In the answer I had the physicist assigned seat #1 but that's not necessarily the case , he boards first ... which can easily confuse someone into thinking his assigned seat is #1
On the other hand, maybe I do think a little like a mathematician. For ease, in my program, I always assigned seat 0 to the physicist, 1 to the first mathematician, 2 to the second mathematician, etc., to 99 for the 99th mathematician. I then used random numbers to choose the seats for each passenger if their seat was taken. Each seat is treated the same, similar to how it was explained in the video (and the assigned seat numbers were similar in the explanation, I think).

So what do I think I found? I think that I found that there are a total of $2^{n-1}$ possibilities. Furthermore, I think this number can be broken down into the following number of possibilities depending on which seat $(0 \text{ to } n-1)$ the physicist chooses:

$\displaystyle \large {\begin{array}{|c|c|} \hline \text{Seat Taken by Phys} & \text{# of Possibilities} \\ \hline 0 & 1 \\ \hline 1 & 2^{n-2} \\ \hline 2 & 2^{n-3} \\ \vdots & \vdots \\ n-2 & 2 \\ \hline n-1 & 1 \\ \hline \end {array}}$

For example, the (sorted) possibilities for $n=6$, followed by the number of possibilities are given below:

Code:
[0, 1, 2, 3, 4, 5]
[1, 0, 2, 3, 4, 5]
[1, 2, 0, 3, 4, 5]
[1, 2, 3, 0, 4, 5]
[1, 2, 3, 4, 0, 5]
[1, 2, 3, 4, 5, 0]
[1, 2, 3, 5, 4, 0]
[1, 2, 4, 3, 0, 5]
[1, 2, 4, 3, 5, 0]
[1, 2, 5, 3, 4, 0]
[1, 3, 2, 0, 4, 5]
[1, 3, 2, 4, 0, 5]
[1, 3, 2, 4, 5, 0]
[1, 3, 2, 5, 4, 0]
[1, 4, 2, 3, 0, 5]
[1, 4, 2, 3, 5, 0]
[1, 5, 2, 3, 4, 0]
[2, 1, 0, 3, 4, 5]
[2, 1, 3, 0, 4, 5]
[2, 1, 3, 4, 0, 5]
[2, 1, 3, 4, 5, 0]
[2, 1, 3, 5, 4, 0]
[2, 1, 4, 3, 0, 5]
[2, 1, 4, 3, 5, 0]
[2, 1, 5, 3, 4, 0]
[3, 1, 2, 0, 4, 5]
[3, 1, 2, 4, 0, 5]
[3, 1, 2, 4, 5, 0]
[3, 1, 2, 5, 4, 0]
[4, 1, 2, 3, 0, 5]
[4, 1, 2, 3, 5, 0]
[5, 1, 2, 3, 4, 0]
32
The probability of the physicist taking any seat number is the same as that of him/her taking any other seat number. It also seems that since for any given seat number that the physicist takes, the probabilities of all of the possibilities are equal since the last passenger gets either their assigned seat or the physicist's, 50% - 50%. I have obviously made figuring out the solution much more complicated than the simple explanation. But for n=100 there appear to be $2^{99}$ possibilities!

Furthermore, I think that the table "ladders down". For example, if you look at the list of possibilities given above, if the physicist chooses seat 1, there is one possibility if the first mathematician chooses the physicist's seat, 8 possibilities if seat 2 is chosen, etc. This continues to "ladder down" if the physicist chooses seat 2, etc. Well, at least I think so because I just noticed this as I was writing this post.

I have run many simulations (about 2 million) with $n=100$ and the probability is very close to 50% as expected. Of course, I will post the Ruby programs (one shows arrays, the other one doesn't) if requested.

 July 29th, 2017, 12:56 AM #8 Math Team     Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 233 I applaud your efforts jks , post the programs , they may be helpful to someone. In my opinion , I don't think you cheated. You used experimental mathematics , on youtube if you search experimental mathematics you will find some very clever mathematicians who post 20 minute videos (mostly number theoretic). In 2 videos guest speaker was N.J.A. Sloane , he is the founder of OEIS and he presented some of his favorite sequences published in the OEIS. Professor Winkler had time constraints and was not reading from a script so I can't fault him for being a bit confusing but I do believe he got most of the main ideas out clearly. Glad someone enjoyed his presentation Among other things , I learned how to pass a cube through a hole in a smaller cube , how to beat Roger Federrer in a Wimbledon final and how to leave Las Vegas with a small fortune. <--(Go to Vegas with a large fortune and quit early) Got more than a few chuckles watching his presentation jks wrote , (and the assigned seat numbers were similar in the -agentredlum- explanation, I think) You are correct in your doubt , I now realise my explanation about how the seats were treated could have been better. I should have said that the physicists assigned seat and the last mathematicians assigned seat had been treated the same by every passenger. (I said 'each seat has been treated the same by every passenger' which is incorrect I think) I apologise for posting the solution too quickly , next time I will ask if anyone needs more time. Last edited by agentredlum; July 29th, 2017 at 01:35 AM.
July 29th, 2017, 09:54 PM   #9
Senior Member

Joined: Jul 2012
From: DFW Area

Posts: 603
Thanks: 83

Math Focus: Electrical Engineering Applications
Thanks agentredlum,

Quote:
 I apologise for posting the solution too quickly , next time I will ask if anyone needs more time.
No problem, in fact in this case it probably worked out for the best since you posted the answer and the easy way to think about the problem in order to arrive at the answer. Otherwise, I probably would have posted a ridiculously long answer that may have driven some people away.

Quote:
 I now realise my explanation about how the seats were treated could have been better.
Your explanation was fine, I had no trouble understanding either you or Professor Winkler.

Quote:
 In 2 videos guest speaker was N.J.A. Sloane , he is the founder of OEIS and he presented some of his favorite sequences published in the OEIS.
I will have to look up those videos as I am interested in what his favorites are. By the way, the whole "apparent" thing in my post is there because of an OEIS rule. I'm sure that you know, but others may not, that for a formula in an OEIS entry, if there is no known proof that the formula is correct (for example, there are only a few terms and the formula fits), the author of the formula has to state "It appears that" and then give the formula.

Quote:
 post the programs , they may be helpful to someone.
The programs are posted below. The first one is used to calculate the probability for a large number of tries. The second one is used to give the number of unique arrays (rather intelligently) for small NUM_SEATS.

Code:
# phys seat is 0, mathms seats are their index.

NUM_SEATS = 100

class Array
def add_seat(ind)                                    # sub that gets seat if not taken or random seat if taken.
if !self.include?(ind)                              # get own seat if available.
self << ind
return self
end

rnd = self.first                                       # otherwise get random seat.
while self.include?(rnd)                          # loop until find one not taken.
rnd = rand(NUM_SEATS)                    # somewhat inefficient but works surprisingly well.
end
self << rnd
self
end
end

num_tries = 100000

last_seat_count = 0
num_tries.times do
seats = [rand(NUM_SEATS)]                              # start seats array with physicist's seat.
(NUM_SEATS - 1).times{|ind| seats.add_seat(ind + 1)}   # ind + 1 is same as each mathametician's seat (ind starts at 0).
last_seat_count += 1 if seats[NUM_SEATS - 1] == NUM_SEATS - 1
# p seats                                                          # uncomment to see seats array (make NUM_SEATS=100 or so).
end

p NUM_SEATS
p num_tries
p last_seat_count.to_f/num_tries.to_f
Code:
# finds all and shows arrays. only works for small NUM_SEATS.

# phys seat is 0, mathms seats are their index.

NUM_SEATS = 6

class Array
def add_seat(ind)                                      # sub that gets seat if not taken or random seat if taken.
if !self.include?(ind)                                 # get own seat if available.
self << ind
return self
end

rnd = self.first                                         # otherwise get random seat.
while self.include?(rnd)                            # loop until find one not taken.
rnd = rand(NUM_SEATS)                       # somewhat inefficient but works surprisingly well.
end
self << rnd
self
end
end

num_tries = 10000

all_arrays = []
last_seat_count = 0
num_tries.times do
seats = [rand(NUM_SEATS)]                              # start seats array with physicist's seat.
(NUM_SEATS - 1).times{|ind| seats.add_seat(ind + 1)}   # ind + 1 is same as each mathametician's seat (ind starts at 0).
last_seat_count += 1 if seats[NUM_SEATS - 1] == NUM_SEATS - 1
all_arrays << seats
all_arrays.uniq!                                                # get rid of duplicates.
end

all_arrays.sort.each{|arr| p arr}                        # sort and print arrays.
p all_arrays.length                                            # and length.
puts
p NUM_SEATS
p num_tries
p last_seat_count.to_f/num_tries.to_f

 July 29th, 2017, 10:40 PM #10 Math Team     Joined: Jul 2011 From: North America, 42nd parallel Posts: 3,372 Thanks: 233 Yesternight I looked up experimental mathematics on youtube and noticed Mr. Sloane in at least 4 presentations regarding sequences in the OEIS. He even offered to pay people to help him in a research project about a particular sequence and the offer was also extended to anyone watching !!! I'm going to look for that youtube video now and post the name of it. Here is the link , Mr. Sloane is the first presenter. At time index 8:40 he mentions he is looking to hire 2 or 3 people to help him investigate 'Lucky Numbers'. That was for last summer 2016 so I don't know how far he got with that. http://www.google.com/url?q=https://...t8Dy2SiP5xzZlw Here is the 'Lucky Numbers' sequence he was referring to https://oeis.org/A000959 He explains how to generate the sequence of 'Lucky Numbers' in his presentation , easy to understand , simple to generate and in my opinion a very interesting sequence. Thanks from jks Last edited by agentredlum; July 29th, 2017 at 11:26 PM.

 Tags absent, minded, professor

### i have math formula to win baccarat

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post ungeheuer Computer Science 0 April 13th, 2014 05:05 AM shunya Algebra 3 January 22nd, 2014 08:10 AM ars111 New Users 10 December 28th, 2011 12:01 PM gezelligtexas Advanced Statistics 5 August 11th, 2007 02:57 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top