Maths Olympiad Prep

Library / /53 of 56

Combinatorics Difficulty 7.1 National Olympiad, round 2 Prove it Singapore

In a 50×5050 \times 50 grid, an integer is written in each of the 25002500 cells. Let GG be the configuration of 88 cells formed by removing the central cell of a 3×33 \times 3 grid. It is given that for any group of 88 cells in the 50×5050 \times 50 grid forming the configuration GG, the sum of the numbers written in the 88 cells is positive. Prove that there is a 2×22 \times 2 grid so that the sum of the numbers in the 44 cells is positive.

Solution

Consider the 4×44 \times 4 grid. Place 44 overlapping copies of GG as shown (left figure), where the number i=1,2,3,4i = 1, 2, 3, 4 indicates the cells of the ithi^{\text{th}} copy of GG. The same grid is also covered by 88 overlapping copies of 2×22 \times 2 grid (right), with each cell covered the same number of times. (Note that in the first figure the top left cells of the 44 copies of GG form a 2×22 \times 2 grid while in the second figure, the top left cells of the 8×2×28 \times 2 \times 2 grid form the configuration GG. This is important for the general case.)

112122
1323413424
1312412324
334344
112233
1412423535
4646757858
667788

Thus the sum of the sums of the numbers in the cells of the 44 copies of GG is equal to that of the 88 copies of the 2×22 \times 2 grid. Since the former is positive, one of the 2×22 \times 2 grid must be positive as well.

It is easy to see that the result holds for any two configurations G1,G2G_1, G_2, provided the grid is large enough. Choose a pair of coordinate axes. Let the number of cells in G1G_1 and G2G_2 be mm and nn respectively. Place G1G_1 and G2G_2 in some position. Let a1,,ama_1, \dots, a_m be the centres of the cells covered by G1G_1 and let b1,,bnb_1, \dots, b_n be the centres of the cells covered by G2G_2. Let G1(bi)G_1(b_i) be the position of G1G_1 after it has been translated by bib_i and let P1(bi)P_1(b_i) be the corresponding sum. The sum P2(ai)P_2(a_i) is similarly defined. It is clear that the cells, counting multiplicity, covered by G1G_1 when it is translated by the vectors b1,b2,,bnb_1, b_2, \dots, b_n are the same as the cells, counting multiplicity, covered by G2G_2 when it is translated by the vectors a1,a2,,ama_1, a_2, \dots, a_m. Thus
P1(bi)=P2(aj). \sum P_1(b_i) = \sum P_2(a_j).
Since the LHS is positive, at least one of the terms on the RHS is positive.

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.