|
Two problems for me to solve over the weekend:
1. Here's a problem I've been trying to solve. I haven't figured it out yet. You start with this:
The goal is to go through each line segment once. You can't go through the same one twice, and you may start wherever you like. One continuous line.Here's an example with the wrong part circled
2. I'm back in my hometown on break from college. My friends attending community college are bored as shit. None of us are 21, and I wanna do something with them to shake things up. Nothing illegal unless its hard to get caught. Open to ideas
my thoughts so far are ranging from:
triple-date w/ random girls
golfing off of various roofs
prank war with somebody
but its cold as shit and rainy outside, so outside ideas are gonna have to be cancelled. We don't know enough people in town to have a good party, and we don't know anybody over 21 who we could reasonably ask to get us anything. After my taser incident I'm not sure I wanna drink either
open to ideas. anything and everything will be considered except obvious trolling
|
Also rule to #1: the line cannot cross over itself
|
pretty sure #1 is impossible
|
|
|
On October 15 2009 15:26 Caller wrote:
pretty easy
start from the center and draw lines squiggly through all the middle segments
then draw parabolic curves touching each segment at one sole point (i.e. tangent)
i thought of this too. my sister is going crazy trying to solve this and she said that doesnt count, it actually has to go through
|
|
|
motbob
United States12546 Posts
On October 15 2009 15:28 KurtistheTurtle wrote:Show nested quote +On October 15 2009 15:26 Caller wrote:
pretty easy
start from the center and draw lines squiggly through all the middle segments
then draw parabolic curves touching each segment at one sole point (i.e. tangent)
i thought of this too. my sister is going crazy trying to solve this and she said that doesnt count, it actually has to go through
Why would you go crazy trying to solve something which is probably impossible?
|
On October 15 2009 15:30 Ryan307  wrote:I think I got it~
you missed one, middle line second horizontal segment from the left
|
oh fuck you're right lol.
then I give up.
|
Yeah that's a graph theory problem. Yeah that's not doable.
Just look at this basic example
Take the top left square, there are 5 edges that you must cross. The only way to do this without crossing an edge twice is to start from INSIDE the square. So that's doable, but now you must start from outside the upper right square, and cross all the edges without crossing one twice. You can't do it.
Also i feel bad for your sister because this only takes a minute tops of reasoning it out instead of trying random paths.
|
Yeah read the wiki article - it pretty much explains it there.
|
@Divinek: If it is a well known problem for which a new type of problem solving was developed to solve it...then it isn't just 'a minute tops of reasoning it out' that most people take to solve it.
|
It doesn't seem possible: unless I miscounted, there are 4 edges of odd degree, which means there is no Eulerian walk for this problem.
|
So simple and so close lol
|
On October 15 2009 16:14 Divinek wrote:
Yeah that's a graph theory problem. Yeah that's not doable.
Just look at this basic example
Take the top left square, there are 5 edges that you must cross. The only way to do this without crossing an edge twice is to start from INSIDE the square. So that's doable, but now you must start from outside the upper right square, and cross all the edges without crossing one twice. You can't do it.
Also i feel bad for your sister because this only takes a minute tops of reasoning it out instead of trying random paths.
That is not true. Leave the top left square, but change the top right square so that it has only 2 interior edges, while not changing the rest of the squares (somehow), and the problem is now solveable. It's not that the top left square has 5 edges that is the problem, because then you have exactly two edges of odd degree (note that there are 11 possible edge destinations from each corner edge that faces the outside white space). Then, since the top right also has two edges of odd degree, you end up with 4 total edges of odd degree, which at THAT point makes the problem impossible.
|
On October 15 2009 16:18 Lemonwalrus wrote:
@Divinek: If it is a well known problem for which a new type of problem solving was developed to solve it...then it isn't just 'a minute tops of reasoning it out' that most people take to solve it.
seems pretty obvious that there cant be a solution just from what i said. You cant even get past that part so there's no part even fiddling with the rest.
On October 15 2009 16:23 EtherealDeath wrote:Show nested quote +On October 15 2009 16:14 Divinek wrote:
Yeah that's a graph theory problem. Yeah that's not doable.
Just look at this basic example
Take the top left square, there are 5 edges that you must cross. The only way to do this without crossing an edge twice is to start from INSIDE the square. So that's doable, but now you must start from outside the upper right square, and cross all the edges without crossing one twice. You can't do it.
Also i feel bad for your sister because this only takes a minute tops of reasoning it out instead of trying random paths. That is not true. Leave the top left square, but change the top right square so that it has only 2 interior edges, while not changing the rest of the squares (somehow), and the problem is now solveable. It's not that the top left square has 5 edges that is the problem, because then you have exactly two edges of odd degree (note that there are 11 possible edge destinations from each corner edge that faces the outside white space). Then, since the top right also has two edges of odd degree, you end up with 4 total edges of odd degree, which at THAT point makes the problem impossible.
That's what i said v_v. If you use them in combination like that. Though the way that paragraph started it did seem i was talking about only the one thing isolated.
|
On October 15 2009 16:24 Divinek wrote:Show nested quote +On October 15 2009 16:18 Lemonwalrus wrote:
@Divinek: If it is a well known problem for which a new type of problem solving was developed to solve it...then it isn't just 'a minute tops of reasoning it out' that most people take to solve it. seems pretty obvious that there cant be a solution just from what i said. You cant even get past that part so there's no part even fiddling with the rest.
I'm just saying implying someone is stupid for not immediately realizing the solution to a problem that is so troublesome it lead to the development of a new type of problem solving is kinda lame.
|
On October 15 2009 16:26 Lemonwalrus wrote:Show nested quote +On October 15 2009 16:24 Divinek wrote:On October 15 2009 16:18 Lemonwalrus wrote:
@Divinek: If it is a well known problem for which a new type of problem solving was developed to solve it...then it isn't just 'a minute tops of reasoning it out' that most people take to solve it. seems pretty obvious that there cant be a solution just from what i said. You cant even get past that part so there's no part even fiddling with the rest. I'm just saying implying someone is stupid for not immediately realizing the solution to a problem that is so troublesome it lead to the development of a new type of problem solving is kinda lame.
I didn't imply she's stupid, i just felt bad that the problem was driving her nuts. I mean the way she tried it is by far way way funner.
I'm sure she could reason it out the same way if she didn't try a brute force method.
|
On October 15 2009 16:24 Divinek wrote:Show nested quote +On October 15 2009 16:18 Lemonwalrus wrote:
@Divinek: If it is a well known problem for which a new type of problem solving was developed to solve it...then it isn't just 'a minute tops of reasoning it out' that most people take to solve it. seems pretty obvious that there cant be a solution just from what i said. You cant even get past that part so there's no part even fiddling with the rest. Show nested quote +On October 15 2009 16:23 EtherealDeath wrote:On October 15 2009 16:14 Divinek wrote:
Yeah that's a graph theory problem. Yeah that's not doable.
Just look at this basic example
Take the top left square, there are 5 edges that you must cross. The only way to do this without crossing an edge twice is to start from INSIDE the square. So that's doable, but now you must start from outside the upper right square, and cross all the edges without crossing one twice. You can't do it.
Also i feel bad for your sister because this only takes a minute tops of reasoning it out instead of trying random paths. That is not true. Leave the top left square, but change the top right square so that it has only 2 interior edges, while not changing the rest of the squares (somehow), and the problem is now solveable. It's not that the top left square has 5 edges that is the problem, because then you have exactly two edges of odd degree (note that there are 11 possible edge destinations from each corner edge that faces the outside white space). Then, since the top right also has two edges of odd degree, you end up with 4 total edges of odd degree, which at THAT point makes the problem impossible. That's what i said v_v. If you use them in combination like that. Though the way that paragraph started it did mean i was talking about only the one thing isolated.
Oh haha misread, interpreted what you typed the wrong way for some reason. 3:27 am ftl.
|
Could you maybe go inside the walls. This way you wont cross the wall but can use it for transport.
|
Being up late indeed! I feel for ya
|
On October 15 2009 16:27 Divinek wrote:Show nested quote +On October 15 2009 16:26 Lemonwalrus wrote:On October 15 2009 16:24 Divinek wrote:On October 15 2009 16:18 Lemonwalrus wrote:
@Divinek: If it is a well known problem for which a new type of problem solving was developed to solve it...then it isn't just 'a minute tops of reasoning it out' that most people take to solve it. seems pretty obvious that there cant be a solution just from what i said. You cant even get past that part so there's no part even fiddling with the rest. I'm just saying implying someone is stupid for not immediately realizing the solution to a problem that is so troublesome it lead to the development of a new type of problem solving is kinda lame. I didn't imply she's stupid, i just felt bad that the problem was driving her nuts. I mean the way she tried it is by far way way funner. I'm sure she could reason it out the same way if she didn't try a brute force method.
Oh...I apologize I guess I misunderstood your first post. Carry on.
Edit: Everybody seems to be misunderstanding you in this thread. 
|
well thanks guys. thought it was impossible, but I still have like 2 sheets of paper just full of random tries just in case. i think ill just go get some skittles..that should be good enough
|
I'll admit even though I know of the seven bridges problem and immediately thought it was just a different version of it...there is still a sheet of notebook paper next to my desk with a few tries on it. 
|
It is techinically solvable though, if you cheat with a 4th dimension of even parity.
But you know, that's just no fun.
|
Omg lol. Two pages without mentioning this:
On October 15 2009 15:16 KurtistheTurtle wrote:
my thoughts so far are ranging from:
triple-date w/ random girls
golfing off of various roofs
prank war with somebody
...
open to ideas. anything and everything will be considered except obvious trolling
Only on Teamliquid...
(He even asks people not to troll, so many nerds on TL lol <3)
EDIT: Starcraft Lan
|
On October 15 2009 17:37 ThunderGod wrote:Omg lol. Two pages without mentioning this: Show nested quote +On October 15 2009 15:16 KurtistheTurtle wrote:
my thoughts so far are ranging from:
triple-date w/ random girls
golfing off of various roofs
prank war with somebody
...
open to ideas. anything and everything will be considered except obvious trolling
Only on Teamliquid... (He even asks people not to troll, so many nerds on TL lol <3)
HAHA :o invite everyone over to watch [MST] group 5? ^_^
|
On October 15 2009 16:19 kOre wrote:So simple and so close lol
You missed bottom-center line, which puts in question the whole idea of going 'circular'.
|
One way to show it's impossible is this:
Make a dot in the center of each box and each wall segment. Draw lines from the dot in each box to every "door." Now you have a graph you have to traverse. Whenever you have to do this, you have to start at some box, and end at some box. Every other box MUST have an even number of lines coming from the center dot. Why? If you're not starting or ending there, every time you enter, you must also leave. (ie- only multiples of two are allowed). These boxes with an even number of lines are called "even nodes." The only "odd nodes" you can have are the starting and ending boxes, since you only add one extra line by starting (and then leaving) or entering (and then ending).
Look at the graph for your picture. The top two boxes and the bottom middle box all have odd nodes. You can only have 0 or 2 odd nodes if you want a transversable graph. So, this graph is impossible to transverse.
Also: I'm a jerk because I like to give this to my students and not tell them it's impossible until a couple days later
|
it is the standard graph traversal problem really, ninjafetus presented it quite nicely.
except that he omitted that you have to put a dot outside all the boxes as well, and have a lines from it to the external doors... the external space happens to also represent an odd graph node.
not a big mistake though, its still as impossible as ever :p
|
|
|
^^ Lines have no thickness. (It wouldn't cross either of the middle ones.)
|
edit: nvm... it was wrong
|
On October 15 2009 23:12 EsX_Raptor wrote:
edit: nvm... it was wrong
Except you missed the middle left one.
Aw, you removed it. GG indeed.
|
|
|
On October 15 2009 23:38 imweakless wrote:maybe this? + Show Spoiler +http://img261.imageshack.us/img261/2604/54043753.png
no
edit: lol i proved it to be impossible indeed
|
It is possible. It's one of those think outside the box problems.
Consider how the math teacher would have showed them in class and what materials they would be using
|
I'm thinking you need to leave one of the outside edges for last and then go around your line and come back in. there was a thread like this a while ago with three houses and three utility lines you had to get to each house, I'll see if I can find it.
EDIT: Found it
http://www.teamliquid.net/forum/viewmessage.php?topic_id=92920
|
United States10328 Posts
graph theory proves it's impossible. if you do cheating things like going into walls sideways etc. it's possible (because this is an extreme case, i.e. barely impossible.) like Hurricane said, this is related to the 3 houses/3 utilities problem (K_{3,3} is nonplanar.)
|
even if you are allowed to intersect your own line, you still can not solve it, so it's not related to whether it is planar or not at all.
you plain simple have 4 areas (3 rooms and the outside) with odd number of doors, which makes it impossible.
ninjafetus explained it already, but i'll give it another go:
for a given area, you have to either enter or leave it through each door. you also have to alternate enter/leave, you can not leave twice without entering in-between.
so odd number of doors means that you either start your trip inside it and end outside it, or you start your trip outside and end inside.
so an "odd area" has to be either your start point or your end point.
well here you have four odd areas, and obviously they can't all be your start/end locations.
|
On October 16 2009 07:37 Hurricane wrote:I'm thinking you need to leave one of the outside edges for last and then go around your line and come back in. there was a thread like this a while ago with three houses and three utility lines you had to get to each house, I'll see if I can find it. EDIT: Found it http://www.teamliquid.net/forum/viewmessage.php?topic_id=92920
LOL that one is definitely impossible. That's just a common example of planar graphs not working
|
|
|
While you are at it, try connect all pairs of 5 dots together but you cannot cross edges.
|
|
|
|
|
|
EPT![[image loading]](http://img122.imageshack.us/img122/6227/impossibleproblem.jpg)
![[image loading]](http://img26.imageshack.us/img26/6821/impossibleproblemsolved.jpg)
![[image loading]](http://c2.ac-images.myspacecdn.com/images02/112/l_b88ab9e58c0549e88c3d2a1b98105c99.jpg)
![[image loading]](http://img26.imageshack.us/img26/6227/impossibleproblem.jpg)
![[image loading]](http://i.imagehost.org/0648/impossibleproblem.jpg)
![[image loading]](http://img128.imageshack.us/img128/23/64478799.jpg)
