The teacher in a certain class room allows you to pass a paper with an assignment around, and whomever it ends up on has to do it. The only two rules are you can't pass it to someone who already has had it and you can only pass it to the person to the left, right, forward, or backward.

In a room of 30 students arranged in a 6 by 5 grid, the teacher starts out with the assignment somewhere on the front row of 6 students. At some point someone is stuck holding the assignment because all his neighbors have had it and passed it on to someone else. If this happens after every student in the room has had it, what is the probablity, for each individual, that he or she turns out to be the lucky winner of the assignment?

(In reply to re: This is very difficult by Tristan)

I disagree with your interpretation of the question. It never says that the assignment is passed to all students, just that the assignment can be passed forwards, backwards, or sideways with an assumed equal probability.

With that in mind there are actually 5 paths each for student 1 and 3 (using the 3x2 grid again) and 4 paths for student 2:

123654
1254
12563
145632
145236

321456
3256
32541
365412
365214

236541
214563
2541
2563

1, 2, and 3 each have a 1/3 chance of being picked as the first student. When student 1 is picked, the assignment will take 1 of 5 paths--2 paths end on student 4, 1 ends on 3, 1 on 2, and 1 on 6. So far, student 4 has a 2/15 chance of being last, and 3, 2, and 6 each have 1/15 chance of being last.

When student 3 is picked as the first student, then student 6 has a 2/15 chance of being last, and students 1, 2, and 4 each have a 1/15 chance of being last.

When student 2 is picked as the first student, then students 1 and 3 each have a 1/6 chance of being last.

When you add them all up you get the fractions I gave in my earlier post.



I think the best way to solve this puzzle with 30 students is to build a traversal tree for each of the 3 students on one side (the other side will have a mirror image tree). The traversal tree would look something like this:

Given the following chart for the 30 students...
<pre>
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
<pre>
We start with student 1, who can brach to 2 students (2, 7)
<pre>
1-+-2
|
+-7
<pre>
Student 2 has two legal branches (3, 8) and 7 also has 2 legal branches (8, 13). We then build on the tree like this:
<pre>
1-+-2-+-3-
| |
| +-8-
|
+-7-+-8-
|
+-13-
<pre>
From this point, path 1-2-3 branches to 4 or 9, path 1-2-8 branches to 7, 9, or 14, path 1-7-8 branches to 2, 9, or 14, and path 1-7-13 branches to 14 or 19.

At some point each path will run out of valid branches, such as path 1-7-13-19-20-26-25. When all the paths are exhausted we count how many times each student is the last in the path and divide by the total number of paths to get each probability.

A computer program which builds traversal trees shouldn't be too terribly difficult to program in order to come up with the answer to this puzzle.
Edited on June 24, 2004, 10:41 pm
Edited on June 24, 2004, 10:43 pm

Posted by Erik O. on 2004-06-24 22:36:32