Moscow Math Olympiad Problems
Problem 1: Each cell in a square table contains a number. The sum of the two greatest numbers in each row is a, and the sum of the two greatest numbers in each column is b. Prove that a = b.
Problem 2: Given some m x n table, and some numbers in its fields. You are allowed to change the sign in one row or one column simultaneously. Prove that You can obtain a table, with non-negative sums over each row and over each column.
Update (11th June 2011):
Solution to both problems posted by NG [Nikhil Garg (CSE IIT Delhi final year undergraduate student)] in comments! Thanks.
Confession: I could never solve Problem 1 even after spending hours. :P :(
Problem 2: Given some m x n table, and some numbers in its fields. You are allowed to change the sign in one row or one column simultaneously. Prove that You can obtain a table, with non-negative sums over each row and over each column.
Update (11th June 2011):
Solution to both problems posted by NG [Nikhil Garg (CSE IIT Delhi final year undergraduate student)] in comments! Thanks.
Confession: I could never solve Problem 1 even after spending hours. :P :(
Solution to problem 2 - Whenever you find a row or a column with negative sum, multiply it with -1. This operation increases the sum of the whole table and hence this can't go on forever.
ReplyDeleteWhen we stop, we have each row or column with a non-negative sum.
Soln to prob1: Let the square be n by n. Let x1>=x2>=..>=xn be the biggest n numbers in the square.
ReplyDeleteCase1:
Let there exist a minimum j<=n such that for some ixj we get a contradiction. Hence xi=...=xj=...=xn. Now WLG xi and xj are in the same column => b=2xj. Consider the row of xj => a<=b. Now consider all columns which does not contain x1,x2..,xj (There are exactly n-(j-1) such columns). All such columns have their biggest and second biggest numbers equal to xj. So consider all elements in the square >=xj. There are atleast n+2 such numbers. Hence atleast two are in a row => a>=b. Hence a=b
Case2:
Now we assume that there does not exist such a j. Hence the biggest n numbers of the square do not share any row or column. Consider the the (n+1)th biggest element of the square. Suppose it shares a column with xp and row with xq (p,q<=n) Now if xp>xn we get a contradiction. Similarly if xq>xn we get a contradiction. Hence a=b
Alternative solution to problem 2( Given by a friend)
ReplyDeleteAssume w.l.o.g that b > a. Now paint largest element of every column in red and second largest element of every column in blue. Note that all red elements are >= b/2
So no two red elements are in same row.Else row sum >= b already. Now look at the largest blue element, say B1. There must be a red element in its row as well, say R1. R1 had some blue in its column as well, say B2. As R1 + B2 = b and B1 >= B2, implying R1 + B1 >= b
But this is a contradiction as R1 & B1 are in same row.
Edit in NG's last comment: Alternative solution to problem 1
ReplyDelete@NG (Nikhil Garg) Correct solution to both problems. Thanks. Awesome explanation to the solution of Problem 1.
ReplyDelete@Siddhant.. I did not understand your solution. Hypothesis in your contradiction argument is not clear. Can you please explain? Thanks.
I believe that my proof didnt print out correctly. Here is the starting part.
ReplyDeleteThe hypothesis was that there exists a pair of elements belonging to x1,x2..,xn such that both of them are in the same row or column. So consider a pair of this kind xi,xj with ia was a masterstroke. Could never have done that.
thanks for the the post here regarding maths Olympiad, i really appreciate your work
ReplyDeleteAnother solution for problem 1 .
ReplyDeleteLet element in cell (i,j) be xij in an n*n square grid; 1<=i,j<=n
Let the largest element in row i be ri. So second largest element = a-ri.Hence for all j,
xij <= a-ri<= ri.Adding this inequality for row 1 to row n (i.e. i=1,2,3,...n) we get
sigma(xij)(i=1,2,3...n) <= a*n -sigma(ri)(i=1,2,3...n) <= sigma(ri)(i=1,2..n)
But sigma (xij) (i=1,2,..n) represents sum of all elements of jth column.
Therefore b <= sigma ( xij)(i=1,2..n)
So combining all the above inequalities, we can write
sigma(ri) >= a*n - sigma(ri) >= b
a*n >= b+ sigma(ri) >= 2*b
Since n>=2, the equality holds for n=2. So 2*a=2*b. So a=b (Proved)