**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

ReplyDelete