15
$\begingroup$

Darkness has descended on the infinite plane of Euclidea. The only sources of light are $4$ lighthouses; they were built long ago, and cannot be moved. The bulbs of these lighthouses can be rotated any direction, and illuminate a $90^\circ$ sector of the plane. The Euclideans want to bring light to the entire plane: can they do it, no matter where the lighthouses were built?

What about when there are $5$ lighthouses, but they only illuminate a $72^\circ$ sector?

(Think of the light houses as being transparant, they don't cast a shadow).

Edit Statement was reworded to clarify that the lighthouse locations cannot be chosen.

$\endgroup$
  • $\begingroup$ I don't think this is getting solved. Maybe just post your own solution? $\endgroup$ – xnor Jun 17 '15 at 20:29
  • $\begingroup$ @xnor Done. Difficult, but hopefully still qualifies as a puzzle. $\endgroup$ – Mike Earnest Jun 20 '15 at 18:57
  • $\begingroup$ You must have been thinking about this problem for quite a while! (I am happy to see the paper you link to in your answer too - I'd been wondering about that generalization) $\endgroup$ – Milo Brandt Jun 21 '15 at 1:33
  • $\begingroup$ @Meelo Indeed, its a very cool problem! I've seen it many places, but the solution I linked came from The Puzzle Toad (listed under "Darkness"). That site has many other cool math puzzles, I think you'd like it. $\endgroup$ – Mike Earnest Jun 22 '15 at 1:23
6
$\begingroup$

This answer proves that four lighthouses is possible. It turns out that it is also possible with five lighthouses.

The first step is to choose a lighthouse, call it $A$, and angle it in such a way that

  • there are two lighthouses on either side of the midline of its light
  • if you rotated it $180^\circ$, it wouldn't shine on any lighthouse

Below is an illustration:

enter image description here

Why is this possible? Imagine stretching a large rubber around all of the lighthouses, forming a polygon. On the vertices must have an angle of at most $108^\circ$; choose this lighthouse to be $A$. Then rotate $A$ until its midline cuts the other four lighthouses in half. If doing this doesn't fulfill the second bullet point, then turning $A$ around $180^\circ$ will.

Next, we use the two lighthouses below the line to illuminate the rest of the upper half. Let's label a compass with degree marks going counterclockwise so $0^\circ$ is east, meaning $90^\circ$ is north, $180^\circ$ is west, etc.

Of the bottom two lighthouses, let $B$ be the one which is further along in the $342^\circ$ direction, and $C$ be the other. Shine $B$ so that the clockwise edge of its beam points towards $72^\circ$. Shine $C$ so its clockwise edge points east. This will illuminate the upper plane, as shown below:

enter image description here

Note that $A$ and $B$'s beams must overlap because of the second bullet point in how $A$ was chosen, while $B$ and $C$'s beams overlap since $B$ is further along in the $342^\circ$ direction.

Doing the same procedure with the upper two lighthouses illuminates the plane.

As a fun fact, it turns out that if you have any number of lighthouses, and their beam angles add up to $360^\circ$, then they can illuminate the plane. However, the proof is quite mathy.

$\endgroup$
3
$\begingroup$

TLDR:

4: yes
5+: no

Extended version:

How do we cover the area?

For $n$ lighthouses, each lighthouse illuminates an arc of $\frac{360°}n$. This means that each lighthouse is responsible for exactly $\frac1n$ of the area--if they were all clumped together, they must all be pointed radially outward cutting the plane into a pie with $n$ equal slices. If a lighthouse is not at the origin, it still must be oriented in a way that it covers that same pie slice. The only way for it to do this is if it is pointed the same direction, and located somewhere in its slice's negative space.

That didn't make sense? I don't blame you. It's easiest to understand with the 4 lighthouse case:

Take the cartesian coordinate system. Each lighthouse is at the origin and pointed at one of the quadrants. Their illumination borders are along the axes. Lighthouse 1 is pointed into the $(x\ge0, y\ge0)$ quadrant; lighthouse 2 is pointed into the $(x\ge0, y\le0)$ quadrant, and so on. Lighthouse 1 continues to cover its entire quadrant as long as it moves (translationally) anywhere in the $(x\le0, y\le0)$ quadrant. A similar statement is true for lighthouse 2 and the $(x\le0, y\ge0)$ quadrant.

To form a solution for $n$ lighthouses:

Take a very large circle and divide it into $n$ equal slices. Orient your circle such that all of the lighthouses are inside it, and exactly one lighthouse is "inside" each slice (a lighthouse directly bordering multiple slices can be chosen to be in any one of them). Aim each lighthouse in the exact opposite direction of its chosen slice. Voila 100% coverage.

Finally

For 4 lighthouses, you should always be able to choose your origin and the orientation of the axes such that one lighthouse is "in" each quadrant. For 5 or more this is not always possible. Take for example a clump of three lighthouses very far away from the other two, which are also clumped together. There is no way to choose an origin such that the lighthouses are evenly distributed to all pie slices.

Here's a picture for the unexplained downvoters

An example of 4 lighthouses, 3 forming a triangle with 1 inside.
Each quadrant is completely covered by its lighthouse, therefore the whole plane is covered.

$\endgroup$
  • 1
    $\begingroup$ I believe your reasoning for 4 lighthouses, but for 5, you've only shown that your method doesn't always work, not all conceivable methods. (I didn't downvote) $\endgroup$ – Mike Earnest Apr 5 '15 at 17:52
  • 1
    $\begingroup$ Can you prove that four points can always be separated by axes? $\endgroup$ – xnor Apr 5 '15 at 19:15
  • $\begingroup$ As xnor says, "Should always be able to" is a long way from a proof; for instance, it's not true if you aren't allowed to arbitrarily choose orientation but can only translate your points. $\endgroup$ – Steven Stadnicki Apr 5 '15 at 19:20
  • 1
    $\begingroup$ @MikeEarnest I was hoping the first section would indicate that there is no other method that can work. If that isn't clear, or if you still have doubts, I can try to take another pass at it. To me, the question about 5+ is whether I've correctly proven my method won't always work (something I'm starting to rethink as I ponder how to respond to xnor). I guess like Engineer's this answer is only partial. I would love to see other people making some attempts at it, yet an ant that can't decide where it wants to go seems to be all that anyone wants to talk about. $\endgroup$ – dmitch Apr 5 '15 at 21:53
  • $\begingroup$ I don't believe most of this. Yes, if you get lucky and place each of your four points into separate quadrants, then you have won. You didn't prove that this is necessary possible, and in fact, it is not necessarily possible (eg, put the four points in a straight line). Yes, you formed a solution for n lighthouses.. but forming a solution is trivial. Just take them all as the same point (more or less) and it works. The question is to either prove that you always can, or to find a counter example (and prove that it is a counter example). $\endgroup$ – Ben Frankel Apr 7 '15 at 10:09
3
$\begingroup$

Here's another solution to the four lighthouse problem. It's very similar to dmitch's, but replaces the bit about placing the axes so there is one lighthouse in each quadrant with something that is a bit more straightforward I think.

Suppose there existed two lighthouses at points $(x_1, y_1)$ and $(x_2, y_2)$, with $x_1 \leq x_2$, below the $x$-axis of the plane. Then these two lighthouses could illuminate the entire plane above the $x$-axis. Just point the $(x_1, y_1)$ in the same direction as quadrant I, and the $(x_2, y_2)$ lighthouse in the same direction as quandrant II.

.

Now separate the four lighthouses with some line so that there are two on each side of the line (To do this, think of a line at a random angle sweeping across the plane; eventually, you'll reach a position with two lighthouses on one side of the line, and two on the other.) The two lighthouses above the line can illuminate the area below the line, and the two lighthouses below the line can illuminate the area above. Hence the whole plane is covered.

$\endgroup$
  • 2
    $\begingroup$ Good point that we don't really need to bother with placing the y-axis in the 4 lighthouse case (it's still there, we just don't care). +1 $\endgroup$ – dmitch Apr 5 '15 at 22:17
0
$\begingroup$

Partial Answer

This answer is only valid when the lighthouses form a convex polygon.

If you can't move the lighthouses, the solution is to

Find the centroid of the polygon formed by connecting the four lighthouses. For 4, you can cheat this by drawing 2 lines between the lighthouses on opposite sides. Point the lighthouses at the intersection of those lines.


Diagram 4


With 5 lighthouses, the solution is similar but a little more complex to find the center point so I'll just approximate it graphically. (I know the diagram still shows the light cover a 90° sector instead of a 72° sector. That's just laziness on my part.)


Diagram 5


As you've probably realized, this operation should work for any polygon with n sides long and lighthouse coverage angle α degrees so long as α ≥ 360/n is true.

$\endgroup$
  • $\begingroup$ You seem to be assuming the lighthouses form a convex polygon. In the four lighthouse case, what about when one of the lighthouses is in the triangle formed by the other 3, so that you can't draw intersecting lines between two pairs of them? $\endgroup$ – Mike Earnest Apr 3 '15 at 3:36
  • $\begingroup$ @MikeEarnest If it is significantly concave such that the centroid is outside the area, the answer is only slightly different for 4. I can't think of a solution for 5 when they're collinear. $\endgroup$ – Engineer Toast Apr 3 '15 at 3:43
  • $\begingroup$ The solution in the first picture doesn't work. From the bottom two vertices, the two light edges going up eventually cross, and beyond that is a wedge of darkness. $\endgroup$ – xnor Apr 3 '15 at 5:08
  • $\begingroup$ So I've never tested this but I just learned I'm not allowed to downvote my own post, either. $\endgroup$ – Engineer Toast Apr 3 '15 at 11:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.