You hold 10 cards, the Ace through 10 and you lay them randomly down in a row...
Now you turn them over one at a time starting with the first. Each time you turn a card face up, that card tells you the position of the card to flip over next. Once it tells you to flip over a card that is already face up, you are done.
What is the probability that you will turn every card face up?
(The Ace counts as a 1)
Image credit: . whatwedoallday.com
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Nice problem! I initially thought "Ahhh... derangements!", so my first attempt was 1 / e . :/
Just a suggestion, but it might be an idea to write "... and you lay them randomly down in a row." The picture at first made it look like you had to lay them down in that order, which of course wouldn't have worked from the get-go.
More generally, if you start by turning over k cards out of n cards this way, then the probability that you eventually turn over all the cards is n k . I don't remember the proof.
Log in to reply
Interesting... I'm surprised it's such a simple formula!
The arrangement of the cards represents a permutation π ∈ S 1 0 . You turn over the cards numbered 1 , π 1 , π 2 1 , π 3 1 and so on. Thus you will fail to turn over all the cards if the constituent cycle of π that contains 1 has length less than 1 0 . Thus the only way that you will turn over all cards before stopping is if π is a 1 0 -cycle.
There are 9 ! 1 0 -cycles and 1 0 ! permutations altogether. Thus the probability of turning over all the cards is 1 0 1 .
Everybody else who has posted a solution here has written a better solution than this one. I wrote some quick and dirty python code to solve this problem. My reasoning was to search through every permutation (about 3 million possibilities which is small enough to brute force search through each and every possibility, although, would not scale well if given more cards) and go through the process of "turning them over" for each one. It is easy to see that when the ace is reached, a cycle forms. We are looking only for cycles of length 10.
from itertools import permutations
def valid(x):
met = [x[0]]
i = 0
while x[i] != 1:
i = x[i] - 1
met.append(x[i])
return len(met) == 10
valids = 0
for p in permutations([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], r = 10):
if valid(p): valids += 1
print(valids / 3628800)
Which outputs 0 . 1 .
Problem Loading...
Note Loading...
Set Loading...
There are 1 0 ! ways the cards could be arranged at first.
9 ! of those result in a pattern where you flip over all the cards.
The 9 ! comes from 9 ways to pick the first card (not an Ace), 8 ways to pick the one in the position it points to, etc. etc. ....
1 0 ! 9 ! = 0 . 1