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

Author

Julian Zbigniew Kuryllowicz-Kazmierczak, Feb 17 2024

Keywords

• nonn
• frac
• tabl

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.

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.
		

Crossrefs

Denominators are in A370399.

Cf. A083864.

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