

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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 ith lowest card in hand 1 is greater than the jth lowest card in hand 2. Let P^n denote the n X n matrix whose ijth 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 "antimain diagonal" in the first a(n) rows, followed by (na(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: (nchoosek)^2 + sum_{j=0..(nk)} (2nchoosej) >= (2nchoosen)}.
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

Table of n, a(n) for n=3..54.
G. Antonick, SternMackenzie OneRound 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 antimain 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
Adjacent sequences: A240564 A240565 A240566 * A240568 A240569 A240570


KEYWORD

nonn,more


AUTHOR

Dana Mackenzie, Apr 08 2014


STATUS

approved



