Application Center - Maplesoft

App Preview:

The Drunk Student Problem

You can switch back to the summary page by clicking here.

Learn about Maple
Download Application


 

 

 

 

 

 

 

      Image 

 

 

The Drunk Student Problem 

 

 

The following was implemented in Maple by Marcus Davidsson (2009)

davidsson_marcus@hotmail.com  The original problem can be found here:

http://www.math.leidenuniv.nl/~naw/home/ps/pdf/2005-2.pdf
 

 

 

 

 

 

 

 

The problem formulation is as follows: 

 

 

 

"A student association organizes a large-scale dinner for 128 students. The chairsare numbered 1 through 128. The students are also assigned a number between1 and 128. As the students come into the room one by one, they must sit attheir assigned seat. However, 1 of the students is so drunk that he can?t findhis seat and takes an arbitrary one. Any sober student who comes in and findshis seat taken also takes an arbitrary one. The drunken student is one of thefirst 64 students. What is the probability that the last student gets to sit in thechair assigned to him?" 

 

 

 

 

We can start by considering a general case where we have 30 students.  

 

 

The effect of a drunk student random selection on the sequential students can be seen below. 

 

 

 






































 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Typesetting:-mprintslash([`assign`(DR, 9)], [9])
Typesetting:-mprintslash([`assign`(DRS, 21)], [21])
ChairsTaken = []
ChairsAvailable = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsAvailable = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1]
ChairsAvailable = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2]
ChairsAvailable = [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3]
ChairsAvailable = [4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4]
ChairsAvailable = [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5]
ChairsAvailable = [6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6]
ChairsAvailable = [7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7]
ChairsAvailable = [8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8]
ChairsAvailable = [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21]
ChairsAvailable = [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10]
ChairsAvailable = [9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11]
ChairsAvailable = [9, 12, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12]
ChairsAvailable = [9, 13, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13]
ChairsAvailable = [9, 14, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14]
ChairsAvailable = [9, 15, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15]
ChairsAvailable = [9, 16, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16]
ChairsAvailable = [9, 17, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17]
ChairsAvailable = [9, 18, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18]
ChairsAvailable = [9, 19, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
ChairsAvailable = [9, 20, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
ChairsAvailable = [9, 22, 23, 24, 25, 26, 27, 28, 29, 30]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30]
ChairsAvailable = [9, 22, 23, 24, 25, 26, 27, 28, 29]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 22]
ChairsAvailable = [9, 23, 24, 25, 26, 27, 28, 29]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 22, 23]
ChairsAvailable = [9, 24, 25, 26, 27, 28, 29]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 22, 23, 24]
ChairsAvailable = [9, 25, 26, 27, 28, 29]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 22, 23, 24, 25]
ChairsAvailable = [9, 26, 27, 28, 29]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 22, 23, 24, 25, 26]
ChairsAvailable = [9, 27, 28, 29]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 22, 23, 24, 25, 26, 27]
ChairsAvailable = [9, 28, 29]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 22, 23, 24, 25, 26, 27, 28]
ChairsAvailable = [9, 29]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 22, 23, 24, 25, 26, 27, 28, 29]
ChairsAvailable = [9]
ChairsTaken = [1, 2, 3, 4, 5, 6, 7, 8, 21, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 30, 22, 23, 24, 25, 26, 27, 28, 29, 9]
ChairsAvailable = [] (1)
 

 

 

 

 

Note that we assume that the drunk student can be anyone of the students but the drunk student 

 

can only select a chair which has a number that is equal to or greater than his allocated queue number

ie all student are queuing to enter the dining room and the drunk student cannot force his way forward in the queue.  

 

 

 

 

 

We can also look at the number of students that are forced to change seats due to the drunk

student random selection process.  

 

 

  1) Shuffle Drunk Student       2) Open the Dining Room             Embedded component 


Students Queue  = Embedded component
Chairs Taken =       Embedded component 

Chairs Available =  Embedded component 


Embedded component 

 

 

 

 

 

 

We can also do some further simulation as follows:
 

 

 






































 

Plot_2d  
 

 

 

 

 

 

 

We can now try to answer the specific question in the problem formulation: 

 

 

 

"There are 128 students. The drunk student is one of the first 64 students, 

 

What is the probability that the last student gets his assigned seat ? " 

 

 

 

as follows: 

 

 

 

 























































 

 

 

 

 

`Probability Last Student Same Chair` = .49200
`Probability Last Student Not Same Chair` = .50800
Plot_2d  
 

 



We can see that the probability that the last student gets his assigned seat is approximately 0.5.