My Math Forum  

Go Back   My Math Forum > High School Math Forum > Probability and Statistics

Probability and Statistics Basic Probability and Statistics Math Forum


Thanks Tree15Thanks
Reply
 
LinkBack Thread Tools Display Modes
July 23rd, 2017, 08:48 PM   #1
Math Team
 
agentredlum's Avatar
 
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
agentredlum is offline  
 
July 25th, 2017, 03:17 AM   #2
Math Team
 
agentredlum's Avatar
 
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
agentredlum is offline  
July 28th, 2017, 12:26 AM   #3
Math Team
 
agentredlum's Avatar
 
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 28th, 2017 at 12:52 AM.
agentredlum is offline  
July 28th, 2017, 12:49 AM   #4
Senior Member
 
Joined: Feb 2016
From: Australia

Posts: 1,460
Thanks: 489

Math Focus: Yet to find out.
Quote:
Originally Posted by agentredlum View Post
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 .
Thanks from agentredlum and 123qwerty
Joppy is offline  
July 28th, 2017, 01:02 AM   #5
Math Team
 
agentredlum's Avatar
 
Joined: Jul 2011
From: North America, 42nd parallel

Posts: 3,372
Thanks: 233

Quote:
Originally Posted by Joppy View Post
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

Thanks from Joppy
agentredlum is offline  
July 28th, 2017, 03: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
123qwerty is offline  
July 28th, 2017, 09:04 PM   #7
jks
Senior Member
 
jks's Avatar
 
Joined: Jul 2012
From: DFW Area

Posts: 607
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.
Thanks from agentredlum
jks is offline  
July 29th, 2017, 01:56 AM   #8
Math Team
 
agentredlum's Avatar
 
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 02:35 AM.
agentredlum is offline  
July 29th, 2017, 10:54 PM   #9
jks
Senior Member
 
jks's Avatar
 
Joined: Jul 2012
From: DFW Area

Posts: 607
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
Thanks from agentredlum and CharlesGBuick
jks is offline  
July 29th, 2017, 11:40 PM   #10
Math Team
 
agentredlum's Avatar
 
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 30th, 2017 at 12:26 AM.
agentredlum is offline  
Reply

  My Math Forum > High School Math Forum > Probability and Statistics

Tags
absent, minded, professor



Search tags for this page
Click on a term to search for related topics.
Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Which professor has biggest number of students?/sql ungeheuer Computer Science 0 April 13th, 2014 06:05 AM
absent-minded bank teller shunya Algebra 3 January 22nd, 2014 09:10 AM
Hi! I'm professor from Brazil... ars111 New Users 10 December 28th, 2011 01:01 PM
A question for math-minded folks gezelligtexas Advanced Statistics 5 August 11th, 2007 03:57 PM





Copyright © 2017 My Math Forum. All rights reserved.