9x9 table

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

9x9 table

G H J

Reveal topic tags

L

G H BBookmark kLocked kLocked NReply

Source: Iranian RMM TST Day2 P5

The post below has been deleted. Click to close.

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

499 posts

#1 h Jan 14, 2020, 4:50 PM • 3 Y

Y by VicKmath7, stroller, Adventure10

A $9\times 9$ table is filled with zeroes.In every step we can either take a row add $1$ to every cell and shift it one unit to right or take a column reduce every cell by $1$ and shift it one cell down. Can the table with the top right $-1$ and bottom left $+1$ and all other cells zero be reached?

This post has been edited 4 times. Last edited by matinyousefi, May 24, 2020, 10:58 PM

Z K Y

The post below has been deleted. Click to close.

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

578 posts

#2 h Jan 15, 2020, 3:21 AM • 5 Y

Y by stroller, matinyousefi, CabinetMatesha, Kobayashi, Adventure10

Funny problem!

We'll assume that when we shift the row to the right, the rightmost number in that row ends up in the leftmost position of the row, and likewise for shifting columns.

We claim that the answer is actually no. We will consider the entries of the table modulo $9$ , and show that it is impossible to reach a state where the top right corner is $8 \pmod{9}$ , the bottom left corner is $1 \pmod{9}$ , and all other corners are $0 \pmod{9}$ .

Let's label the table with $[9]^2$ in the obvious manner so that the bottom left corner is $(1, 1)$ and the top right corner is $(9, 9)$ (and going right increases the $x-$ coordinate). For all $(i, j) \in [9]^2$ , let $a_{i, j}$ be a variable which denotes the value of the number which was originally on cell $(i, j).$

Let's now place a tablet on each cell of the table. Let $t_{i, j}$ denote the tablet which was originally on cell $(i, j).$ At any moment, $t_{i, j}$ will display the number $a_{i, j} - i' - j',$ where $(i', j')$ is the current location of the tablet.

We claim that the number on each tablet is invariant modulo $9$ . Indeed, working in modulo $9$ , when we apply the first operation, $a_{i, j}$ is increased by one, $i'$ is increased by one, and $j'$ is unchanged. Analogously, when working in modulo $9$ , when the second operation is applied, $a_{i, j}$ is decreased by one, $i'$ is unchanged, and $j'$ is decreased by one. It is therefore clear that the number on each tablet is always invariant modulo $9$ .

Initially, for each residue class modulo $9$ , there are precisely nine tablets which display a number belonging to that residue class. Hence, this must always be the case. However, in the end state desired in the problem, there are ten tablets which display a number which is $6 \pmod{9}$ , namely the nine tablets on all cells $(i, j)$ with $i + j \equiv 3 \pmod{9}$ and the one on $(1, 1).$ This implies that the end state we want cannot be obtained, and so the problem is solved.

$\square$

Z K Y

The post below has been deleted. Click to close.

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

894 posts

#3 h Jan 17, 2020, 5:26 PM • 3 Y

Y by Pathological, CabinetMatesha, Adventure10

isomorphic but somewhat different from the above

Z K Y

The post below has been deleted. Click to close.

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

9 posts

#4 h Feb 13, 2020, 9:42 AM • 1 Y

Y by Adventure10

Let $a(i,j)$ be the number in the cell with row number $i$ and column number $j$ . Now let $\omega$ be a complex root of the equation $x^2 +x + 1 = 0$ . Let $V(i,j) = a(i,j) * \omega^{i-1 + 2j-1}$ . Initially $\sum V(i,j) = 0$ . In every step we:
$1)$ Add $1$ to every cell of a column which doesn't change the sum , and shift the columns to the right which multiplies the sum $\sum V(i,j)$ by $\omega$ .
$2)$ Add $-1$ to every cell of a column which doesn't change the sum , and shift the rows down which multiplies the sum $\sum V(i,j)$ by $\omega^2$ .
Since $\sum V(i,j)$ is initially $0$ , it will stay $0$ , but we get that the final value it should take is $\omega - \omega^2$ .

Z K Y

The post below has been deleted. Click to close.

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

68 posts

#5 h Jan 23, 2022, 9:29 PM

Y by

Solution

This post has been edited 1 time. Last edited by chirita.andrei, Jan 23, 2022, 9:31 PM

Z K Y

The post below has been deleted. Click to close.

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

Shayan-TayefehIR

104 posts

Shayan-TayefehIR

#6 h Jul 27, 2022, 8:03 AM • 1 Y

Y by Mango247

Consider all entries mod $9$ and suppose there is number $x_{(i , j)}$ on the cell $(i , j)$ in one of the moves. then assign the number $x_{(i , j)}-i-j$ to cell $(i , j)$ and one can see that the set of all assigned numbers is invariant. Comparing this set for these cases , leads to a contradiction.

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a