Because that's not the answer :) We can solve the general problem recursively. Suppose there are n 1's and k 0's. The minimizer is effectively dividing the 1's into exactly k groups, and the maximizer is choosing a cyclic order for the sizes of these groups (note that the maximizer always chooses a cyclic permutation for which the high bit is 1 and the low bit is 0). I claim that with optimal play the only group sizes are [n/k] = floor(n/k) and [n/k]+1. First, one of the groups must have size at least [n/k], or there would be fewer than n 1's. Second, the minimizer can ensure that no group has size greater than [n/k]+1, and therefore will do so. Finally, suppose some group has size x < [n/k], which means that some other group has size [n/k]+1. After the maximizer plays there will be a group of size [n/k]+1 to the left (higher) than the group of size x, so the sizes will be ..... [n/k]+1 [n/k] [n/k] ... [n/k] x .... but then the minimizer could instead replace the [n/k]+1 group with one of size [n/k] and the x group with one of size x+1 <= [n/k], resulting in a strictly lower score for the maximizer. It follows that the minimizer always creates (n mod k) groups of size [n/k]+1 and (-n mod k) groups of size [n/k]. So... represent the groups of size [n/k]+1 by '1' and the groups of size [n/k] by '0', and we have the original problem with (n mod k) 1's and (-n mod k) 0's. For the specific posed question, we have (n,k) = (17,10). The minimizer chooses groups of size 1 and 2, reducing to the (7, 3) problem. For this, in turn, the minimizer chooses groups of size 2 and 3, reducing to the (1, 2) problem which has answer 100. Working backwards, 100 => 322 => 1110110110 => 2221221221 => 110110110101101101011011010 J.P. On Thu, Apr 30, 2009 at 3:49 AM, Fred lunnon <fred.lunnon@gmail.com> wrote:
110110110110110110110110100 in binary,
or 6*(8^8 - 1)/(8-1) - 2 = 14380468 in decimal.
Uh --- why is that hard? WFL
On 4/30/09, rwg@sdf.lonestar.org <rwg@sdf.lonestar.org> wrote:
We have a 27-bit unsigned word. Minimizer chooses one of the binom(27,10) combinations of 17 ones and 10 zeros. Maximizer then chooses the max of the 27 cyclic permutations. Value =? --rwg HORSEWOMEN HOMEOWNERS SOKEMANRIES NOISEMAKERS STRATOSPHERIC ORCHESTRA PITS
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun