Maths Olympiad Prep

Library / /38 of 48

Combinatorics Difficulty 6.6 National Olympiad Prove it Baltic Way

Problem:

162 pluses and 144 minuses are placed in a 30×3030 \times 30 table in such a way that each row and each column contains at most 17 signs. (No cell contains more than one sign.) For every plus we count the number of minuses in its row and for every minus we count the number of pluses in its column. Find the maximum of the sum of these numbers.

Solution

Solution:

In the statement of the problem there are two kinds of numbers: "horizontal" (that has been counted for pluses) and "vertical" (for minuses). We will show that the sum of numbers of each type reaches its maximum on the same configuration.

We restrict our attention to the horizontal numbers only. Consider an arbitrary row. Let it contains pp pluses and mm minuses, m+p17m+p \leq 17. Then the sum that has been counted for pluses in this row is equal to mpm p. Let us redistribute this sum between all signs in the row. More precisely, let us write the number mp/(m+p)m p /(m+p) in every nonempty cell in the row. Now the whole "horizontal" sum equals to the sum of all 306 written numbers.

Now let us find the maximal possible contribution of each sign in this sum. That is, we ask about maximum of the expression f(m,p)=mp/(m+p)f(m, p)=m p /(m+p) where m+p17m+p \leq 17. Remark that f(m,p)f(m, p) is an increasing function of mm. Therefore if m+p<17m+p<17 then increasing of mm will also increase the value of f(m,p)f(m, p). Now if m+p=17m+p=17 then f(m,p)=m(17m)/17f(m, p)=m(17-m) / 17 and, obviously, it has maximum 72/1772 / 17 when m=8m=8 or m=9m=9.

So all the 306 summands in the horizontal sum will be maximal if we find a configuration in which every non-empty row contains 9 pluses and 8 minuses. The similar statement holds for the vertical sum. In order to obtain the desired configuration take a square 18×1818 \times 18 and draw pluses on 9 generalized diagonals and minuses on 8 other generalized diagonals (the 18th generalized diagonal remains empty).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.