General Question

LostInParadise's avatar

Can you solve this connect the dots problem?

Asked by LostInParadise (17815 points ) December 16th, 2010

Suppose that you draw 10 dots and you want to connect them with lines so that every dot is connected to exactly 3 others. Can you come up with a strategy for doing this? It is okay if the lines cross each other.

This is a kind of aha! problem where, after thinking about it for a while, the answer comes all at once.

I suppose I could have made up a story around the problem, like having 10 people at a meeting arrange things so each person speaks to exactly 3 others, but the problem is easier to solve if you think of it in terms of dots and lines.

Observing members: 0 Composing members: 0

12 Answers

NanoBiscuit's avatar

How about a pyramid format, one dot, then a row with two, then a row of three, and the last row of four, allowing for 18 lines?

Or, an octagon shaped configuration, of two dots, two rows of three, last row of two, allowing for 19 lines?

Or, are these even related to the question?

Edit: nope, i was thinking of lines not connections of one to three.

sumitnxt's avatar

make a circle with 9 dots on the border and each dot connected to the the 10th dot at the centre. now erase the circle leaving behind the dots and join each of the two adjacent dots using lines.
Edit
Nope the central one is going to get connected with more than 3 in this case.

FireMadeFlesh's avatar

Make a circle of all ten dots. Connect each dot to the two either side of it, and the one directly across from it. If done correctly, this can be done without lifting the pen from the page.

sumitnxt's avatar

here is one way… link

LostInParadise's avatar

Nicely done @FireMadeFlesh and @sumitnxt . The lines cannot be drawn without lifting the pencil, as was explained by Euler in the Konigsberg bridge problem. When you trace the lines, each node except the first and last must have an even number of lines connecting it, because each time the node is visited on one link, it must be exited on another.

I came up with another solution. Hint: Think 3D

LostInParadise's avatar

This is the way I solved the problem. Divide the 10 points into two groups of 5. Connect each group of 5 as a pentagon. Then connect corresponding points of each penatgon. If you imagine this in 3 dimensions then you can think of the two pentagons as the top and bottom of a solid, which is called a prism for those who forgot their high school geometry.

What I like about this is that it generalizes to having higher numbers of connections for numbers of points divisible by 2^n. For example 20 points can be connected so that each point connects to 4 others by dividing the 20 points into two groups of 10. Use some method to connect each of the 10 points so each point within the 10 is connected to 3 others. Then connect corresponding points of the two groups of 10 to have all the points connected to 4 others.

6rant6's avatar

@LostInParadise Too bad your original solution didn’t mention the part about not lifting pencil from paper. I would like to have seen if people went 3-d.

Your use of “Dot” rather than “Point” makes me think of drawing on a piece of paper – in other words in 2-d.

Also, I am totally at a loss to see how putting this in a word problem story can include an analog to “Without lifting the pencil from the paper”. I’m sure someone has an idea…

LostInParadise's avatar

Like I said, it is impossible to do the drawing without either lifting the pencil or retracing a line. Consider any point other than the first or last to be connected. The point has 3 lines connecting it. One line will be used to visit it from a previous point. A second line will be used to move to the next point. That leaves one line remaining. When you follow that line to visit the point again, there is no way of leaving. All 3 connecting lines have been used up.

Going 3d was just a way of helping to visualize the connections. The same connections can be made in 2d. The nice thing about visualizing in 3d is that the connections are made without crossing any lines.

gasman's avatar

According to rules discovered & proven by Euler almost 300 years ago, since the graph has more than two odd vertices (in this case, there are 10 vertices, all of them joining 3 edges, which makes them odd) then a so-called Euler circuit does not exist – meaning that you’ll have to lift your pencil off the paper (or retrace some of the lines) to complete the diagram. [ Ref. ]

FireMadeFlesh's avatar

@gasman Oops. I just realised that my method really does require the pen to leave the page. Thanks!

6rant6's avatar

Does this work as a story problem?

Ten math geeks participate in a Secret Santa gift exchange at the office. In this version, each person is assigned three people to give gifts to. And each person is to receive three gifts.

The day of the exchange, one person is chosen to give a gift. They give one of their three gifts away. Then the person who received that gift gives one of theirs away… and so on. They continue until the person receiving a package has none to give.

Is it possible that all the gifts can be exchanged without having to start over? Remember these are math geeks who can arrange the giving pattern and the exchange pattern to accomplish this end.

LostInParadise's avatar

I like your thinking, but the gift giving would have to be mutual since the line counts as a connection for both dots. What you are describing would be good for a different type of problem, which could be modeled by what is called a digraph (short for directed graph) where the connections are arrows that go in just one direction.

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther