MathDB
2013 HMMT Guts #32: Kevin's Stone Solitare Game

Source:

March 26, 2013
HMMTprobability

Problem Statement

For an even positive integer nn Kevin has a tape of length 4n4n with marks at −2n,−2n+1,…,2n−1,2n-2n,-2n+1,\ldots,2n-1,2n. He then randomly picks nn points in the set −n,−n+1,−n+2,…,n−1,n-n,-n+1,-n+2,\ldots,n-1,n and places a stone on each of these points. We call a stone 'stuck' if it is on 2n2n or −2n-2n, or either all the points to the right, or all the points to the left, all contain stones. Then, every minute, Kevin shifts the unstruck stones in the following manner:
[*]He picks an unstuck stone uniformly at random and then flips a fair coin. [*]If the coin came up heads, he then moves that stone and every stone in the largest contiguous set containing that stone one point to the left. If the coin came up tails, he moves every stone in that set one point right instead. [*]He repeats until all the stones are stuck. Let pnp_n be the probability that at the end of the process there are exactly kk stones in the right half. Evaluate pn−1−pn−2+pn−3+…+p3−p2+p1pn−1+pn−2+pn−3+…+p3+p2+p1\dfrac{p_{n-1}-p_{n-2}+p_{n-3}+\ldots+p_3-p_2+p_1}{p_{n-1}+p_{n-2}+p_{n-3}+\ldots+p_3+p_2+p_1} in terms of nn.
Back to ProblemsView on AoPS