Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Jun 3, 2011

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

7 comments:

  1. 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.
    When we stop, we have each row or column with a non-negative sum.

    ReplyDelete
  2. Soln to prob1: Let the square be n by n. Let x1>=x2>=..>=xn be the biggest n numbers in the square.

    Case1:
    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

    ReplyDelete
  3. Alternative solution to problem 2( Given by a friend)

    Assume 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.

    ReplyDelete
  4. Edit in NG's last comment: Alternative solution to problem 1

    ReplyDelete
  5. @NG (Nikhil Garg) Correct solution to both problems. Thanks. Awesome explanation to the solution of Problem 1.

    @Siddhant.. I did not understand your solution. Hypothesis in your contradiction argument is not clear. Can you please explain? Thanks.

    ReplyDelete
  6. I believe that my proof didnt print out correctly. Here is the starting part.

    The 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.

    ReplyDelete
  7. thanks for the the post here regarding maths Olympiad, i really appreciate your work

    ReplyDelete