wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Samwise & Gandalf
        
(Message started by: jabhiji on Feb 13th, 2003, 2:01pm)
Title: Samwise & Gandalf
Post by jabhiji on Feb 13th, 2003, 2:01pm
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" ?
Title: Re: Samwise & Gandalf
Post by SWF on Feb 13th, 2003, 5:10pm
There is a way of length [hide]1+sqrt(3)[/hide], but I see an even shorter method.
Title: Re: Samwise & Gandalf
Post by jabhiji on Feb 13th, 2003, 6:02pm
I initially came up with 2.7071 but it is not the minimum.  
Title: Re: Samwise & Gandalf
Post by aero_guy on Feb 14th, 2003, 1:56am
Nifty puzzle,  jabhiji.  The L=3 answer Same gives seems to be the most inuitive, but only slightly less so is the [hide]2*sqrt(2)[/hide] answer.  When you realize that that was only a subcase of a wider set of answers you get SWF's [hide]1+sqrt(3)[/hide].  This is also a subset of another wider category, which gives a slightly better answer [hide]2.722, three connected lines two unconnected lines[/hide].  I used an interestingly different configuration [hide]five unconnected lines[/hide] to get an answer of [hide]2.728[/hide].  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!
Title: Re: Samwise & Gandalf
Post by poseur on Feb 14th, 2003, 5:11am
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.
Title: Re: Samwise & Gandalf
Post by jabhiji on Feb 14th, 2003, 9:07am
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. "
Title: Re: Samwise & Gandalf
Post by aero_guy on Feb 14th, 2003, 5:00pm
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 [hide]13sqrt(2)/14 -2/7 +2*sqrt(29+2sqrt(2))/7 or 2.64[/hide].  Any answer better than this would require a completely different configuration.
Title: Re: Samwise & Gandalf
Post by SWF on Feb 14th, 2003, 5:09pm
How about 2.639 or

http://www.ai.rug.nl/~towr/PHP/FORMULA/formula.php?md5=6827f0d29afe7f0c0d92a716eabfd518

(Edited to fix the equation after towr's equation generator broke)
Title: Re: Samwise & Gandalf
Post by aero_guy on Feb 14th, 2003, 5:36pm
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?
Title: Re: Samwise & Gandalf
Post by jabhiji on Feb 14th, 2003, 6:34pm
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.
Title: Re: Samwise & Gandalf
Post by aero_guy on Feb 16th, 2003, 2:51am
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.
Title: Re: Samwise & Gandalf
Post by jabhiji on Feb 16th, 2003, 5:50am
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.
Title: Re: Samwise & Gandalf
Post by aero_guy on Feb 16th, 2003, 7:49am
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?
Title: Re: Samwise & Gandalf
Post by Kozo Morimoto on Feb 20th, 2003, 5:05pm
Is the solution at this site the optimal?

http://www.highiqsociety.org/common/puzzles/solution05.htm
Title: Re: Samwise & Gandalf
Post by aero_guy on Feb 21st, 2003, 9:27am
As near as we have been able to figure.
Title: Re: Samwise & Gandalf
Post by Chronos on Feb 24th, 2003, 5:03pm
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).
Title: Re: Samwise & Gandalf
Post by David Ryan on Mar 6th, 2003, 4:08am
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.
Title: Re: Samwise & Gandalf
Post by wowbagger on Mar 6th, 2003, 5:14am

on 03/06/03 at 04:08:01, 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.
Title: Re: Samwise & Gandalf
Post by aero_guy on Mar 6th, 2003, 5:24am
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.
Title: Re: Samwise & Gandalf
Post by David Ryan on Mar 6th, 2003, 6:26am
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.
Title: Re: Samwise & Gandalf
Post by wowbagger on Mar 6th, 2003, 6:52am

on 03/06/03 at 06:26:13, 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 (http://www.highiqsociety.org/common/puzzles/solution05.htm) (spoiler!) in Kozo's post (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1045173700;start=0#13). 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.  :)
Title: Re: Samwise & Gandalf
Post by aero_guy on Mar 6th, 2003, 11:43am
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: [hide]the same as with the square, minus the floating line.[/hide]I will have to think about the pentagon.
Title: Re: Samwise & Gandalf
Post by aero_guy on Mar 6th, 2003, 12:00pm
Oooh! nifty.  I think the optimal solution does expand very nicely to an arbitrarily many sided polygon.  Even expands nicely to infinity, a circle.
Title: Re: Samwise & Gandalf
Post by Icarus on Mar 6th, 2003, 4:47pm
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.)
Title: Re: Samwise & Gandalf
Post by cho on Mar 6th, 2003, 6:09pm
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.
Title: Re: Samwise & Gandalf
Post by Chronos on Mar 7th, 2003, 9:57am
The second point (all intersections of lines must be three lines meeting at 120 degrees) is, in fact, optimal, though I'm not sure of the proof of it.  It showed up in one of the "Hard" puzzles, as well (draw a network of minimum total length to connect a set of points).

