A "draw-it" that has been bugging me for two years

Want to just shoot the breeze? Forum 42 is the place!

Moderator: Moderators

Aguiluz
Posts: 1141
Joined: Tue Nov 20, 2007 7:58 pm
Location: Ontario, Canada
Contact:

A "draw-it" that has been bugging me for two years

Post by Aguiluz »

Image
You see, this little bugger somehow pops in my head every now and then. For the last two years. It all started when one of my classmates drew four dots on the board then challenged us to connect them without going over the same line and without lifting your pen/pencil. The end result must be like on the right.

We can't do it, but we just kept trying time after time. But is it solvable or is it impossible?

EDIT: Yes, we try, try, try and we fail, fail, fail.

EDIT 2: IF YOU DID IT, DON'T POST THE ANSWER WITHOUT WARNING US! (or me) It kinda spoils it.
Image
ghosstt
Senior Member
Posts: 1551
Joined: Mon Feb 26, 2007 4:14 pm

Post by ghosstt »

Yes. I have done it. And I know it. Want to know how?
Kurt_
Portablizer
Posts: 5748
Joined: Thu Nov 24, 2005 10:32 am
Steam ID: kurbert
Location: Ontario, Canada
Contact:

Post by Kurt_ »

The answer is obvious. carve a pencil into a stamp in the shape of the design. Voila.

I tried a bit myself, and there's clearly a trick to it beyond the obvious drawing a line thingie. Like one of those "go around the whole world then end up on the other side" things.
Hey, sup?
WhatULive4
Posts: 329
Joined: Fri Mar 28, 2008 6:19 pm
Location: Saskatchewan, Canada

Post by WhatULive4 »

I do not believe there is an answer. I have been doing this since I was about 9 years old and have never found a solution. I'm 22 now, so either I am extremely stupid, or a solution does not exist.
evilteddy
Portablizer
Posts: 423
Joined: Tue Mar 25, 2008 2:11 am
360 GamerTag: Kirren of Smeg
Steam ID: kizzinator
Location: Newcastle, Australia

Post by evilteddy »

I did it in MS paint in a couple of minutes.
gannon
Moderator
Posts: 6974
Joined: Sun Apr 04, 2004 4:48 pm
Location: Near that one big lake
Contact:

Post by gannon »

Spoiler/answer: http://en.wikipedia.org/wiki/Eulerian_path
Edit: that is, if I interpreted the problem right :P

Oh, and giving each node a letter, the edges are ab, ab, ac, ac, ad, bd, bd, bc, cd, cd
tyromaniac
Posts: 59
Joined: Sun Jan 06, 2008 11:29 am

Post by tyromaniac »

you need to specify more on what you are trying to do....from what you have posted, I could make a box and I'm pretty sure that suffices.

EDIT: I reread it and discovered that "you can't go over the same line" is probably the key to why I was confused. I was thinking you couldn't go over any lines. I'm pretty sure I know the answer, should I post it in a hidden link or what?
Last edited by tyromaniac on Sat May 31, 2008 9:32 pm, edited 1 time in total.
Image
evilteddy
Portablizer
Posts: 423
Joined: Tue Mar 25, 2008 2:11 am
360 GamerTag: Kirren of Smeg
Steam ID: kizzinator
Location: Newcastle, Australia

Post by evilteddy »

The Eulerian paths link above is talking about a situation where you have a set path and you try to find a way to trace the paths already set out with a single line. While this can be applied to the top diagram which looks like a star so that we know that there are no possible solutions you can trace over that I don't think it is applicable when there isn't already a path laid out.

I can do the problem easily. but if you mean that you can't connect two points twice then it is impossible (I think).

Spoiler: here is the link to my solution
Aguiluz
Posts: 1141
Joined: Tue Nov 20, 2007 7:58 pm
Location: Ontario, Canada
Contact:

Post by Aguiluz »

