A370399 Triangle read by rows: T(n, k) is the denominator of the probability of winning a certain game while playing optimally.

1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 3, 18, 6, 1, 1, 15, 60, 15, 10, 1, 1, 15, 2, 100, 25, 20, 1, 1, 15, 210, 75, 1050, 105, 35, 1, 1, 15, 5880, 5880, 73500, 29400, 588, 70, 1, 1, 135, 30240, 35280, 529200, 1852200, 15435, 588, 126, 1, 1, 135, 340200, 453600, 7938000, 466754400, 3111696, 1481760, 19845, 252, 1

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.

Links

Table of n, a(n) for n=1..65.

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

Numerators are in A370398.

Sequence in context: A347187 A027948 A360335 * A095141 A177974 A095140

Adjacent sequences: A370396 A370397 A370398 * A370400 A370401 A370402

Keyword

nonn,frac,tabl

Author

Julian Zbigniew Kuryllowicz-Kazmierczak, Feb 17 2024

Extensions

More terms from Jon E. Schoenfield, Feb 24 2024

Status

approved