1
Question
The numbers 1, 2, ..., 100 are arranged in the squares of an table in the following way: the numbers 1, ... , 10 are in the bottom row in increasing order, numbers 11, ... ,20 are in the next row in increasing order, and so on. One can choose any number and two of its neighbors in two opposite directions (horizontal, vertical, or diagonal). Then either the number is increased by 2 and its neighbors are decreased by 1, or the number is decreased by 2 and its neighbors are increased by 1. After several such operations the table again contains all the numbers 1, 2, ... , 100. Prove that they are in the original order.
The numbers 1, 2, ..., 100 are arranged in the squares of an table in the following way: the numbers 1, ... , 10 are in the bottom row in increasing order, numbers 11, ... ,20 are in the next row in increasing order, and so on. One can choose any number and two of its neighbors in two opposite directions (horizontal, vertical, or diagonal). Then either the number is increased by 2 and its neighbors are decreased by 1, or the number is decreased by 2 and its neighbors are increased by 1. After several such operations the table again contains all the numbers 1, 2, ... , 100. Prove that they are in the original order.
Open in App
Solution
The correct option is B bij is in the same order, and thus the entries 1, 2, ... , 100 appear in their original order.
Label the table entry in the i th row and j th column by aij
where the bottom-left corner is in the first row and first column.
Let bij=10(i−1)+j be the number originally in the i th row and j th column. Observe that P=10∑i,j=1aijbij
is invariant. Indeed, every time entries
amn,apq,ars are changed (with m+r= 2p and n+s= 2q), P increases or decreases by bmn−2bpq+brs,
But this equals 10((m−1)+(r−1)−2(p−1)+(n+s−2q))=0.
In the beginning P=10∑i,j=1aijbij at the end, the entires aij equal the bij
In some order,we now have P=10∑i,j=1aijbij
By the rearrangement inequality, this is at least P=10∑i,j=1aijbij
with equality only when each aij=bij
The equality does occur since P is invariant. Therefore the aij do indeed equal the bij
in the same order, and thus the entries 1,2,...,100 appear in their original order.
Label the table entry in the i th row and j th column by aij
where the bottom-left corner is in the first row and first column.
Let bij=10(i−1)+j be the number originally in the i th row and j th column. Observe that P=10∑i,j=1aijbij
is invariant. Indeed, every time entries
amn,apq,ars are changed (with m+r= 2p and n+s= 2q), P increases or decreases by bmn−2bpq+brs,
But this equals 10((m−1)+(r−1)−2(p−1)+(n+s−2q))=0.
In the beginning P=10∑i,j=1aijbij at the end, the entires aij equal the bij
In some order,we now have P=10∑i,j=1aijbij
By the rearrangement inequality, this is at least P=10∑i,j=1aijbij
with equality only when each aij=bij
The equality does occur since P is invariant. Therefore the aij do indeed equal the bij
in the same order, and thus the entries 1,2,...,100 appear in their original order.
Suggest Corrections
0
Similar questions
View More
Join BYJU'S Learning Program
Explore more
Join BYJU'S Learning Program
