18
$\begingroup$

I dropped in to Ernie's place a while back and he asked me to stay and help calibrate his new Drilling Device. It was an impressive looking machine consisting of a large raygun-like thing mounted on an x-y translation table. An electronic eye was supported above the table, and to one side was a box with two buttons, one red and one blue.

Ernie explained that he was sick of drilling countless holes in sheets of steel manually, so he had built this tool to do the job automatically. "The extraordinarily accurate x-y table has precisely 1000 mm x 1000 mm of travel, so I can cut holes anywhere within an area of one square meter - accurate to the nearest micron. The drill uses an incredibly powerful laser to drill the holes so it takes absolutely no time at all to make the hole. The translation stage has enormously powerful, but restrained, drive motors so it can move the drill between any two locations in the one metre square area at a speed of precisely 1 m/s."

"But how does it know where to drill the holes?", I asked.

"Ahh", Ernie replied, "I felt that an analogue approach was more desirable than a digital one for this job, so you just mark where you want to put the holes on the steel sheet with these two special pens. You draw a circle with the red pen and that is where the drill puts the first hole, and you add a series of crosses with the blue pen to tell the drill where to put the rest of the holes. The electro-mechanical brain works out what path to follow and when to drill"

enter image description here

It felt like a typical Ernie invention - weirdly simple in some ways, but bizarrely complicated in other ways. "Tell me more?", I asked, "what do the two buttons do?". And Ernie explained that each button followed a very exact algorithm.

Red button: 
If a red circle exists:   
   Move the drill, in a straight line, from its current position to the centre of the red circle.

Blue Button:
Drill a hole.
While un-drilled blue crosses exist
   Move the drill, in a straight line, to the centre of the nearest blue cross,
   Drill a hole.

Ernie asked me to mark a plate so we could test the system. I marked the first plate with exactly one red circle and five blue crosses (the plate was a bit oversize so there was plenty of room to mark all the drill-points within the central 1000 mm x 1000 mm square that the drill could reach.). We mounted the plate and Ernie pressed the Red button - the drill moved until it was exactly over the red cross. Then he pressed the Blue button and simultaneously started a stop-watch. There were 6 bright flashes (and a little more flying molten steel than I had expected) as the drill made the holes in the plate. At the exact moment the sixth hole was made, Ernie stopped the watch.

"Hmmm", he exclaimed, and then very carefully measured the positions of the holes in the plate with a ruler. "You seem, quite by chance of course, to have chosen hole positions that maximize the time required for the drill to complete the Blue algorithm for six holes!".

This only happened a few weeks ago ago but Ernie never told me exactly how long it took the Blue algorithm to drill the six holes, or where (exactly) in the steel in the sheet I drew the red circle. Can you help me?

If that is all to easy, I plan to visit Ernie around Christmas and would love to play with his head by "quite by chance" marking out a seven hole plate which maximizes the Blue algorithm time, so knowing where to mark the red circle and six blue crosses would be useful. Ernie only uses his second-best stop-watch and ruler for this kind of job, so positions accurate to the nearest micron, and times to the nearest microsecond should be sufficient.

$\endgroup$
  • $\begingroup$ Any thoughts on proving upper bounds? Besides a horrible casework hootenanny? $\endgroup$ – Lopsy Dec 18 '14 at 1:20
  • $\begingroup$ Well Ernie never gave me a formal proof that the 6-hole solution was the upper bound, but as yet nobody has reached my best estimates for 6 or 7 hole solutions. $\endgroup$ – Penguino Dec 18 '14 at 2:35
  • 1
    $\begingroup$ Love this puzzle. A shame I can +1 only once. $\endgroup$ – BmyGuest Dec 18 '14 at 22:14
  • $\begingroup$ Your Ernie puzzles are consistently amazing. Thanks for creating them! $\endgroup$ – Kevin - Reinstate Monica Dec 20 '14 at 17:06
  • $\begingroup$ I feel I have neglected Ernie recently - work pressure and all that. But hope to have some more of his stories in the new year. $\endgroup$ – Penguino Dec 21 '14 at 2:27
5
$\begingroup$

Starting with @Lopsy's answer for 6 holes, I was able to get a larger value. Here's how I went about it:

