561 security guards are positioned so that no two pairs of guards are the same distance apart. Every guard watches the guard closest to him. Is there an arrangement of the guards so that every guard is being watched?
I don't have the proof of this, but the answer is no. If you consider the guards as vertices of a polygon with distinct sides, and if the number of vertices is odd, then there always remains 1 vertex left unwatched.
If one of the guards is being watched by at least two others then the remaining 560 guards will have at max 559 other fuards to watch them and so by pegion home principle one of them is unwatched. So assume that nobody is being watched by more than two guards. Now take the two guards who are shortest distance apart. The two will be watching each other as the distances are unique. Now they wont be watched by any other guard by the previous result. So we just ignore them and consider the remaining 559 guards and continue applying the same logic. Finally we will be left with one guard who remains unwatched ( As the initially number was odd and each time we remove 2 guards)
I don't have the proof of this, but the answer is no. If you consider the guards as vertices of a polygon with distinct sides, and if the number of vertices is odd, then there always remains 1 vertex left unwatched.
ReplyDeleteNo. Nobody watches the guard who is furthest away from any other guard. From: the solver who uses the name "Moby Dick".
ReplyDeleteIf one of the guards is being watched by at least two others then the remaining 560 guards will have at max 559 other fuards to watch them and so by pegion home principle one of them is unwatched.
ReplyDeleteSo assume that nobody is being watched by more than two guards. Now take the two guards who are shortest distance apart. The two will be watching each other as the distances are unique. Now they wont be watched by any other guard by the previous result. So we just ignore them and consider the remaining 559 guards and continue applying the same logic. Finally we will be left with one guard who remains unwatched ( As the initially number was odd and each time we remove 2 guards)