|
| |
|
|
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.
|
|
1
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,8
|
|
|
COMMENTS
|
A game M(n,k) is played as follows: play begins with k blue tokens and n-k red; 0 <= k <= n > 0. At each move, the order of the r remaining tokens is randomized and observed, and the player then chooses a number d, 1 <= d <= r/2, and discards the last d of the remaining tokens. The game is won iff the last remaining token is blue.
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.
The (generally suboptimal) strategy of removing 1 token on each move (regardless of the randomization result) provides Pr(n,k) >= k/n as a lower bound.
|
|
|
LINKS
|
|
|
|
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.
|
|
|
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) 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.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
