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?
Here's a simulation program
DEFLNG AZ
RANDOMIZE TIMER
DO
REDIM student(6, 7)' unused elements outside bound
f = INT(RND(1) * 6 + 1)
student(1, f) = 1
row = 1: col = f
FOR pass = 2 TO 30
DO
DO
dr = INT(RND(1) * 3  1)
dc = INT(RND(1) * 3  1)
LOOP UNTIL (dr <> 0 OR dc <> 0) AND (dr = 0 OR dc = 0) AND ABS(dr) <= 1 AND ABS(dc) <= 1
newRow = row + dr: newCol = col + dc
LOOP UNTIL newRow > 0 AND newRow < 6 AND newCol > 0 AND newCol < 7 AND student(newRow, newCol) = 0
row = newRow: col = newCol
p = pass
surr = 1
FOR dr = 1 TO 1
FOR dc = 1 TO 1
IF (dr <> 0 OR dc <> 0) AND (dr = 0 OR dc = 0) THEN
newRow = row + dr: newCol = col + dc
IF newRow > 0 AND newRow < 6 AND newCol > 0 AND newCol < 7 THEN
IF student(newRow, newCol) = 0 THEN
surr = 0: EXIT FOR
END IF
END IF
END IF
NEXT
IF surr = 0 THEN EXIT FOR
NEXT
IF surr THEN EXIT FOR
student(row, col) = 1
NEXT
IF p = 30 THEN
tot(row, col) = tot(row, col) + 1
fCount = fCount + 1
PRINT row, col, fCount, tr
END IF
tr = tr + 1
LOOP UNTIL fCount = 10000
FOR row = 1 TO 5
FOR col = 1 TO 6
PRINT USING "#####"; tot(row, col);
NEXT
PRINT
NEXT
PRINT
FOR row = 1 TO 5
FOR col = 1 TO 3
PRINT USING "#####"; tot(row, col) + tot(row, 7  col);
NEXT
PRINT
NEXT
PRINT
PRINT fCount, tr
PRINT
It produces:
628 176 402 321 225 788
244 470 273 304 305 306
418 178 500 193 192 322
98 453 257 321 529 177
566 48 258 128 180 740
1416 401 723
550 775 577
740 370 693
275 982 578
1306 228 386
10000 1649473
indicating that it toook 1,649,473 trials to get 10,000 in which all the students had handled the paper.
The first output grid shows the number of times the particular row and column ended up with the paper. But some of the leftright asymmetries are glaring. Even though I had distributed the teacher's choice evenly among all 6 frontrow students, and did not prefer any direction of passing over any other, some symmetrically opposite seats appear glaringly different, like 500 and 193, or 48 and 180.
The second output grid shows the first three columns with each number enhanced by the corresponding symmetrically opposite total, on the assumption that they really have the same probability each. But I'm worried about why the asymmetry comes up as much as it does.

Posted by Charlie
on 20040624 15:34:06 