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?

  • 0
    Have you tried any small examples? You might find some patterns that would give you bounds or perhaps even suggest general answers.2011-10-21

1 Answers 1