Author |
Topic: Searching for a friend (Read 3551 times) |
|
nothing_
Newbie
Posts: 22
|
 |
Searching for a friend
« on: Mar 20th, 2008, 7:12pm » |
 Quote  Modify
|
You are standing at a crossing from where there emerge four roads extending to infinity. Your friend is somewhere on one of the four roads. You do not know on which road he is and how far he is from you. You have to walk to your friend and the total distance traveled by you must be at most a constant times the actual distance of your friend from you. In terminology of algorithms, you should traverse O(d) distance, where d is the distance of your friend from you.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Searching for a friend
« Reply #1 on: Mar 21st, 2008, 1:44am » |
Quote Modify
|
Walk 2i miles up road i mod 4, until you meet your friend.
Or buy a pair of binoculars and look for him first.
|
| « Last Edit: Mar 21st, 2008, 1:44am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pscoe2
Junior Member
Gender:
Posts: 77
|
|
Re: Searching for a friend
« Reply #2 on: Mar 22nd, 2008, 10:53pm » |
Quote Modify
|
u just have to walk 1 mile in 1 direction come back goto another and like this check in all directions...
if you dont find him go double next time and keep doing this all the time till you find your friend
max distance travelled=4d+4*2*d/2+4*2*d/4.....+4*2*1=12d
so it is always O(d)
|
|
IP Logged |
|
|
|
johny_cage
Full Member
Gender:
Posts: 155
|
|
Re: Searching for a friend
« Reply #3 on: Mar 25th, 2008, 1:58am » |
Quote Modify
|
@nothing_
this is not a CS problem, please post this type of puzzles into the Puzzles category...
Thank,..
Johny
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Searching for a friend
« Reply #4 on: Mar 25th, 2008, 9:20am » |
Quote Modify
|
on Mar 25th, 2008, 1:58am, johny_cage wrote:@nothing_
this is not a CS problem, please post this type of puzzles into the Puzzles category...
Thank,..
Johny |
|
Isn't it common problem in robotics? Just kidding 
But the complexity issue is interesting here ... minimize the worst ratio of frends actual distance and your traveled path.
(Actually it's very simillar to walking around wall except there are 4 ways instead of just 2).
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Searching for a friend
« Reply #5 on: Mar 25th, 2008, 2:27pm » |
Quote Modify
|
Regarding the "best worst case" question:
Assuming the searched distance increases by a factor r each time. You will start by infinitely small and infinitely many short trips until you almost reach your friend. The worst case is when you just arrive to an epsilon of your friend and turn back. The distance travelled is almost
... + 2d/r3 + 2d/r2 + 2d/r + d
You then do a last round and travel
d + 2dr + 2dr2 + 2dr3 + d
where you meet the friend.
Summing all that gives
D = 2d·r3·r/(r-1) + d
A minimum can be found at r = 4/3.
From there you can compute D/d = 539/27 or almost 20
If I haven't made a mistake somewhere.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Searching for a friend
« Reply #6 on: Mar 25th, 2008, 3:45pm » |
Quote Modify
|
Grimbal: good job, easily generalised result is for k-ways from the origin (the wall has k=2 and optimal r was 2 minimising r2/(r-1)) .... minimise rk/(r-1) ... 0=(krk-1(r-1)-rk)/(r-1)^2 ... (k-1)rk=krk-1 ... (k-1)r=k ... r=k/(k-1)
|
| « Last Edit: Mar 25th, 2008, 3:47pm by Hippo » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print