As for the expected value problem, I think it's safe to say that the probability of any given line is directly proportional to the length of its intersection with the plot of land, and then we should be able to normalize.
Title: Re: Samwise & Gandalf
Post by aero_guy on Mar 7th, 2003, 1:09pm
The problem with that reasoning on probabilities is that you have an infinite amount of finite lines, so you can't represent them as a portion of the infinite whole.

As to the two points, that is the general idea.  You do have a couple problems though.  First, your pentagon solution with two lines hanging by themselves does not prevent all of Sauron's possible lines.  The general form is that if there is an odd number of sides you will have groups of three lines at 120 degree angles each covering two adjacent edges, while one edge is left open.  If the number of sides is even, you will have the same thing, but with a single line extending in between two uncovered edges, just long enough to separate them.

One last note, for an octagon or above you will no longer have the three lines intersecting, but rather two lines along the edges, since the three points form too obtuse of an angle to make it possible.  Here is where it really starts to look like the solution for the circle, with the one or two uncovered sides getting smaller and smaller as the number of sides increases.

At least that is what I cam up with.
Title: Re: Samwise & Gandalf
Post by Icarus on Mar 7th, 2003, 3:48pm
To show the 120o result, just note that if you move the intersection point a little off the 120o position, the sum of the line lengths increases. This shows at least that the 120o solution is a local minimum.
Title: Re: Samwise & Gandalf
Post by cho on Mar 7th, 2003, 3:51pm
I believe my pentagon solution does work. Maybe I didn't describe it well.
Picture a pentagon with A at the top and CD at the bottom.
Draw a line straight down from A until you can turn 120 degrees to hit C and D. Those three lines block anything from CD going anywhere and from DE or EA to AB or BC. A short, disconnected line from E to the midpoint of the imagined line AD blocks anything from DE to EA. Ditto with the B short line. Where can Sauron dig?
And with the hexagon, did you consider having corners A, C, and E meet at the center and corners B, D, and F have a short disconnected line to the midpoint of the adjacent corners?
Title: Re: Samwise & Gandalf
Post by SWF on Mar 7th, 2003, 6:13pm

Quote:
...the shortest length of road to connect three points consists of an intersection at 120 deg, howsoever those points are arranged.



Quote:
The second point (all intersections of lines must be three lines meeting at 120 degrees) is, in fact, optimal,


What if the three points are the vertices of an isosceles triangle with apex angle 140 degrees?

Aero_guy, I don't think your general solution is giving optimal lengths, and your approach to getting a 120 degree intersection from adjacent vertices breaks down on the hexagon, not the octagon.  Also, cho's suggestions are valid routes but not optimal.

Using Aero_guy's approach to a pentagon I get a length of 3.978, and 3.580 with cho's route.  I see a way giving length 3.528.

For the hexagon, with Aero_guy's 'octagon' suggestion and the different route suggested by cho, it looks like they give the same length of 4.5. There is a way to get length of 4.464.

I haven't looked at either of these cases closely enough to convince myself given are optimal.
Title: Re: Samwise & Gandalf
Post by Icarus on Mar 7th, 2003, 7:48pm
Hmmm...That wasn't very nice of you, SWF! It seems I had forgotten that the 120o rule has exceptions. :-[
Though I also failed to notice that aero_guy had already mentioned it as well!
Title: Re: Samwise & Gandalf
Post by jabhiji on Mar 8th, 2003, 3:35pm
On the extension of the problem where Sam's plot of land is a unit circle, the optimum answer for the original question seems to be 2 + pi. Is there something shorter ?
Title: Re: Samwise & Gandalf
Post by Icarus on Mar 9th, 2003, 11:15am

on 03/08/03 at 15:35:28, jabhiji wrote:
On the extension of the problem where Sam's plot of land is a unit circle, the optimum answer for the original question seems to be 2 + pi. Is there something shorter ?

