Brain Teaser that is impossibly solvable

[kinnabird5]

My teacher gave this problem to my class, for anyone who was failing, only one person was able to solve it correctly. It has been driving me crazy for almost two years. a lot of peolpe have said that it is impossible, but I assure you it is not. It was solved by a 17yr old student. here is the best I can explain it, without drawing it actually.

Imagine a rectangle that has a split line horizontaly through the middle. On the top half of the rectangle is a line that is vertical, in the center, connecting the first and second horizontal lines. Now on the bottom half of the rectangle, there are two vertical lines, connecting the second and third horizontal lines, one vertical line on either side of the top vertical. So in all, it should appear to be a large rectangle with two small rectanles on top of three smaller rectangles. Simply five in one.

Now you must draw a line through each line, or sides, of all reactangles. There are 16 sides in all. The line cannot break, fork, or overlap. The line cannot pass through the same side twice.

Please email me if this confusses you and i can email you the picture back. Thank you for your help!

 

[franznietzsche]

Originally posted by kinnabird5
My teacher gave this problem to my class, for anyone who was failing, only one person was able to solve it correctly. It has been driving me crazy for almost two years. a lot of peolpe have said that it is impossible, but I assure you it is not. It was solved by a 17yr old student. here is the best I can explain it, without drawing it actually.

Imagine a rectangle that has a split line horizontaly through the middle. On the top half of the rectangle is a line that is vertical, in the center, connecting the first and second horizontal lines. Now on the bottom half of the rectangle, there are two vertical lines, connecting the second and third horizontal lines, one vertical line on either side of the top vertical. So in all, it should appear to be a large rectangle with two small rectanles on top of three smaller rectangles. Simply five in one.

Now you must draw a line through each line, or sides, of all reactangles. There are 16 sides in all. The line cannot break, fork, or overlap. The line cannot pass through the same side twice.

Please email me if this confusses you and i can email you the picture back. Thank you for your help!

Um, as you describe it, it is mathematically impossible. Now if when you say you must draw a line through each side, you really mean draw acontinuous curve then it is possible. You really need to be more clear on definitions with these kinds of things, ambiguities like that will make it impossible. Now I'm off to solve it on the assumption you meant draw a continuous curve.

 

[kinnabird5]

im sorry but I do not understand the meaning of an acontinuous curve, or how an acontinuous curve would make it possible if a line makes it impossible.

 

[kinnabird5]

please please share!

 

[NateTG]

It's not possible. The top center rectangle, and the bottom rectangles all have an odd number of sides (5).

Now, if a line goes into a rectangle, then it must come out, so unless the path starts or ends in a rectangle, only an even number of sides can be crossed by the line.

Now, since the path only has two ends, it cannot start or end in all three of those rectangles. That means that you cannot make a squiggle go through all of the segments.

...unless you think outside of the box. If you punch holes in the paper inside some of the squares and then put the squiggle through, for example, you can do it.

 

[cookiemonster]

Edit: noticed he missed a side. oops.

cookiemonster

 

[kinnabird5]

you cannot punch holes in the paper, it is able to be done on a black board

 

[cookiemonster]

Still missing a side. And you have two overlaps.

What do corners count as?

cookiemonster

 

[kinnabird5]

missed one in the middle

 

[aychamo]

I was given the same assignment in 6th grade. It has to pass through all the barriers, and it can not overlap. I've never been able to solve it.

 

[Palpatine]

It looks like NateTG was right. Maybe the diagram should look like this.

 

[cookiemonster]

Except that now there are only 15 sides instead of the specified 16.

cookiemonster

 

[franznietzsche]

Originally posted by kinnabird5
im sorry but I do not understand the meaning of an acontinuous curve, or how an acontinuous curve would make it possible if a line makes it impossible.

twas a typo. I meant a continuous curve. A line is by definition linear, its direction cannot change.

Originally posted by Palpatine
It looks like NateTG was right. Maybe the diagram should look like this.

Just stop posting till it actually works. Everyone of those has missed a side. Not trying to be nasty, its just a lot of links to click.

Been trying for a while and haven't been able to solve it yet. I'll prolly have better luck proving whether or not its possible. NateTG may be right in principle, but his post lacks in rigor...off to try and construct rigorous proff in either direction.

 

[aychamo]

Guys:

This is exactly how the puzzle should look, and the # of sides are numbered, 16 total. I am pretty sure this is unsolvable.

http://www.imageshack.us/img1/3949/diagram.jpg

 

[Palpatine]

For a Euler path to exist (each edge traversed exactly once) two vertices need to have odd degree and the rest must have even degree.

The graph has vertices with degrees, 5,5,5,9,4,4

So it looks like a no-go.

The last drawing i posted had 5,4,4,4,4,9. So that at least checks out.

 

[matt grime]

Originally posted by franznietzsche
NateTG may be right in principle, but his post lacks in rigor...off to try and construct rigorous proff in either direction.

Assuming NateG got the right picture, and I've no reason to doubt that, then his proof is perfectly rigorous (and assuming one can't pass through corners claiming to intersect both sides simultaneously).

 

