3
$\begingroup$

On a table lies a 13 x 14 board with black and white tiles, of which we can alter the colours with 27 levers. With each of the levers we can swap the colour of each row or column, so any black tiles in this row (or column respectively) turn white and vice versa. We can use the levers infinite number of times. Starting from all 182 tiles in their black position, how many different layouts can we achieve?

It would be easy to say that if for each tile we have have two values, black and white, it would be $2^{27}$ but I don't think so...

$\endgroup$
  • 1
    $\begingroup$ You should be using MathJax by now $\endgroup$ – gen-z ready to perish Nov 17 '17 at 21:29
  • 4
    $\begingroup$ Hint: use any lever twice and you get a result as if you didn't use that particular lever at all. $\endgroup$ – CiaPan Nov 17 '17 at 21:31
  • 1
    $\begingroup$ For a given tile configuration, flipping all the levers (both rows and columns) yields the same configuration. $\endgroup$ – Fabio Somenzi Nov 17 '17 at 22:14
1
$\begingroup$

You can prove by induction that for an $m \times n$ board with $m+n$ levers (or switches), the number of configurations reachable from "all black tiles" is $2^{m+n-1}$.

Base: For $m=n=1$ there is one tile that can be in two configurations.

Inductive Step: Suppose an $m \times n$ board has $2^{m+n-1}$ reachable configurations. Adding one row yields an $(m+1) \times n$ board. For each configuration of the $m \times n$ board and for each position of the new row switch, a distinct configuration is obtained. The reasoning is the same when a column is added.

For the $13 \times 14$ board, we get at most $2^{26} = 67108864$ different configurations, no matter how we flip the switches and no matter which configuration we start with.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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