I'm not sure how you get 2 + pi. As far as I can see, the shortest possible trench guaranteed to hit the line is to dig out the circumference of the circle. If all the trenches are on his own property (his neighbor, Farmer Maggot, will sic the dogs on him if Sam goes digging up Maggot's fields), then leaving any stretch of the circumference undug allows for a line just inside from being tangent to the circle to miss any interior trenches. I don't see how exterior trenches could catch every line with less length than the circumference either (though that one I can't prove).

The Length depends on what dimension of the circle you are taking to be 1. If the circle has diameter 1, then the optimal answer is PI, less than yours. If the circle has radius 1, then the optimal answer I get is 2*PI, greater than yours.
Title: Re: Samwise & Gandalf
Post by aero_guy on Mar 9th, 2003, 12:17pm
Hmm, some interesting points.  First, SWF you are right, it breaks down on the hexagon, my mistake.  Second, yup they are not optimal, though they are nice and easy.  Third, it is interesting to note that for some of these you can get smaller digging lengths if you can dig outside your property.  Lastly, cho you are right, I was misinterpreting what you were saying.  Your new description clears it up.

So, it looks like there is no simple way to expand these things.  Dang, I like it when it comes out that way.  Oh well.  Still, we are no closer to telling Sam the order in which he should dig.
Title: Re: Samwise & Gandalf
Post by jabhiji on Mar 9th, 2003, 12:49pm
You can get 2 + pi for the circle radius = 1.

The answer will be 2*pi if Sam digs along the circumference. But he can do better, although at the cost of incurring the wrath of his neighbour, Farmer Maggot.
Title: Re: Samwise & Gandalf
Post by Icarus on Mar 10th, 2003, 5:59pm
Okay - I suppose that would work - but Maggot's wrath is not to be faced idly! Maggot has been known to have his dogs chase young hobbits all the way to Bucklebury ferry, for no worse crime than eating a few of his mushrooms! Maybe a little extra digging is the wiser course...  ;)
Title: Re: Samwise & Gandalf
Post by DrOctopus on Mar 16th, 2003, 9:50pm
Hey, I don't know anything about math. I'm just practical. Hasn't anyone thought of this stuff?

1) Start at the center and dig a wide spiral outwards. I don't know if that is what all you are saying (2xsqr4unit3halfx4 - Wha??) or the exact math to it, but pictured in my head it makes sense. (Bees dance in a spiral, by the way)

2) Dig a straight line accross your land parallel to Lord Sauron's haunt. It seems to make sense that the line would run as a straight line from point A to point B. If it was necessary to put the line through Sam's land, point B must be on the other side of his land to Sauron's haunt. Using a bit of logic, Same could figure out where to dig the straight line. (I hope that made sense)

3) Dig a circle around the houses of the hobbits on the other side of Sam's property to Sauron's haunt, if it is low enough.

4) If Gandalf is this great, brilliant wizard, make him do it. In fact, if he knows enough that it is under Sam's property, make him locate the damn thing exactly. "It runs under your property, Sam." Can't he do any better than that?

5) What does the powerful white wizard Lord Sauron need with a telephone line? Can't he just use a magic mirror or somthing?
Title: Re: Samwise & Gandalf
Post by aero_guy on Mar 17th, 2003, 9:33am
1) A spiral is roughly equivalent to a big circle with lots of smaller circles inside.  The smaller ones are therefore useless.  We have shown that you can dig much less of a distance than a circle would require.

2) We don't know where the line will terminate or where it started, just that it crosses Sam's property.  We don't even know if it is a straight line when it is off of Sam's property.

3) We don't know which house is sending the message.

4) Gandalf, while reading over old Hobbit texts discovered an odd entry where it stated than Sam's gaffer's father allowed a certain fellow hobbit to dig a straight line across his property for 'undisclosed' reasons.  Gandalf, being the wise wizard that he is, has pieced together odd tidbits of info to tell him that it was a telepone line for passing secret messages.  No record exists of exactly where the trench was dug.

5) Because there is no Palantir in the shire, and the evil hobbits need to be able to send messages faster than even a flying Nazgul can carry them.
Title: Re: Samwise & Gandalf
Post by Icarus on Mar 17th, 2003, 4:59pm
Also: Saruman The White was the wizard who was ensnared by lust for the ring. Sauron is the Dark Lord of Mordor & Lieutenant of Morgoth before Morgoth was defeated by the Valar and banished from Middle-Earth.

