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"

(Created page with "==Problem== Let <math>n</math> be a positive integer. Show that the equation<cmath>\sqrt{x}+\sqrt{y}=\sqrt{n}</cmath>have solution of pairs of positive integers <math>(x,y)</m...")
 
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
==Problem==
 
==Problem==
−
Let <math>n</math> be a positive integer. Show that the equation<cmath>\sqrt{x}+\sqrt{y}=\sqrt{n}</cmath>have solution of pairs of positive integers <math>(x,y)</math> if and only if <math>n</math> is divisible by some perfect square greater than <math>1</math>.
+
Given positive integers <math>m</math> and <math>n</math>. Let <math>P</math> and <math>Q</math> be two collections of <math>m \times n</math> numbers of <math>0</math> and <math>1</math>, arranged in <math>m</math> rows and <math>n</math> columns. An example of such collections for <math>m=3</math> and <math>n=4</math> is
 +
<cmath>\left[ \begin{array}{cccc} 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right].</cmath>
 +
Let those two collections satisfy the following properties:
 +
(i) On each row of <math>P</math>, from left to right, the numbers are non-increasing,
 +
(ii) On each column of <math>Q</math>, from top to bottom, the numbers are non-increasing,
 +
(iii) The sum of numbers on the row in <math>P</math> equals to the same row in <math>Q</math>,
 +
(iv) The sum of numbers on the column in <math>P</math> equals to the same column in <math>Q</math>.
 +
Show that the number on row <math>i</math> and column <math>j</math> of <math>P</math> equals to the number on row <math>i</math> and column <math>j</math> of <math>Q</math> for <math>i=1,2,\dots,m</math> and <math>j=1,2,\dots,n</math>.
  
 
==Solution==
 
==Solution==
  
−
 
+
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>
 +
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"