• Cards in slots (counting problem)

    From riverman@21:1/5 to All on Sun Nov 13 07:12:42 2022
    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?

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Edward Murphy@21:1/5 to riverman on Sun Nov 13 14:31:25 2022
    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.)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)
  • From Jonathan Dushoff@21:1/5 to Edward Murphy on Mon Nov 14 09:14:05 2022
    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.)

    --- SoupGate-Win32 v1.05
    * Origin: fsxNet Usenet Gateway (21:1/5)