Classic Dot Puzzle Inspiration

Probability Level 1

What is the minimum number of straight segments needed in a single closed loop , in order to pass through a $3\times 3$ square grid of points such that

each point is intersected exactly once, and
none of the lines have any grid point as their endpoint(s)?

This closed loop meets the requirements, but can we do with fewer segments?

3 4 5 6

6 solutions

Michael Huang
Oct 10, 2018

Since two lines each pass through a single point, we can change their slopes, such that the lines do not pass an extra point. This is inspired by 12-dot puzzle , where 5 straight lines in a loop must pass through a $3\times 4$ grid.

It was not clear to me that you wanted this accomplished with a closed loop. Thanks for clarifying that in the problem now.

Good puzzle!

Steven Perkins - 2 years, 8 months ago

Since the grid points are finite in size, how about if you closed off these three lines, making it 4 lines in a loop?

Geoff Pilling - 2 years, 7 months ago

That is the mentioned solution true in infinite loop case. The problem asked here is more simplified.

Michael Huang - 2 years, 7 months ago

Hahaha. The diameter of a dot! I yell CHEAT, you win, congrats! I'll find something else to do. DISGUSTING.

Bill Weihmiller - 2 years, 7 months ago

That is why I restrict the problem to 2D case. :)

Michael Huang - 2 years, 7 months ago

@Michael Huang – But dots are 2D...

Geoff Pilling - 2 years, 7 months ago

@Geoff Pilling – But if 9 dot problem were to exist on the sphere, then it is possible to have a line, which may not be straight.

More strictly, the lines should pass directly the centers instead of outside the centers.

Michael Huang - 2 years, 7 months ago

I got four. I violated one condition. We need at least three lines. How to prove this rigorously that 5is the answer.

Srikanth Tupurani - 2 years, 7 months ago

It can be done with 3 lines on a sphere, interpreting "straight lines" as shortest paths and "square" as a quadrilateral with four right angles and four sides of equal length. I wonder if there's some exotic metric in which it can be done with 2 or less geodesics.

Jakub Rybak - 2 years, 7 months ago

@ Michael Huang - You are the original poser. You mentioned this is inspired by "12-dot puzzle." But, you used the words "point/s" and "endpoint(s)" in your problem. Points have no dimension, but dots can. It makes a difference for this problem and the answer (staying within the plane).

Linda Slovik - 2 years, 7 months ago

Yes, but points and endpoints are actually two different things. Instead of posing this problem as the single-stroke-pencil problem, I instead ask for the minimum number of lines. Otherwise, the interpretation becomes the issue for both pencil-stroke-drawers and logicians.

Michael Huang - 2 years, 7 months ago

No, my post was not the distinction between points and endpoints. It was to make sure in your problem that the points have no size. The "12-dot puzzle" that is an inspiration for yours is not a good name. It should be called the "12-point puzzle," because the lines pass through points, not dots. So, I understand, in your puzzle as well, the lines pass through points, again, which have no size.

Dennis Rodman - 2 years, 7 months ago

@Dennis Rodman – Yes, that is the thing I made the adjustment. However, someone have edit this problem.

Michael Huang - 2 years, 7 months ago

If I look at the drawing and read "point" as "dot" (with a dimension) there is a solution with only four straight line segments. You can choose the endpoints in the drawing linked below so they can be connected with the fourth straight line to build the loop without touching the dots again: https://i.dailymail.co.uk/i/pix/2016/10/12/11/395321CF00000578-3833985-image-m-27_1476268613250.jpg

Jörg Straube - 2 years, 7 months ago

Given that you say straight lines couldn't one just use a curved line?

Theodore Sinclair - 2 years, 7 months ago

I counted 4 lines because one line contains three points and the other three lines each contain two points.

Kermit Rose - 2 years, 5 months ago

Ben Symington
Oct 22, 2018

It has been shown it can be done with 5, but not that it cannot be done with 4 or below.

The most dots a line can pass through is 3, so 2 or below lines is ruled out otherwise the total is below 9.

3 lines: All lines must have three dots, it is clearly impossible to join them up in a loop.

I will partition 4 lines by the numbers of dots on each line.

4 lines: if three lines have 3 dots then they must be parallel so as not to repeat a dot, and the last line cannot make them a loop.

If two lines have three dots then they still must be parallel, one of the other lines must have two dots, therefore must be parallel, therefore cannot be used to make a loop.

If none of the lines have 3 dots then the most the total dots crossed can be is 4x2=8 So this cannot work.

Therefore we can just consider the situation with one line with 3 dots, and the other lines must each have 2 to reach the total of 9.

If the 3 dot line is a diagonal, then it never intersects (beyond the grid as it must) another line which passes through 2 dots, so is impossible.

If the 3 dot line is a middle vertical or horizontal, then again beyond the grid it never intersects a line which goes through two other points.

If the 3 dot line is an end vertical or horizontal it is trickier (And I don't know how to add a diagram here). But from each end of the 3 dot line there are two possible 2 dot lines, and by attempting the 4 combinations, in none of them can you join the ends up in such a way it passes through the two final points.

A good explanation regarding different cases

Kazi Hafiz - 2 years, 7 months ago

@ Ben Symington - You are referring to them as "dots." That is not equivalent to "points." The OP mentioned "points."

Linda Slovik - 2 years, 7 months ago

Sorry, perhaps sloppy notation. I used 'dots' to describe the 9 points in the original grid.

Ben Symington - 2 years, 7 months ago

If a closed loop solution with 4 lines was possible, one line would intersect three points and the other three lines would intersect two points. Imagine that you had a closed loop solution of 4 lines. Start with the line that has three points on it. The second line going through 2 points would have a particular horizontal and vertical direction. For example, suppose the second line went down and to the right. Then the third line would have to go up and to the left. And the fourth line would again go down and to the right, the same as the second line. Therefore, the fourth line could not end where the first line began.

Kermit Rose - 2 years, 5 months ago

Garv Khurana
Oct 21, 2018

https://www.desmos.com/calculator/f3vqpwantn

As Alexandre Nolan notes, the line can be shifted so that the lines do not have any gridpoint endpoints.

The minimum number of lines required is 5 lines .

Endpoints cannot be gridpoints?

Peter Kron - 2 years, 7 months ago

Indeed the endpoints are wrong but this graph can be easily "massaged" into a graph with that property. https://www.desmos.com/calculator/m723znrwqe

Alexandre Nolin - 2 years, 7 months ago

Yes. Thank you, I should have been more clear on how to shift the graph to make a solution.

Garv Khurana - 2 years, 7 months ago

Vinod Kumar
Oct 22, 2018

4 is the best answer without a closed loop, 6 is the luxurious answer with a closed loop, therefore, the best most probable answer is 5.

Answer=5

I saw a closed loop with 4 lines. Am I mistaken? I don't know how to show my drawing here.

1 2 3

4 5 6

7 8 9

First line is 7 5 3

second line continues from 3: 3 6 9

Third line is 8 4

Fourth line is 1 2 3, ending in 3.

Oops. Not a closed loop.

Kermit Rose - 2 years, 5 months ago

Amrit Anand
Oct 26, 2018

Can it be generalized for NxN square ?

Michael McLaughlin
Oct 26, 2018

5 lines is possible. One 3, two 2s and two 1s. mention[5004150:Ben Symington]'s excellent answer proves that 4 lines is not.

Classic Dot Puzzle Inspiration

6 solutions

0 pending reports