20090505, 16:15  #1 
Dec 2005
304_{8} Posts 
Lines in a Square
Consider an n x n chessboard.
What is the size of the smallest collection of lines such that every square of the chessboard is intersected by at least one line ? PS: I do not pretend to have a solution, but as this is more puzzle than serious math I decided to put it here. 
20090505, 16:26  #2  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6685_{10} Posts 
Quote:
Last fiddled with by retina on 20090505 at 16:27 

20090505, 16:27  #3 
Account Deleted
"Tim Sorbera"
Aug 2006
San Antonio, TX USA
11×389 Posts 
Assuming straight lines only.
I can't find a way to do it with any less than n lines, no matter the number of squares, and it can always be done with n lines by putting one horizontal line through each row, so my answer is: n. It takes a minimum of n lines to put a line through every square of a n x n "chessboard". 
20090505, 16:34  #4 
"Lucan"
Dec 2006
England
2×3×13×83 Posts 
I can't improve on n

20090505, 16:35  #5  
Jun 2003
491_{16} Posts 
Quote:
Last fiddled with by Mr. P1 on 20090505 at 16:36 

20090505, 16:50  #6 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
6685_{10} Posts 
If the n is large (or the squares are large, or both) and the universe is closed, then only one line is needed.

20090505, 16:53  #7 
Nov 2008
2·3^{3}·43 Posts 
I am pretty sure the answer is n (although it is possible to miss by one square on smaller boards, not sure about larger ones).

20090505, 16:57  #8  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
1A1D_{16} Posts 
Quote:


20090505, 17:01  #9 
Jun 2003
2^{2}×3^{2}×151 Posts 
not true for 3x3

20090505, 18:20  #10 
"Lucan"
Dec 2006
England
2×3×13×83 Posts 

20090505, 18:29  #11 
"Jacob"
Sep 2006
Brussels, Belgium
3×5×127 Posts 
for n even or n=1 one needs n lines, for n uneven one needs n1 lines
I have no mathematical proof, just a bit of fidling around with a vector drawing program. Jacob Last fiddled with by S485122 on 20090505 at 18:31 Reason: stated reasoning (?) behind assertion. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
decoding results lines  dbaugh  PrimeNet  3  20151217 07:22 
Multiply By Drawing Lines  petrw1  Math  2  20140520 06:13 
Putdown lines  davieddy  Soap Box  3  20111214 20:53 
need help with ecm lines  jasong  Information & Answers  3  20071116 07:32 
Strange result lines  dave_0273  Data  4  20040228 02:40 