The integers from to are placed in some order into an grid of cells with one number in each cell. Let be the number placed in the cell in row and column , and let be the sum of the absolute differences between adjacent cells. That is,
Find the remainder when the maximum possible value of is divided by .
Consider a checkerboard coloring of the grid of cells resulting in white and black cells. Consider an assignment involving placing the larger numbers on the black cells and the smaller numbers on the white cells.
Under this arrangement, note that some cells get counted more times than other cells. For example cells on the outer ring of the board get counted or times, but cells on the interior get counted times. So for the black cells, we place larger numbers on the cells that are counted more times and smaller numbers on the cells that are counted less. We do a similar process for the white cells but flipped (smaller when counted more and larger when counted less).
For each color, there are cells counted twice, cells counted times and cells counted times. Thus, the best we can achieve with this construction is
Summing cleverly: .
Now, we show that this is in fact the maximum we can possibly make a sum. Consider the final sum, after we have flipped all the absolute value signs (turned into if and otherwise.
Let for be the positive terms and defined similarly for the negative terms. The sum is now:
Now, note that in this new sum, each appearance of any number from contributes either or . We will assume, for the purposes of bounding, that a number contributes as this only increases the sum. Taking into account that numbers are counted times, are counted times, and are counted twice, we assign numbers with larger values of to larger multiplicities by rearrangement inequality. The largest values of are when is on the range or , the next larger values are when is on the range or and the remaining values are assigned to a multiplicity of . Clearly, this gives us the same sum as the one we computed above, so our answer is the maximum.
Solution 2:
Let be the set of cells in the grid, and represent the number of edges in the grid connecting cells, where each edge is labeled with the weight (where the edge is the edge connecting the cells with and ). Denote each edge in connecting cells with and as , with .
Our goal is to find
Define to be the set of cells in labelled with a number at most . Then, the number of edges of with is simply the number of edges between and (we will denote this as .
Consider some arbitrary set with . We claim that is maxmimized when has no internal edges.
Note that we can say that for each vertex , each edge goes either to another vertex in , or a vertex in . Thus, all vertices from that do not go to must go to another vertex in , hence
as each internal edge will be double counted, one for each endpoint in . But note that for all .
We claim one possible maxima of this is given by the following construction: color the squares in a checkerboard fashion, and call a square "corner" if it has degree , "edge" if it has degree , and "center" if it has degree . Then,
Note that this is just a greedy algorithm. If we have center squares, imagine tiling the inner central grid with dominoes. Since we have dominoes, the Pigeonhole Principle tells us that at least domino pairs exist. This means that for every increase in degree we introduce (which is a maximum of to ), we also increase the number of internal edges by at least , hence our sum increases by at most (with a similar idea if we have more than edge squares). Thus indeed we get an optimal value of whenever has no internal edges.
This means that the optimal solution is when has no internal edges, so thus the lowest numbers must be one color (assume black) of the checkerboard (note that this maximizes for ). This would mean the highest numbers would be the other color (white), and this maximizes for ( is the highest numbers). Thus, our sum is maximized with this checkerboard.
Our checkerboard pattern means that all edges are weighed with the value
Note that there are black (center) cells that have degree , with degree , and with degree (and the same for white cells). By the rearrangement inequality, we want our largest black (and smallest white) to be center cells, and the smallest black and largest white on the corners. Thus, the maximum possible sum is
for an answer of .
The problems on this page are the property of the MAA's American Mathematics Competitions