3. Plane is divided with horizontal and vertical lines into unit squares. Into each square we write a positive integer so that each positive integer appears exactly once. Determine whether it is possible to write numbers in such a way, that each written number is a divisor of a sum of its four neighbours.
Solution
To determine whether it is possible to write numbers in such a way that each written number is a divisor of the sum of its four neighbors, we will use a constructive approach. We will label the plane in a spiral pattern and fill in the numbers according to specific rules to ensure the divisor condition is satisfied.
1. Labeling the Plane:
We start by labeling the plane in a spiral pattern. For example, the first few numbers are labeled as follows:
```
13 12 11 10 25
14 3 2 9 24
15 4 1 8 23
16 5 6 7 22
17 18 19 20 21
```
2. Filling the Numbers:
We fill the numbers in the squares using the following rule:
- Let be the unfilled square with the smallest label according to our labeling scheme.
- If filling in square with the number will not lead to an illegal configuration (one where a square and all its neighbors are filled in, but fail to satisfy the divisor condition), we do so.
- Otherwise, we place in the square in position relative to the origin (i.e., squares up and squares to the right of the square labeled 1).
3. Ensuring Each Number is Written:
By construction, each number is written in some square, and the divisor condition is satisfied. We need to show that each square is eventually labeled. We do this by induction on the label of the square.
4. Base Case:
The square labeled 1 is filled in by 1.
5. Inductive Step:
Assume that all squares labeled smaller than have been filled in. Since our construction always defaults to trying to fill in square , we need to check that at some point it will be legal to do so. There are two reasons why it would not be so:
- All of square 's neighbors have already been filled, so filling in square leads to a divisor condition which must be satisfied. This is impossible since each square is adjacent to two squares with higher labels, only one of which is on that upper right diagonal.
- Square is the last unfilled neighbor of a square whose other neighbors are filled. It can be seen that there can only be one such filled square adjacent to . If that square is filled in with , then once takes on the appropriate value modulo , we can fill in square with and still have that divisor condition satisfied.
By following this construction, we ensure that each number is placed in a square such that it is a divisor of the sum of its four neighbors.