Maths Olympiad Prep

Track / Stage 6 / 391 of 400 #1871 of 2444

Problem 1871

National Olympiad, first round
Combinatorics Difficulty 7.0 Prove it Italy competition problems · 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.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

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

Source: MathNet, licensed CC-BY-4.0. Statement translated into English from it; metadata (topic, difficulty, ordering) added by this project.