login
A240567
a(n) = optimal number of tricks to throw in the game of One Round War (with n cards) in order to maximize the expected number of tricks won.
1
1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7
OFFSET
3,5
COMMENTS
A precise definition of a(n) is as follows. Let p^n_ij denote the number of ways to deal 2n cards into two hands (n cards per hand) such that the i-th lowest card in hand 1 is greater than the j-th lowest card in hand 2. Let P^n denote the n X n matrix whose ij-th entry is p^n_ij. Let M denote the n X n permutation matrix that has the maximum inner product with P^n. As proved in Mackenzie (2014), provided n is sufficiently large, the optimal permutation matrix M consists of a(n) 1's on the "anti-main diagonal" in the first a(n) rows, followed by (n-a(n)) 1's that all lie on the a(n)-th diagonal below the main diagonal. The following exact formula holds for all n less than 60 and for all n greater than 10 million:
a(n) = max{k: (n-choose-k)^2 + sum_{j=0..(n-k)} (2n-choose-j) >= (2n-choose-n)}.
The formula is conjectured to hold for all n between 60 and 10 million, as well.
Note: a(1) and a(2) are undefined, so the first number given is a(3).
LINKS
G. Antonick, Stern-Mackenzie One-Round War, New York Times (online), Jan. 13, 2014.
D. Mackenzie, Sun Bin's Legacy, 2014.
EXAMPLE
For n = 3, the matrix P is [[10, 4, 1], [16, 10, 4], [19, 16, 10]]. The permutation matrix that maximizes the inner product with P is M = [[0, 0, 1], [1, 0, 0], [0, 1, 0]]. (It is easy to see that M dot P = 33 and that this beats the other five permutation matrices.) M has one entry on the anti-main diagonal above the main diagonal. Thus a(3) = 1.
In terms of the card game One Round War, if your cards are A, B, C (from high to low) and your opponent's cards are a, b, c (from high to low) this means that the optimal strategy is to "throw" one trick. In other words, you should play C against a, A against b, and B against c. With this strategy you will win on average 33/20 = 1.65 tricks out of 3.
CROSSREFS
Sequence in context: A132085 A111654 A264749 * A067099 A098429 A132090
KEYWORD
nonn,more
AUTHOR
Dana Mackenzie, Apr 08 2014
STATUS
approved