Win a copy of The Java Performance Companion this week in the Performance forum!

# Nine dots

Anupam Sinha
Ranch Hand
Posts: 1090
Hi all
I read this puzzle somewhere. Here it goes

Now the challenge is to use just 4 lines(is it possible to solve it with lesser no. lines ) to cover all the dots without lifting the pen/pencil and crossing a point that has been earlier marked. I wasn't able to solve this and don't have the solution.

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34681
367

Anupam Sinha
Ranch Hand
Posts: 1090
Hi Jeanne

Roy Tock
Ranch Hand
Posts: 83
There is a three line solution to the stated problem. Honest - no kidding.
I'll hold off on posting it...maybe somebody else can come up with it.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Well, I can think of two one-line solutions - depending which of the unstated "standard" assumptions we wish to violate. There's a three-line solution too, which is a bit easier to justify, given the way the problem was phrased. I'd be interested in seeing you make a good ASCII diagram of the 3-line solution though, Roy.
[ August 05, 2003: Message edited by: Jim Yingst ]

Anupam Sinha
Ranch Hand
Posts: 1090
Roy : I'll hold off on posting it...maybe somebody else can come up with it.
Jim : I'd be interested in seeing you make a good ASCII diagram of the 3-line solution though, Roy.

So Jim is waiting for Roy and Roy for Jim to give the answers.

Anupam Sinha
Ranch Hand
Posts: 1090
Jim : Well, I can think of two one-line solutions - depending which of the unstated "standard" assumptions we wish to violate.

I also thought of one but thats with three lines use three pens.

Bhau Mhatre
Ranch Hand
Posts: 199
Hi Jeanne, the solution that you gave crosses the lower-left point twice. Anupam's question reads "without lifting the pen/pencil and crossing a point that has been earlier marked"

Bhau Mhatre
Ranch Hand
Posts: 199
Originally posted by Roy Tock:
There is a three line solution to the stated problem. Honest - no kidding.
I'll hold off on posting it...maybe somebody else can come up with it.

I know one three-line solution that involves using bigger sized dots
Is that what you have?

Anupam Sinha
Ranch Hand
Posts: 1090
Originally posted by Mumbai cha bhau:
Hi Jeanne, the solution that you gave crosses the lower-left point twice. Anupam's question reads "without lifting the pen/pencil and crossing a point that has been earlier marked"

Yeah in the answer yes it does. But you can surely start from the second dot of the first vertical row.
[ August 05, 2003: Message edited by: Anupam Sinha ]

Anupam Sinha
Ranch Hand
Posts: 1090
I guess in the original version, no overwriting was also a rule. So I guess that the Jeanne's solution wouldn't hold in that case. But yes if we start from the second dot of the first vertical row, then it does answers my question.
Now another thing, is it possible to solve this puzzle with the orignal challenges and adding these two as well.
1. No overwritting. (no crossing of lines)
2. Use exactly four lines (no more no less)
Now is it solvable. Or is it solvable by us. Without using bigger dots and thin lines or so kinda approach.
[ August 05, 2003: Message edited by: Anupam Sinha ]

Bhau Mhatre
Ranch Hand
Posts: 199
Originally posted by Anupam Sinha:
Yeah in the answer yes it does. But you can surely start from the second dot of the first vertical row.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
I guess in the original version, no overwriting was also a rule.
If by "no overwriting" you mean "no crossing of lines, ever" then I doubt this was part of the original problem; it makes an elegant solution impossible. If "no overwriting" just means "don't pass through any dot more than once" then that's fine.
Now another thing, is it possible to solve this puzzle with the orignal challenges and adding these two as well.
1. No overwritting. (no crossing of lines)
2. Use exactly four lines (no more no less)
Now is it solvable. Or is it solvable by us. Without using bigger dots and thin lines or so kinda approach.

Well, I don't need bigger dots - the dots you gave us in the first place are already big enough. Seriously, you did use 'o' to indicate the dots, rather than '.' - to me that indicates that the dots do have nonzero width. Any width is sufficient for a 3-line solution (if the paper is really big); adding a 4th line is not difficult. Plus I've still got a 1-line solution you haven't excluded yet; I can add lines to that as necessary.
I had two 1-line solutions, but one required a really big marker. I suppose that was excluded by the very vague "without using bigger dots and thin lines or so kinda approach." I've still got the other solution though...

Roy Tock
Ranch Hand
Posts: 83
Jim and Mumbai both allude to the three-line solution I have in mind.
Since the dots have thickness, it's possible to draw lines through, say, the top three dots on a small non-zero angle from horizontal. With that observation, and the observation that your lines can be as long as you wish, you can see that it is possible to connect the nine dots with three lines.

ben ben
Greenhorn
Posts: 1
does anyone know the solution to a 16 dots sq? max 6 lines and a added challenge of no criss-crossing of the lines.

fred rosenberger
lowercase baba
Bartender
Posts: 12149
31
I assume we're talking about the dots being on a standard, Euclidian plane? I'm not SURE, but i'd wager that if you could put the dots on a curved plane (possibly a sphere), you could do it in fewer lines...

and if you could curve the plane enough, you could then draw a single line through the 3D world that hit all 9 points
[ April 04, 2005: Message edited by: fred rosenberger ]

ankur rathi
Ranch Hand
Posts: 3830
Hi everybody,
I am not able to see this solution link because of some policies of company. Cound any body please draw that solution here for me.
Thanks a lot.

Ryan McGuire
Ranch Hand
Posts: 1069
4
Ok, has anyone found a solution to the puzzle that the original author was trying to pose that uses four lines that DON'T cross? I'm convinced there isn't one, but I'm not positive.

- Nine zero-size points in a 3x3 square on a non-foldable euclidean plane.
- The line segments are zero-width.

Ryan

Jim Yingst
Wanderer
Sheriff
Posts: 18671
I don't believe the original author of this thread required that the lines never cross. It was required that they not cross "a point which has earlier been marked." I took this to mean that for the nine points/dots which are shown originally, you can't go through those points more than once. However it's legal for two lines to cross at some other point besides those nine - and indeed, I don't believe a solution is possible otherwise. (Unless we violate one of the other originally-unstated assumptions of the problem, as discussed above.)

Recently a similar problem was posted here with the restriction "you should not overwrite a line". If this means that a line cannot intersect another line at all, and our other restrictions are also in place, then I don't believe a solution is possible. This is just another problem that, depending on how carefully it's stated, may have too many solutions, or none at all.