This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A370398 #58 Mar 21 2024 20:49:44
%S A370398 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,
%T A370398 49,829,94,34,1,0,4,2783,3733,56069,25367,551,69,1,0,32,13439,21517,
%U A370398 389573,1543163,14011,565,125,1,0,32,149621,271643,5709959,379562191,2757715,1392901,19388,251,1
%N 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.
%C A370398 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.
%C A370398 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.
%C A370398 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.
%F A370398 T(n,k) = numerator(Pr(n,k)) where Pr(n,k) =
%F A370398 0 if k = 0,
%F A370398 1 if k = n, and
%F A370398 (1/C(n,k))*Sum_{c=1..C(n,k)} Max_{j=1..floor(n/2)} Pr(n-j, k-f(c,j)) otherwise,
%F A370398 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.
%e A370398 The values of Pr(n,k) begin as follows:
%e A370398 .
%e A370398 n\k| 0 1 2 3 4 5 6 7
%e A370398 ---+---------------------------------------------------------
%e A370398 1 | 0/1 1/1
%e A370398 2 | 0/1 1/2 1/1
%e A370398 3 | 0/1 1/3 2/3 1/1
%e A370398 4 | 0/1 1/3 11/18 5/6 1/1
%e A370398 5 | 0/1 4/15 31/60 11/15 9/10 1/1
%e A370398 6 | 0/1 4/15 1/2 69/100 21/25 19/20 1/1
%e A370398 7 | 0/1 4/15 101/210 49/75 829/1050 94/105 34/35 1/1
%e A370398 ...
%e A370398 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.
%e A370398 .
%e A370398 randomized if remove if remove probability
%e A370398 sequence last j=1 token last j=2 tokens of win
%e A370398 of --------------- --------------- given optimal
%e A370398 tokens n' k' Pr(n',k') n' k' Pr(n',k') choice
%e A370398 ========== == == ========= == == ========= =============
%e A370398 rrbb 3 1 1/3 * 2 0 0/1 1/3
%e A370398 rbrb 3 1 1/3 2 1 1/2 * 1/2
%e A370398 brrb 3 1 1/3 2 1 1/2 * 1/2
%e A370398 rbbr 3 2 2/3 * 2 1 1/2 2/3
%e A370398 brbr 3 2 2/3 * 2 1 1/2 2/3
%e A370398 bbrr 3 2 2/3 2 2 1/1 * 1/1
%e A370398 .
%e A370398 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).
%e A370398 The probability of winning M(4,2) is the average of the probabilities of winning for each randomized sequence, i.e.,
%e A370398 Pr(4,2) = (1/3 + 1/2 + 1/2 + 2/3 + 2/3 + 1/1)/6 = 11/18.
%Y A370398 Denominators are in A370399.
%Y A370398 Cf. A083864.
%K A370398 nonn,frac,tabl
%O A370398 1,8
%A A370398 _Julian Zbigniew Kuryllowicz-Kazmierczak_, Feb 17 2024
%E A370398 More terms from _Jon E. Schoenfield_, Feb 24 2024