While walking down the street one day, you notice people gathering around a woman playing the shell game. With each game, she places a ball under one of three cups, and then swaps the positions of pairs of cups several times before asking passersby which cup they think the ball is now under.

You have it on good authority that she is playing fairly, performing all the moves in plain sight, albeit too fast for you to track precisely which cups she’s moving. However, you do have one additional key piece of information — every time she swaps cups, one of them has the ball. In other words, she never swaps the two empty cups.

When it’s your turn to guess, you note which cup she initially places the ball under. Then, as she begins to swap cups, you close your eyes and count the number of swaps. Once she is done, you open your eyes again. What is your best strategy for guessing which cup has the ball?

If we denote as P(100, n), P(010, n) and P(001, n) the probability that the shell ends in the position where the 1 is after n swaps, then we have the following recurrence relations P(100, n) = 1/2*P(010, n-1)+1/2*P(001, n-1) and similarly P(010, n) = 1/2*P(100, n-1)+1/2*P(001, n-1) and P(001, n) = 1/2*P(100, n-1)+1/2*P(010, n-1).
Writting the first few cases in a grid, one gets the following:

Swaps 100 010 001
0 1/2^0 0/2^0 0/2^0
1 0/2^1 1/2^1 1/2^1
2 2/2^2 1/2^2 1/2^2
3 2/2^3 3/2^3 3/2^3
4 6/2^4 5/2^4 5/2^4
5 10/2^5 11/2^5 11/2^5
6 22/2^6 21/2^6 21/2^6
7 42/2^7 43/2^7 43/2^7
8 86/2^8 85/2^8 85/2^8

The denominators are nothing but 2^n.

For n even, notice that the numerator is the previous one + 4^((n/2)-1), so the nth term for "100" is 1+sum from k=0 to (n/2)-1 of 4^k = (4^(n/2)+1)/3+1=(2^n+1)/3+1 and similarly for "010" and "001" it's (2^n-1)/3.

For n odd, the rule is similar, the numerator is the previous one + 2*4^((n-1)/2-1), so the nth term for "100" is sum from k=0 to (n-1)/2-1 of 2*4^k = 2*(4^((n-1)/2)-1)/3 = 2*(2^(n-1)-1)/3 and similarly for "010" and "001" it's 2*(2^(n-1)-1)/3+1.

Using induction + the recurrence it can be seen that this is indeed true.
Therefore, for n even it's best to select the cup that initially had the shell, and for n odd, any of the others.

P5331
Forgot to mention that I was assuming one starts at position "100" without loss of generality.

P5332
*of joviality.

P5331
Looks right except for a small sign error here:
>1+sum from k=0 to (n/2)-1 of 4^k = (4^(n/2)+1)/3+1=(2^n+1)/3+1
should be (4^(n/2)-1)/3+1=(2^n-1)/3+1

P5344
Yeah, it's fine on my notes I just fugged up when transcribing it. Other case it's fine so I guess it proves I can sum a geometric series.

What if only adjacent cups get swapped?

P5388
Do the leftmost and the rightmost count as adjacent? i.e. they're arranged in a circle.

P5728
You can arrange the cups in a circle to spice up and brand your shell game. Three cups would be a pretty uninspiring approximation of a circle though.

P5728
>Do you mean the original problem?
That anon most likely asked the question because the odds evolve differently when you can only move the ball from A to B, from B to A or C and from C to B.
In that case the chance of the ball being at B constantly flips between 0% and 100%, while the chances of it being at A or C constantly flip between 0% and 50%.
Interestingly, it's less interesting than freely moving the ball between A, B and C.