First, I assume that if two blue crosses are equidistant from the drill, then the drill can choose either, and I should assume that the smaller total path is the total distance.

With 2 holes, the holes must go in opposite corners.
$(0, 0), (1, 1)$

With 3 holes, the holes go in any 3 corners, starting with the one adjacent to the other two.
$(0, 0), (1, 0), (0, 1)$

With 4 holes, the holes go in 3 corners and on the diagonal, making sure the diagonal length is less than 1. Start with corner adjacent to the other two.
$(0, 0), (\sqrt2/2, \sqrt2/2), (1, 0), (0, 1)$

With 5 holes it gets interesting. Using the existing holes, the obvious place for the 5th hole is the empty corner. However, once this is done, the center hole can be moved to give a longer distance. It maximizes at $(\sqrt3/2, 0.5)$.
$(0, 0), (\sqrt3/2, 0.5), (1, 1), (1, 0), (0, 1)$

For the 6th hole, there is now an equilateral triangle with vertices at $(0, 0), (0, 1), (\sqrt3/2, 0.5)$. The sixth hole goes in the center of this triangle, at $(\sqrt3/6, 0.5)$

Tweaking the 2 non-corner points and starting in the center of the triangle gives the following 6 points in the order they would be drilled:
$(0.288674, 0.499999), (0, 0), (0.866024, 0.500001), (1, 1), (0, 1), (1, 0)$
The total distance is 4.509199 meters.

6 dots

For the 7th dot, there's a large space in the upper half of the area with nothing, so getting it as far from $(0.255674, 0.499999)$ as possible while still making it the closest dot gives a point of $(0.500000, 0.955388)$. With this as the new starting point you have the following 7 points in the order they would be drilled:
$(0.500000, 0.955388), (0.288674, 0.499999), (0, 0), (0.866024, 0.500001), (1, 1), (0, 1), (1, 0)$
The total distance is 5.011189 meters.

7 dots

While looking for 6 dots, I tried various placements. For example, I started with the full area and tried points at every 0.1 meter point, then picked the best ones and scaled down to 0.01 meter and so on. So I'm fairly confident in my answer.

For 7 dots, I assumed the positioning of the first 6 dots wouldn't change, found a spot for the 7th dot, then tested the values to make sure they were at least a local maximum (meaning that there might be a longer distance, but there wouldn't be one using the same approximate positioning). So I think my answer is correct, but I wouldn't be surprised if a drastic re-positioning of all 3 points turned out a larger distance.

$\endgroup$
  • $\begingroup$ That is as good as I can find too. The 0.955388 is more accurately given by (4+sqrt(3))/6, as I am sure you know. Nice analysis. $\endgroup$ – Penguino Dec 21 '14 at 2:25
2
$\begingroup$

Here are my punts for six and seven holes. The lengths are:

Six holes: $2+\sqrt 2+2\sqrt{2-\sqrt{3}}=4.449...$ meters
Seven holes: $2+ \sqrt 2+3\sqrt{2-\sqrt{3}}=4.967...$ meters

First off, six holes:

enter image description here

If this is a unit square, then the non-corner holes are at $A=(\frac 12, \frac {\sqrt{3}}{2})$ and $B=(\frac {\sqrt{3}}{2}, \frac 12)$. Many distances are equal, so adjust the hole positions by a very tiny amount so that the drill path is the red path shown.

Now seven holes. Just add one more hole, symmetrically, at $C=(\frac 12, 1-\frac {\sqrt 3}{2})$, and then change $B$ to the red hole.

enter image description here

Again, adjust the hole positions by a very tiny amount so that the drill path is the red path shown.

For reference, if we add an eighth point to complete the symmetry (shown below), then all the red distances and all the blue distances are equal.

enter image description here

$\endgroup$
  • $\begingroup$ Both the 6-hole and 7-hole solutions are close, in terms of time to drill the holes, but not optimal. $\endgroup$ – Penguino Dec 18 '14 at 8:25
  • $\begingroup$ Just a bit of a thought, from five years on - wouldn't that be most pessimal? (see: catb.org/jargon/html/story-of-mel.html ) $\endgroup$ – Stackstuck Mar 19 at 19:11

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.