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
KEYWORD
nonn,more
AUTHOR
Dana Mackenzie, Apr 08 2014
STATUS
approved