The goal is to trace a line with your pencil across each edge on the box only once without crossing the vertices or picking your pencil up.

Note that this "box" contains 16 unique "edges".

Prove why this is an impossible task regardless of where you first place your pencil.

Maybe I should learn to read problems first.  I thought it said to trace ALONG the edges.  And then I didn't pay attention to the "without crossing vertices" part.  My bad.  Eric O. has the correct node-segment representation.  Pay no attention me =)

--------------------------------------------------------------
I also represented this in terms of nodes and segments, but I think I did it differently from Erik O.

I called each corner of a box a node. So there are 4 nodes along the top horizontal edge, 5 nodes along the center horizontal, and 3 on the bottom horizontal edge. Then the segments were the unique edges of the boxes (16 in all as mentioned in the problem statement).

The four nodes that represent the four corners of the whole grid have two segments attached to each of them, so they are both even nodes. The other 8 nodes all have 3 segments attached to them, so they are all odd nodes.

Euler has already proven that if you have more than two odd nodes then it is impossible to find a path.  8>2 so it is indeed impossible.

Edited on April 6, 2005, 6:23 pm

Posted by nikki on 2005-04-06 16:19:20