OFFSET

1,4

COMMENTS

T(n, k) is the numerator of the probability of winning a game M(n, k) while playing optimally. The game is played by a single player who begins with n tokens of which k are blue and the rest are red; 0 <= k <= n > 0. Each move consists of randomizing the order of the remaining tokens, observing their resulting order, choosing a number m of tokens to remove, and removing the m tokens that are ordered last; m must be at least 1 but no more than half of the remaining tokens. Play continues until only one token remains; the game is won if that token is blue, otherwise the game is lost.

Let Pr(n,k) be the probability of winning a game M(n,k). Then Pr(n+1,1) = (n/(n-1))*Pr(n,1) if n is a power of 2, Pr(n,1) otherwise. So lim_{n->oo} Pr(n,1) = (1/2)*(2/3)*(4/5)*(8/9)*(16/17)*... = A083864.

EXAMPLE

The values of Pr(n,k) begin as follows:

.

n\k| 0 1 2 3 4 5 6 7

---+---------------------------------------------------------

1 | 0/1 1/1

2 | 0/1 1/2 1/1

3 | 0/1 1/3 2/3 1/1

4 | 0/1 1/3 11/18 5/6 1/1

5 | 0/1 4/15 31/60 11/15 9/10 1/1

6 | 0/1 4/15 1/2 69/100 21/25 19/20 1/1

7 | 0/1 4/15 101/210 49/75 829/1050 94/105 34/35 1/1

...

We can calculate Pr(4,2) using the table below, given the values of Pr(n,k) for n=3 and for n=2. The leftmost column lists each of the six possible results of randomizing the n=4 tokens during the first move; in each randomized sequence, the red and blue tokens are represented by "r" and "b", respectively.

.

randomized probability result if result if

sequence of last 1 token last 2 tokens

of tokens occurrence is removed are removed

========== =========== ============== =============

rrbb 1/6 Pr(3,1) = 1/3 Pr(2,0) = 0/1

rbrb 1/6 Pr(3,1) = 1/3 Pr(2,1) = 1/2

brrb 1/6 Pr(3,1) = 1/3 Pr(2,1) = 1/2

rbbr 1/6 Pr(3,2) = 2/3 Pr(2,1) = 1/2

brbr 1/6 Pr(3,2) = 2/3 Pr(2,1) = 1/2

bbrr 1/6 Pr(3,2) = 2/3 Pr(2,2) = 1/1

.

For example, when we get rbrb it's better to remove the last two tokens (one r and one b) instead of removing only the last token (b). So the probability of winning M(4,2) is

Pr(4,2) = (1/6)(1/3) + (1/6)(1/2) + (1/6)(1/2) + (1/6)(2/3) + (1/6)(2/3) + (1/6)(1/1) = 11/18.

Of course Pr(n,k) >= k/n, because k/n could be achieved by removing 1 token on each move.

CROSSREFS

KEYWORD

AUTHOR

Julian Zbigniew Kuryllowicz-Kazmierczak, Feb 17 2024

EXTENSIONS

More terms from Jon E. Schoenfield, Feb 24 2024

STATUS

approved