Given positive integer $n \geq 2$. Now Cindy fills each cell of the $n*n$ grid with a positive integer not greater than $n$ such that the numbers in each row are in a non-decreasing order (from left to right) and numbers in each column is also in a non-decreasing order (from top to bottom). We call two adjacant cells form a $domino$ , if they are filled with the same number. Now Cindy wants the number of $domino$s as small as possible. Find the smallest number of $dominos$ Cindy can reach. (Here, two cells are called adjacant if they share one common side)
Problem
Source: 2024 CWMO P4
Tags: grid, combinatorics
07.08.2024 11:46
Any solution? I found an example for $\lfloor \frac{n^2}{2} \rfloor$
07.08.2024 12:34
egxa wrote: Any solution? I found an example for $\lfloor \frac{n^2}{2} \rfloor$ Not exactly right, very close
07.08.2024 13:17
Imaging the visual proof of the first n odd numbers summing up to n^2, with the 1x1 square beeing the one on the left bottom. Now every L shape with m squares of area Will have inside at least m-n domino ( suppose m>n ) and summing up this gives you half the bound. The other half you get from doing the same thing on the upmost right Square beeing the 1x1 of the "prof of the odd numbers" tiling ( and checking that you are'nt double counting any domino 'cause the two tilings are 'perpendicular' ). To prove that this is enought you can tile in such a way that every bound is sharp ( suppose n=5, cartesian plane coordinates, put a 3 on x=y, a 4 on x=y+1 and a 3 on x=y-1 and fill the rest with 1s and 5s, should give you n^2/2 ). The way I came up with this is by looking at the fact that #dominoes are 2n(n-1)-#(non dominoes) and if you look at the peremeter between two subsequent numbers you want that to be maximum
10.08.2024 13:21
any solution?
11.08.2024 19:40
Twoisaprime wrote: egxa wrote: Any solution? I found an example for $\lfloor \frac{n^2}{2} \rfloor$ Not exactly right, very close I got the same answer. Here is my solution hopefully you can point out the mistake. Answer: $$ \left\{ \begin{array}{lr} 2k^2, & n=2k \\ 2k^2+2k, & n=2k+1 \end{array} \right\} $$ Construction: The constructions for $n=7$ and $n=8$ easily generalize $$ \begin{bmatrix} 1&1&1&1&2&3&4\\ 1&2&2&2&3&4&5\\ 1&2&3&3&4&5&6\\ 1&2&3&4&5&6&7 \\ 2&3&4&5&5&6&7\\ 3&4&5&6&6&6&7\\ 4&5&6&7&7&7&7 \\ \end{bmatrix} $$ $$ \begin{bmatrix} 1&1&1&1&2&3&4&5\\ 1&2&2&2&3&4&5&6\\ 1&2&3&3&4&5&6&7\\ 1&2&3&4&5&6&7&8 \\ 2&3&4&5&5&6&7&8\\ 3&4&5&6&6&6&7&8\\ 4&5&6&7&7&7&7&8 \\ 5&6&7&8&8&8&8&8\\ \end{bmatrix} $$ Bound: Notice that any down-right path of length $n+k$ must contain $k$ dominoes. The following stuff is hard to describe but relatively straight-forward. Label the top left corner $(1,1)$ and bottom right corner $(n,n)$. Consider the down right paths that starts at $(1,k)$ pass through $(n+1-k,k)$ and ends at $(n+1-k,n)$ and the down right paths that start at $(k,1)$ pass through $(k,n+1-k)$ and end at $(n,n+1-k)$ (L-paths). These paths all contain different pairs of adjacent cells. Standard computation gives the desired bound.
12.08.2024 07:49
sami1618 wrote: Twoisaprime wrote: egxa wrote: Any solution? I found an example for $\lfloor \frac{n^2}{2} \rfloor$ Not exactly right, very close I got the same answer. Here is my solution hopefully you can point out the mistake. Answer: $$ \left\{ \begin{array}{lr} 2k^2, & n=2k \\ 2k^2+2k, & n=2k+1 \end{array} \right\} $$ Construction: The constructions for $n=7$ and $n=8$ easily generalize $$ \begin{bmatrix} 1&1&1&1&2&3&4\\ 1&2&2&2&3&4&5\\ 1&2&3&3&4&5&6\\ 1&2&3&4&5&6&7 \\ 2&3&4&5&5&6&7\\ 3&4&5&6&6&6&7\\ 4&5&6&7&7&7&7 \\ \end{bmatrix} $$ $$ \begin{bmatrix} 1&1&1&1&2&3&4&5\\ 1&2&2&2&3&4&5&6\\ 1&2&3&3&4&5&6&7\\ 1&2&3&4&5&6&7&8 \\ 2&3&4&5&5&6&7&8\\ 3&4&5&6&6&6&7&8\\ 4&5&6&7&7&7&7&8 \\ 5&6&7&8&8&8&8&8\\ \end{bmatrix} $$ Bound: Notice that any down-right path of length $n+k$ must contain $k$ dominoes. The following stuff is hard to describe but relatively straight-forward. Label the top left corner $(1,1)$ and bottom right corner $(n,n)$. Consider the down right paths that starts at $(1,k)$ pass through $(n+1-k,k)$ and ends at $(n+1-k,n)$ and the down right paths that start at $(k,1)$ pass through $(k,n+1-k)$ and end at $(n,n+1-k)$ (L-paths). These paths all contain different pairs of adjacent cells. Standard computation gives the desired bound. The answer is correct, and your solution should also be correct. There is a simpler construction that I used during the exam.
12.08.2024 08:57
Hi Lincoln Orz
12.08.2024 13:43
sami1618 wrote: Twoisaprime wrote: egxa wrote: Any solution? I found an example for $\lfloor \frac{n^2}{2} \rfloor$ Not exactly right, very close I got the same answer. Here is my solution hopefully you can point out the mistake. Answer: $$ \left\{ \begin{array}{lr} 2k^2, & n=2k \\ 2k^2+2k, & n=2k+1 \end{array} \right\} $$ Construction: The constructions for $n=7$ and $n=8$ easily generalize $$ \begin{bmatrix} 1&1&1&1&2&3&4\\ 1&2&2&2&3&4&5\\ 1&2&3&3&4&5&6\\ 1&2&3&4&5&6&7 \\ 2&3&4&5&5&6&7\\ 3&4&5&6&6&6&7\\ 4&5&6&7&7&7&7 \\ \end{bmatrix} $$ $$ \begin{bmatrix} 1&1&1&1&2&3&4&5\\ 1&2&2&2&3&4&5&6\\ 1&2&3&3&4&5&6&7\\ 1&2&3&4&5&6&7&8 \\ 2&3&4&5&5&6&7&8\\ 3&4&5&6&6&6&7&8\\ 4&5&6&7&7&7&7&8 \\ 5&6&7&8&8&8&8&8\\ \end{bmatrix} $$ Bound: Notice that any down-right path of length $n+k$ must contain $k$ dominoes. The following stuff is hard to describe but relatively straight-forward. Label the top left corner $(1,1)$ and bottom right corner $(n,n)$. Consider the down right paths that starts at $(1,k)$ pass through $(n+1-k,k)$ and ends at $(n+1-k,n)$ and the down right paths that start at $(k,1)$ pass through $(k,n+1-k)$ and end at $(n,n+1-k)$ (L-paths). These paths all contain different pairs of adjacent cells. Standard computation gives the desired bound. Sorry, I wrote the answer in a more complex form, so I didn't recognize it. Besides, My construction is also different from yours.