Shuffling And Deleting
We begin with the set { 1 , 2 , 3 , … , 2 0 1 6 } .
We will perform the following operations on the set until the set has only one element left:
- Shuffle the set.
- Delete the first element.
The probability that the last remaining element is 2016 can be written as B A , where A and B are positive coprime integers. Find A + B .
Note: After shuffling a set of n distinct elements, any of the n ! permutations is equally likely to occur.
The answer is 2017.
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.
3 solutions
Nice streak pranshu 715 !! Awesome BTW I did the same way ;)
This solution is incomplete, because we shuffle the elements after deleting one element. Thus the fact that an element is the last element in the first shuffle doesn't matter, because it gets shuffled again.
Log in to reply
By "last element", I meant the "last remaining element". By symmetry, each element is equally likely to be last remaining element after 2015 deletions.
Steps 1-2 can be merged into "delete a random element", because shuffling the list will give equal probability for any element to be at the front.
Now, deleting 2015 elements is equivalent to picking one element that is safe. Thus the probability that a particular element is not deleted is if it gets picked as safe; that is, 1 desired element out of 2016 elements, or 2 0 1 6 1 .
The probability of not deleting 2016 from the set is 2 0 1 6 2 0 1 5 the first time the operation is done. Next the probability will be 2 0 1 5 2 0 1 4 . This continues until only the 2016 element remains.
2 0 1 6 2 0 1 5 × 2 0 1 5 2 0 1 4 × . . . × 3 2 × 2 1 = 2 0 1 6 ! 2 0 1 5 ! = 2 0 1 5 ! × 2 0 1 6 2 0 1 5 ! = 2 0 1 6 1 = B A
Hence as A and B are coprime integers A + B = 2 0 1 7
Note that due to symmetry, every element of the original set is equally likely to end up as the last remaining element. There are 2016 elements in the original set, therefore the probability of any number being the last remaining element is 2 0 1 6 1 .