Brain Teaser that is impossibly solvable

[kinnabird5]

My teacher gave this problem to my class, for any one who was failing, only one person was able to solve it correctly. It has been driving me crazy for almost two years. Alot 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, with out 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 verticle, in the center, connecting the first and second horizontal lines. Now on the bottom half of the rectangle, there are two verticle lines, connecting the second and third horizontal lines, one vertical line on either side of the top verticle. 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 any one who was failing, only one person was able to solve it correctly. It has been driving me crazy for almost two years. Alot 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, with out 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 verticle, in the center, connecting the first and second horizontal lines. Now on the bottom half of the rectangle, there are two verticle lines, connecting the second and third horizontal lines, one vertical line on either side of the top verticle. 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! :tongue2:)

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! :tongue2:)

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. :rolleyes:

[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.

[Rashad]

Palpatine, you are showing that this is a traceable network, I don't think that is what we're going for here. Is the problem to show that you can 'go over' (trace) the network itself and cover every line without overlapping, like what Palpatine is doing (...I think)? Ie draw the rectangle and its accompanying segments without lifting up your writing utensil or going over the same segment twice. Or is it to prove whether or not a continuous curve (a rather insane curve) can pass through all of the small segments only once? That's what I'm trying to do...and if you say that it is impossible, that claim is insatiable without a proof.


~Rashad

[NateTG]

Palpatine, you are showing that this is a traceable network, I don't think that is what we're going for here. Is the problem to show that you can 'go over' (trace) the network itself and cover every line without overlapping, like what Palpatine is doing (...I think)? Ie draw the rectangle and its accompanying segments without lifting up your writing utensil or going over the same segment twice. Or is it to prove whether or not a continuous curve (a rather insane curve) can pass through all of the small segments only once? That's what I'm trying to do...and if you say that it is impossible, that claim is insatiable without a proof.

That's also impossible. There are more than two intersections where an odd number of segments meet. A similar argument as before applies; consider that, unless the path starts or ends at a particular intersection, it must go in to the intersection as many times as it comes out, so the path must start or end at every intersection that connects an odd number of segments.

[Gokul43201]

Didn't Icarus promise us a solution ?

[dave8684]

Quite easy if you do think outside the box:

there is a logic problem that goes like this: draw a square, divide in half horizontally, divide the top half in to two equal parts with a vertical line, then divide the bottom portion into 3 equal portions with 2 vertical lines.

the task is to draw a continues line through all lines without ever crossing your own line or crossing any line two times. The problem is presented on this sight. Now according to conventional logic this problem seems impossible because line always needs an entry and exit but there are an odd number of spaces and an odd number of segments in three of them.

The real difficulty here is that an assumption is made, creating an unwritten rule. This unwritten rule, this self imposed limitation forces the problem solver to focus on the problem, NOT THE SOLUTION. By recognizing the problem (NOT FOCUSING ON IT) - a long line cannot enter and leave each space enough times without making an illegal crossing- we can find the solution.

The solution is this: use a very wide marker and cross the entire box in one diagonal line. All stated conditions are met, the problem is circumvented and the solution is found. Clearly this is not the intended answer, but it is indisputable.

[check]

And Dave8684's answer is verbatim from http://www.puzzles.com/PuzzleHelp/PuzzleHelpItems25_36.htm :uhh:

[Matter]

would a spirel work!?

[koroljov]

I found it. First try worked. (See attachment).

edit:
You're right, I missed one.

[Zorodius]

I found it. First try worked. (See attachment).
Missed a spot, there. You did not cross the segment directly to the left of the center of the figure.

You will always "miss a spot", because there exist no solutions to this problem, aside from the "thinking outside the box" answers like poking holes in the paper and so on.

[Galileo]

There are five rooms. The wall between two given rooms must be crossed by the line.
So you have to get from one room to the next.
Give every room a vertex and connect the vertices when there is a wall between them.
This will give you the following graph (see graph.bmp).

Then the upper two rooms (vertices) must have two more lines going out, and so do the two rooms and the bottom left and bottom right.
The room in the bottom center has one more line going out.
The graph will look graph1.bmp.

Since the line must be drawn without removing your pencil from the paper, the entire graph must be connected.
However you connect the loose ends, there will be 3 odd vertices, so there is no solution to the problem.

[CrankFan]

I've heard of a similar problem to this one, which had no solution and was supposedly given to grade school students for extra credit. As if that isn't enough of a coincidence just like this version of the story it was rumored to have been solved by one student, so you "know" a solution has to exist!

I suspect that stories of this kind are intentional hoaxes which persist as a kind of elementary math folklore.

[Ethereal]

I've heard of a similar problem to this one, which had no solution and was supposedly given to grade school students for extra credit. As if that isn't enough of a coincidence just like this version of the story it was rumored to have been solved by one student, so you "know" a solution has to exist!

I suspect that stories of this kind are intentional hoaxes which persist as a kind of elementary math folklore.
That's a good one! I bet the same thing happened with all those famous conjectures which were supposedly proven by mathematicians in the past, but whose proofs were lost. Fermat comes to mind...

[Matter]

How do I post an attachment!!!!??? This is driving me maaaaad Never mind I got it!

[Galileo]

Dude, you missed a spot.

It can't be done!

[Gokul43201]

It is not possible to do this : this is an old problem known as the Bridges of Konigsberg, and was solved by Euler, nearly 300 years ago.

PROOF : There are 3 rooms with an odd number of walls. If you start inside a room with an odd number of walls, and walk through each wall once (you're a ghost), you will end up outside the room. Conversely, if you started outside, then after walking through the last wall, you will end up inside - and can't leave because you've walked through all the walls. This means that one end of your journey must always be inside an odd walled room - either the beginning or the end. Unfortunately, a journey (or a line or curve or whatever you choose to call it) has only 2 ends. But the house has 3 odd-walled rooms, and you can't have a journey with 3 ends, so it's not possible.

THE END

...unless you cheat, by traveling through vertices, (or drawing the figure on a torus), or using a really thick marker, or some other such childish ploy.

[Matter]

Dude, you missed a spot.

It can't be done!
There are 5 rectangels with 4 walls each! 6 of these walls are shared or common walls . I went through each wall of each rectangel once ! so where did I miss one! :confused:

[Matter]

There are 5 rectangels with 4 walls each! 6 of these walls are shared or common walls . I went through each wall of each rectangel once ! so where did I miss one! :confused:
don't answer that I see it! Dang! I hate not having a solution!#"!

[Galileo]

:smile:bladibladibladibla

EDIT: Whoops. I`ve been screwing with that picture so long you posted your message in the meantime. :rofl:

[discomb]

aaaaahhhhhhhhh.

after reading all that, I feel soooooo much better.

before, i was like this:

:surprised :rofl: :grumpy: :cry: :confused: :bugeye: :frown:

and now, i am like this:

:smile: :approve: :rofl:

cheers everybody, and particularly to Mr. Euler and his chums

[Myclicheisbetter]

If you approach the puzzle in three dimensions you can easily do it, in fact it only takes about 5 seconds, and the mind set of a jackass. I can attach it if you want, but I'm sure you understand what I'm getting at.

[Gokul43201]

Yes, the problem is insoluble only on the plane or the homotopy class of a sphere.

It has a solution, for instance, on the torus.

[kerryfan]

I was given this problem as a brain teaser and am wondering if I've found the solution (see attachment) or if there is a solution besides cheating, use a marker, etc. This has been driving me nuts, please help if you know the answer.
Thanks

[cogito²]

I was given this problem as a brain teaser and am wondering if I've found the solution (see attachment) or if there is a solution besides cheating, use a marker, etc. This has been driving me nuts, please help if you know the answer.
Thanks
If going through a corner counts as going through all three then yes this is a solution. If that is not allowed then there is no solution as has been shown like 10 times throughout this thread. It depends on what conditions you put on the problem. So you decide: is that a solution?

[BTruesdell07]

make it really small then draw through it with a thick marker covering the entire puzzle. You go through every line only once.

[Sisco424]

Hi,
I've been lookin for the answer to this on the internet because one of my teachers was offering a small cash reward to whoever could solve it and i now know that it is possible because my friend printed a picture of it completed off the net but i just got a quick glance and he took it away thinkin that we was going to steal his answer, i just want to figure it out cause its driving me crazy so if someone finds the answer tell me. It is definetly possible

[BigStelly]

This has been seen to be impossible for several centuries ever since Euhler proved it was. This comes from the bridges of Konisberg and for centuries nobody figured out a way to cross all the bridges once and only once without crossing back over their path, Because its impossible.

[Data]

Sisco424, you will impress your teacher more if you take a book on Graph Theory out of the library, learn about the question, and prove that it is impossible in front of your class :)

If you want a bunch of "completed solutions" then just look through this thread: All of them either cheat or miss a side.

There is a very good reason for this.

[animejunkie1100]

I have worked on it for like a year almost and still can't find the answer please help!

[d_leet]

I have worked on it for like a year almost and still can't find the answer please help!

This is because, as many people have mentioned in this thread, that it is impossible and has been proven impossible.

[-Job-]

You can convert the problem to the attached graph.
The problem can be solved only if you can find a path that goes through every edge exactly once. Such a path is called a Euler path, or Euler tour. Euler showed that a graph can only contain such a path if either all or all but two nodes have an even degree. The graph corresponding to this problem has 4 nodes of odd degree and two of even degree, so it can't contain a Euler tour.

[ValenceE]

Hello to all !,

Guys, if we accept the fact that any corner is the junction of as many sides as are connected, then there’s a way to solve this puzzle. Actually there’s probably more than one way, but here’s what one of them looks like.

It also has a neat shape to it…


VE

edited to replace .jpg file by .bmp

[nerd_police]

can we enter a line, then trace along it for a while without having "crossed it twice"

[Tclack]

___________
|_____|_____|
|__|_____|__|

This is basically what the image looks like, and yes it is impossible. If you look, you'll see any rectangle has either 4 or 5 sides (even or odd). Now if you were to start inside an odd one, you eventually would have to end up on the outside and if there were two odd box's it would be fine but there are three... it's hard to explain, but it's impossible. I actually devised a way to find out whether or not a puzzle like this is impossible or possible. First add up all the rectangles with even "doorways" and odd ones. Cancel every even with every even, and every odd with every odd. I found that's it's not possible if you end up with an odd. It's possible: if they all cancel out, if you have a remaining even. However there is a special case if you end up with 1 even and 1 odd; If you have an odd amount of odds (3, 5, 7...) then it's not possible, But it is for 1.

As I read over that, it's a little difficult to understand, read it carefully.

So if we look at the original we see that we have 3 odds and 2 evens:
o oo ee . The paired ones cancel out so we have an o remaining. If you look back at my list, a remaining odd is...Not Possible, hence the puzzle is unsolvable.

Note: I haven't showed this mathematically, I made puzzle types a bunch of times and tried them, the ones that weren't possible and the ones that were possible had the same properties, that's what this is based upon. You can try it yourself.

[Gib Z]

Yea i was thinking that too, can the line trace alot the sides abit, then it will be simple.

[Brainteasercool]

the rules
you can go over a line one time
you can't go along a line
you can start in the middle or outside
you can have a straight line or a curved line
you can't cut or go through corners

[cristo]

the rules
you can go over a line one time
you can't go along a line
you can start in the middle or outside
you can have a straight line or a curved line
you can't cut or go through corners

With those rules, the problem has been shown (many times in this thread) to be insoluble.

[bagelboy92]

this seems to be impossible because first of all there is an even number of lines to cross for one line to go through and second of all i have made a NOTEBOOK of individual papers that have front and back non repetitive attempts....i lie to you not this is impossible...i have lost time trying to figure this out on a state highschool test that determines if i pass high school! (Breathing hard like a maniac while saying that) ... ... yes im okay but i tell you with confidence for all who read this that it is impossible

[cristo]

this seems to be impossible because first of all there is an even number of lines to cross for one line to go through and second of all i have made a NOTEBOOK of individual papers that have front and back non repetitive attempts....i lie to you not this is impossible...i have lost time trying to figure this out on a state highschool test that determines if i pass high school! (Breathing hard like a maniac while saying that) ... ... yes im okay but i tell you with confidence for all who read this that it is impossible

Wow... you really haven't read the earlier posts in this thread have you? :rolleyes:

[light_bulb]

fun, will insert another quarter :(

[light_bulb]

i think this one is right?

[cristo]

i think this one is right?

Nope... you missed a side. It is impossible!!

[light_bulb]

i have a new one with all lines but it adds up to 17? maybe unsolvable

[tehno]

Nope... you missed a side. It is impossible!!
I'd second that.

[Sting1974]

Why doesn't someone make a computer program to see if its solvable? might be easier and it could do calculations or attempts hundreds of times faster than us.

[d_leet]

Why doesn't someone make a computer program to see if its solvable? might be easier and it could do calculations or attempts hundreds of times faster than us.

Because that would be entirely pointless, for as it has been said numerous times in this thread it is simply not possible.

[MindCrack]

This thing is like crack cocaine! I dont know what its called so I just call it Mind Crack. Ive been doing this puzzle for about 6 months now and havent figured it out. It was shown to me by a neighbor who says hes seen the answer but had been done on a computer. Whether thats true or not I do not know. Seeing as hes an alcoholic but still. If anyone has the true answer. Quit hiding it and reveil it! Because Im sure there is otehr people out there that are craving to know the answer!

...Mind Crack

[cristo]

This thing is like crack cocaine! I dont know what its called so I just call it Mind Crack. Ive been doing this puzzle for about 6 months now and havent figured it out. It was shown to me by a neighbor who says hes seen the answer but had been done on a computer. Whether thats true or not I do not know. Seeing as hes an alcoholic but still. If anyone has the true answer. Quit hiding it and reveil it! Because Im sure there is otehr people out there that are craving to know the answer!

...Mind Crack

Why don't you read the n posts above telling you that this is impossible! There's a proof of this in one of the early replies.

[mhhottie111]

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!

i want to see your solution......

[mhhottie111]

i want to see your soltution to this problem.i have been trying for 2 years and still can not seem to find any answer

[Hootenanny]

i want to see your soltution to this problem.i have been trying for 2 years and still can not seem to find any answer
As has been said many, many times before (and proven once), this problem has no solutions. Therefore, it serves no purpose to continue to seek solutions to this problem and hence any discussion on the topic is also useless.

Thread closed.