Let be a positive integer. Consider an square. In each cell of the square, one of the numbers from the set is to be written. One such filling is called "good" if, for every index , , row no. and column no. , together, contain all the elements of .
a) Prove that there exists for which a good filling exists.
b) Prove that for there is no good filling of the square.
Solution
a) For the filling below is good.
| 1 | 2 | 4 | 5 |
|---|---|---|---|
| 3 | 1 | 6 | 4 |
| 7 | 5 | 1 | 2 |
| 6 | 7 | 3 | 1 |
b) We prove that there is no good filling of an square if is odd. Assume the contrary to be true. Then, for some odd number , we have that, for every index , , the row no. and the column no. contain, together, exactly once, each element of . If we denote by the number situated on row no. and column no. , , and in which the term only appears once, then each element of must appear in such sums. But if , then the element will contribute to both and . Thus, any number that is not situated on the main diagonal contributes to two sums. But in total, there is an odd number of sums, so each element of must appear an odd number of times on the main diagonal. Thus, each element of needs to appear at least once on the main diagonal, which is not possible because there are elements in and only places on the diagonal.
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.