Maths Olympiad Prep

Library / /20 of 24

Combinatorics Difficulty 7.0 National Olympiad Prove it Italy

In each of the cells of a square 4×44 \times 4 table there is written the digit 11 or the digit 22. It is known that the sum of the 99 digits contained in each of the 44 squares 3×33 \times 3 contained in the table is a multiple of 44, while the sum of all 1616 digits is not a multiple of 44.

Determine the maximum and minimum possible value for the sum of all 1616 digits.

Solution

Solution:

The maximum and the minimum are, respectively, 3030 and 1919 and are realized, for example, by the following tables

2222
2212
2122
2222
1111
1221
1211
1111

Indeed, in order for the sum of the 99 digits in a square 3×33 \times 3 to be divisible by 44, there are only two possibilities: to have 66 times the digit 11 and 33 times the digit 22 (sum 1212), or to have 22 times the digit 11 and 77 times the digit 22 (sum 1616).

It is therefore evident that in the 4×44 \times 4 table there are at least 22 digits 11. If we arrange them, in whatever way, inside the central 2×22 \times 2 square of the table, that is, so as to be contained in all 44 squares 3×33 \times 3, no further digits 11 are necessary. The maximum sum is therefore realized with 22 digits 11 and 1414 digits 22, for a total of 3030.

Similarly, in the 4×44 \times 4 table there are at least 33 digits 22, and no further ones are needed if these are arranged, in whatever way, inside the central 2×22 \times 2 square of the table. The minimum sum is therefore realized with 33 digits 22 and 1313 digits 11, for a total of 1919.

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 translated into English from it; metadata (topic, difficulty) added by this project.