4. In the maze diagram in Fig. 1, each segment (link) is a corridor, and each circle is a small room. In some rooms, there are beacons that hum - each with its own voice. When in any room, the robot hears the signal from each beacon and determines the distance to it by the attenuation, i.e., the number of links on the shortest path to the beacon. For example, if a beacon is located in room $A$ (in chess notation, this is room a4), and the robot is in room $B$ (this is room g4), the distance between them is 7 links. The robot has the maze diagram and the beacons are marked on it. For what minimum number of beacons can the robot, when in any room, uniquely determine its location by sound?

a) Indicate how such a number of beacons can be placed. Why will the robot be able to determine its room by them?

b) Prove that it is impossible to manage with a smaller number of beacons.

![](https://cdn.mathpix.com/cropped/2024_05_06_7a6694d067306ba85dedg-02.jpg?height=505&width=529&top_left_y=513&top_left_x=775)

Fig. 1: Maze
Answer: the minimum number of beacons is 3, for example, they can be placed in rooms a1, d3, a5.

## Solution.

![](https://cdn.mathpix.com/cropped/2024_05_06_7a6694d067306ba85dedg-02.jpg?height=528&width=517&top_left_y=1392&top_left_x=198)

Fig. 2: Parts of the maze

![](https://cdn.mathpix.com/cropped/2024_05_06_7a6694d067306ba85dedg-02.jpg?height=549&width=551&top_left_y=1373&top_left_x=1255)

Fig. 3: Distances to beacon a5

b) Estimation. We will prove that two beacons are not enough. Consider three parts of our maze (Fig. 2): part $\mathcal{K}$ is room $K$ and two long dead-end corridors that lead from it to the left and right, part $\mathcal{L}$ is room $L$ and two dead-end corridors that lead from it upwards and to the right, part $\mathcal{N}$ is room $N$ and two dead-end corridors that lead from it to the left and downwards. If there are no more than 2 beacons, then one of these parts will not have a beacon. For example, let this be part $\mathcal{K}$, signals from beacons will reach this part via the edge entering room $K$ from below. Then a robot in room a3 will hear the same signals as in room b3, and therefore will not be able to distinguish which of these two rooms it is in. Similarly, indistinguishable rooms can be found in other parts if they do not contain a beacon.

a) Example. Let's check that beacons in rooms a1, d3, a5 will allow the robot to orient itself in this maze. Here, it is easier to perform a case-by-case check than to come up with general considerations. In Fig. 3, we have marked the distances from all rooms to beacon a5. As we can see, rooms with distances from 0 to 5 are uniquely defined. Rooms with a distance of 6 are at different distances from beacon d3. Similarly, rooms with distances of $8, 9, 10, 11$. As for the four rooms with a distance of 7, two of them, v2 and v4, are at distances of 3 and 7 from beacon d3 and are thus uniquely defined by the distances to a5 and to d3. The other two rooms, a2 and b1, are at a distance of 5 from d3, but they are at different distances from a1.