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, 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

Author

Dana Mackenzie, Apr 08 2014

Keywords

• nonn
• more

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).

Examples

			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.
		

Links

• G. Antonick, Stern-Mackenzie One-Round War, New York Times (online), Jan. 13, 2014.
• D. Mackenzie, Sun Bin's Legacy, 2014.