How many straight lines do you need to cross every square of a 3x3 board?
geometry/grid.lines New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
How many straight lines do you need to cross every square of a 3x3 board? (Crossing means that a square becomes 2 different shapes; tangent is not enough.) Prove that it cannot be done with less. Same question for a 4x4 board, and for an N x N board: can you find a constant k smaller than 1 such that kN lines will be enough? -- Shay Galon <sgalon@iil.intel.com>
Show solution
[ Editor: 3x3 board. ]
2 lines. The figure below should illustrate the idea.
\
+----+----+----+
| \| | |
| | | |
| | | |/
| |\ | /|
+----+----+----+
| | \ |/ |
| | /| |
| |/ | |
| /| \ | |
+----+----+----+
|/ | \| |
/| | | |
| | | |
| | |\ |
+----+----+----+
\
Because of the limitations of ASCII graphics, the lines are not
straight in the picture, but they can be made so in "real life". The
right-and-up line starts 3/4 up the left edge of the bottom left square
and has a slope of 1/2. The other line starts 3/4 along the top edge
of the top-left square and has a slope of -2.
[ Editor: proof that fewer will not do. ]
No line can cross all four squares in a 2x2 square.
[ Editor: 4x4 board. ]
3 lines. Two lines at slope 1/2 starting at 1/4 up the bottom
left and at 3/4 up the one above that plus a line with slope -4/3
starting at the middle of the top edge of the top-left square.
Since no line can cross all squares in a 2x2 square, a single line
will miss (at least) one of the 2x2 squares that form the 4x4 square.
And at least two more lines are required to cross all squares in that.
Hence, 3 lines is minimum.
[ Editor: N x N board. ]
The idea used for the 3x3 and 4x4 case can be used for
arbitrarily large squares: Draw slope 1/2 lines starting at 2.25
squares from the top down the left hand side spaced 1.5 squares apart.
Continue until the last line crosses the right edge 2.25 squares above
the bottom. This is a total of 2/3*(N+N/2-3) = N-2 lines. These lines
will cross all squares except for two squares in the top left corner
and two squares in the bottom right corner. These can be covered by a
single line with slope close to -1. Hence, we can always do with N-1
lines.
I don't think you can get better than N-1 lines, which means that k=1,
as any k<1 will have an upper limit of N=1/(1-k).
-- Torben Mogensen <torbenm@diku.dk>
----
[ Editor: Glenn Rhoads had found 3-line arrangements for the 4x4 that
leave one square uncrossed and doubted that all 16 could be crossed;
Fred Curtis replied with a counter-example. ]
>-----------------
>| 3 | 2 | 2 | 1 |
>----------------- This combination can be obtained with lines
>| 3 | 2 | 1 | 1 | running from
>----------------- 1: (2.5, 0 ) to (4, 4 )
>| 2 | 2 | 1 | 3 | 2: (0 , 0 ) to (2, 3.5)
>----------------- 3: (0 , 3.5) to (4, 0.5)
>| 2 | 1 | 1 | 3 |
>-----------------
-- Fred Curtis <fred@zip.com.au>
Nice solution. This is minimal since 2 is impossible.
Note: Your starting point for line 1 isn't correct. Two possible
starting points are (2.5, 1.5) and (1.75,0).
-- Glenn Rhoads <rhoads@necturus.rutgers.edu>
In general, the same pattern can be used to cover an NxN board in no
more than (N-1) lines. I can't prove that this is the minimum, and I
don't know any bounds for an MxN case.
-- Fred Curtis <fred@zip.com.au>