Math Forum / Mathematics / Recreational Math / June 2009

tk_ wrote :

Hi,

It is not a question of "I have tried all possibilities" or
"I just haven't succeeded", but of what IS a valid proof.

However I don't agree with bobmck. He wrote :

No. etc. It seems he completely discarded the X's, and even then
not counting properly the edges.

Apart with the problem of wording (your "attempts", and I can't
see a way of considering your figure as a set of "cubes" either),
the problem you state seems to be the one usually described as
"drawing a picture in one stroke".

A stroke being a line drawn without lifting the pen up,
and it is forbidden to draw a segment twice.
Defined as "continuous path" by Ben.

The result, which is _logically_ prooved (by Ben Saucer for
instance) is that it is impossible to draw a figure in one
stroke if it has more than two vertices with odd number of lines
at them.

So your figure can't be drawn in one stroke, as it has 12 odd
vertices (not just the 8 outer, but also the 4 inner corners
which have 7 lines. Only the midpoints of the X's have even number
of lines)

Now an additional result is that there are in any drawing an
even number of odd vertices (or none, but 0 is an even number)
By counting the total number of edges, it is half times the
sum of the numbers of lines at each point, as each line is counted
twice, one for each end. So this sum must be an even number,
hence an even number of odd numbers in the sum.

And then we can draw any drawing in half that number of strokes.
As we can draw a single stroke between any two odd vertices,
leaving n-2 odd vertices, the number of lines at these vertices
being reduced by an even number (every entering at that point
is followed by an exit).
Then a new stroke can be drawn between two of these remaining odd
vertices etc...

That is here you have 12 odd vertices, hence you need 12/2 = 6
strokes to draw your figure.

Hence impossible to draw it in 5 strokes (or 5 "attempts")
Effectively drawing it in 6 strokes or more is quite easy.

Regards.

On 6/29/09 tk wrote:

******************************

I interpreted (incorrectly) your message of Jun 29, 2009, 3:07 AM "Please ignore the green line in the picture..."
as meaning that there was no line from node B to node D.

Putting that back in, philippe is correct and a 5-stroke solution is impossible. (My not mentioning the "X's" as nodes was not an oversight: I simply sought a convenient way to describe the graph in a textual manner, with an understanding that X type nodes are irrelevant in these type problems...unless they include a prohibition of line-crossing.)