[Chen]

http://mathforum.org/isaac/problems/bridges1.html

 

[franznietzsche]

WEll I've been at it fairly consistently, and no luck, there is always one side i cannot get. I think arachymo and palpatine are right here, it is unsolvable.

matt: palaptine's post was more what i was looking for when i said rigor, logically its right, but without the basis on things already proven to be true i was concerned that there might be a small loophole or something. but yes it seems he was right.

 

[NateTG]

Originally posted by franznietzsche
matt: palaptine's post was more what i was looking for when i said rigor, logically its right, but without the basis on things already proven to be true i was concerned that there might be a small loophole or something. but yes it seems he was right.

No offense to Palpatine, but I should point out that my argument was more rigorous than Palpatine's. (For example, he doesn't show how to construct the graph he's making Euler paths on.) I elected not to bring graph theory or the results of graph theory into it because, among other things, I expect that many of the people here have not been exposed to it. The theorem that

There are, by the bye, many different 'out of the box' solutions. On a blackboard you can wipe out one of the lines after crossing it (use your left hand if you can't put the chalk down), and the gap will allow you finish the rest of the lines.

 

[killerinstinct]

Very interesting problem...

 

[Gokul43201]

This is the same (type of) problem as the Bridges of Konigsberg or watchamacallit... and I believe nateTG has the correct solution. The only "lack" of rigor may be a failure to eliminate points of intersection as allowed points. Palpatine is merely quoting a graph theory result that is based on nateTG's argument.

 

[Icarus]

While Euler analysis is correct as far as it goes, the problem is still solvable. Everyone so far has made an assumption about the meaning of the phrasing of the problem which is not required. If a more liberal interpretation is made, the Eulerian difficulty goes away and the problem admits of an easy solution.

(I can't claim to have found the solution myself: this problem has been around for a long time, and so have I! )

By the way: Euclid used "line" in exactly the same way that kinnabird5 did. It is only recently that people started demanding that "line" by itself should mean what used to be called a "straight line, extended indefinitely in both directions".

 

[fourier jr]

ohhhh yeahhh... I vaguely remember doing something like that in a discrete math course using graph theory. I hadn't heard about it until I took the course when we learned all about graphs & how easy it is to solve that problem using them. I can see how it would be hard for a high school student to figure it out though. I'd have to look it up in my textbook for the details. There's something about the vertices of the graph being the "rooms" and the edges being the "path through the doorways."

 

[Gokul43201]

While Euler analysis is correct as far as it goes, the problem is still solvable. Everyone so far has made an assumption about the meaning of the phrasing of the problem which is not required. If a more liberal interpretation is made, the Eulerian difficulty goes away and the problem admits of an easy solution.

(I can't claim to have found the solution myself: this problem has been around for a long time, and so have I! )

By the way: Euclid used "line" in exactly the same way that kinnabird5 did. It is only recently that people started demanding that "line" by itself should mean what used to be called a "straight line, extended indefinitely in both directions".

Are you suggesting that it is possible to traverse the path satifying the required conditions ? You also claim that everyone has made some wrong assumption - can you tell us what this is ? The only assumption I can imagine we are making (one that renders the problem insoluble) is that the figure is on a plane and not on a torus, or some such thing. I believe this requirement was clearly implied in the original post. In your final sentence, do you mean to say that the problem can be solved if we used a "straight line" instead of a continuous curve ?

 

[Icarus]

First of all, the comment about the meaning of the word "line" was in response to franznietzsche's complaint in post #2 that kinnabird5 should have said "continuous curve". While kinnabird5's usage of "line" to mean the same thing is somewhat out-of-date, this usage is still found occasionally (after all, Euclid is still in print)!

Secondly, the figure in question is exactly the one aychamo linked to, and it can be solved in the plane.

The particular phrase which has been interpreted more stringently than the puzzler is intending is part of

"The curve must pass through each of the 16 edges of the graph exactly once."

(I've cleaned up the wording to avoid other misunderstandings - but the misinterpreted part is still here.)

I will tell no more than this for now, but if no one figures it out by tomorrow, I'll be more explicit.

**Warning** You may well feel like the solution is a cheat - but that is to be expected when common expectations are violated.

 

[Gokul43201]

I hope your curve has only 2 ends... Waiting for your solution.

 

[baffledMatt]

"The curve must pass through each of the 16 edges of the graph exactly once."

(I've cleaned up the wording to avoid other misunderstandings - but the misinterpreted part is still here.)

Hmm, is it just me or should we ask the obvious question:

define 'pass through'.

?

Matt

EDIT: Icarus got there seconds before me... grrr

 

[Icarus]

I've removed my posting of the solution so that anyone who wants to follow up on baffledMatt's excellent insight will have a chance to do so!

 

[Gokul43201]

Clearly, "bouncing" off an edge is cheating. So I can't see more than one correct interpretation of "pass through". Unless your using extra dimensions, which is also cheating.

 

[Icarus]

Not bouncing or using extra dimensions. Merely a matter of direction.