Puzzle Math

[JamesCarroll]

There is a puzzle that I draw as a doodle. I know its unsolvable but I draw it none the less. Here's how you do it:

Draw a recatangle about twice as wide as it is high.
Divide it in half along its long axis.
Divide the top half of the rectangle into two even sections with a vertical line.
Divide the bottom half into equal thirds with vertical lines.

Back in 8th grade or so I swear that we were taught that there was a math formula that would tell you if a problem like this was solvable.

Anyone remember what that was?

Thanks.

[wolf_meister]

All such puzzles are similar to the Seven Bridges of Konigsberg problem.
The Swiss mathematician Leonard Euler analyzed this type of problem. Here is a site that should tell you what you need to know.
http://mathforum.org/isaac/problems/bridges2.html

[friedo]

I don't get it - what's the puzzle? I just drew a rectangle and divided it as you said. What is there to solve?

[friedo]

OK, I'm not math dude, but I fail to see how wolf_meister's link has anything to do with the shape described in the OP.

[friedo]

Oh, I get it now. This is one of those "traverse every line without doubling back" things, right?

Now I'm having flashbacks of long CS lectures about the Traveling Salesman Problem.

[Achernar]

Not quite. The idea is to cross each little line segment in the graph exactly once, with a continuous curve.

[TJdude825]

Originally Posted by Achernar

Not quite. The idea is to cross each little line segment in the graph exactly once, with a continuous curve.

It turns out to be a very similar problem. You imagine each region of the figure to be a point, and each line which can be crossed to be a line between the points. Or something like that.

[JamesCarroll]

Originally Posted by wolf_meister

All such puzzles are similar to the Seven Bridges of Konigsberg problem.
The Swiss mathematician Leonard Euler analyzed this type of problem. Here is a site that should tell you what you need to know.
http://mathforum.org/isaac/problems/bridges2.html

Bingo!! I knew I wasn't insane thinking that there was some math to my little doodle. Of course, the fact that an unsolvable puzzle is my favorite doodle might say that I am.

Either way, Thanks WM!!

[Jinx]

Originally Posted by friedo

I don't get it - what's the puzzle? I just drew a rectangle and divided it as you said. What is there to solve?

I still don't get it...all you did what divide a rectangle into parts. Like there's a formula for that? What's the point to this? ...please enlighten us all. - Jinx

[Bryan Ekers]

Okat, let's see if I have this straight. The figure resembles the following, with numbers added to the regions for clarity:

┌───┬────┐
│ 1 │ 2  │
├──┬┴─┬──┤
│ 3│4 │5 │
└──┴──┴──┘

In this case, the numbers of line segments forming the border of each region are as follows:

1: 5
2: 5
3: 4
4: 5
5: 4

Having more than two areas with an odd number of segments dooms any attempt to cross all segments with a continuous line. You'd have to start in 1, 2 or 4 and end in 1, 2 or 4, leaving one region incomplete.

[Cabbage]

Having more than two areas with an odd number of segments dooms any attempt to cross all segments with a continuous line. You'd have to start in 1, 2 or 4 and end in 1, 2 or 4, leaving one region incomplete.

That's almost it, but not quite.

You need exactly zero or two areas with an odd number of segments.

If you have two, you can start in one of the odd areas, and end in the other odd area.

If you have zero, you have the extra benefit of being able to start anywhere, and you'll end up back where you started.

If you have one, however, it ain't gonna work. You can start in the odd area, but where can you possibly end up?

[Bryan Ekers]

Originally Posted by Cabbage

If you have one, however, it ain't gonna work. You can start in the odd area, but where can you possibly end up?

You can either start in the single odd area or end in it, without a problem. Consider a simplified version of the original puzzle:

┌───┬────┐
│ 1 │ 2  │
├───┴────┤
│   3    │
└────────┘

If you start in area 3, you can draw the long line easily enough. You could, for example:

Start in 3
Up to 2.
Right to outside.
Up, left and down into 2.
Left to 1.
Up to outside.
Left, down and right into 1.
Down into 3.
Left to outside.
Down, right and up into 3.
Right to outside.


You could start elsewhere and end in 3, but this is a little trickier since it's easier to accidently put yourself in a dead end.

[Achernar]

On the other hand, you can think of the outside as another area which necessarily evens out the parity. In the first example, the outside has 9 segments to its border. In which case there are always an even number of areas with odd numbers of segments, so "exactly zero or two" is the same as "no more than two".

I have seen this puzzle completed on the surface of a torus, with the hole inside area 4 (I think), but that's not so surprising. You can do anything on a torus.

[Cabbage]

Bryan Ekers, you're forgetting there's a fourth region--the outside, and it is odd, giving us exactly two odd regions.

[Achernar]

Of course if you count that, then what on earth do you mean "only one"? That's impossible!

[Cabbage]

You're right, Achernar, I didn't actually stop to think if it was possible to have exactly one odd region or not (which I do see is impossible, now that I think about it). I was just thinking in terms of starting and stopping points.

[ftg]

The Mathematical version of this problem is called an "Euler Tour" (or "Cycle" if it has to end where it begins). It is defined on connected undirected graphs. The tour has to cross each edge of the graph exactly once. In the OP puzzle, each region is a vertex in the graph and two vertices are connected if they have a boundary in common. Since an edge in a graph has two endpoints, the sum of degree of all vertices must be even. So the only solvable cases are ones where there exactly zero or 2 vertices of odd degree. Cabbage's post is quite correct if you understand what is meant.

Note that the test for the existence of an Euler tour is trivial. The corresponding problem of visiting each vertex exactly once is a "Hamiltonian Path." Determining if a graph has a Hamiltonian Path is NP-Complete. I.e., very hard as far as we know. If you prove for sure that it is hard or not, you will be instantly world famous.

There are a remarkable number of deep problems in Math and Computer Science that are small variations of such simple puzzles.

[CookingWithGas]

Originally Posted by JamesCarroll

"It's a big enough umbrella, but its always me getting wet"

Isn't that "always me who ends up getting wet"?