No, no! Evil Teddy and Gannon, you should end up with the same figure on the right. :(

I think nobody can really do this.
Image
evilteddy
Portablizer
Posts: 423
Joined: Tue Mar 25, 2008 2:11 am
360 GamerTag: Kirren of Smeg
Steam ID: kizzinator
Location: Newcastle, Australia

Post by evilteddy »

Ahh now I get it.
Using the figure on the right you cannot trace it and solve it.
To know why you have to go back to Euler and a little problem called the Konisberg bridge problem. This was a town located on two islands and two shores of a river. There were 7 bridges in that town and the locals wanted to know if you could cross each bridge exactly once. Euler solved the problem with a simple proof. If you think about it it is quite simple. Every point needs an even number of lines connected to it one to get there and then go away. It is possible to have two points which have odd numbers of lines connected to them because you can start there (you don't need a line there to enter only to exit) or you can finish there (opp. to above). With that in mind you can make a statement-

If a puzzle which requires you to trace a line over points without lifting the pen has more than two points with an odd number of lines connecting them then it is unsolvable.

Your figure at the top has 4 points all with odd numbers of lines connecting them, it is therefore unsolvable.
Aguiluz
Posts: 1141
Joined: Tue Nov 20, 2007 7:58 pm
Location: Ontario, Canada
Contact:

Post by Aguiluz »

evilteddy wrote:If a puzzle which requires you to trace a line over points without lifting the pen has more than two points with an odd number of lines connecting them then it is unsolvable.

Your figure at the top has 4 points all with odd numbers of lines connecting them, it is therefore unsolvable.
Oh well...

Let me try something new.
Image
vskid
Senior Member
Posts: 6314
Joined: Fri Mar 25, 2005 8:25 am
Steam ID: vskid3

Post by vskid »

I'm glad it is impossible, I was feeling kinda stupid for not figuring it out (especially when others thought they had).
Image
Kurt_
Portablizer
Posts: 5748
Joined: Thu Nov 24, 2005 10:32 am
Steam ID: kurbert
Location: Ontario, Canada
Contact:

Post by Kurt_ »

Definitely impossible. Using some logic posted here, you'd need to start in the centre (the middle of the X), cross through the diagonal, and finish on the second half of the X you started with. Simply put, it can't be done.

Thought this was interesting: (Taken from: http://plus.maths.org/issue25/features/budd/)

David Hilbert

David Hilbert was probably the greatest mathematician of the end of the 19th and beginning of the 20th centuries. Among his many mathematical achievements can be included profound discoveries in logic, algebra and differential equations. Hilbert spaces, a special type of vector space, form the basis for the whole of quantum mechanics.

Hilbert was invited to speak at the International Congress of Mathematicians held in Paris in the year 1900. He could have given a (dull) talk on the achievements of mathematicians in the 19th century, but instead he did something far more interesting. At the start of the 20th century, Hilbert decided to throw out a challenge to keep mathematicians busy for the next 100 years. His talk comprised 23 problems, now called the Hilbert problems, the attempts to solve which he believed would stimulate 20th century mathematics and mathematicians. He chose his problems well. Not only have they proved immensely challenging to solve, but they have led to an enormous amount of new mathematics. Anyone who solved one of the Hilbert problems became extremely famous (within the mathematical community), but not necessarily very rich. Most of the Hilbert problems have now been solved. One which lasted until nearly the end of the 20th Century was Fermat's last theorem.

Pierre de Fermat was an Italian mathematician who worked in the 16th century and was interested in number theory. This is (essentially) the study of problems involving the natural numbers 1,2,3,…. A test for prime numbers based on one of Fermat's results called Fermat’s little theorem has just been discovered, and could play an important role in modern cryptography. It has been known since ancient times that you could find natural numbers $a$, $b$ and $c$ with $a^2 + b^2 = c^2$, an example being $3^2 + 4^2 = 5^2.$ In contrast, Fermat had managed to show that you couldn’t find natural numbers with $a^4 + b^4 = c^4$, using a method he called steepest descent. He wondered whether, if $n$ was any integer different from 2, the problem

[ a^ n + b^ n = c^ n ]

had any whole-number solutions. While thinking about this he retreated to a library and read Diophantus's Arithmetica. It is not recorded whether he liked the text of the book, but he certainly did not like its margins - or to be more accurate the size of them. We know this because he wrote in the margin that he had found a truly marvellous proof of the fact that the above problem could not be solved, but unfortunately the margin of the book was too small to write it down. Did he have a proof? To be honest, we don't know, and mathematicians have been trying hard ever since to find out (with extra points to be awarded to any proof that would fit into a book margin). The problem gained such notoriety that it was called Fermat’s last theorem.

Hilbert posed exactly this problem as one of his unknown problems at the start of the 20th century, and bang on cue, almost 100 years later, it was solved by Andrew Wiles as part of his proof of the Tatyana-Shumura conjecture. Fermat was right (but Wiles' solution will not fit into a margin). You can read about the story of this problem in the wonderful book Fermat's last theorem by Simon Singh.

Another of Hilbert's problems was the Riemann Hypothesis, which is not only still unsolved, but is generally regarded as the most important unsolved problem in mathematics. You can find out more about this problem in A whirlpool of numbers, also in this issue of Plus.


Problems:

TWO BUCKS AND A FLY:

Two bucks, vying for the attention of a young doe standing nearby, lowered their antlers and came hurtling toward each other from a distance apart of 100 meters, each at a speed of 12.5 meters per sec.

A super-fast, but crazy, deer-fly flew in a straight line from the head of one buck to the head of the other, turned and flew back to the first buck. It continued to fly back and forth between the two bucks as the distance between them became dangerously shorter. The fly's speed was 80 meters per sec. How many meters had the fly traveled when the two bucks eventually made contact?



When teacher asked Penny Bright for her place and date of birth she quickly replied "I was born in London at exactly 25 minutes and 4 seconds before Big Ben struck one on the afternoon of the 7th day of August in the year 1990."

The teacher was amazed. "Goodness. How can you remember all that information after all these years". Penny has a method. How does she remember?



Farmer Newer had two poles erected on his land, one was 74 feet high and the other 100 feet high.

He attached a 114 foot length of rope from the top of one pole to the top of the other. The rope sagged so that its lowest point was 30 feet above the ground. What distance apart are the poles?
Hey, sup?
grossaffe
Posts: 1450
Joined: Thu May 29, 2008 11:54 pm
Location: USA

Post by grossaffe »

Its impossible to get the design wanted. one of the rules of graph-theory are that it is impossible to create a Euler Circuit (Circuit that transverses every edge once and only once and starts and stops at the same point) if there is a vertex with an odd degree. In the picture provided, every vertex has a degree of five, which is odd, therefore it is impossible.
Chapel
Posts: 176
Joined: Tue May 20, 2008 12:57 am

Post by Chapel »

At the start of the 20th century, Hilbert decided to throw out a challenge to keep mathematicians busy for the next 100 years. His talk comprised 23 problems, now called the Hilbert problems, the attempts to solve which he believed would stimulate 20th century mathematics and mathematicians. He chose his problems well. Not only have they proved immensely challenging to solve, but they have led to an enormous amount of new mathematics. Anyone who solved one of the Hilbert problems became extremely famous (within the mathematical community), but not necessarily very rich.
This part is a little romanticized. A hand full of the Hilbert problems were solved rather quickly (scale of weeks), but a bunch of them proved pretty challenging.

If anyone wants to try their hand at a Millenium problem, here is the link to the official statements of the problems.
http://www.claymath.org/millennium/
The problem called "P vs. NP" is the one most likely to be solvable by someone outside of the mathematical community.
Post Reply