Hello,
My architecture teacher gave us a problem that he says is possilble. I myself don’t think it is possible but before I go and say that he is lying I thought I would get a second opinion. Here is the puzzle.
Connect the bottom three dots to the top three dots without crossing a line.
. . .
. . .
(sorry if that isn’t formatted right)
My teacher said that he did it but it took him a very long time to do it (years). If its possible could I get a solution and if it is not possible could I some kind of explanation why? I want some evidence so I can back up what I say. Thanks for your help!
Just for clarification, all the dots must be connected so that there is a line going each bottom dot to each top dot. The only restrition, I beleive, is that the lines cannot cross. Thanks again
Well, if you’re not specifying straight lines, it’s pretty easy.
Otherwise, I’d be doing crazy stuff such as folding the paper as I move the pen in order to eventually get the dots connected - hey, the line’s straight, even if the space isn’t.
I’d check your solution, BraheSilver. It’s impossible to connect each of the three bottom dots to each of the three top dots without having some of the lines cross, or “cheating” in some other way.
This is a pretty famous topological problem, usually known as the “three utilities puzzle.” Here’s a web page about it.
Because the dots are all co-planar does not mean the lines need to be, and if “crossing” means “intersecting” as in existing in the same point in space, then it can be done with ease.
Below is a link with all the math you might care to throw at this problem. Doesn’t look like there is a solution if they are all on the same plane. As mentioned it is easy if you can move the dots in three dimensions.
Note that you can make eight connections if everything has to remain on the same plane without crossing a line. The ninth connection will see a line getting crossed.
Place the thing on a doughnut shaped plane, and it can be done by looping one or two around the inside of the doughnut, so to speak, but it cannot be done on a flat piece of paper in two dimensions.
I sat down and in maybe a minute solved this. Granted, I had drawn the dots a bit close together, so the lines were a bit tight. I then tried to duplicate the feat more clearly. On my third try, I realized that in my original successful diagram, one of the dots had two lines connected to it, and one of the others had 4.
D’oh!
Anyway, the OP was answered, but I wanted to share my ‘discovery’ of how simple it is to mess it up.
The OP is not clear on the problem. The graph being referred to is called K[sub]3,3[/sub]. The 6 node bipartite-complete graph. It cannot be embedded in the plane without a crossing.
There’s a really interesting result in Graph Theory involving this graph and K[sub]5[/sub], the complete graph of 5 nodes. All non-planar graphs can be reduced to an instance of one or the other of these two using 3 operations: eliminate an edge, eliminate a node with <2 edges, and eliminate a node with 2 edges-replacing with a single edge.
For something comletely different. I just took the sat’s today and I was thinking it might be useful for somet kind of formula for adding long strings of consecutive integers. So I was playing with my calculator and I figured this out:
in positive integers there is a pattern. 1+2+3+4+5+6… and so on, if n is the last number in a string starting with 1 then the formula is n(n/2+.5). I just figured this out by guess and check but im just wondering what is this called and how do you use it for odd intergers or numbers starting at -5 and going up by 3’s or something like that.
Before leaving the OP, I remember seeing exactly this problem in a magazine or brain puzzler book or something. The solution was based on the fact that the dots were not points but good-sized discs, and fairly close together, so a Z-shaped figure could actually pass through each pair of dots.
But considering all the advanced math that’s been brought to bear by other posters here, maybe this isn’t an acceptable solution. (Or maybe it is: your instructor is having a little fun with you and everyone here is overthinking it.)
The numbers you mentioned are called the triangular numbers. It’s easy to see where they get this name if you consider the number of pins in bowling (10=1+2+3+4) or balls in a pool rack (15=1+2+3+4+5).
In general, the sequences you’re talking about are called arithmetic sequences (where the difference between consecutive terms is constant, for example, 3,7,11,15,19,23,…) It’s always easy to add up a finite arithmetic sequence:
(n/2)*(a[sub]f[/sub]+a[sub]l[/sub]
n=the number of terms in the sequence
a[sub]f[/sub]=the first term in the sequence
a[sub]l[/sub]=the last term
This works because, for example, in my above sequence:
03, 07, 11, 15, 19, 23
23, 19, 15, 11, 07, 03
Add up the columns to get:
26, 26, 26, 26, 26, 26
which is the sum of the first and last terms. We have six 26’s because there were six terms in the sequence. But we must to divide by two since this is exactly twice the sum of the sequence:
