4. In the maze diagram in Fig. 13, each segment (link) is a corridor, and each circle is a small room. Some rooms have 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 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 5 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 fewer beacons.

![](https://cdn.mathpix.com/cropped/2024_05_06_57b8ad17478f0226d916g-10.jpg?height=509&width=529&top_left_y=368&top_left_x=775)

Fig. 13: Maze
Answer: the minimum number of beacons is 3, for example, they can be placed in rooms a1, b3, d4.

## Solution.

b) Estimation. We will prove that two beacons are not enough. Consider three parts of our maze (Fig. 14): part $\mathcal{K}$ is room $K$ and the dead-end corridors that lead from it to the right and down, part $\mathcal{L}$ is room $L$ and the two dead-end corridors that lead from it up and to the right, part $\mathcal{N}$ is room $N$ and the two dead-end corridors that lead from it to the left and down. 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 link entering room $K$ from the right. Then the robot, being in room a3, will hear the same signals as in room b4, 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, b3, d4 will allow the robot to orient itself in this maze. Here, it is easier to perform a case-by-case analysis than to come up with some general considerations. In Figure 15, we marked the distances from all rooms to beacon b3. As we can see, rooms with distances $0,1,2,5$ and 8 are uniquely defined. Rooms with a distance of 3 are at different distances from beacon a1. Similarly, rooms with distances of 4, 6, and 7. There are three rooms with a distance of 9: one of them -62- is at a distance of 2 from beacon a1, while the other two are at a distance of 4 from a1, but they have different

![](https://cdn.mathpix.com/cropped/2024_05_06_57b8ad17478f0226d916g-10.jpg?height=543&width=580&top_left_y=2084&top_left_x=218)

Fig. 14: Parts of the maze

![](https://cdn.mathpix.com/cropped/2024_05_06_57b8ad17478f0226d916g-10.jpg?height=529&width=551&top_left_y=2094&top_left_x=1044)

Fig. 15: Distances to beacon b3
distances to d4. Two rooms with a distance of 10 - g1 and g3 - are at a distance of 5 from beacon a1, but they differ in their distance to d4, while another one - b1 - is at a distance of 1 from a1 and thus differs from the previous two. Two rooms with a distance of 11 - d3 and g4 - are at distances of 1 and 3 from beacon d4, while the other two - a1 and d1 - are at a distance of 7 from d4, but at different distances from a1. Finally, rooms with a distance of 12 differ in their distance to d4.