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 A-Z
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 left-right asymmetries are glaring.  Even though I had distributed the teacher's choice evenly among all 6 front-row 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 2004-06-24 15:34:06