Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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.

Please help me to solve this riddle!


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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/