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


  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.

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

    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

    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

  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.

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

  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.

  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.

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

  8. Another solution for problem 1 .
    Let 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)


Post a Comment

Popular posts from this blog

Asking a girl out

Coins Puzzle

Consecutive Heads