Leticia has a $9\times 9$ board. She says that two squares are friends is they share a side, if they are at opposite ends of the same row or if they are at opposite ends of the same column. Every square has $4$ friends on the board. Leticia will paint every square one of three colors: green, blue or red. In each square a number will be written based on the following rules: - If the square is green, write the number of red friends plus twice the number of blue friends. - If the square is red, write the number of blue friends plus twice the number of green friends. - If the square is blue, write the number of green friends plus twice the number of red friends. Considering that Leticia can choose the coloring of the squares on the board, find the maximum possible value she can obtain when she sums the numbers in all the squares.
Problem
Source: Pan-American Girls' Mathematical Olympiad 2022, Problem 1
Tags: combinatorics, grids, PAGMO, Colors
28.10.2022 05:16
This is the only problem from day 1 that I actually like. It is easy and cute. The maximum is $6\times 81=486$ which can be achieved using the following configuration [asy][asy] unitsize(0.5cm); for (int i = 0; i <= 9; ++i) { draw((i, 0)--(i, 9)); draw((0, i)--(9, i)); } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { filldraw((3i,3j)--(3i+1,3j)--(3i+1,3j+1)--(3i,3j+1)--cycle, red); filldraw((3i+1,3j)--(3i+2,3j)--(3i+2,3j+1)--(3i+1,3j+1)--cycle, blue); filldraw((3i+2,3j)--(3i+3,3j)--(3i+3,3j+1)--(3i+2,3j+1)--cycle, green); } } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { filldraw((3i,3j+1)--(3i+1,3j+1)--(3i+1,3j+2)--(3i,3j+2)--cycle, green); filldraw((3i+1,3j+1)--(3i+2,3j+1)--(3i+2,3j+2)--(3i+1,3j+2)--cycle, red); filldraw((3i+2,3j+1)--(3i+3,3j+1)--(3i+3,3j+2)--(3i+2,3j+2)--cycle, blue); } } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { filldraw((3i,3j+2)--(3i+1,3j+2)--(3i+1,3j+3)--(3i,3j+3)--cycle, blue); filldraw((3i+1,3j+2)--(3i+2,3j+2)--(3i+2,3j+3)--(3i+1,3j+3)--cycle, green); filldraw((3i+2,3j+2)--(3i+3,3j+2)--(3i+3,3j+3)--(3i+2,3j+3)--cycle, red); } } [/asy][/asy] Notice that two friends of different colors add 3 to the total sum, because it adds one to one of the cells and two to the other one. Moreover, two friends of the same color don't add anything to the sum. Thus the sum is equal to the number of friends of different colors, which is less than or equal to the total number of friends. There are $\frac{4\times 81}{2}=486$ friends in total and we get the desired maximum.
28.10.2022 22:40
The answer is $3 \cdot 162 = 486$. The ``maximality'' is mostly a red herring due to the following claim: Claim: The sum in question is equal to $3$ times the number of neighboring cells which are different colors. Proof. If $s$ and $t$ are different colors, one of them gets counted as $+2$ and the other as $+1$. No contribution if they're the same color. $\blacksquare$ As there are $162$ pairs of neighboring cells, the bound of $486$ follows. Equality occurs in any coloring with no adjacent cells of the same color, e.g.\ $x+y \bmod 3$.
30.10.2022 05:49
Nice and easy. Note that any two friends contributes $3$ in total (e.g. green and blue has $2$ for the green and $1$ for the blue), thus the sum must be $\frac{3\cdot 4\cdot 81}{2}=486.$
21.01.2023 01:58
The answer is $81 \cdot 6 = 486$. Observe that the total sum of numbers written is precisely equal to three times the number of pairs of adjacent squares. However, there are at most $81 \cdot 2$ such pairs of adjacent squares in the grid, which proves the bound. It is sharp when all neighboring squares have different colors.
03.04.2023 16:53
Notice if a blue square is next to a red one, the blue square increases by $2$ due to this adjacency and the red square increases by $1$ due to this adjacency. Hence, the total sum of the squares increases by $3$. This is similar for blue next to green and red next to green. Hence, the total sum of the squares is \[3\sum_{\text{cyc}}\#\text{ of blue next to red}\le 3\cdot\frac{81\cdot 4}{2}=486\]where the RHS is counting three times the total number of pairs of squares adjacent to each other. We see $486$ is possible when we color the first row $brgbrgbrg$ and then we shift this to the right be one for the second row, shift it by two for the second row, and so on. $\square$
23.04.2023 19:24
We claim that the answer is $486$. Notice that the maximum possible sum occurs when no two squares of the same color are adjacent (because if two squares of the same color are adjacent, if we set one of the squares to be a different color we can make the sum larger), and this is just the number of pairs of adjacent squares times $3$. Notice that there are $\frac{1}{2}*4*9*9$ or $162$ such pairs, and multiplying by $3$, we get a maximum of $486$. We now must prove that this is attainable, which is true since it is possible when we alternate colors symmetrically between blue, red, and green, and we are done.
07.05.2023 19:20
Consider how many squares each pair of friends contributes. Notice that they have to be different colors (otherwise no contribution), and if so, then such a pair of friends contributes $3$ to the sum. (For example, if we had a red friend and a blue friend, then we would have $2+1=3$ from this pair.) There are $81$ squares on the board, so there are $\frac{4\cdot 81}{2}=162$ pairs of friends on the board (each square has $4$ neighbors but you counted twice for each pair of friends). Therefore the sum would be at most $162\cdot 3=486$. It is achieved by a repeating pattern of $RGB$ in the first row, shifting this by $1$ for each subsequent row. $\blacksquare$
30.08.2023 05:33
Looking at a specific relationship when green and red are neighbors (note that the conditions are symmetric so these properties will hold for the other colors). We can see that this relations ship adds $1$ to green and adds $2$ to red. Since the properties are symmetric we can see that each pair of neighbors that is different from each other will sum to $3$. Thus the maximum is $\frac{4\cdot81}{2} \cdot3 = \boxed{486}$. This is easily attainable by starting with green in the upper left corner. Then coloring all of those neighbors red. Then coloring all of those neighbors blue, and repeating this till the grid is full. $\blacksquare$
18.09.2023 06:12
We claim the answer is $486$, which works when all adjacent squares are of different colors. We know prove this is the maximum. Claim: For any pair of neighboring squares, the value that each one contributes to each other, sums to at max $3$. Proof: If in a neighboring pair, the colors are different, one must contribute $2$ to the other, while the other must contribute $1$ to the other, leading to a sum of $3$. If the colors are the same, the total contribution is $0$. Thus, the maximum occurs when all neighboring pairs are of different colors. As there are a total of $162$ neighboring pairs, the maximum sum of values is: \[162\cdot 3=486.\]
15.10.2023 23:12
18.10.2023 00:34
We claim the answer is $486$. This is possible with the below configuration (not mine), [asy][asy] unitsize(0.5cm); for (int i = 0; i <= 9; ++i) { draw((i, 0)--(i, 9)); draw((0, i)--(9, i)); } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { filldraw((3i,3j)--(3i+1,3j)--(3i+1,3j+1)--(3i,3j+1)--cycle, red); filldraw((3i+1,3j)--(3i+2,3j)--(3i+2,3j+1)--(3i+1,3j+1)--cycle, blue); filldraw((3i+2,3j)--(3i+3,3j)--(3i+3,3j+1)--(3i+2,3j+1)--cycle, green); } } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { filldraw((3i,3j+1)--(3i+1,3j+1)--(3i+1,3j+2)--(3i,3j+2)--cycle, green); filldraw((3i+1,3j+1)--(3i+2,3j+1)--(3i+2,3j+2)--(3i+1,3j+2)--cycle, red); filldraw((3i+2,3j+1)--(3i+3,3j+1)--(3i+3,3j+2)--(3i+2,3j+2)--cycle, blue); } } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { filldraw((3i,3j+2)--(3i+1,3j+2)--(3i+1,3j+3)--(3i,3j+3)--cycle, blue); filldraw((3i+1,3j+2)--(3i+2,3j+2)--(3i+2,3j+3)--(3i+1,3j+3)--cycle, green); filldraw((3i+2,3j+2)--(3i+3,3j+2)--(3i+3,3j+3)--(3i+2,3j+3)--cycle, red); } } [/asy][/asy] Notice that each of the $81$ squares has $4$ friends so there are a total of $\frac{81 \cdot 4}{2}=162$ unique pairs of friends. Each of these pairs will add $3$ to the total sum if they are distinct and $0$ if they are the same. Thus, the maximum possible value Leticia can obtain is $3 \cdot 162=486$.
08.12.2023 17:59
We can instead think about this sum as a score. Leticia gets one point for a (green cell, red friend) pair, etc. But for a pair of neighbors, (A,B) and (B,A) always score three points in total if they are different colors and no points in total otherwise. Now a mod $3$ diagonal coloring guarantees that each pair of neighbors has different colors so the answer is just $2\cdot 9\cdot 9\cdot 3=\boxed{486}$.
26.12.2023 05:05
The answer is $9 \cdot 18 \cdot 3 = \boxed{486}$. Note that if two neighboring squares are different colors, together they contribute $3$ to the total sum (if they are the same color, they contribute nothing). There are $9$ pairs of neighbors for each row and each column, and $9 \cdot 18 = 162$ total such pairs, so the maximum is indeed 486. This can be achieved by having the first row be G, R, B, and so on, the second row be R, B, G, and so on, the third row be B, G, R, and so on, and then cycling this for every three consecutive rows.
26.12.2023 19:21
The maximum is $\boxed{486}$, achieved with a checkerboard-style coloring with no two adjacent cells the same color. Consider each of the $\frac{81 \cdot 4}{2} = 162$ borders between two cells on the board. If the two squares with that border are the same color, there is no value added to either square. If they are of different colors, this border contributes a $+1$ to one of the squares and $+2$ to the other, so $+3$ to the total sum of all values. Hence our optimal sum is $162 \cdot 3 = 486$, which we have shown to be achievable. $\blacksquare$
26.12.2023 21:19
The answer is $\boxed{486}$ and the construction is outlined in the attached figure. Note that if two different colors are neighbours, then they contribute a total of $1+2=3$ to the sum. We need to maxmise the number of such ``neighbourings". The total number of neighbourings are $\frac{81\cdot4}{2}=162$. So, the maximum possible sum is $486$.
Attachments:

