All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Probability
Class Pass (Posted on 2004-06-24) Difficulty: 4 of 5
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?

No Solution Yet Submitted by Gamer    
Rating: 4.0000 (2 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Some Thoughts Better randomization for simulation. | Comment 6 of 15 |

This version of the simulation has a different algorithm for randomizing the direction, changed on the theory that the second call to RND might be influence by the first or some such thing.  The results look more symmetric now:

DEFINT A-Z
DIM drCt(-2 TO 2) AS LONG
DIM dcCt(-2 TO 2) AS LONG
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
     rNo = INT(RND(1) * 9)
     dr = rNo \ 3 - 1
     dc = rNo MOD 3 - 1
    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&

In a sample run it took 1,660,656 trials to get 10,000 in which all 30 students held the assignment.

The array of final hits per seat is:

 673  302  409  384  261  813
 187  550  318  226  308  205
 275  225  278  271  261  468
 112  440  303  285  548  121
 494  111  195  275   97  605

Which is much more nearly symmetric.

Combining the left and right corresponding number, and plotting on the left, the totals are:

1486  563  793
 392  858  544
 743  486  549
 233  988  588
1099  208  470

Implying the percentages, rounded to the nearest percent are half of the below figures (as it's based on the number combined left and right, and duplicated):

15  6  8  8  6 15
 4 9 5 5 9 4
7 5 5 5 5 7
2 10 6 6 10 2
11 2 5 5 2 11

So the most dangerous places are the corners of the room, with about 7 1/2% probability for each of the front-left and front-right seats, and 5 1/2% each for rear-left and rear-right.  The safest places are just to the front of or next to the guy in a back corner--only about 1% chance of landing there.

Of course this counts only those cases which extend all the way to having everyone having seen the paper, and so is a conditional probability.  In only about 1 in 166 trials does this happen altogether.

If we count all the cases when the passing is forced to stop by the holder being surrounded by previous seers, we get:

 919  400  420  410  396  969
 210  359  252  207  341  205
 243  248  194  228  221  223
 181  309  204  206  341  166
 780  116  167  198  129  758
1888  796  830
 415  700  459
 466  469  422
 347  650  410
1538  245  365

For percentages that are half of:

19  8  8  8  8 19
 4  7  5  5  7  4
5 5 4 4 5 5
3 7 4 4 7 3
15 2 4 4 2 15
 

 


  Posted by Charlie on 2004-06-24 21:56:34
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information