When I was a student at NMSS, one of the problems that we looked at was the museum guard problem.
Basically, the problem is to work out how many guards you need so that everywhere in the museum is under observation.
Obviously, the answer depends on the shape of the museum. I am going to consider only 1-storey museums.
Here is an example:
Clearly, 1 guard is enough to guard this museum. (Moreover, it doesn’t matter where the guard stands; he or she can see the whole of the museum from any position.) I think it is fairly clear that you only need one guard for any museum whose shape is a convex polygon (that is, a polygon where all internal angles < 180°).
Things get more interesting when you have concave polygons (that is, polygons which have at least 1 internal angle > 180°). Here’s an example:
How many guards does this museum need? How can you figure it out?
Here are a few ideas:
- You could put in one guard somewhere and then see if there is an unobserved area, and add another guard into observe that area, and so on until all of the areas are covered.
- You could count the number of edges and then say that if there was one guard observing each edge the whole museum would be covered.
- You could chop the museum up into sections so that every section was a concave polygon and put one guard in each section.
Can you come up with a method that works for every possible museum?
Could you list a set of rules (an algorithm) to be followed in employing and placing guards?
Does your method use the least number of guards? How do you know? Can you prove it?
I think it’s an interesting problem.
When I was an NMSS student and we looked at this problem, we kept looking deeper and deeper into it, and trying to prove more and more basic things. For example, when we wanted to cut a complex polygon into two simpler polygons, we first had to consider whether or not this was always possible, and when it was possible we had to consider why this was so and see if we could prove it. Then we took the reasons that we used in this proof and looked at why they were true. And so on, until we got down to things that we just couldn’t prove. We got down to the statement that “an infinite, straight line divides a plane into two pieces”.
There are some basic statements in maths that cannot be proven, but which are true. Such statements are called “axioms”. It is amazing how much mathematics can be built up from just a few axioms. But that’s a topic for a different blog.