0

There is an odd number of cameras in an area, placed in a way that the distance between any two cameras is unique. Each camera is pointed towards the nearest camera. Show that at least one camera is not being monitored.

I've been thinking about this problem and believe the solution may lie in an application of Dirichlet's Principle. My first thought was that there will be a greatest distance and so there would be a closer point to each of these and therefore one would not be watched however after more consideration the logic in that statement is extremely flawed.

Any complete solutions or even pointers as to how to solve this problem are greatly appreciated.

Luke Parker
  • 13
  • 2

1 Answers1

0

Some pointers for one possible approach:

Start by considering the case with three cameras. There will be two cameras that are separated by the overall shortest distance. Which cameras are these two watching? What does that imply about the third camera?

Next, consider $2n+1$ cameras. Again, there will be two cameras that are separated by the overall shortest distance. Which cameras are these two watching?

  • What if some other camera is watching one of these two (pigeonhole principle)?
  • Alternatively, if no other camera is watching one of these two, consider the remaining $2n-1$ cameras.

Additional note. The case with just one camera doesn't really fit the question since it has no closest camera to watch, but it seems reasonable to conclude that it is not watching itself.

nickgard
  • 4,116