Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
Have you tried any small examples? You might find some patterns that would give you bounds or perhaps even suggest general answers. – Gerry Myerson Oct 21 '11 at 5:18

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.