In each cell of an n×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×n grid such that, when calculating the sum of the numbers in each row and each column, the numbers 1,2,…,2n are obtained in some order.
Problem
Source: Pan-American Girls’ Mathematical Olympiad 2023 P2
Tags: square grid, combinatorics
09.08.2023 02:19
2× 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≤i≤k we fill with i numbers 1 in the beginning of row and other are 0. Row i where k+1≤i≤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
09.08.2023 02:28
Note that every cell contributes to two of the sums 1,2,…,2n (once on its row and once on its column). So the sum 1+2+⋯+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 Xn be a table with dimensions n×n whose entries are 0, 1 or 2 and column and row sums are 1,2,…,2n. Consider table 02Xn020200…00222…212which has dimensions (n+2)×(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,…,2n+3,2n+4. This finishes our induction.
09.08.2023 22:26
Given that every cell contributes to one row and one column, then it contributes twice on the sum 1,2,…,2n. So the sum 1+2+⋯+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 We can observe a beautiful pattern made by the original 2×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×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×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} 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:
