|
%I #21 May 26 2014 12:35:07
%S 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,
%T 6,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,7,7
%N 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.
%C 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:
%C a(n) = max{k: (n-choose-k)^2 + sum_{j=0..(n-k)} (2n-choose-j) >= (2n-choose-n)}.
%C The formula is conjectured to hold for all n between 60 and 10 million, as well.
%C Note: a(1) and a(2) are undefined, so the first number given is a(3).
%H G. Antonick, <a href="http://wordplay.blogs.nytimes.com/2014/01/13/war">Stern-Mackenzie One-Round War</a>, New York Times (online), Jan. 13, 2014.
%H D. Mackenzie, <a href="http://arxiv.org/abs/1404.1093">Sun Bin's Legacy</a>, 2014.
%e 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.
%e 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.
%K nonn,more
%O 3,5
%A _Dana Mackenzie_, Apr 08 2014
|
