Can You Make Room For Goats?

Riddler Classic

From Quoc Tran comes a caprine conundrum:

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?

Solution

If all goats have their own floor, then for any outcome of goat preferences, each goat's preference will be less than or equal to their respective floor.

Given g, the number of goats, I wrote some code:

  1. A list of g floors from 1 to g was created.
  2. A list of g preferences, where each preference is randomly selected from 1 to g was created.
  3. The preferences list was sorted from least to greatest.
  4. The last (highest value) element in the preference list and floor list was compared.
  5. If the preference was greater that the floor, then that resulted in at least one goat on the roof. The scenario failed.
  6. If the preference was less than than or equal to the floor, both preference and floor were removed (assume that is a match), and repeat steps 4-6.
  7. If all preferences are less than or equal to corresponding floors, the scenario passed, andall goats had their own floor.
  8. A count was incremented. I ran 1,000,000,000 simulations for each of 1 - 11 goats.

I do not know why, but the probability seems to be the same as $\dfrac{(g+1)^{g-1}}{g^g}$.

Goats Simulation of 1,000,000,000 $\dfrac{(g+1)^{g-1}}{g^g}$
1 1 1
2 0.750004596 0.75
3 0.592558973 0.59259
4 0.488287741 0.48828
5 0.414732100 0.41472
6 0.360210095 0.36023
7 0.318294739 0.31831
8 0.285087681 0.28509
9 0.258127130 0.25812
10 0.235781540 0.23579
11 0.217040838 0.21702

Answer

$$\dfrac{11^9}{10^{10}} \approx 0.23579$$

Rohan Lewis

2022.06.26

Code can be found here.