Since Mordor is hundreds of leagues south and east of the Shire, on the other side of two great mountain ranges, and the miles wide river Anduin, it is unlikely this cable was run in anything resembling a straight line all the way!
Title: Re: Samwise & Gandalf
Post by DrOctopus on Mar 20th, 2003, 12:23pm
Er... May the force be with you?
Title: Re: Samwise & Gandalf
Post by DrOctopus on Mar 20th, 2003, 12:34pm
Seriously, are you saying he just digs and X from the four corners? I'm confused.
Title: Re: Samwise & Gandalf
Post by ThyGod on Oct 13th, 2004, 10:50am
WHy does he not just dig a straight line from each opposite corner to the other? that way, he only digs 2 lines. Maybe i'm wrong, but it seems like it would work.
Title: Re: Samwise & Gandalf
Post by Icarus on Oct 13th, 2004, 7:35pm
This will work, but it is longer than optimum. The two diagonals are each 1.414 in length, for a total length of 2.828. The apparent optimum is 2.639 in length (see the link in Kozo's post).
Title: Re: Samwise & Gandalf
Post by Lewis Temple on Dec 9th, 2004, 4:00am
OK, I came up with just 2, if you dig across the top and don't find it then you dig down one side, you will find it there since it runs straight.
Title: Re: Samwise & Gandalf
Post by rmsgrey on Dec 9th, 2004, 8:20am
That still leaves phone lines passing through the two sides you haven't touched - pick a (non-corner) point on each, and the straight line connecting them won't pass through either ofthe other sides.
Title: Re: Samwise & Gandalf
Post by Icarus on Dec 9th, 2004, 9:21am
For example:
Title: Re: Samwise & Gandalf
Post by Grimbal on Aug 31st, 2006, 12:55am
Interestingly, you can solve the circle with a length of 6.12363581, less than 2·pi.
Title: Re: Samwise & Gandalf
Post by SMQ on Aug 31st, 2006, 5:41am
I'd be interested to see that, Grimbal!

Also, incidentally, the link from Kozo's post no longer works, and the puzzle to shich it was an answer does not appear on the site any more.  Does anyone else have a diagram of the optimal answer?

[edit]I assume this is the figure being discussed as optimal: Warning: Spoiler (http://www.dwarfrune.com/~smq/wu/sam_gamgee.gif)[/edit]

--SMQ
Title: Re: Samwise & Gandalf
Post by Grimbal on Aug 31st, 2006, 1:20pm
For the Samwise circle, click here! (http://florian.net/puzzle/pic/SamwiseCircle.gif)

And If my calculations are correct, it can even go down to  5.2253629465 (warning: spoiler) (http://florian.net/puzzle/pic/SamwiseCircle2.gif).
Title: Re: Samwise & Gandalf
Post by SMQ on Aug 31st, 2006, 1:36pm
Confound Cantor sets strike again... :D

--SMQ
Title: Re: Samwise & Gandalf
Post by Icarus on Aug 31st, 2006, 3:31pm
My memory is shaky, but yes, I believe SMQ's picture is the optimal solution for the square.
Title: Re: Samwise & Gandalf
Post by alien on Sep 5th, 2006, 10:49am
Maybe I didn't read the riddle carefully enough, as I just glanced at it, but it looks to me that a [hide]diagonal[/hide] solution is optimal? Just [hide]connect two corners in the straight line[/hide], and bingo. But I am more of a visual guy, so if someone sketched the optimal solution, I sure would like to see it.   ::)
Title: Re: Samwise & Gandalf
Post by Grimbal on Sep 5th, 2006, 2:40pm
Straight doesn't mean horizontal or vertical.
With a diagonal, you still could cut the one or other corner.
Title: Re: Samwise & Gandalf
Post by Icarus on Sep 8th, 2006, 4:42pm

on 09/05/06 at 10:49:19, alien wrote:
But I am more of a visual guy, so if someone sketched the optimal solution, I sure would like to see it.   ::)


Follow the link in SMQ's post (http://www.dwarfrune.com/~smq/wu/sam_gamgee.gif) to see the sketch he kindly has put up for us.
Title: Re: Samwise & Gandalf
Post by A-man on Dec 15th, 2006, 12:07am
Would someone please post the diagram that used to be at highiqsociety with the solution of L=2.6389, best I can do is 2.73205.  Thanks!
Title: Re: Samwise & Gandalf
Post by SMQ on Dec 15th, 2006, 6:08am
The brown text in Icarus' post above is a link to the diagram of the solution.

--SMQ
Title: Re: Samwise & Gandalf
Post by THUDandBLUNDER on Dec 15th, 2006, 5:25pm

on 12/15/06 at 00:07:02, A-man wrote:
Would someone please post the diagram that used to be at highiqsociety with the solution of L=2.6389, best I can do is 2.73205.  Thanks!

This?
Title: Re: Samwise & Gandalf
Post by Drokles on Sep 16th, 2011, 3:38am

on 03/07/03 at 13:09:28, aero_guy wrote:
The problem with that reasoning on probabilities is that you have an infinite amount of finite lines, so you can't represent them as a portion of the infinite whole.


Hello! Sorry for reviving this old thread but I saw it after searching for a while and it's actually a very interesting problem.
Now, I actually think it's perfectly reasonable to work out some expressions that are useful in determining the probability. I don't see it as a problem that there's an infinite amount of possible lines, the probability for finding each of them just becomes infinitesimal.
Now first of let's denote by P(a)da the probability of the line described by y = a*x + b, where (x,y) starts in the left most lower corner as (0,0) and ends in the upper most corner of Sams plot as (1,1), having a value of a in the interval [a, a+da]. We can also do P(b)db. Then we have all the necessary parameters for describing all kinds of different straight lines.

We can now require that int(P(a)da from -infty to infty) = 1, and that int(P(b)db from -infty to infty) = 1 as well, so they are normalized, meaning that for a straight line we are considering, the probability of it having a value for a and a value for b is one.
Now, since the value of b doesn't actually have to be between 0 and 1 ( you can easily imagine a line on Sam's plot that doesn't actually intersect the left side of the plot (which I only realized while writing just now, so I don't have a solution for P(b) after all >_< )), it's difficult to figure out how to determine P(b)db.

P(a)da however can be determined if we just say that there's an equal probability of the line having any possible angle of intersection with the y-axis. This seems a lot more reasonable and straightforward than working directly with a. It means that we can instead consider P(T) = C, T being the angle going from -pi/2 to pi/2. So all that remains is to determine C, and we'll require that int(P(T) dT, -pi/2, pi/2) = 1, which gives us C = 1/pi. If we want to obtain an expression for P(a)da, then we'll use the fact that a = arctan(T), so dT = 1/(a^2+1) da. We can now write P(T)dT = C dT = C/(a^2+1) da. (It looks like the absorption cross section's dependency of frequency for light absorption of atoms.) So let's say that P(a) -> (1/pi)/(a^2 + 1) (It's normalized from -infty to infty. I checked ;). We can still also use P(T) if we want to instead.
Unfortunately determining P(b) seems a little harder, but maybe we can use some other parameter than b?
Anyway, hope this helps a bit. I don't think we've hit a dead end just because we need to use infinitesimal quantities, but I may be on the wrong track of course.

