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?

I went to http://www.random.org/ and downloaded two ten meg files and concatenated them to get a stream of over 160,000,000 random bits.  Indeed the randomization is better than provided by the basic RND function.  I get:

 686  243  357  377  276  726
 176  494  300  259  502  158
 355  235  292  272  232  359
 158  489  281  275  452  140
 552  155  240  261  138  560

1412  519  734
 334  996  559
 714  467  564
 298  941  556
1112  293  501

With 1,685,934 trials needed to get the 10,000 in which all 30 students get to hold the paper.

Percentage probabilities for each position are, as in previous posts, half the shown number:

14  5  7  7  5 14
 3 10  6  6 10  3
 7  5  6  6  5  7
 3  9  6  6  9  3
11  3  5  5  3 11

The version of the program that utilizes the truly random numbers from the downloaded concatenated file is:

DEFINT A-Z
DIM drCt(-2 TO 2) AS LONG
DIM dcCt(-2 TO 2) AS LONG
RANDOMIZE TIMER
OPEN "20megs.1-2" FOR BINARY AS #1
st$ = " "
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
     IF supply = 0 THEN
       GET #1, , st$
       IF EOF(1) THEN PRINT "Ran out of random #'s": END
       source = ASC(st$)
       supply = 8
     END IF
     bit1 = source MOD 2
     bit2 = (source AND 2) / 2
     source = source \ 4
     supply = supply - 2
     dr = 1: dc = 0
     IF bit1 THEN dr = -dr
     IF bit2 THEN SWAP dr, dc
    LOOP UNTIL (dr OR dc) AND (dr = 0 OR dc = 0)
    drCt(dr) = drCt(dr) + 1
    dcCt(dc) = dcCt(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 ABS(dr) <> ABS(dc) 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: overTot = overTot + 1
    fCount = fCount + 1
    PRINT row, col, fCount, tr&
  ' FOR i = -2 TO 2: PRINT drCt(i); : NEXT
  ' PRINT
  ' FOR i = -2 TO 2: PRINT dcCt(i); : NEXT
  ' PRINT
  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 tr&

CLOSE

 

Posted by Charlie on 2004-06-25 00:44:19