Colour how?

Probability Level 5

Peter starts with a $20 \times 18$ grid of white squares and colors some of them blue. Then, in each white square not colored, he writes down the number of blue squares that share an edge with it.

Determine the maximum possible sum of such numbers he writes down.

Here is a $3 \times 4$ example of how to write down the numbers and get their sum.

The answer is 682.

2 solutions

Zico Quintina
May 12, 2018

Peter should be able to maximize the sum of the numbers by painting half the squares blue in a checkerboard (or chess board) pattern. This would mean all the white squares not on one of the edges would be adjacent to four blue squares, the non-corner white squares on an edge would be adjacent to three blue squares, and the corner white squares would be adjacent to two blue squares. (A smaller example is shown below.)

Internal squares: There are $18 \times 16$ internal squares; half would be white. Their sum would be $\dfrac{18 \times 16}{2} \times 4 = 576$ .
Edge squares: There are $(20 \times 18) - (18 \times 16) - 4$ edge squares; half would be white. Their sum would be $\dfrac{(20 \times 18) - (18 \times 16) - 4}{2} \times 3 = 102$ .
Corner squares: There are $4$ corner squares, half would be white. Their sum would be $\dfrac{4}{2} \times 2 = 4$ .

So the sum of all numbers would be $576 + 102 + 4 = \boxed{682}$

I have no strict proof that this is a maximum; but informally at least, if we change any current white square to blue, we would simply remove the white square's number without increasing the numbers in any other white squares (because white squares aren't adjacent to other white squares), so the total would decrease; and if we change any current blue square to white, that square would be numbered zero, and the four adjacent white squares would have their numbers reduced by one, so again the total would decrease.

Anyone have suggestions for a formal proof that this is indeed a maximum?

If you swap blue squares and white squares, the sum doesnt change! The number in the white squares is the number of blue squares adjacet to it, conversely, the amout of times a blue square gets "counted" is the number of white squares adjacent to it. So if the way to get the maximum sum was by filling less then half of the white squares, then you could swap whites and blues to get another "oposite" way that fills more than half. But if that happens, its clear that there must be at least 1 blue square with 2 blue squares adjacent to it, and if you remove it, the sum can't decrease. So there must be a way to get the maximal sum that fills up exatly half of the white squares. From here, its preety clear the checkerboard pattern maximizes the sum, as it maximkzes the number of 4s and minimizes the mumer of 2s

Pedro Cardoso - 3 years ago

James Pohadi
May 12, 2018

Let $x$ be the sum of all numbers that Peter writes down.

Since the number in white square is the number of the blue square that share an edge with it, $x$ is basically just number of edge of the overall blue shape if the edge is not the perimeter of the $20\times18$ rectangle (perimeter of the blue shape $-$ the intersection between the perimeter of the blue shape with the perimeter of $20\times18$ rectangle)

Theoretical maximum of $x$ is if all the sides of the small squares inside the rectangle are the edge of the blue shape, which can be achieved if it is chess-board shape.

In general, for any $m\times n$ rectangle, the maximum $x$ is $(m-1)n+m(n-1) = 2mn-m-n$

Hence, the maximum $x$ for $20 \times 18$ rectangle is $2\times20\times18-20-18=\boxed{682}$

Great way to look at it!

zico quintina - 3 years ago

Thank you :)

James Pohadi - 3 years ago

It proves that 682 is maximum by observation

James Pohadi - 3 years ago

Colour how?

The answer is 682.

2 solutions

0 pending reports