28.02.2024 19:07
for each pair of two, they contribute to $3$ because there are $162$ pairs of $2$, the answer is $162*3=\boxed{486}$
09.07.2024 23:38
Let $S$ be the sum of all squares on the board. Note that for any two neighboring squares that have different colors, they will contribute $3$ to $S$. Thus we have $\frac{4(81)}{2}=162$ pairs of neighboring squares in total on the toroidal board and that means $S \leq 3(162)=486$. Any construction where every neighboring square has distinct colors work, an example is one posted above. [asy][asy] unitsize(0.5cm); for (int i = 0; i <= 9; ++i) { draw((i, 0)--(i, 9)); draw((0, i)--(9, i)); } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { filldraw((3i,3j)--(3i+1,3j)--(3i+1,3j+1)--(3i,3j+1)--cycle, red); filldraw((3i+1,3j)--(3i+2,3j)--(3i+2,3j+1)--(3i+1,3j+1)--cycle, blue); filldraw((3i+2,3j)--(3i+3,3j)--(3i+3,3j+1)--(3i+2,3j+1)--cycle, green); } } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { filldraw((3i,3j+1)--(3i+1,3j+1)--(3i+1,3j+2)--(3i,3j+2)--cycle, green); filldraw((3i+1,3j+1)--(3i+2,3j+1)--(3i+2,3j+2)--(3i+1,3j+2)--cycle, red); filldraw((3i+2,3j+1)--(3i+3,3j+1)--(3i+3,3j+2)--(3i+2,3j+2)--cycle, blue); } } for (int i = 0; i < 3; ++i) { for (int j = 0; j < 3; ++j) { filldraw((3i,3j+2)--(3i+1,3j+2)--(3i+1,3j+3)--(3i,3j+3)--cycle, blue); filldraw((3i+1,3j+2)--(3i+2,3j+2)--(3i+2,3j+3)--(3i+1,3j+3)--cycle, green); filldraw((3i+2,3j+2)--(3i+3,3j+2)--(3i+3,3j+3)--(3i+2,3j+3)--cycle, red); } } [/asy][/asy]
13.07.2024 10:05
Let $T$ be the sum of all the squares on the board. Additionally, let $R$, $B$, and $G$ be the total number of red, blue, and green squares on the board. Define $r_{(i,c)}$ to be the number of neighbors the $i$th red square has of color $c$, where $c$ is ether $r$, $b$, or $g$, and define $b_{(i,c)}$ and $g_{(i,c)}$ similarly. We have that \[T=\sum_{i=1}^R r_{(i, g)}+2r_{(i,b)}+\sum_{i=1}^B b_{(i, r)}+2b_{(i,g)}+\sum_{i=1}^G g_{(i, b)}+2g_{(i,r)}\]by thinking about the what neighbors count a particular square and by how much. Then, \[T=\sum_{i=1}^R r_{(i, b)}+2r_{(i,g)}+\sum_{i=1}^B b_{(i, g)}+2b_{(i,r)}+\sum_{i=1}^G g_{(i, r)}+2g_{(i,b)}\]is obtained by thinking about how much a particular square counts its neighbors. By summing them, we obtain \[\frac{2}{3}T =\sum_{i=1}^R r_{(i, b)}+r_{(i,g)}+\sum_{i=1}^B b_{(i, g)}+b_{(i,r)}+\sum_{i=1}^G g_{(i, r)}+g_{(i,b)},\]and this is simply maximized when no neighbors have the same color, which can be obtained by coloring the diagonals three different colors and repeating the pattern. Therefore, we have $\frac{2}{3}T=4\cdot 9^2$, giving $T=486$.
31.07.2024 01:07
It is easy to see that the final sum is $3$ times the number of adjacent cells with different color, which must be at most $3 \times 2 \times 9^2 = 486.$ This is achievable by the following coloring: \[\begin{matrix} R & G & B & R & G & B & R & G & B\\ G & B & R & G & B & R & G & B & R\\ B & R & G & B & R & G & B & R & G\\ R & G & B & R & G & B & R & G & B\\ G & B & R & G & B & R & G & B & R\\ B & R & G & B & R & G & B & R & G\\ R & G & B & R & G & B & R & G & B\\ G & B & R & G & B & R & G & B & R\\ B & R & G & B & R & G & B & R & G\\ \end{matrix}\]
08.10.2024 20:19
03.11.2024 05:50
Note that the answer is just $3$ times the number of adjacent cells with different colors (since that pair of friends would get a total of $2+1 = 3$ points). The answer is $$3\cdot 162 = \boxed{486},$$and a construction is possible when all adjacent squares have different colors.
06.12.2024 18:43
The sum is just the number of adjacent cell pairs with different colors, each counted three times. There are $81$ cells, each with $4$ pairs but each pair is counted twice so divide by $2$. Multiply by $3$ to get $81 \cdot 4 \cdot \frac12 \cdot 2 = 486$, construction is trivial.