How Many Straight Lines to Connect an N by M Array of Points in a Closed Loop?

[bob012345]

Given an $nxm$ array of evenly spaced points, what is the minimum number of straight lines to connect them in a closed loop? Here are the rules, start on one point and end on the same point. You cannot go through the same point more than once but can cross lines. For example, for a 2x2 array with four points, one can do it in three lines I believe. Thanks.

 

[anuttarasammyak]

I observe the way of 2 min(M,N) - 1. Smarter answers are welcome.

 

[Nugatory]

I observe the way of 2 min(M,N) - 1. Smarter answers are welcome.

3x3 can be done in 4 lines, if you’re thinking outside the box.

 

[bob012345]

3x3 can be done in 4 lines, if you’re thinking outside the box.

Are you starting at one of the array points or at a point elsewhere? Also, the lines must go through all the points.

 

[Nugatory]

Are you starting at one of the array points or at a point elsewhere?

Start at bottom right corner, up and left to top left corner, straight down 3 units (so “outside the box”), 45 degrees up and right to pick up the middle dots on the bottom and right sides continuing until level with top (again, outside the box), then left across the top row.

 

[bob012345]

Start at bottom right corner, up and left to top left corner, straight down 3 units (so “outside the box”), 45 degrees up and right to pick up the middle dots on the bottom and right sides continuing until level with top (again, outside the box), then left across the top row.

Thanks. Great thinking “outside the box”! I believe in general any 3xm, m>3 array can be done in six lines but I think the minimum for the 3 square is five lines when using your method of extended lines which is allowed under the above rules. While this solution does connect all the points in four lines, it does not finish at the same point it starts. To do so would retrace some points.

 

[bob012345]

I observe the way of 2 min(M,N) - 1. Smarter answers are welcome.

I believe that works for nxn squares but for nxm arrays where m>n it seems to be 2n.

 

[anuttarasammyak]

I believe that works for nxn squares but for nxm arrays where m>n it seems to be 2n.

But for m=2 n=1, one line. 2*min(1,2)-1=2-1=1.
PS
Correction to my answer : for m=n=1 zero line

 

[bob012345]

But for m=2 n=1, one line. 2*min(1,2)-1=2-1=1.
PS
Correction to my answer : for m=n=1 zero line

But still, not pointless…

 

[WWGD]

Maybe start with a complete graph and start weeding out all spanning trees? Is there a method for counting them? Wasn't there too a result on powers of the adjacency matrix of a graph? Just brainstorming.

 

[bob012345]

Here is my thought as to how it goes using the rules in post #1. I verified the squares up to 4x4 but haven’t verified it for 5x5 or higher.

Array	# points	Min # lines
2x2	4	3
2x3 or more	≥6	4
3x3	9	5
3x4 or more	≥12	6
4x4	16	7
4x5 or more	≥20	8
5x5	25	9
5x6 or more	≥30	10
6x6	36	11

ect.

 

[anuttarasammyak]

I don't figure out how to draw in these number of lines. Could you show me the figures ?

 

[bob012345]

View attachment 359919
View attachment 359920
View attachment 359921
I don't figure out how to draw in these number of lines. Could you show me the figures ?

For the 4x4 set the bottom left corner as (0,0) and the top right corner as (3,3). Then;

Line 1 starts at (0,0) and goes to (0,3)
Line 2 goes to (4,3)
Line 3 goes to (1,0)
Line 4 goes to (5,0)
Line 5 goes to (1,2)
Line 6 goes to (2,2)
Line 7 goes to (0,0)

I am still working on the 5x5 and am looking for a general strategy for squares.

 

[anuttarasammyak]

Thanks. I had misread you table. 4x4 as well as 4 X 200 has 7 lines ? Except 3x3 2min(n.m)-1 is applicable ?

 

[bob012345]

Thanks. I had misread you table. 4x4 as well as 4 X 200 has 7 lines ? Except 3x3 2min(n.m)-1 is applicable ?

If you stop on the same point that you start on according to the rules in post #1, the 4x4 has 7 lines but the4x5 or more has 8 lines. Here are my diagrams;

For a 4x5 or longer, I think this is the best one can do;

Here is my 3x3;

 

[bob012345]

A subtle point about the rules if you start at a point in the middle of a line, in the diagram below the first case is done in 4 lines but the second case is done in 5 lines because that is how many line segments you need to get back to the starting point.

 

[bob012345]

Thanks. I had misread you table. 4x4 as well as 4 X 200 has 7 lines ? Except 3x3 2min(n.m)-1 is applicable ?View attachment 360003

Where are you starting and where are you ending? They need to be at the same point. In this graph, I start at zero and end at zero. If you loop back to the starting point it will be 8 lines.

 

[anuttarasammyak]

Thanks. Now I see the rule.

 

[bob012345]

So far, I haven’t been able to show the 5x5 array can be done in 9 lines according to the rules set out in post #1. I leave it as an exercise for someone else to try.

 

[anuttarasammyak]

A 9 segment loop for 5X5 arrays extended from your 4X4 array solution with latice points added right upper side. Does this satisfy your rule ?

Adding lattice points in left downer side we can further extend the diagram for 6X6 arrays

We can further go to 7X7 case adding . In this way we can make 2n-1 segment loop for nXn lattice ponts.

 

[bob012345]

Nice try but unfortunately, lines 7 and 8 go through points already traversed which is one of the rules. It’s not clear to me that 5x5 and higher squares are possible in 2n-1 lines.

 

[anuttarasammyak]

Thanks for the remind. I amended 5 x 5 diagram.

 

[bob012345]

Thanks for the remind. I amended 5 x 5 diagram. View attachment 360158

Congratulations! You have restored my lapsing faith that this was possible.

 

[anuttarasammyak]

I observe the way of 2 min(M,N) - 1. Smarter answers are welcome.

Now I understand the condition and restate a conjecture that the least number of lines N for m x n dots for m,n>1 under the condition of post #1 is
N(m,n)=2\ min (m,n)-\delta_{mn}
or including m,n=1
N(m,n)=max (3,\ 2\ min(m,n)-\delta_{mn})

 

[bob012345]

Now I understand the condition and restate a conjecture that the least number of lines N for m x n dots for m,n>1 under the condition of post #1 is
N(m,n)=2\ min (m,n)-\delta_{mn}
or including m,n=1
N(m,n)=max (3,\ 2\ min(m,n)-\delta_{mn})

Is $\delta_{mn}$ just 1?

 

[anuttarasammyak]

Kronecker delta,i.e., 1 for m=n, 0 otherwise. .