Socially Distant Goats

**Polite, yet demanding, our goats will wait their turn.**

Problem:

This week’s Classic from Quoc Tran asks:

“A goat tower has 10 floors, each of which can accommodate a single goat. Ten goats approach the tower, and each goat has its own (random) preference of floor. Multiple goats can prefer the same floor.

One by one, each goat walks up the tower to its preferred room. If the floor is empty, the goat will make itself at home. But if the floor is already occupied by another goat, then it will keep going up until it finds the next empty floor, which it will occupy. But if it does not find any empty floors, the goat will be stuck on the roof of the tower.

What is the probability that all 10 goats will have their own floor, meaning no goat is left stranded on the roof of the tower?”

After considering the problem there a few observations:

The order in which goats choose floors will not change the overall outcome of the result (whether all the goats do or do not get a floor.)
The condition that all goats find a floor is equivalent to the condition that in a sorted list of goat floor choices, each entry in the list is <= to it’s position in the list. For example: [0,1,2,2,3,7,7,7,8,9] is a valid sorted selection of random goat floor choices, with positions labeled 0-9, and [1,2,2,3,4,5,6,7,8,9] is not. We will use this as a fast way to filter out possible sorted solutions.

We will proceed this way and compute the number of valid possible random goat floor choices. One issue is the entire space of choices is very large = 10^10. We will reduce this by using our sorting observation and calculate all the sorted combinations with repetitions (multiple goats can choose the same floor), look for valid combinations, then calculate the number of permutations (not the permutations themselves) for each valid combination to arrive at the correct total probability. The number of unique sorted combinations with repetitions for n=10 is $\binom {19}{10}$ or only 92,738. This calculation only takes a few seconds, and we calculate some of the program variables for n=2-12.

Note that the percentage of valid permutations of sorted combinations is much higher than the percentage of valid sorted combinations alone. I was unable to get the analytical form for the solution, but was able to visually pick out some functional forms in the table, which upon doing some (OEIS!) research we see are well known in the combinatoric literature of “parking functions.”