The bright minds of my HAVO final exam class

HAVO is the Dutch term for higher general continued education.

These are the 16 students in my final exam class:
Amy, Bob, Cynthia, Daphne, Eva, Faye, Grace, Hazel, Ivy, Joy, Ken, Liz, Mia, Noa, Owen, and Peter.
Pretty names, don't you think? And these students are very smart too!

These pupils enjoy taking on intellectual challenges. This year I challenged them with a mailbox problem:
CYN
Cynthia's card
On the wall next to the classroom there are 16 post boxes with the letters A to P on them, so that each student has his own post box.
I was in possession of a card of all the students with the first three letters of the student's name on it. I put one of these cards in each mailbox, but did so randomly. The task for the students is to find their own card. To do this, students may open up to 8 mailboxes. They do this one after the other - in random order - without seeing what others have opened and they only consult beforehand (if they feel it is necessary). When they have found their card, they leave it in the mailbox. The assignment is successful if all students find their cards after opening a maximum of eight mailboxes.
The first reaction of Owen was: the probability of success is (1/2)16 ≈ 0.000015, right?
By coincidence, at that moment the teaching assistant Souffian was present. He proclaimed:
“That's right if you randomly open mailboxes, but if you do it smartly then that chance becomes more than 1/3. In fact, the chance is 100% if I exchange two tickets in advance.”

At this, Grace said, “I know how to do it, shall we discuss?”
Not necessary the other students thought. “We know how to do it too!”

Solution

This problem is a variant of the well-known 100 prisoners problem. The catch is that you do not open the mailboxes randomly, but make a chain of them. You start by opening your own mailbox (so suppose you are Joy, then you open mailbox J). You look at the card and now open the box of the person on the card. So if it says Amy then you open box A. You keep going until you find your own name. You remember in which mailbox that is, but leave your card. If you have opened more than 8 boxes then everyone stops because there can be no winning.

Why does this method work?

If you work this way then one thing is certain: your own card will appear somewhere in the chain, but perhaps not until after the eighth mailbox. The part of the chain that you use before you meet your own name is called a cycle. Every student you have encountered on the cards is in the same cycle and can never be in any other cycle. In a series of 16 boxes there can be a different number of cycles, but the total length of all the cycles added together is always 16. It is clear that in a chain of 16 links, there can at most be one cycle that is longer than 8. Let's take as an example a cycle with a length of 9. You may have learned in math that you can choose this in "16 choose 9" ways (calculator 16 nCr 9). You can do this in as many as 11440 ways. In each of these distributions, you can swap the numbers randomly, both in the cycle of 9 and in the other 7 numbers. So we need to multiply by 8! (not 9!, because a cyclic shift doesn't matter) and by 7!
If you know how to calculate "16 choose 9" you'll see that you can eliminate some terms, leaving only the term 16!/9. Since you want a probability, you have to divide by the total number of possible sequences (= 16!). You are left with only 1/9. To calculate the total probability of a cycle being longer than 8, you need to add to this the probabilities of the other lengths greater than 8. To get the probability of NOT having a cycle greater than 8, you need to take 1 minus. So the probability that there is no cycle longer than 8 (i.e. the probability that everyone finds his ticket in time) is 1 − (1/9+1/10+1/11+1/12+1/13+1/14 +1/15+1/16) ≈ 0.337. So it is true what Souffian said.

A few interesting facts:

A worked example with four students

It is very difficult to work out the situation all the way through with 16 students. With four students and four mailboxes, it can be done. If you would choose randomly, the chance that all students find their own card within two tries is (1/2)4 = 0.0625.
With the smart method, that becomes as much as 1 − 1/3 − 1/4 ≈ 41.67%. Below you see all 16 ways the cards could have been distributed among the four mailboxes. The mailboxes are in the order A B C D.

Amy  Bob  Cyn  Dap Bob  Amy  Cyn  Dap Cyn  Amy  Bob  Dap Dap  Amy  Bob  Cyn
Amy  Bob  Dap  Cyn Bob  Amy  Dap  Cyn Cyn  Bob  Amy  Dap Dap  Bob  Cyn  Amy
Amy  Cyn  Bob  Dap Bob  Cyn  Amy  Dap Cyn  Bob  Amy  Dap Dap  Bob  Amy  Cyn
Amy  Cyn  Dap  Bob Bob  Cyn  Dap  Amy Cyn  Bob  Dap  Amy Dap  Bob  Cyn  Amy
Amy  Dap  Bob  Cyn Bob  Dap  Amy  Cyn Cyn  Dap  Amy  Bob Dap  Cyn  Amy  Bob
Amy  Dap  Cyn  Bob Bob  Dap  Cyn  Amy Cyn  Dap  Bob  Amy Dap  Cyn  Bob  Amy


You get the first box if by chance all the cards ended up in the right mailboxes. Then everyone is done after looking in one mailbox. The blue colored boxes represent the situations in which everyone finds their card within two tries.
As an example, I'll take Cyn Dap Amy Bob:
Amy opens mailbox A and finds Cynthia's card
Amy opens mailbox C and finds Amy's card: done after two tries
Bob opens mailbox B and finds Daphne's card
Bob opens mailbox D and finds Bob's card: done after two tries
Cynthia opens mailbox C and finds Amy's card
Cynthia opens mailbox A and finds Cynthia's card: done after two tries
Daphne opens mailbox D and finds Bob's card
Daphne opens mailbox B and finds Daphne's card: done after two tries
The order in which students go to the mailboxes does not matter.
We can also calculate the probability by counting: 10 out of 24 possibilities are correct, that is indeed 41.67%.

Souffian assistance

Soufian said that if he is allowed to swap two tickets beforehand, he can increase the chances of success to 100%. He must then be able to view the tickets. How does he proceed? He checks if there is any cycle that is longer than half the number of letterboxes. If not, he does nothing. If yes, he swaps two cards, so that the cycle is broken. This is always possible.
To find the largest cycle he starts with mailbox A and follows the cycle. If it is shorter than 8, he goes to the next box he hasn't opened yet. If he has already opened more than 8 boxes in total, he knows that there are no cycles longer than 8. So he doesn't always have to check all the mailboxes.
An example: suppose we have the following situation:
ABCDEFGH IJKLMNOP
AmyCynDapEvaJoyBobHaz FayGraIvyKenLizMiaNoaOwePet
The top row is the letters on the mailboxes, the bottom row is the name on the card that is in the mailbox.
Souffian opens the first box and finds Amy's card. Then he goes to box B and then successively opens box C, D, E, J, I, G, H and F. Only at F does he find Bob's card. So this cycle is too long. He must swap two cards within this cycle so that the cycle is broken. There are several possibilities, but not every swap works. Souffian checks this one more time. Suppose he swaps the cards of Joy and Faye. Then, starting from square B, he opens boxes C, D, E and F. The next cycle starts at box G. After G, he opens H, J and I. There is no longer a cycle than the one starting from mailbox B. The students will always find their cards in time. Because Souffian always swaps the last card in the cycle with the middle card, there is no need to check this all the time.

Computer programs

Below is a Python 3 program that allows you to calculate the probability for an arbitrarily large group.
while True:
    n = int(input('Enter the number of students: '))
    if n % 2 != 0:
        print('The number of students must be an even number')
    else:
        break
    
def H(N): 
    som = 0
    for x in range(N//2 + 1, N + 1):
        som += 1/x
    return som

print('The probability that students will succeed is', 1 - H(n))

A JavaScript simulation

Specify here how many students and thus mailboxes you have: