5
$\begingroup$

Each cell of an $\;8\times8\;$ table is colored either black or white such that every column has equal number of black cells and no two rows have equal number of black cells.

Find the maximum possible number of pairs of adjacent cells that have distinct colors.

The cells are adjacent if they share a common edge.

My attempt :

Suppose that the $\;8\times8\;$ table has $k$ black cells, we have $8\mid k$.

The number of black cells in each row can be between $0$ and $8$,

so the number of black cells in the $\;8\times8\;$ table is between $28$ and $36$.

Since $8\mid k\;$ and $28\leq k\leq36$, so $k=32$ and each column has $4$ black cells.

Number of pairs of adjacent cells that have distinct colors =

Number of pairs of adjacent cells - Number of pairs of adjacent cells that have same colors.

Number of pairs of adjacent cells $= 7 \times 8 \times 2 = 112$.

Number of pairs of adjacent cells that have same colors :

  1. Consider adjacent cells in the same row.

The rows that have 0 or 8 black squares will have 7 pairs of adjacent cells that have same colors.

The rows that have 1 or 7 black squares will have 5 pairs of adjacent cells that have same colors.

The rows that have 2 or 6 black squares will have 3 pairs of adjacent cells that have same colors.

The rows that have 3 or 5 black squares will have 1 pair of adjacent cells that have same colors.

Total number of pairs of row adjacent cells that have same colors is 32.

  1. Consider adjacent cells in the same column.

I don't know how to find the number of pairs of column adjacent cells that have same colors.

I constructed a table and found that it was 3 but didn't know how to prove.

enter image description here

$\endgroup$
5
$\begingroup$

Let an alternating column be one that is black-white-black-white etc. or white-black-white-black etc.

Observe:

  • An alternating column has no adjacent cells of the same colour
  • A non-alternating column has at least one pair of adjacent cells of the same colour
  • An alternating column has all even rows the same colour

Now without loss of generality assume the row which is all white is an even row, else we can flip the board across the horizontal rule through the middle. Consider the row out of rows 2, 4, 6 and 8 which has the most black squares. This must have at least 3 black squares, else there are four rows with 0, 1 or 2 black squares and by the pigeonhole principle two rows must have the same number of black squares.

Then at least three columns have a black cell in the even row with the most black cells. But they have a white cell in the row which is all white, and we stipulated that this was an even row too. So this column cannot be alternating, since not all even rows are of the same colour.

Thus there are at least three non-alternating columns and at least three pairs of adjacent cells of the same colour.

$\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.