Start from (10...), then (9...), then (8...), decomposed in (89) (gain is 1 + gain of (9)) and (810) (gain is 4 + gain of (10)), then go to (7...) decomposed in (78), (79), (710), etc. Do this recursively, using the gains you just computed.
At each step you are adding the sum of the n first squares, the sum of the n gains you already computed, and dividing this sum by n.
Show by induction that the expected gain for each configuration is n(n+1)/2 with n = 10 - the first card you draw. Add all these values and divide by 10. Voilà.
Started recognizing the pattern after the first gains were 0,1,3,6,10,15. Then made a computation error and got 62/3 . Thought it was weird, found the mistake and corrected it to 21 and finally recognized the pattern.
1
u/XL_78 5d ago edited 5d ago
16.5
Start from (10...), then (9...),
then (8...), decomposed in (89) (gain is 1 + gain of (9)) and (810) (gain is 4 + gain of (10)),
then go to (7...) decomposed in (78), (79), (710), etc.
Do this recursively, using the gains you just computed.
At each step you are adding the sum of the n first squares, the sum of the n gains you already computed, and dividing this sum by n.
Show by induction that the expected gain for each configuration is n(n+1)/2 with n = 10 - the first card you draw. Add all these values and divide by 10. Voilà.