Kenodarov R.g.

A board $7 \times 7$ is either empty or has an invisible ship $2 \times 2$ placed on it "by cells". It is allowed to place detectors in some cells of the board, and then turn them on simultaneously. An activated detector signals if its cell is occupied by the ship. What is the smallest number of detectors needed to guarantee that their readings will determine whether there is a ship on the board, and if so, which cells it occupies?
Evaluation. In each rectangle $2 \times 3$, there should be at least two detectors: the rectangle consists of three dominoes $1 \times 2$ (strips), and if a detector is in the edge domino, we might not know if there is a ship on the other two dominoes, and if a detector is in the middle domino, we might not know which of the edge dominoes the ship occupies along with the middle domino. Therefore, there should be no fewer than 16 detectors (see the figure).

![](https://cdn.mathpix.com/cropped/2024_05_06_864d5071b377f8fb364bg-08.jpg?height=383&width=374&top_left_y=1712&top_left_x=842)

Example. In the figure below, black indicates the placement of 16 detectors. Every ship intersects with exactly one black square $2 \times 2$ in one cell, two adjacent cells, or all four cells. In any case, the position of the ship or its absence is uniquely determined.

![](https://cdn.mathpix.com/cropped/2024_05_06_864d5071b377f8fb364bg-08.jpg?height=383&width=372&top_left_y=2244&top_left_x=843)

## Answer

16 detectors.

## Author: Bakayev E.V.

In each cell of a strip of length 100, there is a chip. For 1 ruble, you can swap any two adjacent chips, and you can also swap any two chips that have exactly 4 chips between them for free. What is the minimum number of rubles needed to reverse the order of the chips?

## Solution

We will number the chips and cells in order from 0 to 99. The free operation does not change the remainder of the cell number when divided by 5.

Evaluation. Imagine arranging the piles of chips in a circle. First, the pile of chips with a remainder of 0, then the pile with a remainder of 1, and so on up to 4. A paid operation swaps a pair of chips from adjacent piles. Chips from the zero pile must participate in at least one such swap to reach the fourth pile. Similarly for chips from the fourth pile. Chips from the first pile must participate in at least two swaps to reach the third pile. Similarly for the third pile. Therefore, at least ( $20+20+40+40$ ):2 $=60$ rubles are required. But if only 60 rubles are spent, then the chips from the first pile will have to go through the second pile, so at least one chip from the second pile will participate in swaps. Therefore, more than 60 rubles are necessary.

Algorithm. Clearly, with free operations, the chips within a pile can be arranged in any order. Therefore, the chips from the zero and fourth piles can be correctly arranged for 20 rubles. Consider the remaining three piles. We will mentally leave only one chip $\$ A \$$ in the second pile. We will swap it with a chip from the first pile. Each time, we will move the chip that has come to the second pile further using a new chip. Then, for 40 rubles, we will move all the chips from the first pile to the third, and from the third to the first, except for one: it will remain in the second pile, not reaching the first. We will swap it with $\$ A \$$, and all the chips will be in the correct piles.

## Answer

For 61 rubles.