Project Euler Forum

Does "expected number of shuffles" mean that a 50% probability is reached. The problem states that S(2) = 1. If I'm understanding the problem correctly, two cards would be thrown in the air and picked up. If "one" was picked up first (50% probability) then the deck would be sorted. If "two" was picked up first then the deck remains unsorted and the two cards are thrown in the air again and the process repeated until the "one" card is picked up first.

rphenson wrote: Mon Sep 25, 2017 8:33 pm Does "expected number of shuffles" mean that a 50% probability is reached. The problem states that S(2) = 1. If I'm understanding the problem correctly, two cards would be thrown in the air and picked up. If "one" was picked up first (50% probability) then the deck would be sorted. If "two" was picked up first then the deck remains unsorted and the two cards are thrown in the air again and the process repeated until the "one" card is picked up first.

I'm not quite sure what you mean by "that a 50% probability is reached", so perhaps I've misunderstood, but I think the answer to your question is "no".

The "expected number of shuffles" is using the standard definition of expected value (i.e. in this case it is the sum of k*p_k, where p_k is the probability that k shuffles are required to sort n cards, for all possible k).

To clarify the exact procedure for two cards, the case where they are sorted the first time you pick them up (this has 50% probability, as you say) is counted as zero shuffles, not one shuffle ("the order is checked before the first shuffle"). If they were not sorted initially, but then thrown up once and picked up in the correct order this second time, this counts as one shuffle. And so on.

I hope this helps.