6
$\begingroup$

The military field has rectangle shape with the dimension of 16 km to 12 km and recently there are some drone activities around the area and drones are not welcome to the military region!

Your commander gives you an order to put some small 2-km range radar towers in the region to detect and track these drones while they are flying in the field then it will be eliminated! So you cannot have any blind spot in the region, that means radars need to cover whole region to track the drone all the time.

What is the minimum number of radar towers you need to guarantee there is no blind spot in the region?

Notes:

  • Radar tower has 2-km radius capacity, you may assume they are point for simplicity.
  • Drones can be detected in spite of their height if they are in the horizontal range of the radar towers. In other words, this is 2-D question.
  • Radars needed to be inside the military area for security.
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It's interesting that of the answers posted so far two say (roughly) "aha, I spotted the trick, you only need to cover the edge" and one says (roughly) "aha, really you only need to cover the edge, but I assume that's not the intention of the puzzle". If the latter is correct, then it might be worth editing the question to make it more explicit that you really do want the whole thing covered. $\endgroup$
    – Gareth McCaughan ♦
    Oct 24, 2017 at 21:05
  • 2
    $\begingroup$ @GarethMcCaughan you needto cover whole region, thats what i tried to mean by "no blind spot in the region" $\endgroup$
    – Oray
    Oct 25, 2017 at 4:51

4 Answers 4

Reset to default
8
$\begingroup$

(Now with coordinates.)

After more than a month of admiring the development of this puzzle’s poser’s solution of The farmer and the olive trees, I was ready to try a similar approach, and came up with...

22 radar towers
           The (northeast edges of) commas are at their circles’ centers. 

Radar tower coordinates as text: (-6.83,4.37) (-4.20,4.67) (-1.33,4.53) (1.33,4.53) (4.20,4.67) (6.83,4.37) (-6.30,1.67) (-3.03,1.43) (0,1.07) (3.03,1.43) (6.30,1.67) (-7.60,-1.30) (-4.87,-1.60) (-1.70,-1.93) (1.70,-1.93) (4.87,-1.60) (7.60,-1.30) (-6.57,-4.63) (-3.40,-4.97) (0,-4.97) (3.40,-4.97) (6.57,-4.63)


This puzzle’s parameters also allow a perfectly fitting 5×5 (suboptimal) arrangement and other tantalizingly almost-perfect arrangements, one of which leads to a near-optimal 24-tower solution. These arrangements provide excellent clues, as the initial solution ensued from the near misses.

24 radar towers


Initial solution.   More intriguing than the eventual solution.

23 radar towers


Another 23-tower solution provided by Oray.   How this alternates (and warps) columns led to the present solution’s alternating (and warping) of rows.
Oray

Improve this answer
$\endgroup$
8
  • $\begingroup$ I thought for sure this must have been what you had in mind, @Oray. I haven't proven this works analytically, or tested it with a modeling program, but I have made some very slightly different sloppier variations that also seem to work, just barely. You might also like the other (analytically-provable) 24-tower solutions when their pictures are ready. $\endgroup$
    – humn
    Oct 25, 2017 at 12:24
  • 1
    $\begingroup$ I have confirmed this answer is the right one. very brilliant one! $\endgroup$
    – Oray
    Oct 25, 2017 at 13:21
  • $\begingroup$ Guess I only had one other 24-tower solution that worked after all, @Oray, now on display. This puzzle's innocent-looking parameters really pack a lot of tight adventure along the borders of solutions. $\endgroup$
    – humn
    Oct 25, 2017 at 14:56
  • 1
    $\begingroup$ Thank you for adding that elegant refinement of 5x5 into 5-4-5-4-5, @Oray, this answer certainly was incomplete without it. Another delicate fit to reflect the puzzle's well-chosen parameters! Thank you also for taking the trouble to verify my solution. $\endgroup$
    – humn
    Oct 25, 2017 at 20:02
  • 1
    $\begingroup$ Guess what, @Oray, your solution led to an improvement! The new solution has only one axis of symmetry but otherwise contains no precise regularity, so I constructed it with safe, though small, overlaps at triple junctions. I feel like I'm paralleling your adventure of solving The farmer and the olive trees. $\endgroup$
    – humn
    Oct 26, 2017 at 3:14
