Permutation of \(1,\ldots,2n\) in the sum of rows and columns

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

Permutation of \(1,\ldots,2n\) in the sum of rows and columns

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Pan-American Girls’ Mathematical Olympiad 2023 P2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

20 posts

#1 h Aug 8, 2023, 10:37 PM

Y by

In each cell of an $n \times n$ grid, one of the numbers $0$ , $1,$ or $2$ must be written. Determine all positive integers $n$ for which there exists a way to fill the $n \times n$ grid such that, when calculating the sum of the numbers in each row and each column, the numbers $1, 2, \ldots, 2n$ are obtained in some order.

This post has been edited 1 time. Last edited by rilarfer, Aug 9, 2023, 9:42 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4871 posts

#2 h Aug 8, 2023, 11:19 PM

Y by

$2 \times$ sum of all numbers $= (1+2+...+2n)=n(2n+1)$ and so $2|n$

If $n=2k$ then exists such way:

Row $i$ where $1 \leq i \leq k$ we fill with $i$ numbers $1$ in the beginning of row and other are $0$ .
Row $i$ where $k+1 \leq i \leq 2k$ we fill with $2k-i$ numbers $1$ in the end of the row and other are $2$ .

As example for $n=8$
$10000000$
$11000000$
$11100000$
$11110000$
$22222111$
$22222211$
$22222221$
$22222222$

Easy to show, that rows contain sums $1,2,...,k$ and $3k+1,3k+2,...,4k$ and columns contain sums $k+1, k+2,....,3k$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

293 posts

cefer

#3 h Aug 8, 2023, 11:28 PM

Y by

Note that every cell contributes to two of the sums $1, 2, \ldots, 2n$ (once on its row and once on its column). So the sum $1 + 2 + \dots + 2n = n(2n + 1)$ must be even, which in turn means $n$ is even.

For even $n$ we can construct such a table by induction. For $n=2$ observe that table with rows $(0, 2), (1, 2)$ satisfies the problem. Let $X_n$ be a table with dimensions $n\times n$ whose entries are $0$ , $1$ or $2$ and column and row sums are $1, 2, \ldots, 2n$ . Consider table
$\begin{matrix} &&& & 0 & 2\\ &&X_n& & 0 & 2\\ &&& & 0 & 2\\ 0& 0&\ldots &0 & 0 & 2\\ 2& 2&\ldots & 2 & 1&2\\ \end{matrix}$ which has dimensions $(n+2) \times (n+2)$ . This new table extends every column and row sum of $X$ by $2$ while the remaining $4$ new rows and columns give us sums $1, 2, 2n+3, 2n+ 4$ , Therefore the new board has row and column sums $1, 2, \ldots, 2n+3, 2n+4$ . This finishes our induction.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

13 posts

#4 h Aug 9, 2023, 7:26 PM • 3 Y

Y by PennyLane_31, TheHerculean11, AlexCenteno2007

Given that every cell contributes to one row and one column, then it contributes twice on the sum $1, 2, \ldots, 2n$ . So the sum $1 + 2 + \dots + 2n = n(2n + 1)$ must be even, which in turn means $n$ is even. $n=2k$
Checking the first 3 even values of $n$ : $2,4,6$

https://tinypic.host/images/2023/08/09/PAGMO_2023_P2_I1.png

We can observe a beautiful pattern made by the original $2\times 2$ yellow block, blocks of 0's (in red) and blocks of 2's (in blue).
So basically we see that for every value of $k$ , we can construct a table of $k\times k$ blocks, where the diagonal is made by yellow blocks, the upper left is filled by red blocks and the lower right by blue blocks.

Quote:

Note that the original $2\times 2$ contains rows with sums $\equiv 1,0 \pmod{4}$ and columns with sums $\equiv 2,3 \pmod{4}$ so: when adding a blue block, each row/column increases by 4, and adding a red block doesn't change the sum, so we're maintaining the congruences for row sums and column sums $\mod{4}$

https://tinypic.host/images/2023/08/09/PAGMO_2023_P2_I5.png

For any given $n\times n$ table with this block construction, row sums end in $2n-3$ and $2n$ , while column sums end in $2n-2$ and $2n-1$ .
Now, we can construct the $n+2\times n+2$ table by overlapping the same $n\times n$ table as the second image shows. Note that previous row sums and column sums are preserved because of the red blocks.
So all we need to do is add the final blue block that adds 4 to each of the last 2 rows and column sums, therefore creating the extra 4 values $2n+1,2n+2,2n+3,2n+4$ .

Attachments:

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a