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.
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.
Students Queue = Chairs Taken =
Chairs Available =
We can also do some further simulation as follows:
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:
We can see that the probability that the last student gets his assigned seat is approximately 0.5.
