wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Connect the 6 dots together, is this impossible? 
        
(Message started by: Etard94 on Nov 1^st, 2008, 11:38pm)

Title: Connect the 6 dots together, is this impossible?
Post by Etard94 on Nov 1^st, 2008, 11:38pm

So there is this puzzle, a puzzle which everybody on every site which has this puzzle has claimed to be impossible, but according to my maths teacher is not.
Please, I'm like dying for the solution, like literally! And if you can't find the solution, recommend a forum which i can post this puzzle on and get some good responses.
And apparently it's a maths problem, so maybe you could maths to solve it, i have no idea ;S

. . .
. . .

Okay, well you have to make each dot connect to the other 5 dots. So like, if you start with the top left dot and connect it to the other 5, do the same to every other dot. So you'll end up with a lot of lines, and they can also curve around the dots, they don't have to go straight.

But the thing is, you can't cross the lines, so they can't touch.

IS THIS REALLY IMPOSSIBLE!? ???

Title: Re: Connect the 6 dots together, is this impossibl
Post by Eigenray on Nov 1^st, 2008, 11:46pm

It's [edit: not] known as the utilities problem, and it is in fact impossible. There is a nice proof [link=http://www.cut-the-knot.org/do_you_know/3Utilities.shtml]here[/link].

Title: Re: Connect the 6 dots together, is this impossibl
Post by towr on Nov 2^nd, 2008, 7:48am

You can do the utility problem on a torus (donut).
But in the plane (or equivalently on the surface of a sphere) it is impossible (as explained in Eigenray's link).

If each dot has to be connected to all five other dots, then it's not quite the same problem, but even more difficult. However, it can still be solved on the surface of some object* (as long as it has enough holes in the right places), just not on the plane.

[edit]* Actually, it seems this one can also still be done on a torus.[/edit]
[edit2]See attachment, line-ends with the same color are connected over the torus/donut (i.e. top and bottom, and left and right wrap together) [/edit2]

Title: Re: Connect the 6 dots together, is this impossibl
Post by Eigenray on Nov 2^nd, 2008, 11:46am

Whoops, you're right. I saw 2 rows of 3 dots and my mind jumped straight to K_3,3.

Even if there were only 5 dots, it would still be impossible (in the plane). The interesting thing is that the converse holds as well: a graph can be embedded in the plane if and only if it doesn't contain either the utilities graph (K_3,3) or the complete graph on 5 vertices (K₅) as a minor (that is, by removing vertices, edges, or contracting edges).

Edit: There are five dots! How many do you see now?

Title: Re: Connect the 6 dots together, is this impossibl
Post by SMQ on Nov 2^nd, 2008, 1:03pm

on 11/02/08 at 11:46:18, Eigenray wrote:

Even if there were only 4 dots, it would still be impossible (in the plane).

Eh?

http://www.dwarfrune.com/smq/wu/4planar.png

--SMQ

Title: Re: Connect the 6 dots together, is this impossibl
Post by Hippo on Nov 2^nd, 2008, 1:15pm

on 11/02/08 at 11:46:18, Eigenray wrote:

Whoops, you're right. I saw 2 rows of 3 dots and my mind jumped straight to K_3,3.

Even if there were only 4 dots, it would still be impossible (in the plane). The interesting thing is that the converse holds as well: a graph can be embedded in the plane if and only if it doesn't contain either the utilities graph (K_3,3) or the complete graph on 4 vertices (K₄) as a minor (that is, by removing vertices, edges, or contracting edges).

Wow, weeker side of our algebraic hero?
Kuratowski theorem talks about divisions of K_3,3 or K₅.
And tetrahedron can be projected on sphere easily ;).

Sorry for magnifying that, but until now, I felt everyone expect you Eigenray can be cought as beeing mistaken occasionaly so please take it more like a compliment ;)

Title: Re: Connect the 6 dots together, is this impossibl
Post by Eigenray on Nov 2^nd, 2008, 1:43pm

on 11/02/08 at 13:03:10, SMQ wrote:

Eh?

Strange... I see five. Are you quite sure? ::)

Well, looks like I've embarrassed myself enough for one thread. Cheerio!

Title: Re: Connect the 6 dots together, is this impossibl
Post by rmsgrey on Nov 2^nd, 2008, 2:00pm

If memory serves, K₇ can also be done on a torus, though not K₈

Title: Re: Connect the 6 dots together, is this impossibl
Post by Grimbal on Dec 6^th, 2008, 12:57pm

It does.

Title: Re: Connect the 6 dots together, is this impossibl
Post by towr on Dec 6^th, 2008, 1:29pm

on 12/06/08 at 12:57:41, Grimbal wrote:

It does.

So obvious once you see it. Wish I thought of it..