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

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.

ReplyDeleteEdit in NG's last comment: Alternative solution to problem 1@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)