Maths Olympiad Prep

Library / /16 of 62

Combinatorics Difficulty 5.0 AIME, harder Prove it Ukraine

In every cell of the table 5×95 \times 9 either 00 or 11 is written. Then the sums of the numbers for every row and column are calculated. What is the maximum amount of different values that can be among these 1414 numbers?

Figure 1

Solution

The sums vary from 00 to 99, thus there exist 1010 different values for the sum. Let us show that all 1010 values cannot be present simultaneously. Let us suppose that there is a row or a column with the sum 00, thus all the cells of that row or column are zeroes. If it is a column, then the maximum value for the row is 88. If it is a row, then in columns can be only values from 00 to 44. But then there can be 44 more different values in rows. Together we have not more than 99 different values. Example is shown on the picture (Fig. 20).

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.