2012 Indonesia MO Problems/Problem 5

Problem

Given positive integers $m$ and $n$ . Let $P$ and $Q$ be two collections of $m \times n$ numbers of $0$ and $1$ , arranged in $m$ rows and $n$ columns. An example of such collections for $m=3$ and $n=4$ is $\left[ \begin{array}{cccc} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right].$ Let those two collections satisfy the following properties: (i) On each row of $P$ , from left to right, the numbers are non-increasing, (ii) On each column of $Q$ , from top to bottom, the numbers are non-increasing, (iii) The sum of numbers on the row in $P$ equals to the same row in $Q$ , (iv) The sum of numbers on the column in $P$ equals to the same column in $Q$ . Show that the number on row $i$ and column $j$ of $P$ equals to the number on row $i$ and column $j$ of $Q$ for $i=1,2,\dots,m$ and $j=1,2,\dots,n$ .

Solution

let the collection X be named $\begin{bmatrix} X_{1,1}&X_{1,2}&\dots&X_{1,n}\\X_{2,1}&X_{2,2}&\dots&X_{2,n}\\\vdots&\vdots&\vdots&\vdots\\X_{m,1}&X_{m,2}&\dots&X_{m,n}\end{bmatrix}$ by (i), for all $i$ , $P_{i,1}\geq P_{i,2}\geq \dots \geq P_{i,n}$ , that means $(P_{1,1}+P_{2,1}+\dots+P_{m,1})\geq(P_{1,2}+P_{2,2}+\dots+P_{m,2})\geq\dots\geq(P_{1,n}+P_{2,n}+\dots+P_{m,n})\implies(Q_{1,1}+Q_{2,1}+\dots+Q_{m,1})\geq(Q_{1,2}+Q_{2,2}+\dots+Q_{m,2})\geq\dots\geq(Q_{1,n}+Q_{2,n}+\dots+Q_{m,n})$ for the collection Q, all the 1's are getting pushed up and the inequality of the sum of columns of Q are pushing it to the left, if we do the same logic to P we also sed it getting pushed up and left. notice how if the sum of some row/column is some number $p$ , then the first p numbers of the row/column is $1$ and the rest $0$ , so we can deduce its equal (sorry i have no idea how to tody the writing, some1 help :()

2012 Indonesia MO (Problems)
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6 • 7 • 8	Followed by Problem 6
All Indonesia MO Problems and Solutions

Page

Toolbox

Search

2012 Indonesia MO Problems/Problem 5

Problem

Solution

See Also