Author |
Topic: Samwise & Gandalf (Read 12282 times) |
|
jabhiji
Newbie
Gender: 
Posts: 24
|
 |
Samwise & Gandalf
« on: Feb 13th, 2003, 2:01pm » |
 Quote  Modify
|
Samwise Gamgee has a square plot of land, each side being 1 unit. One day, Sam finds out that the dark Lord Sauron has a telephone line that he uses to speak with a traitor amongst the hobbits.
Gandalf informs him that the telephone line runs in a straight line parallel to the ground and passes beneath the square plot of land, but he does not know its location. Sam decides to dig up around the perimeter of his land to discover the telephone line, but Gandalf says it is not necessary to dig around the entire length of 4 units.
Sam brightens up, and says "I know what you mean. I can just dig 3 sides and still discover it. For even if the phone line runs along the fourth side, I will still detect it at the end points ! "
Gandalf shakes his head. "No, Sam. You are on the right track, but you can do better than that."
What solution does Gandalf have in mind for the optimum length of the "digging curve" ?
|
|
 IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Samwise & Gandalf
« Reply #1 on: Feb 13th, 2003, 5:10pm » |
Quote Modify
|
There is a way of length 1+sqrt(3), but I see an even shorter method.
|
|
IP Logged |
|
|
|
jabhiji
Newbie
Gender:
Posts: 24
|
|
Re: Samwise & Gandalf
« Reply #2 on: Feb 13th, 2003, 6:02pm » |
Quote Modify
|
I initially came up with 2.7071 but it is not the minimum.
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Samwise & Gandalf
« Reply #3 on: Feb 14th, 2003, 1:56am » |
Quote Modify
|
Nifty puzzle, jabhiji. The L=3 answer Same gives seems to be the most inuitive, but only slightly less so is the 2*sqrt(2) answer. When you realize that that was only a subcase of a wider set of answers you get SWF's 1+sqrt(3). This is also a subset of another wider category, which gives a slightly better answer 2.722, three connected lines two unconnected lines. I used an interestingly different configuration five unconnected lines to get an answer of 2.728. Not as good, but a cool solution. I am thinking of a way to release some symetry constraints on that one to get a better answer, but I have yet to see something as low as jabhiji.
But lets face it, this is Sam here. Nice guy, but he ain't gonna figure this out, if he does he won't be able to figure out how to plot out where to dig, and even if he can he will have wasted more time on figuring and plotting than it would have taken to dig a simpler solution unless a unit is more than a mile and the telephone line is ten feet under!
|
|
IP Logged |
|
|
|
poseur
Guest
|
I too came up with jabhiji's answer. It's simple but doesn't seem optimal. It might be easier to figure this one out if he expressed it as 2+sqrt(2)/2.
|
|
IP Logged |
|
|
|
jabhiji
Newbie
Gender:
Posts: 24
|
|
Re: Samwise & Gandalf
« Reply #5 on: Feb 14th, 2003, 9:07am » |
Quote Modify
|
After days and days of struggle (and with the help of Frodo, Merry and Pippin) Sam finally decides that the optimum solution is L = 2 + SQR(2)/2. On the morning he is about to start digging, an unfortunate accident occurs. While tending to his flowers, Sam gets stung by a bee.
"I wish these stupid bees would build their hive somewhere else ! " Sam mutters to himself. And then he is suddenly hit by an idea.
"Hey, there is a slightly better solution ! Even Gandalf would not have thought ot it. "
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Samwise & Gandalf
« Reply #6 on: Feb 14th, 2003, 5:00pm » |
Quote Modify
|
ok, I will post a figure with one of my earlier answers eventually. It isn't optimum, but it is cool. It took a huge amount of thought and optimization, and then the simple answer that ends up giving 1+sqrt(2)/2 screams out at me. Ugh. OK, now... bees...
hmm, I don't see how bees fit in, but that last answer can be modified to give 13sqrt(2)/14 -2/7 +2*sqrt(29+2sqrt(2))/7 or 2.64. Any answer better than this would require a completely different configuration.
|
| « Last Edit: Feb 14th, 2003, 5:32pm by aero_guy » |
IP Logged |
|
|
|
SWF
Uberpuzzler
Posts: 879
|
|
Re: Samwise & Gandalf
« Reply #7 on: Feb 14th, 2003, 5:09pm » |
Quote Modify
|
How about 2.639 or
(Edited to fix the equation after towr's equation generator broke)
|
| « Last Edit: Mar 6th, 2003, 5:07pm by SWF » |
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Samwise & Gandalf
« Reply #8 on: Feb 14th, 2003, 5:36pm » |
Quote Modify
|
Ha! I immediately went back to modify my last post (added the second paragraph) and you posted the same solution, SWF. Did a much better job of simplifying it though, I must say. Actually, now that I do the math, yours is .0004 better. Is this a modification of the 2+sqrt(2)/2 geometry or something new?
|
|
IP Logged |
|
|
|
jabhiji
Newbie
Gender:
Posts: 24
|
|
Re: Samwise & Gandalf
« Reply #9 on: Feb 14th, 2003, 6:34pm » |
Quote Modify
|
The bee connection......
I think both SWF and aero_guy have hit upon the same answer as I did. It is just a slight tweaking of the L = 2 + SQR(2)/2 solution. If you look at the intersection of the three lines in the solution, the angle between each is 120 deg. So it is part of a hexagonal tiling.
I look forward to aero_guy putting some of his earlier solutions, even though they may not be optimal.
I am not sure still if L = 2.6389 is optimal or not, but it is the best one can get for this particular configuration.
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Samwise & Gandalf
« Reply #10 on: Feb 16th, 2003, 2:51am » |
Quote Modify
|
OK, I have a nifty little picture, now how do I post it?
Interestingly, the answer we got relates to the road construction riddle, where it was determined that the shortest length of road to connect three points consists of an intersection at 120 deg, howsoever those points are arranged.
|
| « Last Edit: Feb 16th, 2003, 2:56am by aero_guy » |
IP Logged |
|
|
|
jabhiji
Newbie
Gender:
Posts: 24
|
|
Re: Samwise & Gandalf
« Reply #11 on: Feb 16th, 2003, 5:50am » |
Quote Modify
|
So the bees seem to have mastered the art of using a minimum amount of material to build their homes without taking any math courses. Anyway, most of my previous attempts to solve this riddle were capital letters from english: O, C/I/H, X, N/Z. I was just wondering if anybody had any other variants.
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Samwise & Gandalf
« Reply #12 on: Feb 16th, 2003, 7:49am » |
Quote Modify
|
I have a couple. First, one of the earlier solutions was to take the x, then stretch the middle so it looks like two Y's, bottom to bottom. This is a close to minimum answer. Another I am proud of, and I really need to figure out how to post a picture for this, is a little more complex. A straight line comes off of each corner pointing generally clockwise, never touching each other. There is a small free-floating line in the middle as well. It also comes close. Any ideas on how to post a oic of it?
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Samwise & Gandalf
« Reply #14 on: Feb 21st, 2003, 9:27am » |
Quote Modify
|
As near as we have been able to figure.
|
|
IP Logged |
|
|
|
Chronos
Full Member
Gender:
Posts: 288
|
|
Re: Samwise & Gandalf
« Reply #15 on: Feb 24th, 2003, 5:03pm » |
Quote Modify
|
After a lot of hard thinking, Sam finally came up with a solution of total length 2.6389584338 , which Gandalf verified was optimal. But then Sam had a realization! He didn't have to dig the full length, he just had to dig until he hit the wire, then he could stop. Maybe, if he dug those trenches in the right order, he could have a shorter expected length that he'd have to dig! Maybe, he could even get a shorter expected length with a different pattern altogether!
So, can Sam save himself any (expected) work this way? And if so, which pattern should he use, and in what order should he dig it?
(by the way, I'm not sure of the answer to this, but it seems a logical enough extension of the problem).
|
|
IP Logged |
|
|
|
David Ryan
Guest
|
Does anyon here ever play battleship? My father taught me the startegy to find the carrier definitely, and this uses the same principal. I arrived at an answer of just over 2sqrt(2), or about 1.42.
given square ABCD
dig a line from midpoint of AB to midpoint of BC
length is sqrt(2)
dig second line from midpoint of CD to AD
length is sqrt(2)
this requires only 2 digs, each of slightly over sqrt(2) in legnth. Being diagonal, they, should cover any line through the lot, except, potentially, the one straight across the midpoints (you might lucky and dig right on top of it). however, just extend each end of the lines slightly past midpoint so they overlap, and probelm solved.
This will give you 2 points of intersection, and you can use these points to plot the line of the wire.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
 
Gender:
Posts: 727
|
|
Re: Samwise & Gandalf
« Reply #17 on: Mar 6th, 2003, 5:14am » |
Quote Modify
|
on Mar 6th, 2003, 4:08am, David Ryan wrote:| I arrived at an answer of just over 2sqrt(2), or about 1.42. |
|
Well, sqrt(2) = 1.4142...
So 2 sqrt(2) > 2.6389... (alleged minimal length)
Quote:given square ABCD
dig a line from midpoint of AB to midpoint of BC
length is sqrt(2) |
|
Actually, the length is sqrt(2)/2, as the length of one side is 1.
Quote:dig second line from midpoint of CD to AD
length is sqrt(2)
this requires only 2 digs, each of slightly over sqrt(2) in legnth. |
|
Total length: sqrt(2). This should look suspicious to you, considering the optimal length.
Quote:| Being diagonal, they, should cover any line through the lot, except, potentially, the one straight across the midpoints |
|
I think you assumed that the telephone line is parallel to a side of the square. This, however, is not stated in the riddle - only "parallel to the ground". Obviously your arrangement fails to detect any "diagonal" telephone line running parallel to your ditches.
|
| « Last Edit: Mar 6th, 2003, 5:20am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Samwise & Gandalf
« Reply #18 on: Mar 6th, 2003, 5:24am » |
Quote Modify
|
I see a problem with the way the new version of the problem is presented, which is why I never got around to it before. How do you determine the probability that any give dig will intersect the line? For any dig that does not leave zero possible ways the wire could run or a single possibility, there will still be an infinite number of possibilities left over. How does one quantify the likelihood of intersecting the line with any given dig when one removes an infinite number of possibilities leaves an infinite number? High level mathematics and number theory aren't my hobbies, so perhaps someone who has posted one of the various posts discussing the different types of infinities could enlighten us.
|
|
IP Logged |
|
|
|
David Ryan
Guest
|
yes, i realized my mistake, each diagonal is sqrt(2)/2, not sqrt(2). it was right on my paper, but miscopied.
this leaves my two lines totaling sqrt(2), but does not account for a diagonal, which would require a 3rd side of the internal square, making a total length of 3sqrt(2)/2, or approx 2.13 untis.
however, how do we know it doesnt just cut a corner? an insanely small portion of the wire actually on sma's grounds? can this be determined without digging 3 sides? please tell me if it can, and explainor draw, but give soemthing other than just the numbers.
again, i apologize for the copying error.
|
|
IP Logged |
|
|
|
wowbagger
Uberpuzzler
Gender:
Posts: 727
|
|
Re: Samwise & Gandalf
« Reply #20 on: Mar 6th, 2003, 6:52am » |
Quote Modify
|
on Mar 6th, 2003, 6:26am, David Ryan wrote:| however, how do we know it doesnt just cut a corner? an insanely small portion of the wire actually on sma's grounds? |
|
Well, this could indeed be the case.
Quote:| can this be determined without digging 3 sides? please tell me if it can, and explainor draw, but give soemthing other than just the numbers. |
|
What do you mean by "3 sides"?
A total length of less than 3? - Yes. The two diagonals of the unit square of length 2sqrt(2) can achieve that.
Less than three ditches (= straight lines)? - Not if you want to attain the minimal length. I'd guess the two diagonals would be best if you're only allowed at most two lines.
If you're just desperate for a drawing, follow the link (spoiler!) in Kozo's post. Maybe you can come up with other (suboptimal, but who cares?) solutions using totally different configurations after seeing an example.
Quote:| again, i apologize for the copying error. |
|
No problem. 
|
| « Last Edit: Mar 6th, 2003, 6:56am by wowbagger » |
IP Logged |
"You're a jerk, <your surname>!"
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Samwise & Gandalf
« Reply #21 on: Mar 6th, 2003, 11:43am » |
Quote Modify
|
David, your thought on it crossing the corner illustrated one of the concepts that all of the above ideas had in common. Whatever the design, lines MUST intersect with every one of the four corners to cover this.
That leads to an interesting thought... can the optimal design be expanded to any regular polygon? Or perhaps easier, what are the optimal solutions for an equilateral triangle and regular pentagon?
My guess for the triangle is: the same as with the square, minus the floating line.I will have to think about the pentagon.
|
|
IP Logged |
|
|
|
aero_guy
Senior Riddler
Gender:
Posts: 513
|
|
Re: Samwise & Gandalf
« Reply #22 on: Mar 6th, 2003, 12:00pm » |
Quote Modify
|
Oooh! nifty. I think the optimal solution does expand very nicely to an arbitrarily many sided polygon. Even expands nicely to infinity, a circle.
|
|
IP Logged |
|
|
|
Icarus
wu::riddles Moderator
Uberpuzzler
Boldly going where even angels fear to tread.
Gender:
Posts: 4863
|
|
Re: Samwise & Gandalf
« Reply #23 on: Mar 6th, 2003, 4:47pm » |
Quote Modify
|
Perhaps I am being a little thick here, but how does the answer extend to a circle? Since Sauron's line can intersect the cirlcle in a slice barely deeper than a tangent, Sam's trench must cover every point on the perimeter, so his best possible answer here is to dig out the perimeter itself. How is this an extension of answer above.
(Actually, I am definitely being thick, since whatever form the optimal answer takes, it should reasonably be expected to converge to the optimal answer for the limit of the polygons.)
|
| « Last Edit: Mar 6th, 2003, 5:43pm by Icarus » |
IP Logged |
"Pi goes on and on and on ...
And e is just as cursed.
I wonder: Which is larger
When their digits are reversed? " - Anonymous
|
|
|
cho
Guest
|
I'm sure it extends to the circle simply in the sense that it was established that you must minimally have a line beginning at every corner of the shape. And since a circle is viewed as a polygon with infinite corners, every point on the circle must be part of the line.
I'm wondering how else the optimal solution extends to other polygons. I suppose you could perhaps make 2 rules.
1. The line from each corner must either extend straight toward the center as far as the midpoint between the 2 adjacent corners, or it must intersect other lines.
2. All intersections will be 3 lines coming together at a 120 degree angle.
At least that's what the square and triangle cases would seem to suggest. Is that necessarily optimal? Can it be demonstrated? Does the solution for larger polygons flow simply out of those 2 rules?
What's the optimal for a pentagon? Those rules might suggest 2 solutions. Either a line joining corners A,C, and D at a point fairly close to CD, plus 2 short disconnected lines at B and E. Or maybe a set of lines joining corners A,B, and C at the proper angle and another set of lines joining C,D, and E.
I haven't figured out the totals for either of those solutions, but, jotting the lines down on paper, the first looks shorter, yet it's the second that would seem to be implied by your suggestion that there is such a simple expansion of the idea to infinity.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove