**Problem link: [CSES — Distinct sums grids](https://cses.fi/problemset/task/3424/)** ↵
**Problem statement:** ↵
**Create an $n \times n$ grid that fulfills the following requirements:** ↵
**  $1. $ Each integer $1 \dots n$ appears n times in the grid.** ↵
**  $2. $ If we create a set that consists of all sums in rows and columns, there are 2n distinct values.** ↵
↵
**My solution:** ↵
For a given $n \gt 4$, create a $n \times m$ matrix named A, every element in A will be as follow:↵
$$↵
a_{i,j} =↵
\begin{cases}↵
n, & j = 1,\\↵
i, & j > i,\\↵
i-1, & 2 \le j \le i.↵
\end{cases}↵
$$ ↵
For example, n = 6 would look like this:↵
$$↵
A =↵
\begin{pmatrix}↵
6 & 1 & 1 & 1 & 1 & 1\\↵
6 & 1 & 2 & 2 & 2 & 2\\↵
6 & 2 & 2 & 3 & 3 & 3\\↵
6 & 3 & 3 & 3 & 4 & 4\\↵
6 & 4 & 4 & 4 & 4 & 5\\↵
6 & 5 & 5 & 5 & 5 & 5↵
\end{pmatrix}↵
$$ ↵
Now it can be seen that for each row $i$ from 1 to n, its sum is as follow: $row_{i} = 2 \times n - 1 + (n - 2) \times (i - 1)$ ↵
For each column from 2 to n, its sum is as follow: $column_{i} = \frac{n \times (n - 1)}{2} + i - 1$. And for the first columns, its sum is $n ^ 2$ ↵
This construction give us a powerful fact that is there can only be one row's sum being equal to a column's sum, and from the third to last row onward, there can not be a match between these and any column. Also the matching column can not be the second and the last. This is true for $n \gt 4$ and will be proven later in this blog. ↵
From this we can do the following procedure: Find the matching row and column $i, j$, swap $a_{2, 1}, a_{2, j}$, and then swap $a_{i + 1, n}, a_{i + 2, n}$_{i} = \frac{n \times (n - 1)}{2} + i - 1$ and $col_{1} = n ^ 2$ ↵
This construction give us a powerful fact that is there would always be atleast 1 matching position. Also, there can only be one row's sum being equal to a column's sum, and from the third to last row onward, there can not be a match between these and any column. Moreover the matching column can not be the second and the last. This is true for $n \gt 4$ and will be proven later in this blog. ↵
From this we can do the following operations: Find the matching row and column $i, j$, swap $a_{2, 1}, a_{2, j}$ and then swap $a_{i + 1, n}, a_{i + 2, n}$ ↵
Doing this, we change $col_{1} = n ^ 2$ to $n \times (n - 1) + 2$ and $col_{j} = \frac{n \times (n - 1)}{2} + j - 1$ to $\frac{n \times (n - 1)}{2} + j - 3 + n$. ↵
↵
And $row_{i + 1} = 2 \times n - 1 + (n - 2) \times i$ to $2 \times n + (n - 2) \times i$, $row_{i + 2} = 2 \times n - 1 + (n - 2) \times (i + 1)$ to $2 \times n - 2 + (n - 2) \times (i + 1)$, this is true because $i + 1, i + 2$ is not $n - 1$ and $n$, which guarantee that $a_{i + 1, n} + 1 = a_{i + 2, n}$.↵
↵
Consider $col_{1} = n \times (n - 1) + 2$: this is still the single largest value, so there is only one ↵
      $row_{i + 1} = 2 \times n + (n - 2) \times i$: this value does not equal to any other rows or columns because the maximum column is $\frac{n \times (n - 1)}{2} + n - 1$, and since $i, j$ matches this value is smaller than $\frac{n \times (n - 1)}{2} + j - 3 + n$. Alongside the fact that $row_{i + 1} = 2 \times n + (n - 2) \times i = row_{i} + n - 2$, and because $row_{i} = col_{j}$: $$row_{i + 1} = 2 \times n + (n - 2) \times i = row_{i} + n - 2 = col_{i} + n - 2 = \frac{n \times (n - 1)}{2} + j - 3 + n > \frac{n \times (n - 1)}{2} + n - 1 $$↵
      So there is only one sum equal $row_{i + 1}$ ↵
      $row_{i + 2}$ : the same as above, so there is also only one sum equal $row_{i + 2}$ ↵
      $col_{j} = \frac{n \times (n - 1)}{2} + j - 3 + n$ : after the increment, it now is larger than the $n\text{-th}$ column because it matches at a column with index larger than 2, the difference from that to the $n\text{-th}$ column is smaller than $n - 2$. This would have matched with the $i+1\text{-th}$ row but since we have changed it before, it now does not match with any row so there is only one appearance of this sum. ↵
After doing all of the above, we would end up with a 2d matrix which satisfy the conditions. ↵
↵
**Now i will be proving the claims above for $n \gt 4$, which is:** ↵
**  $1. $ There would always be atleast 1 matching position.** ↵
**  $2. $ There can only be one row's sum being equal to a column's sum.** ↵
**  $3. $ From the third to last row onward, there can not be a match between these and any column.** ↵
**  $4. $ The matching column can not be the second or the last.** ↵
Proof: ↵
$1. $ It can be seen that the minimum of all column which is $col_{2} = 1 + \frac{n \times (n - 1)}{2} \gt row_{1} = 2 \times n - 1$ and the $n\text{-th}$ column which also is the second largest: $col_{n} = \frac{n \times (n - 1)}{2} + n - 1 \lt 2 \times n - 1 + n^n $. Which imply that there must be at least one matching position. ↵
$2. $ For two of them to match, the matching column must be the second and the last column. You can visualize the value of the columns as a window of size n, while the difference between each column is n — 1. From this, we can try to find the first matching position $i$ by solving this equation:↵
$$1\ +\ \frac{\left(n\ -\ 1\right)n}{2}=2\cdot n-1+\left(n-2\right)\cdot\left(i-1\right)$$↵
$$\implies \frac{n-1}{2}-\frac{n-1}{n-2}+1=i$$↵
It can be shown that the function above only return positive interger for n = 2 and 4, so for $n /gt 4$ it return fractional numbers. From this, we can see that for n > 4 there can not be two matching positions. ↵
$3. $ For it to match then $col_{n} \geq row_{n-2}$, which is the same as this inequation:↵
$$n-1+\frac{\left(n-1\right)n}{2}-\left(2\cdot n-1\ +\ \left(n-3\right)^{2}+\left(n-2\right)\cdot2\right) \geq 0$$↵
$$\implies \frac{5}{2}x-\frac{x^{2}}{2}-5 \geq 0$$ ↵
It can be shown that the inequation above have no real solution, so point proven. ↵
$4. $ This is the direct result of $1. $, because no two matching so the position can not be the second or the last. ↵
Example of the mentioned functions in desmos:↵
↵
For the special case $n = 4$: we can just bruteforce to find the solution ↵
              $n \le 3$: impossible ↵
↵
Thank you for reading my post, this is the first time i have ever written a blog, along with how bad i am at explaining so i expect a lot of criticism. Please point out what i could have done better so that i can improve, thank you so much!!
**Problem statement:** ↵
**Create an $n \times n$ grid that fulfills the following requirements:** ↵
**  $1. $ Each integer $1 \dots n$ appears n times in the grid.** ↵
**  $2. $ If we create a set that consists of all sums in rows and columns, there are 2n distinct values.** ↵
↵
**My solution:** ↵
For a given $n \gt 4$, create a $n \times m$ matrix named A, every element in A will be as follow:↵
$$↵
a_{i,j} =↵
\begin{cases}↵
n, & j = 1,\\↵
i, & j > i,\\↵
i-1, & 2 \le j \le i.↵
\end{cases}↵
$$ ↵
For example, n = 6 would look like this:↵
$$↵
A =↵
\begin{pmatrix}↵
6 & 1 & 1 & 1 & 1 & 1\\↵
6 & 1 & 2 & 2 & 2 & 2\\↵
6 & 2 & 2 & 3 & 3 & 3\\↵
6 & 3 & 3 & 3 & 4 & 4\\↵
6 & 4 & 4 & 4 & 4 & 5\\↵
6 & 5 & 5 & 5 & 5 & 5↵
\end{pmatrix}↵
$$ ↵
Now it can be seen that for each row $i$ from 1 to n, its sum is as follow: $row_{i} = 2 \times n - 1 + (n - 2) \times (i - 1)$ ↵
For each column from 2 to n, its sum is as follow: $col
This construction give us a powerful fact that is there can only be one row's sum being equal to a column's sum, and from the third to last row onward, there can not be a match between these and any column. Also the matching column can not be the second and the last. This is true for $n \gt 4$ and will be proven later in this blog. ↵
From this we can do the following procedure: Find the matching row and column $i, j$, swap $a_{2, 1}, a_{2, j}$, and then swap $a_{i + 1, n}, a_{i + 2, n}$
This construction give us a powerful fact that is there would always be atleast 1 matching position. Also, there can only be one row's sum being equal to a column's sum, and from the third to last row onward, there can not be a match between these and any column. Moreover the matching column can not be the second and the last. This is true for $n \gt 4$ and will be proven later in this blog. ↵
From this we can do the following operations: Find the matching row and column $i, j$, swap $a_{2, 1}, a_{2, j}$ and then swap $a_{i + 1, n}, a_{i + 2, n}$ ↵
Doing this, we change $col_{1} = n ^ 2$ to $n \times (n - 1) + 2$ and $col_{j} = \frac{n \times (n - 1)}{2} + j - 1$ to $\frac{n \times (n - 1)}{2} + j - 3 + n$. ↵
↵
And $row_{i + 1} = 2 \times n - 1 + (n - 2) \times i$ to $2 \times n + (n - 2) \times i$, $row_{i + 2} = 2 \times n - 1 + (n - 2) \times (i + 1)$ to $2 \times n - 2 + (n - 2) \times (i + 1)$, this is true because $i + 1, i + 2$ is not $n - 1$ and $n$, which guarantee that $a_{i + 1, n} + 1 = a_{i + 2, n}$.↵
↵
Consider $col_{1} = n \times (n - 1) + 2$: this is still the single largest value, so there is only one ↵
      $row_{i + 1} = 2 \times n + (n - 2) \times i$: this value does not equal to any other rows or columns because the maximum column is $\frac{n \times (n - 1)}{2} + n - 1$, and since $i, j$ matches this value is smaller than $\frac{n \times (n - 1)}{2} + j - 3 + n$. Alongside the fact that $row_{i + 1} = 2 \times n + (n - 2) \times i = row_{i} + n - 2$, and because $row_{i} = col_{j}$: $$row_{i + 1} = 2 \times n + (n - 2) \times i = row_{i} + n - 2 = col_{i} + n - 2 = \frac{n \times (n - 1)}{2} + j - 3 + n > \frac{n \times (n - 1)}{2} + n - 1 $$↵
      So there is only one sum equal $row_{i + 1}$ ↵
      $row_{i + 2}$ : the same as above, so there is also only one sum equal $row_{i + 2}$ ↵
      $col_{j} = \frac{n \times (n - 1)}{2} + j - 3 + n$ : after the increment, it now is larger than the $n\text{-th}$ column because it matches at a column with index larger than 2, the difference from that to the $n\text{-th}$ column is smaller than $n - 2$. This would have matched with the $i+1\text{-th}$ row but since we have changed it before, it now does not match with any row so there is only one appearance of this sum. ↵
After doing all of the above, we would end up with a 2d matrix which satisfy the conditions. ↵
↵
**Now i will be proving the claims above for $n \gt 4$, which is:** ↵
**  $1. $ There would always be atleast 1 matching position.** ↵
**  $2. $ There can only be one row's sum being equal to a column's sum.** ↵
**  $3. $ From the third to last row onward, there can not be a match between these and any column.** ↵
**  $4. $ The matching column can not be the second or the last.** ↵
Proof: ↵
$1. $ It can be seen that the minimum of all column which is $col_{2} = 1 + \frac{n \times (n - 1)}{2} \gt row_{1} = 2 \times n - 1$ and the $n\text{-th}$ column which also is the second largest: $col_{n} = \frac{n \times (n - 1)}{2} + n - 1 \lt 2 \times n - 1 + n^n $. Which imply that there must be at least one matching position. ↵
$2. $ For two of them to match, the matching column must be the second and the last column. You can visualize the value of the columns as a window of size n, while the difference between each column is n — 1. From this, we can try to find the first matching position $i$ by solving this equation:↵
$$1\ +\ \frac{\left(n\ -\ 1\right)n}{2}=2\cdot n-1+\left(n-2\right)\cdot\left(i-1\right)$$↵
$$\implies \frac{n-1}{2}-\frac{n-1}{n-2}+1=i$$↵
It can be shown that the function above only return positive interger for n = 2 and 4, so for $n /gt 4$ it return fractional numbers. From this, we can see that for n > 4 there can not be two matching positions. ↵
$3. $ For it to match then $col_{n} \geq row_{n-2}$, which is the same as this inequation:↵
$$n-1+\frac{\left(n-1\right)n}{2}-\left(2\cdot n-1\ +\ \left(n-3\right)^{2}+\left(n-2\right)\cdot2\right) \geq 0$$↵
$$\implies \frac{5}{2}x-\frac{x^{2}}{2}-5 \geq 0$$ ↵
It can be shown that the inequation above have no real solution, so point proven. ↵
$4. $ This is the direct result of $1. $, because no two matching so the position can not be the second or the last. ↵
Example of the mentioned functions in desmos:↵
↵
For the special case $n = 4$: we can just bruteforce to find the solution ↵
              $n \le 3$: impossible ↵
↵
Thank you for reading my post, this is the first time i have ever written a blog, along with how bad i am at explaining so i expect a lot of criticism. Please point out what i could have done better so that i can improve, thank you so much!!
