Maths Olympiad Prep

Library / /39 of 41

Combinatorics Difficulty 8.8 Shortlist Prove it Slovenia

Let n4n \ge 4 be a positive integer. Into every square of an n×nn \times n array we inscribe an integer so that the sum of the integers inside any 3×33 \times 3 square is negative. Find all positive integers nn for which this can be done in such a way that the sum of all the numbers in the array is positive.

Solution

When nn is divisible by 33, n=3kn = 3k. The array can be divided into k2k^2 3×33 \times 3 squares. The sum of the numbers inside each square is negative, so the sum of all these sums, which is the sum of all the numbers in the array, is negative as well.

If nn is not divisible by 33, the numbers can be inscribed as required. To make things easier let us assume that all positive numbers in the array are equal and all negative numbers in the array are equal.

The cases n=4n = 4 and n=5n = 5 are represented in the top two figures. Each 3×33 \times 3 square contains eight ones and one 9-9, so the sum is 1-1, while the sum of all the numbers in the array is 88 and 1313, respectively.

<table>
<tr><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>-9</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>1</td><td>1</td></tr>
</table>

<table>
<tr><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>-9</td><td>1</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
<tr><td>1</td><td>1</td><td>1</td><td>1</td><td>1</td></tr>
</table>

Now, let us choose an arbitrary kk and consider the (3k1)×(3k+1)(3k-1) \times (3k+1) array and the (3k+2)×(3k+2)(3k+2) \times (3k+2) array. Cover the 3k×3k3k \times 3k array in the upper left corner with k2k^2 3×33 \times 3 squares as shown. For each of these 3×33 \times 3 squares put b-b into the lower right corner and aa into the other eight squares as well as into all the remaining squares in the array.

<table>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>-b</td><td>a</td><td>a</td><td>-b</td><td>a</td><td>a</td><td>-b</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>-b</td><td>a</td><td>a</td><td>-b</td><td>a</td><td>a</td><td>-b</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>-b</td><td>a</td><td>a</td><td>-b</td><td>a</td><td>a</td><td>-b</td><td>a</td></tr>
<tr><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td><td>a</td></tr>
</table>

The sum inside each 3×33 \times 3 square is 8ab8a - b and the sum of all numbers in the array is k2b+((3k+1)2k2)a-k^2 \cdot b + ((3k + 1)^2 - k^2)a or k2b+((3k+2)2k2)a-k^2 \cdot b + ((3k + 2)^2 - k^2)a. Since 8ab<08a - b < 0, we can write b=8a+cb = 8a + c, where cc is a positive integer. Then k2b+((3k+2)2k2)a>k2b+((3k+1)2k2)a=((3k+1)29k2)ak2c>0-k^2 \cdot b + ((3k+2)^2-k^2)a > -k^2 \cdot b + ((3k+1)^2-k^2)a = ((3k+1)^2-9k^2)a-k^2c > 0 implies
6k+1k2>ca. \frac{6k+1}{k^2} > \frac{c}{a}.
If we set a=ka = k and c=1c = 1, we get b=8k+1b = 8k + 1.

Hence, for (3k+1)×(3k+1)(3k + 1) \times (3k + 1) or (3k+2)×(3k+2)(3k + 2) \times (3k + 2) arrays we can arrange the numbers kk and 8k1-8k - 1 as described above. Then the sum of the numbers inside each 3×33 \times 3 square is equal to 1-1, while the sum of all the numbers in the array is 5k2+k5k^2 + k or 11k2+4k11k^2 + 4k, and thus 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.