2
$\begingroup$

If $mn$ squares out of a $2m\times n$ white checkerboard are colored black, and a move consists of interchanging the color on any two squares who share a side, how many moves at maximum can it take to rearrange it such that all squares of one color are grouped together on either $m\times n$ halfboard?

What is the least moves needed such that it is always possible to rearrange this way if a move consists of interchanging two squares a knight's distance apart?

bounty: What is the most moves that is needed to move any configuration to another with x black squares on an mn board? For which x is the most attained?

$\endgroup$
1
  • $\begingroup$ Have you tried any small examples? You might find some patterns that would give you bounds or perhaps even suggest general answers. $\endgroup$ Commented Oct 21, 2011 at 5:18

1 Answer 1

5
$\begingroup$

Not a proof, but a lower bound that I suspect will be hard to beat. Let the $2m$ direction be horizontal and assume $n$ is even. The starting position is the upper $2m \times n/2$ squares black and the bottom white. All the $mn/2$ black squares on the left need to move $m$ squares right and $n/2$ squares down, so there are a total of $m^2n^2/4$ moves required.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .