|
Well, it's been a while since I put these puzzles up. But I never finished the fortnight and it's been bugging me. So here's another puzzle. Hopefully I can find four more good ones to finish this collection.
I posted this one in the Riddles thread, but it's more of a brainteaser/math puzzle and doesn't really fit in as a 'riddle'.
So here it is:
On June 11 2011 12:06 JeeJee wrote:Quite well done. Here's another riddle, more of a math puzzle, from the same source: TheAnswerIsZero, upon answering JeeJee's riddle correctly, won a square plot of land, each side being one unit. Today, his lawyer informs him that some jerk built a pipe running under his plot of land without TAIZ's permission! This pipe runs in a straight line, parallel to the ground, and passes beneath his plot of land somewhere, but he doesn't know where. TAIZ doesn't like this of course, so he plans to dig up the perimeter of his land, 4 units, to discover this pipe. His lawyer says, "It's not necessary to dig the entire perimeter!" "Ah, I know what you mean" Taiz replies. "I can just dig 3 sides and still discover it, since even if it runs through the fourth side, I will find it at the other end point! Only 3 units!" Lawyer shakes his head. "You're on the right track, but you can do better than that" What optimal solution does the lawyer have in mind? edit: some sample images of how the pipe could run since apparently the explanation isn't very good? + Show Spoiler +![[image loading]](http://i.imgur.com/OGqnF.png) Just a straight line through the square somewhere. Naturally you can dig anywhere in the square, not just the perimeter.
Best of luck 
Various Solutions
Solutions ordered by length from best to worst. Don't click if you don't want to be spoiled, naturally.
1. Optimal?
+ Show Spoiler +As far as I'm aware, Kantom's Optimized by Hamster1800 is optimal. Not 100% sure though, and would love to be proven wrong. It is the solution I had in mind.
2. Kantom's Optimized -- by Hamster1800
+ Show Spoiler +sqrt(2)/2 + 2*(sqrt(2/3)) + (1/sqrt(2) - 1/sqrt(6))
= sqrt(2) + sqrt(3/2)
2.639...
3. Kantom
+ Show Spoiler +
4. awu25's Optimized -- by Slithe, Zortch
+ Show Spoiler +4*(1/sqrt(3)) + (1-1/sqrt(3))
= 1+sqrt(3)
2.732...
5. awu25
+ Show Spoiler +
6. Default
+ Show Spoiler +
 
|
+ Show Spoiler +Two diagonal lines forming an X within the plot of land? A total of 2*sqrt(2) units.
|
My brain tells me the answer to this is probably + Show Spoiler +, but I can't figure out how to justify it quite yet.
I will edit this post if I can figure out a good reason for it.
|
+ Show Spoiler +![[image loading]](http://i.imgur.com/OtfUt.png) Digging along the red lines. 2 + 0.5*sqrt(2) comes out as slightly less than 2*sqrt(2) if my math is correct.
Is the best that I could come up with.
|
i spoiled myself in the riddles thread 
such an interesting optimization problem.
riddle me this is actually a good thread too.
|
@Rayeth
I would be quite impressed if you can manage such a solution. It's significantly better than what I have in mind. Unfortunately I don't think it's possible -- keep in mind the pipe doesn't have to run perpendicular to any sides or anything. Any angle would do, see the spoiler in OP for illustrations.
@awu
Good start! Not the optimal solution yet though
@Kantom
Ah, very clever. Still, it's possible to improve
I'll keep a leaderboard in the OP.
Kantom #1 now ^^
edit: yes if you spoiled yourself in the riddle thread please don't spoil it for everyone else here just yet. I edited out that solution for now
|
I couldn't think of anything better than the awu solution. Kantoum's solution is pretty nifty. I'm getting close to giving up soon :/
|
I optimized Kantom's solution to get the following:
+ Show Spoiler +
Let x = 1/2 - 1/(2*sqrt(3)). Label the square ABCD clockwise from the top left. Consider an x by x square at the top right, and draw the diagonal from B across it to a point E. Then draw AE, CE, and draw from D to the center of the square. This gives you one segment of length 1/sqrt(2), one of length 1/sqrt(2) - 1/sqrt(6), and two of length 2/sqrt(6), which gives you a total length of sqrt(2) + sqrt(3/2) = 2.6389...
My guess is this still isn't optimal, but it beats the current best ^^. My best lower bound for the answer is 2, although I am pretty sure that it's not attainable.
|
Oh using the same idea as Hamster's optimization we can do something similar to other solution.
+ Show Spoiler +Instead of having an exact X, we can create an extended shape like this (too lazy to upload picture):
>-<
I dunno if I calculated right but I'm getting a total length of 1+sqrt(3)
|
+ Show Spoiler +Slithe's solution above (once minimized with basic calculus) is optimal among all connected solutions (connected meaning that once you are in the trench you can walk to any other point in the trench without leaving it). However, I don't know how to prove that it is optimal over all solutions that may not be connected like Kantom's above.
|
Ah, quite impressive.
Hamster indeed brought up the solution I had in mind. If you don't mind me asking, how did you come up with that x? The way I came about the solution was forcing a 120degree angle intersection between the 3 lines and calculating the distances from there.
I updated the leaderboard (although it's not really a leaderboard, more of a who thought of what solution)
|
I just wrote down the lengths in terms of x, differentiated, and set the derivative equal to 0, which becomes a quadratic equation. We should collectively try to improve it or prove that it is optimal. First question: Can anyone prove a lower bound better than 2?
|
Consider this shape:
![[image loading]](http://img829.imageshack.us/img829/301/unledvae.png)
Where t is half the distance of the horizontal red line. And everything is nice and regular .
Then we can write the equation for the length of the red trench and minimize, which I have done on wolfram: http://www.wolframalpha.com/input/?i=minimize 2(2((1/2-t)^2+(1/2)^2)^1/2 +t)
So once we use calculus to find the minimum it turns out to be 1+sqrt(3)=2.732...
Unless I have made some error?
|
consider the bottom left "example"
theoretically the pipe could intersect a corner and not exist anywhere else in the square
therefore, the only way to GUARANTEE finding it is to cut along perimeter. = 4.
|
On June 14 2011 11:10 annul wrote:
consider the bottom left "example"
theoretically the pipe could intersect a corner and not exist anywhere else in the square
therefore, the only way to GUARANTEE finding it is to cut along perimeter. = 4.
Hmm? I think there is some misunderstanding. Can you explain your reasoning further?
|
On June 14 2011 11:00 Zortch wrote:Consider this shape: Where t is half the distance of the horizontal red line. And everything is nice and regular . Then we can write the equation for the length of the red trench and minimize, which I have done on wolfram: http://www.wolframalpha.com/input/?i=minimize 2(2((1/2-t)^2+(1/2)^2)^1/2 +t)So once we use calculus to find the minimum it turns out to be 1+sqrt(3)=1.732... Unless I have made some error?
Indeed that's correct, it's an optimization of the X approach. Don't forget to add the one though, final answer 2.732..
@Hamster
I'm working on a lower bound but it's tricky =(
I'm not a math wiz by any means, most of my solutions are intuitive and lower bound work isn't my area of expertise, it's not really "intuitive" per se
That said, there are some really smart people here...
*nudge nudge*
|
On June 14 2011 11:19 Zortch wrote:Show nested quote +On June 14 2011 11:10 annul wrote:
consider the bottom left "example"
theoretically the pipe could intersect a corner and not exist anywhere else in the square
therefore, the only way to GUARANTEE finding it is to cut along perimeter. = 4. Hmm? I think there is some misunderstanding. Can you explain your reasoning further?
edit: nevermind, im a dumb
|
Nvm. Late night = fail solving.
Hm didn't notice this was a blog post. Posted in the other thread.
+ Show Spoiler +For a square ABCD, dig up from A to midpoint of CD then from midpoint of CD to B. Gives 2*sqrt(1^2+0.5^2) = 2.23 units
|
On June 15 2011 14:12 Cremali wrote:Nvm. Late night = fail solving. Hm didn't notice this was a blog post. Posted in the other thread. + Show Spoiler +For a square ABCD, dig up from A to midpoint of CD then from midpoint of CD to B. Gives 2*sqrt(1^2+0.5^2) = 2.23 units
I'm afraid that doesn't work
See here:
+ Show Spoiler +
Where black is the square, red is your digging and blue is the potential pipe case not covered by your solution
|
On June 14 2011 06:52 Hamster1800 wrote:I optimized Kantom's solution to get the following: + Show Spoiler +
Let x = 1/2 - 1/(2*sqrt(3)). Label the square ABCD clockwise from the top left. Consider an x by x square at the top right, and draw the diagonal from B across it to a point E. Then draw AE, CE, and draw from D to the center of the square. This gives you one segment of length 1/sqrt(2), one of length 1/sqrt(2) - 1/sqrt(6), and two of length 2/sqrt(6), which gives you a total length of sqrt(2) + sqrt(3/2) = 2.6389...
My guess is this still isn't optimal, but it beats the current best ^^. My best lower bound for the answer is 2, although I am pretty sure that it's not attainable.
Could someone please illustrate this?
EDIT: Image should say ".4" not just "4"
My contribution. I think blue can be less than .4. Perhaps even as low as .25
![[image loading]](http://i.imgur.com/9J3IR.png)
|
|
|
|
|
|
EPT![[image loading]](http://i.imgur.com/Pe7fD.png)
![[image loading]](http://i.imgur.com/9tNvY.png)
