25 Dots, 8 Lines | Hacker News Reader

25 Dots, 8 Lines

e-riddles.blogspot.gr

25 pointshliaskal24 comments

Spoiler - interesting solution [from the comments]: http://www.scribd.com/doc/133494020/Extended-9-dots-puzzle-t...

Solved mathematically :)

Where's the 'solved' part? At the very best, he shows that you can do it with 2n-2 lines. Even that includes a lot of hand waving/implicit "it is easy to see"-s.

That you need 2n-2 lines, he doesn't talk about at all.

Additionally the OEIS now contains a wrong fact [1] - the sequences are offset by one. I am not even convinced that 2n - 2 is optimal - does somebody know if it is or can proof a better lower bound than the trivial n?

[1] http://oeis.org/A058992

I left a hill-climbing solver running overnight and found quite a few solutions, including a couple that can be made to stay inside the square: http://imgur.com/a/Wd2dS

I can solve it with just 5 lines. You just have to get the pen to infinity and then come back.

Wait, if infinity wraps around that'll take just one line!

I am pretty sure that it is meant to be solved on a compact, simple connected subset of |R^2, with Euclidean metric.

Careful with that. If the frontier of that subset is not far enough from the points, the problem will not be solvable.

And probably the word 'open' is also missing, then I can always find an embedding such that there is enough room :)

I'm pretty sure I was just joking.

Never meant to imply otherwise. But you are raising a good point, if one thinks about the general problem then it is not really straightforward to embed the points in |R^n instead of (for example) a torus.

It doesn't say you have to go through the center of the dot. If you angle them a bit 5 non-infinite lines will do.

My technical drawing teacher called that the "fat point theorem".

In your advanced class, you'll meet the "fat pen theorem". That's even more powerful. It gives you a solution using a single point.

It doesn't have to go to infinity.

Look at this solution for 9 dots/three lines: http://www.goodmorningcreativity.com/wp-content/uploads/2010...

That scales up to whatever sized square of dots you like, provided the "dots" are not points but are circles with a non-zero diameter.

What if you wrap the paper (if the dots are on paper) and draw a line round-and-round?

A bit hard to ensure that it's straight though..

Who needs paper when you have ℝ²? :P

My solution: http://i.imgur.com/z2mo2Jj.jpg

My solution http://i.imgur.com/S2L9pht.jpg

Solution (rot13):

Whfg genpr nebhaq gur bhgfvqr gura hfr gur fbyhgvba gb gur fznyyre chmmyr.

Great. Keeps it simple.

On a side note, can anyone build a cool ROT13 converter? There are some, but they are showing their age.

Why do you need 8 lines? You just need 5 lines, and an enormous piece of paper.

EDIT: Beaten to the punch. I should learn to read comments first.

It doesn't specify that you can't add curved lines between your straight lines without lifting your pen.

It's possible to solve it entirely "within" the box.

What? kindly explain a little..

Reply on news.ycombinator.com