Problem 595
Forum rules
As your posts will be visible to the general public you are requested to be thoughtful in not posting anything that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
As your posts will be visible to the general public you are requested to be thoughtful in not posting anything that might explicitly give away how to solve a particular problem.
This forum is NOT meant to discuss solution methods for a problem.
In particular don't post any code fragments or results.
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
Don't start begging others to give partial answers to problems
Don't ask for hints how to solve a problem
Don't start a new topic for a problem if there already exists one
See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
-
rphenson
- Posts: 1
- Joined: Mon Sep 25, 2017 8:21 pm
Problem 595
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.
-
MHealy
- Posts: 40
- Joined: Sat Nov 17, 2012 11:32 pm
Re: Problem 595
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".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.
The "expected number of shuffles" is using the standard definition of expected value (i.e. in this case it is the sum of k*pk, where pk 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.
