Extremely Tough Brain Teaser

[brikis98]

you can't do it without bending/reinterpreting the rules a bit. for example, if a line goes through a corner, does that count as 0 gates, 1 gate, or 2 gates? likewise, does it have to be one continuous line (or can you lift your pencil)? what about a line that is right on top of an edge of the rectangle? we'd need to have clearly defined rules to prove it's possible (by solving) or impossible...

 

[SpecialEd]

There is no solution to this problem.

Reason: Consider a room with five gates. In order to pass through each gate exactly once, your options for that room are either:

enter, leave, enter, leave, enter

or

leave, enter, leave, enter, leave.

Therefore, if a room has five gates, you must have either started in that room or stopped in that room. But the number of rooms with five gates is 3. If a solution existed, you would have a room with five gates that you neither started in or stopped in.

QED

 

[cubby1223]

Originally posted by: Murphy Durphy
If this is such a famous problem, shouldn't the answer be somewhere on the internet? I've searched the web and I've searched books about Euler theory and can't find mention of this problem anywhere.

It isn't on the internet because it's not a famous problem, nor does it have a solution.

The only possible "solution" is by bending the rules, by jumping over a gate in some way that's "acceptable", or passing through a corner and having it count as crossing both at once, or if you took the drawing and curved it around a sphere somehow to change the positioning of the gates.

Wait, I know the solution! Accellerate the right half close to the speed of light, and it's mass will increase, altering the gates' gravitational pulls, causing two gates to bend into one, now giving you the proper requirement to solve the puzzle!!! Or maybe it's the Matrix solution, it's not the gates that are bending, it's your mind that's bending!!

 

[Murphy Durphy]

Originally posted by: brikis98
you can do it without bending/reinterpreting the rules a bit. for example, if a line goes through a corner, does that count as 0 gates, 1 gate, or 2 gates? likewise, does it have to be one continuous line (or can you lift your pencil)? what about a line that is right on top of an edge of the rectangle? we'd need to have clearly defined rules to prove it's possible (by solving) or impossible...

You can't lift your pencil, and the corner bit I'm getting clarified within the next two hours. I'm going to see if the professor who wanted to bet me $50 there was a solution was including any type of trickery (such as corners) in the process, even though he did originally say there was none.

 

[dullard]

Originally posted by: cubby1223
It isn't on the internet because it's not a famous problem, nor does it have a solution.

I agree with the rest of what you wrote, but this is a famous problem. It has been taught for centuries in school, it has been smeared all over the internet, it has been posted on ATOT dozens of times, etc.

 

[Goosemaster]

Originally posted by: tm37
Think I got it

you missed one

 

[Kyteland]

Redefining the problem as graph theory.

In that picture, trace each edge of the graph exactly once without picking up your pencil. Because it's now a graph, the problem is well defined. This is equivalent to the original problem.

The conceptual proof of why this is impossible is because you have 6 nodes in the graph, 4 of which have an odd edge count. If you have >2 odd nodes the problem has no solution. The reason is that every time you enter a node you must also leave it, consuming two edges in the node. because you are drawing a path with a pen, that path is allowed to have two endpoints. Because of this you can start and stop in two different nodes and those two nodes will have an odd edge count.

The reason the "hole in the paper" trick works is because it essentially allows you to partition the graph in to two pieces. If you select properly this leaves you with exactly two odd nodes in each partition.

 

[irishScott]

I got this
http://pics.bbzzdd.com/users/irishScott/w58550207.jpg

 

[jman19]

Originally posted by: irishScott
I got this
http://pics.bbzzdd.com/users/irishScott/w58550207.jpg

You can't go through a gate twice... check out the bottom-middle gate.

 

[mezrah]

Originally posted by: irishScott
I got this
http://pics.bbzzdd.com/users/irishScott/w58550207.jpg

crossed bottom middle twice

 

[Pastore]

Originally posted by: irishScott
I got this
http://pics.bbzzdd.com/users/irishScott/w58550207.jpg

Bottom middle twice... The puzzle isn't possible.

 

[irishScott]

Originally posted by: jman19

Originally posted by: irishScott
I got this
http://pics.bbzzdd.com/users/irishScott/w58550207.jpg

You can't go through a gate twice... check out the bottom-middle gate.

fvck.

 

[brikis98]

Originally posted by: irishScott
I got this
http://pics.bbzzdd.com/users/irishScott/w58550207.jpg

you went through the bottom middle one twice.

 

[mezrah]

Hey, if Dr. Math says it can't be done, then it can't be done:

http://mathforum.org/library/drmath/view/54306.html

 

[JustAnAverageGuy]

Do tangent lines (i.e. parabola, see pic) count?

JaAG's Solution

- JaAG

 

[jdini76]

 

[Pastore]

Blargh!

 

[Pastore]

 

[crt1530]

Euler: The Master of Us All

 

[BrownTown]

not possible unless you allow some sort of non-expected thing like beign able to fold the paper, or running along the lines without intersecting them.

 

[ahurtt]

If your line crosses directly across the intersection point of 2 or more gates, does that count as having crossed all the gates that intersect at that point? Or must it be solved as if there were no actual intersecting or touching lines in the template?

 

[TheChort]

where the hell is the OP with the update from his prof?

i nEEd mY fIX, NOw!!

 

[FoBoT]

read the wiki Kyteland linked

 

[SViper]

Here's my take on it. I have lines through the corners, which don't actually go through any sides.

http://pics.bbzzdd.com/users/SViper/box_riddle_solved.JPG

 

[edro]

Originally posted by: Kyteland
Redefining the problem as graph theory.

In that picture, trace each edge of the graph exactly once without picking up your pencil. Because it's now a graph, the problem is well defined. This is equivalent to the original problem.

The conceptual proof of why this is impossible is because you have 6 nodes in the graph, 4 of which have an odd edge count. If you have >2 odd nodes the problem has no solution. The reason is that every time you enter a node you must also leave it, consuming two edges in the node. because you are drawing a path with a pen, that path is allowed to have two endpoints. Because of this you can start and stop in two different nodes and those two nodes will have an odd edge count.

The reason the "hole in the paper" trick works is because it essentially allows you to partition the graph in to two pieces. If you select properly this leaves you with exactly two odd nodes in each partition.

Genius. I love those old school math tricks.