This week the question is: Where Will the Sorting Hat Put You?
You are waiting in line to be sorted into one of the four houses of Logwarts (a posh wizarding boarding school in the Scottish highlands) by an anthropomorphic sorting hat. The hat is a bit of a snob about the whole matter, and refuses to sort two students in a row into the same house. If a student requests a certain house, but the previously sorted student was already sorted into that same house, then the hat chooses randomly from among the three remaining houses. Otherwise, the hat grants the student’s request.
You are standing 10th in line, and you make plans to request Graphindor house for yourself. As for the other students in line, you can assume that they have random preferences from among the four houses.
The first student steps up, and has a brief, quiet conversation with the hat. After a few moments, the hat proclaims, “Graphindor!”
At this point, what is the probability that you will be sorted into Graphindor?
Highlight to reveal (possibly incorrect) solution:
When a student isn’t sorted into Graphindor, they might end up in Hafflepuff instead. For symmetry reasons, the 3 non Graphindor houses behave the same way, ending up with the same probabilities, so I’m just going to track Graphindor and Hafflepuff.
Student #1 got G.
Student #2 may want G (p=1/4) or something else, like H (p=1/4). If G was requested, H might be granted (p=1/3). The total probability for H is therefore 1/4 + (1/4)*(1/3) = 1/3. The probability for getting G is 0.
This holds in general. A random student wanting something random will end up in a random house, p=1/3, where the previously granted house has p=0.
Student #3 may want H (p=1/4) or something else. The probability this student ends up in G is p(H) from the previous step, or rather p(H) * 3/3. The probability this student ends up in H is (p(G)+…)/3. Therefore p(G) = 1/3 = 3/9 and p(H) = 2/9.
This holds in general. If at a certain step, p(G) = a/c and p(H) = b/c, in the next step, p(G) = 3b/3c and p(H) = (a+2b)/3c.
| Step | p(G) | p(H) |
| 1 | 1 | 0 |
| 2 | 0 | 1/3 |
| 3 | 3/9 | 2/9 |
| 4 | 6/27 | 7/27 |
| 5 | 21/81 | 20/81 |
| 6 | 60/243 | 61/243 |
| 7 | 183/729 | 182/729 |
| 8 | 546/2187 | 547/2187 |
| 9 | 1641/6561 | 1640/6561 |
The general formula for step odd n+1 is p(G) = [3n/4, rounded down]/3n and p(H) = [3n/4, rounded up]/3n. For even n+1, reverse rounding up and down. Values verified via spreadsheet.
In step 10, I can get G, if G wasn’t granted in the previous step. The probability of this is (6561-1641)/6561 = 4920/6561 = 0.749886… or approximately 1/4.
Stuff from ommadawn.dk (Lise Andreasen) 