J.P.Grossman> 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.
Elegant. But then (17/27,reverse(makelist(floor((k+1)*%%)-floor(k*%%),k,0,26))) [1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0] (Doug Hofstadter calls these "eta sequences".)
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
It's a simplification of a problem where the function to be minimaxed is not quite monotone on the bit strings. --rwg POLYESTERS PRESYSTOLE PROSELYTES PTERYLOSES
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