Transforming a grid to another

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

Transforming a grid to another

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: STEMS 2021 Cat B P5

The post below has been deleted. Click to close.

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

742 posts

#1 h Jan 24, 2021, 10:05 PM • 2 Y

Y by ImSh95, Mango247

Sheldon was really annoying Leonard. So to keep him quiet, Leonard decided to do something. He gave Sheldon the following grid

$\begin{tabular}{|c|c|c|c|c|c|} \hline 1 & 1 & 1 & 1 & 1 & 0\\ \hline 1 & 1 & 1 & 1 & 0 & 0\\ \hline 1 & 1 & 1 & 0 & 0 & 0\\ \hline 1 & 1 & 0 & 0 & 0 & 1\\ \hline 1 & 0 & 0 & 0 & 1 & 0\\ \hline 0 & 0 & 0 & 1 & 0 & 0\\ \hline \end{tabular}$

and asked him to transform it to the new grid below

$\begin{tabular}{|c|c|c|c|c|c|} \hline 1 & 2 & 18 &24 &28 &30\\ \hline 21 & 3 & 4 &16 &22 &26\\ \hline 23 &19 & 5 & 6 &14 &20\\ \hline 32 &25 &17 & 7 & 8 &12\\ \hline 33 &34 &27 &15 & 9 &10\\ \hline 35 &31 &36 &29 &13 &11\\ \hline \end{tabular}$

by only applying the following algorithm:

$\bullet$ At each step, Sheldon must choose either two rows or two columns.

$\bullet$ For two columns $c_1, c_2$ , if $a,b$ are entries in $c_1, c_2$ respectively, then we say that $a$ and $b$ are corresponding if they belong to the same row. Similarly we define corresponding entries of two rows. So for Sheldon's choice, if two corresponding entries have the same parity, he should do nothing to them, but if they have different parities, he should add 1 to both of them.

Leonard hoped this would keep Sheldon occupied for some time, but Sheldon immediately said, "But this is impossible!". Was Sheldon right? Justify.

This post has been edited 2 times. Last edited by Severus, Jan 24, 2021, 10:15 PM

Z K Y

The post below has been deleted. Click to close.

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

595 posts

#2 h Jan 25, 2021, 8:51 AM • 2 Y

Y by Severus, Rg230403

Proposed by Writika Sarkar

Official Solution:
Sheldon was indeed right (of course, because he is so smart)!

For notational convenience, let $c_{ij}$ denote the entry of the grid on the $i$ th row and $j$ th column.

Note that whenever we perform the algorithm on two rows (or columns), we swap the parities of two corresponding entries if they were different modulo 2. This means, that if we interpret all the values modulo 2, then the algorithm switches two rows (or columns). For example, if two rows $(1,1,1,1,1,0)$ and $(1,1,0,0,0,1)$ were chosen then the algorithm transforms them to $(1,1,2,2,2,1)$ and $(1,1,1,1,1,2)$ . But modulo 2, they simply get transformed to $(1,1,0,0,0,1)$ and $(1,1,1,1,1,0)$ (they are simply exchanged). Now, we associate with the $n$ th step of the algorithm, a $6\times 6$ matrix $A^n$ such that $A^n_{ij}=c_{ij}$ , where $A^n_{ij}$ is the entry on the $i$ th row and $j$ th column of $A^n$ . (Here, $n=1$ corresponds to the original grid.)
Then notice the value $\det(A^n)\pmod 2$ is an invariant for all $n$ , under this algorithm, since for any square matrix, switching two rows doesn't change the absolute value of the determinant. We can easily figure out that $\det(A^1)=0\equiv 0\pmod 2$ , and writing the matrix for our target grid, by replacing all the entries with their values modulo 2, we can see that the determinant is $1\pmod 2$ . Hence, the transformation is impossible.

This post has been edited 2 times. Last edited by kapilpavase, Jan 25, 2021, 9:08 AM

Z K Y

The post below has been deleted. Click to close.

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

742 posts

#3 h Jan 26, 2021, 6:09 PM

Y by

Here's an elementary solution that doesn't involve matrices/determinants

Once we figure out that the algorithm simply switches rows/columns modulo 2, and interpret all the values in the second grid in mod 2, we can note that a row-switching only permutes the elements in the columns, but doesn't change the elements. Similarly a column-switching only permutes the elements in each row, but doesn't change the elements. Now in the first grid, the first row $(1,1,1,1,1,0)$ is the only row with five $1$ s and in the second grid, the last row $(1,1,0,1,1,1)$ modulo 2, is the only row with five $1$ s. This means that the first row must have shifted to the last row after some number of row-switchings. Similarly, there's only one column with exactly five $0$ s in each grid, and we see that it is the last column in both the grids. However in the first grid, the intersection entry of the last column and the first row is $0$ , and in the second grid, the intersection entry of the last row and last column is $1$ . But for a fixed pair of row and column, row/column-switching can never change the entry in their intersection, so it's impossible to transform the first grid to the second one.

This post has been edited 1 time. Last edited by Severus, Jan 26, 2021, 6:10 PM
Reason: blah blah

Z K Y

The post below has been deleted. Click to close.

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

Project_Donkey_into_M4

163 posts

Project_Donkey_into_M4

#5 h Apr 20, 2025, 2:23 PM

Y by

Here are $2$ solutions by me, Distorteddragon1o4 and Sammy27

Solution 1
We work modulo $2$

Note that the operations when done row-wise ,switches the rows and same goes for the columns.Note that switching rows doesn't affect the composition of the columns i.e, the number of $1$ 's or $0$ 's in the columns remain the same.Now note that the composition of the columns of the first and second matrices are the same, so we can say that column switching isn't really needed i.e. switching only rows suffices. Now consider the first row of the first matrix, it has $5,1'$ s and the $6$ th row of the new matrix, it also has $5,1'$ s.So these two needs to be switched. But note that the first row of the first matrix is $( 1,1,1,1,1,0)$ and the last row of the next matrix is $(1,1,0,1,1,1)$ .The way to get the $0$ is to swap the $3$ rd and $6$ th row at some point. But that changes the number of $1$ in the last row, hence sherlock is correct $\blacksquare$

Solution 2
Note that the value of the determinant (with elements modulo $2$ ) only changes sign under the operations.Value of the first determinant is $1$ and the second one is $0$ and hence sherlock is correct.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a