The idea, after having an expression for P(b) as well is to establish a model for which portion of the possible values for the parameters we're "cutting off" by extending a single trench in one direction on Sam's plot. All it requires is that we make some reasonable assumption about the probability distribution for b, and then do some clever math when we try to see how big a probability we've effectively "cut off" by digging a small portion of a trench.
Title: Re: Samwise & Gandalf
Post by malchar on Sep 20th, 2011, 1:40pm
I don't think that I quite understand the previous post about probability. I'm not sure what P(a) refers to, or why we need to find it.

My thoughts are to examine each dig line in the solution. For each of the points along those dig lines, look at how many possible telephone locations could pass through it. Of course, while you dig the first line, each point has an equal number of telephone locations associated with it. But, when you start digging the second line, each point on that dig line will have less possible telephone locations since some have already been ruled out by the first line. This is perhaps more apparent if you start from the end. If you already have all the dig lines drawn and then start "erasing" one of them, the first point on any line that you "erase" will allow for only one possible telephone location, and then the numbers will increase from there.

The question is, does the order of digging matter? My intuition says yes because the solution is not symmetrical with respect to the shape of the farm field.

So, for each dig line in the solution, we want to look at all the possible telephone locations that pass through that dig line. But we also want to take note of the telephone locations that pass through multiple dig lines, since digging one of those lines would exclude the possibility of the telephone being there when you dig the second line. Of course, the second line is still eliminating some possibilities at each step, but perhaps not as many as the original line was.

I see that the above post mentions that the solution is probably some function of pi. This makes sense. At any point along a dig line, the set of telephone locations that pass through it form a circle centered at that point, which corresponds to having T range from -pi/2 to pi/2 as in the above post.

Now, this problem appears to be somewhat similar to another problem I saw on here a while ago which had to do with dropping a pin (on its side) onto a piece of graph paper and finding the probability that it intersected one of the grid lines. I believe that solution was also a function of pi.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board