I have 15 slots with a card in each one. The cards are collectively numbered 1-15, and each card belongs in the slot of the same number.

I pull out the card in a random slot, and i says the number of a different slot. So I put it in the proper slot, removing the card that is already there. It likewise has the number of a different slot, so I repeat.

What are the odds that I end up relocating EVERY card to its rightful slot?

On 11/13/2022 7:12 AM, riverman wrote:

> I have 15 slots with a card in each one. The cards are collectively numbered 1-15, and each card belongs in the slot of the same number.
>
> I pull out the card in a random slot, and i says the number of a different slot. So I put it in the proper slot, removing the card that is already there. It likewise has the number of a different slot, so I repeat.
>
> What are the odds that I end up relocating EVERY card to its rightful slot?

[spoiler space]

https://en.wikipedia.org/wiki/Random_permutation_statistics#Probability_that_a_random_element_lies_on_a_cycle_of_size_m

In this case, n = m = 15, so the probability is 1/15.

Let's build a proof of this result:

* Consider this modified procedure: You act as described, but if you
return to a slot already visited, then you start again at the lowest
numbered slot not already visited. This is guaranteed to finish,
even if it's not guaranteed to relocate every card in the process.

* To relocate every card, there are 14 valid choices for the first
card's proper slot, 13 for the second card's, and so on, so 14!
ways total.

* To just get through the procedure at all, there are 15 valid
choices for the first card's proper slot (including the one it's
already in), 14 for the second card's (all the slots except the
first card's proper slot), and so on, so 15! ways total.

* Thus, the probability of relocating every card is
14! / 15!
= 14! / (15 * 14!)
= 1/15

(How to prove the stated answer for n > m is left as an exercise.)

On Sunday, November 13, 2022 at 10:31:27 PM UTC, Edward Murphy wrote:
> On 11/13/2022 7:12 AM, riverman wrote:

> > I have 15 slots with a card in each one. The cards are collectively numbered 1-15, and each card belongs in the slot of the same number.

> > I pull out the card in a random slot, and i says the number of a different slot. So I put it in the proper slot, removing the card that is already there. It likewise has the number of a different slot, so I repeat.

> > What are the odds that I end up relocating EVERY card to its rightful slot?

Super-nice, but!

> [spoiler space]

We are _given_ that the first two cards move to new slots. So I would argue that the answer to the problem as stated is 1/13.

> https://en.wikipedia.org/wiki/Random_permutation_statistics#Probability_that_a_random_element_lies_on_a_cycle_of_size_m

> In this case, n = m = 15, so the probability is 1/15.

> Let's build a proof of this result:

> * Consider this modified procedure: You act as described, but if you
> return to a slot already visited, then you start again at the lowest
> numbered slot not already visited. This is guaranteed to finish,
> even if it's not guaranteed to relocate every card in the process.

> * To relocate every card, there are 14 valid choices for the first
> card's proper slot, 13 for the second card's, and so on, so 14!
> ways total.

> * To just get through the procedure at all, there are 15 valid
> choices for the first card's proper slot (including the one it's
> already in), 14 for the second card's (all the slots except the
> first card's proper slot), and so on, so 15! ways total.

> * Thus, the probability of relocating every card is
> 14! / 15!
> = 14! / (15 * 14!)
> = 1/15

> (How to prove the stated answer for n > m is left as an exercise.)