Associated Topics || Dr. Math Home || Search Dr. Math

### Line Drawn through Lines Puzzle

```
Date: 10/18/2001 at 20:40:26
From: lauren
Subject: A puzzle that seems impossible to many people

Here is the riddle/puzzle:

Draw a box that has two rectangles on top, connecting at the right
side of one and the left side of the other. Then draw three squares
directly under the rectangles.
___________
|     |     |
|_____|_____|
|   |   |   |
|___|___|___|

Now draw a line that goes through each line without going through a
line twice.

```

```
Date: 10/22/2001 at 09:18:59
From: Doctor Code
Subject: Re: A puzzle that seems impossible to many people

Hi Lauren,

___________
|     |     |
|_____|_____|
|   |   |   |
|___|___|___|

There are five rectangles. Notice that each of the the top left, top
right, and bottom center rectangles has five lines on its border.

Another way to think about it is that each rectangle is a room and the
lines between them are doors. Three of the rooms have five doors, and
two of them have four doors. If you pass through a room, you must
enter through one door and leave through another door. So the two
rooms with four doors can be entered twice and exited twice. But the
rooms with 5 doors could have two possibilities:

a) entered 3 times, exited 2 times

b) entered 2 times, exited 3 times

Notice that if it's case (a), the order of exits and entrances is:

enter, exit, enter, exit, enter.

Since you can't exit after the last enter (there are no more doors
left), the line must finish inside that room.

Similarly, for case (b), the order is:

exit, enter, exit, enter, exit.

Therefore the line must start inside that room. Each room that has
five doors must either be the starting point of the line, or the
ending point.

The problem is that we have 3 rooms that have 5 doors. Since a line
only has one start and one end, we can't start in two different rooms
or end in two different rooms. Therefore there is no solution.

This puzzle is a variation on the Bridges of Konigsberg, a problem
that inspired the great Swiss mathematician Leonard Euler to create
graph theory, which led to the development of topology. See

The Beginnings of Topology... - Isaac Reed, The Math Forum
http://mathforum.org/isaac/problems/bridges1.html

- Doctor Code, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Discrete Mathematics
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search