Lines in a Square

Kees · 2009-05-05, 16:15

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.

retina · 2009-05-05, 16:26

Quote:

Originally Posted by Kees

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.

One line only is needed. The puzzle does not specify that the lines have to be straight so I make it a single spiral with pitch of < one square width.

TimSorbet · 2009-05-05, 16:27

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".

davieddy · 2009-05-05, 16:34

I can't improve on n

Mr. P-1 · 2009-05-05, 16:35

Quote:

Originally Posted by retina

One line only is needed. The puzzle does not specify that the lines have to be straight so I make it a single spiral with pitch of < one square width.

In mathematics, lines are straight by definition. A spiral is a curve.

retina · 2009-05-05, 16:50

If the n is large (or the squares are large, or both) and the universe is closed, then only one line is needed.

10metreh · 2009-05-05, 16:53

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).

retina · 2009-05-05, 16:57

Quote:

Originally Posted by Mr. P-1

In mathematics, lines are straight by definition. A spiral is a curve.

Okay, no argument from me there, but maybe the OP meant this type of line. :p

axn · 2009-05-05, 17:01

not true for 3x3

davieddy · 2009-05-05, 18:20

Quote:

Originally Posted by axn

not true for 3x3

Neat.
Or on second thoughts a bit messy

S485122 · 2009-05-05, 18:29

for n even or n=1 one needs n lines, for n uneven one needs n-1 lines

I have no mathematical proof, just a bit of fidling around with a vector drawing program.

Jacob

2009-05-05, 16:15	#1
Kees Dec 2005 304₈ 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.

2009-05-05, 17:01	#9
axn Jun 2003 2²×3²×151 Posts	not true for 3x3 Attached Thumbnails

2009-05-05, 18:29	#11
S485122 "Jacob" Sep 2006 Brussels, Belgium 3×5×127 Posts	for n even or n=1 one needs n lines, for n uneven one needs n-1 lines I have no mathematical proof, just a bit of fidling around with a vector drawing program. Jacob Last fiddled with by S485122 on 2009-05-05 at 18:31 Reason: stated reasoning (?) behind assertion.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
decoding results lines	dbaugh	PrimeNet	3	2015-12-17 07:22
Multiply By Drawing Lines	petrw1	Math	2	2014-05-20 06:13
Put-down lines	davieddy	Soap Box	3	2011-12-14 20:53
need help with ecm lines	jasong	Information & Answers	3	2007-11-16 07:32
Strange result lines	dave_0273	Data	4	2004-02-28 02:40

2009-05-05, 16:27	#3
TimSorbet 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".

2009-05-05, 16:34	#4
davieddy "Lucan" Dec 2006 England 2×3×13×83 Posts	I can't improve on n

2009-05-05, 16:50	#6
retina Undefined "The unspeakable one" Jun 2006 My evil lair 6685₁₀ Posts	If the n is large (or the squares are large, or both) and the universe is closed, then only one line is needed.

2009-05-05, 16:53	#7
10metreh Nov 2008 2·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).