A370398 Triangle read by rows: T(n,k) is the numerator of the probability of winning a 1-player game M(n,k) as defined below while playing optimally.
0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 11, 5, 1, 0, 4, 31, 11, 9, 1, 0, 4, 1, 69, 21, 19, 1, 0, 4, 101, 49, 829, 94, 34, 1, 0, 4, 2783, 3733, 56069, 25367, 551, 69, 1, 0, 32, 13439, 21517, 389573, 1543163, 14011, 565, 125, 1, 0, 32, 149621, 271643, 5709959, 379562191, 2757715, 1392901, 19388, 251, 1
Offset: 1
Examples
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) given the values of Pr(n,k) for n=3 and n=2 as seen in the table below. The leftmost column lists each of the six possible outcomes (i.e., C(4,2) = 6 combinations, all equally likely) of randomizing the n=4 tokens during the first move; in each randomized sequence (i.e., combination), the red and blue tokens are represented by "r" and "b", respectively. Removing the last j = 1 or 2 tokens will leave n' = n - j remaining tokens of which k' = k - f(c,j) are blue. For each randomized sequence, an asterisk marks the probability of winning using the optimal choice of the number j of tokens to remove.
.
randomized if remove if remove probability
sequence last j=1 token last j=2 tokens of win
of --------------- --------------- given optimal
tokens n' k' Pr(n',k') n' k' Pr(n',k') choice
========== == == ========= == == ========= =============
rrbb 3 1 1/3 * 2 0 0/1 1/3
rbrb 3 1 1/3 2 1 1/2 * 1/2
brrb 3 1 1/3 2 1 1/2 * 1/2
rbbr 3 2 2/3 * 2 1 1/2 2/3
brbr 3 2 2/3 * 2 1 1/2 2/3
bbrr 3 2 2/3 2 2 1/1 * 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).
The probability of winning M(4,2) is the average of the probabilities of winning for each randomized sequence, i.e.,
Pr(4,2) = (1/3 + 1/2 + 1/2 + 2/3 + 2/3 + 1/1)/6 = 11/18.
Formula
T(n,k) = numerator(Pr(n,k)) where Pr(n,k) =
0 if k = 0,
1 if k = n, and
(1/C(n,k))*Sum_{c=1..C(n,k)} Max_{j=1..floor(n/2)} Pr(n-j, k-f(c,j)) otherwise,
and where the summation is over all combinations of n tokens, exactly k of which are blue, and f(c,j) is the number of blue tokens among the last j tokens in the c-th combination.
Extensions
More terms from Jon E. Schoenfield, Feb 24 2024
Comments