Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2012 Indonesia MO Problems/Problem 5"
 
Line 13: Line 13:
 
let the collection X be named
 
let the collection X be named
 
<cmath>\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}</cmath>
 
<cmath>\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}</cmath>
−
since for all <math>i</math>, <math>P_{i,1}\geq P_{i,2}\geq \dots \geq P_{i,n}</math>, that means <math>(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})</math>
+
by (i), for all <math>i</math>, <math>P_{i,1}\geq P_{i,2}\geq \dots \geq P_{i,n}</math>, that means <math>(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})</math>
 +
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 <math>p</math>, then the first p numbers of the row/column is <math>1</math> and the rest <math>0</math>, so we can deduce its equal (sorry i have no idea how to tody the writing, some1 help :()
 
==See Also==
 
==See Also==
 
{{Indonesia MO box|year=2012|num-b=4|num-a=6}}
 
{{Indonesia MO box|year=2012|num-b=4|num-a=6}}
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]

Latest revision as of 21:14, 24 December 2024

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 :()

See Also

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_Indonesia_MO_Problems/Problem_5&oldid=237767"