Finding your way through the lighthouses… RESOLVED!
It’s been three days since I posted in “Problem of the Day”, and that’s because it was Labor Day Holiday! Happy (belated) Labor Day!
Anyway, let’s refresh our minds by revisiting the following problem:
If you haven’t read this yet, have a quick look and think about it for 5 minutes. Try drawing the lighthouses on paper, building them with Lego, or go visit an actual lighthouse!
(Wait 5 minutes)
If you’re still stuck, that’s perfectly fine. This is not an easy problem; in fact, it’s based on a problem from an international collegiate mathematics competition. On the other hand, don’t lose confidence upon hearing this! It can be solved directly, and quite cleverly, using the mathematics taught in primary school (or maybe in kindergarten).
For reference, here’s my approach:
Let’s label the lighthouses A, B, C, D, E, and F, just for convenience. There are two lighthouses that nobody can see, and just call them E and F (since the labeling doesn’t really matter, as long as it’s consistent).
There’s something very interesting: no three lighthouses are in a single line! If this is the case, how can two lighthouses be blocked off at the same time? Since at least one lighthouse is required to block your friend’s view, that means we need two lighthouses blocking E and F. So, it’ll probably look something like this:
Meanwhile, let’s consider how this may restrict the maximum number of friends present. As we know from the conditions, each friend must lie at the intersection points of two lines, with each line passing through two distinct lighthouses.
One of these two lines must pass through E, and the other must pass through F. Also, notice that they cannot lie on a line that passes through both E and F, otherwise there cannot be a third lighthouse blocking E/F.
We can now see that your friends have to meet very strict requirements! Under these considerations, there could be at most 4 lines passing through E, and at most 4 lines passing through F. Friends must lie on the intersections of lines; since each line through E can intersect with at most 4 lines through F. Theoretically, there could be 16 friends.
But… we have a problem. In our discussion, we have also counted cases where the lines intersected on top of a lighthouse like this:
In this case, your friend’s view isn’t really being blocked by the lighthouse. How many such scenarios have we counted? Well, this only happens if we have selected the same lighthouse twice in the previous step. Since there are 4 lighthouses other than E and F, it has occurred four times.
12 seems like a more reasonable number, but if you tried to find the positions of 12 friends, you would spend a very (infinitely) long time. Why is this?
Well, the above picture shows the location of our real friend, but there’s also an “imaginary” friend, who is located at the intersection of the diagonals of the quadrilateral formed by the four lighthouses.
For each of the friends we counted, we also counted an additional “imaginary” friend! Hence, we have to divide the previous number by 2 to obtain 6 friends. Notice that we do not have to divide the 4 friends we subtracted previously: this is because the imaginary friend does not occur when both blocking lighthouses overlap.
But wait! We’re not done yet. The above work only shows that there are at most 6 friends, but we don’t know if 6 friends is achievable. Our final step is to construct a scenario where 6 friends exist, and this is shown below:
And there you go! 6 friends (including yourself) for the rescuer to find. Though to be honest, if you can’t remember that you came with 5 other people, you probably should go check your memory (I should probably go check mine at this point).
