Shapoveaov A.B.

The plan of the palace is a $6 \times 6$ square, divided into rooms of size $1 \times 1$. There is a door in the middle of each wall between the rooms. The Shah told his architect: "Knock down some walls so that all rooms become $2 \times 1$, no new doors appear, and the path between any two rooms passes through no more than $N$ doors." What is the smallest value of $N$ that the Shah should name to make it possible to carry out the order?
Consider an arbitrary route from the lower left corner of the palace to the upper right. Since one needs to "climb" 5 horizontal levels and "shift right" 5 vertical levels, one has to pass through at least 10 doors, visiting at least 11 rooms (including the starting and ending rooms).

11 rooms of size $1 \times 1$ could not have been transformed into 5 rooms of size $2 \times 1$. Therefore, the same route in the reconstructed palace must pass through at least 6 rooms, and thus through at least 5 doors. Such a reconstruction of the palace is indeed possible (see the figure).

| 2 | 2 | 2 | 2 | $\mid 2$ |
| :---: | :---: | :---: | :---: | :---: |
|  |  | 1 |  |  |
|  |  | 0 |  | 1 |
|  |  |  |  | 1 |
| 2 | 9 | 1 | 2 | 19 |
|  |  | 2 |  |  |

In this case, it is indeed possible to get from any room to any other room by passing through no more than 5 doors. Let's denote the central rooms with the number 0, those connected to them by a door with the number 1, and those connected by a door to rooms of type 1 with the number 2. Since all rooms have been marked, one can get from any room to one of the central rooms by passing through no more than two doors. Therefore, one can get from any room to any other room by constructing a route through the central rooms and passing through no more than 5 doors (the fifth door is needed if one has to move from one central room to another).

## [Tournaments and tournament tables] Problem 116689 Topics: [Examples and counterexamples. Constructions] Difficulty: 4 [ $\underline{\text { Induction (other) }}$ ] Classes: 8,9,10

Author: Blyunkov A.d:

a) In a football tournament in a single round-robin format, 75 teams participated. A team received 3 points for a win, 1 point for a draw, and 0 points for a loss. It is known that every two teams scored a different number of points. Find the smallest possible difference in points between the teams that took first and last place.

b) The same question for $n$ teams.

## Solution

b) The minimum gap between the first and last place cannot be less than $n-1$. We will prove that for $n>3$ it is possible to construct a tournament schedule such that the gap is $n-1$ (if $n=2$ or 3, the minimum gap is obviously 3 points).

By induction, we will construct a table for $n$ teams, where the results are all integers from $n-2$ to $2n-3$. Base case $(n=4)$. An example of a tournament table for four teams:

| Team | 1 | 2 | 3 | 4 | Points |
| :--- | :---: | :---: | :---: | :---: | :--- |
| 1 | $\times$ | 3 | 1 | 1 | 5 |
| 2 | 0 | $\times$ | 1 | 3 | 4 |
| 3 | 1 | 1 | $\times$ | 1 | 3 |
| 4 | 1 | 0 | 1 | $\times$ | 2 |

Inductive step. By the inductive hypothesis, there is such a table for $n$ teams. We will divide the teams into triples based on the number of points they scored: the first triple consists of teams with $2n-3, 2n-4, 2n-5$ points, the second triple consists of teams with $2n-6, 2n-7, 2n-8$ points, and so on (the last triple may be incomplete). We will add one more team. Consider three cases.

1) $n=3k+1$. Let the new team win against the first team in the first triple and lose to the second and third. Then the first team will still have $2n-3$ points, the second team will have $2n-1$ points and move to the first place, and the third team will have $2n-2$ points. We will do the same for the other complete triples. Then all triples will shift "up" by two points. There will be one team left, which was in the last place with $n-2$ points, and the new team will have $n-1$ points. Let them play a draw and add one point each.

2) $n=3k+2$. The teams from $k$ triples play against the new team similarly to case 1). The last two teams had $n-1$ and $n-2$ points, and the new team has $n-2$ points. Let the last team win against the new team, and the second-to-last team play a draw with the new team.

3) $n=3k$. After the new team plays against the first $k-1$ triples, it will have $n-3$ points. The last three teams had $n, n-1$, and $n-2$ points. Let the second-to-last team win against the new team, the last team play a draw with the new team, and the team with $n$ points lose. Then the former last teams will have $n, n+2, n-1$ points, and the new team will have $n+1$ points.

## Answer

a) 74; b) $n-1$, if $n>3$; 3, if $n=2$ or 3.

Send a comment