9
$\begingroup$

For the case the question also covers drones that appear from vacuum fluctuations:


I need 24 towers. In the image the hexagons have an edge length of 2 km, so that each of them is the territory of one of the towers.
Note: The biggest rectangle that would fit into the area in this constellation of towers would be $7 \cdot \sqrt{3} \, \text{km} \cdot 17 \, \text{km}$.

For those who might wonder whether the same arrangement needs less towers if the pattern is rotated by 90° with respect to the territory:


In this case there are many small pieces at the edges that need an extra tower. So it takes 26 towers (27 if I followed the pattern strictly and did not replace the two towers in the top right corner).

The question was extended, so that all towers must be inside the area:

Starting from the solution with 24 towers, to solve this, the military either has to expand its territory (with weapons) so that the short side of it is $7 \cdot \sqrt{3} \, \text{km}$. Then the upper towers are at the border of the territory.
If this military action is not so appreciated it is also possible to shift the towers lying outside to the border:

Now the towers on the top, left and bottom border are exactly on the border, but can still cover the whole area.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Is that the same number if you tile with the hexagons (or field) rotated 90deg? $\endgroup$
    – user19641
    Oct 24, 2017 at 23:36
  • 2
    $\begingroup$ You don't need vacuum fluctuations to explain the need to cover internal regions. It could be that they need to keep tracking the drone's position until they have time to shoot that drone down. $\endgroup$
    – justhalf
    Oct 24, 2017 at 23:49
  • $\begingroup$ could you mark tower locations? $\endgroup$
    – Oray
    Oct 25, 2017 at 5:36
  • $\begingroup$ @oray I'd say it's fairly trivial they go in the center of each hexagon.. $\endgroup$
    – Tim Couwelier
    Oct 25, 2017 at 6:53
  • $\begingroup$ Also, question should probably include if all towers need to be built INSIDE the surveyed area. This image has towers outside the 'northern' edge of th rectangular area. $\endgroup$
    – Tim Couwelier
    Oct 25, 2017 at 6:55
2
$\begingroup$

Surely-suboptimal answer

This question is equivalent to: how many radius-2 circles does it take to cover all of a 16x12 rectangle? Or, rescaling for convenience: how many radius-1 circles to cover all of an 8x6 rectangle?

(I remark that in practice it would probably be sufficient to put radar towers around the edge of the field, but never mind that.)

This is a problem to which no general solution is known. I'm not sure whether the optimal solution is known for this particular size, but here's a straw-man answer (I expect one can do better with a nearer-to-regular-hexagonal packing): suppose the field has (0,0)km at one corner and (16,12)km at the other, and then place towers at (0,2)+(4m,4n) and at (2,0)+(4m,4n). The total number of towers here is 5x3+4x4=15+16=31.

Improve this answer
$\endgroup$
1
  • $\begingroup$ yes, this is what is asked actually. :) $\endgroup$
    – Oray
    Oct 25, 2017 at 6:01
-1
$\begingroup$

I believe you only need

14 radar towers

Because

Since the towers can detect any drone that passes over them, we do not need to cover the interior of the field, as long as we ensure that we cover the perimeter of the field. Incoming image...

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ But what if there was already a drone inside the base before you started building... $\endgroup$
    – Mike Earnest
    Oct 24, 2017 at 22:39
  • 2
    $\begingroup$ "you cannot have any blind spot in the region." $\endgroup$
    – micsthepick
    Oct 24, 2017 at 23:42
  • $\begingroup$ @micsthepick - I agree this is not the answer now, but at the time of the answer, it fit the question. Edits to the question after the fact made this answer irrelevant. $\endgroup$
    – APrough
    Oct 25, 2017 at 12:12
  • $\begingroup$ I agree with this approach. $\endgroup$
    – Overmind
    Oct 26, 2017 at 9:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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