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

  • B
  • Thread starter Thread starter bob012345
  • Start date Start date
AI Thread Summary
The discussion focuses on determining the minimum number of straight lines required to connect an n by m array of points in a closed loop, adhering to specific rules. Participants suggest various strategies and conjectures, including a formula of 2 min(M,N) - 1 for calculating the number of lines needed. Examples are provided, such as achieving a closed loop in four lines for a 3x3 array, but challenges arise in ensuring the endpoint matches the starting point without retracing. A consensus emerges around the conjecture that the minimum number of lines can be expressed as N(m,n) = 2 min(m,n) - δ(m,n), where δ is the Kronecker delta. The conversation highlights the complexity of the problem and the need for visual representations to clarify solutions.
bob012345
Gold Member
Messages
2,287
Reaction score
1,010
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.
 
Mathematics news on Phys.org
I observe the way of 2 min(M,N) - 1. Smarter answers are welcome.
 
anuttarasammyak said:
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.
 
  • Like
Likes bob012345 and anuttarasammyak
Nugatory said:
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.
 
Last edited:
bob012345 said:
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.
 
Nugatory said:
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.
 
anuttarasammyak said:
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.
 
bob012345 said:
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
 
anuttarasammyak said:
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…
 
  • #10
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.
 
  • #11
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# pointsMin # lines
2x243
2x3 or more≥64
3x395
3x4 or more≥126
4x4167
4x5 or more≥208
5x5259
5x6 or more≥3010
6x63611

ect.
 
  • #12
1744758351536.png

1744758371602.png

1744758387233.png

I don't figure out how to draw in these number of lines. Could you show me the figures ?
 
  • #13
anuttarasammyak said:
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.
 
Last edited:
  • Like
Likes anuttarasammyak
  • #14
Thanks. I had misread you table. 4x4 as well as 4 X 200 has 7 lines ? Except 3x3 2min(n.m)-1 is applicable ?
1744921302818.png
 
Last edited:
  • #15
anuttarasammyak said:
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;

IMG_3230.jpeg

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

IMG_3231.jpeg

Here is my 3x3;

IMG_3228.jpeg
 
  • #16
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.

IMG_3232.jpeg
 
  • #17
anuttarasammyak said:
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.
 
  • #18
Thanks. Now I see the rule.
1744932435138.png
 
Last edited:
  • #19
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.
 
  • #20
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 ?

1745070652525.png

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

We can further go to 7X7 case adding . In this way we can make 2n-1 segment loop for nXn lattice ponts.
 
Last edited:
  • #21
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.
 
Last edited:
  • Like
Likes anuttarasammyak
  • #22
Thanks for the remind. I amended 5 x 5 diagram.
1745211866001.png
 
Last edited:
  • Like
Likes Tom.G and bob012345
  • #23
anuttarasammyak said:
Thanks for the remind. I amended 5 x 5 diagram. View attachment 360158
Congratulations! You have restored my lapsing faith that this was possible.
 
  • #24
anuttarasammyak said:
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})
 
  • #25
anuttarasammyak said:
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?
 
  • #26
Kronecker delta,i.e., 1 for m=n, 0 otherwise. .
 
Back
Top