Lazy Walking Strategy Puzzle
Source: Quantnet Interview Questions
Problem: You are standing on the middle of a East-West street. A row of closed doors in front of you, and you have a key on hand which can only open one specific door. Compose a strategy so that X/N is least under the worst situation. X is the distance you covered when arriving at the correct door. N is the distance between the door and the original point.
Problem: You are standing on the middle of a East-West street. A row of closed doors in front of you, and you have a key on hand which can only open one specific door. Compose a strategy so that X/N is least under the worst situation. X is the distance you covered when arriving at the correct door. N is the distance between the door and the original point.
go to one end of street from midpoint, then turn back to the other end point, opening each new door that comes on the way. Worst case X/N = 3 (the door might be on other end, so we traversed thrice that distance)
ReplyDeleteAbove strategy is worst case infinite. Since the worst case wont occur for the door at the end but for first door on the other side, so this door is at a distance 1 from midpoint and X=2n+1 (n is number of door on one side) , and N=1; so X/N is potentially unbounded.
ReplyDeleteIt can be seen that all the possible path can only be of type east-west-east-west-east type. If we want to optimize the worst case situation, then worst case only occur for the first new door that he encounters while going in east or in west direction, for subsequent doors he opens X/N will keep decreasing.
Also, when he encounters first new door in one side, he must immediately change the direction for reducing the worst case X/N of the door he'll encounter in other side. Hence, he should follow 1east-2 west-3east-4 west and so on
X/N = (1+2+3+4+5+6.../1-2+3-4+5..) = 2N-1 for N on east+ve,-(2N+1) for N on west,(-ve)
call your current position 0, 1 being just to right and -1 being just to left.
ReplyDeleteHere is what you do: go to 1, then -1, then 2, -2, 4, -4, etc. until you reach the door you want.
Suppose correct door is at +/- N, where m = 2^k is smallest power of 2 which is no less than N. Since we are going right first and then left, -N is the worse case. Total distance travelled here, X = 2(2m-1) + 2(m-1) + N = 6m - 4 + N.
X/N = 6m/N - 4/N + 1 <= 12 + 1 = 13. (m <= 2N)
We see we can get fixed bounds this way. Suppose now that instead of 2, we use powers of any general real number a > 1.
m = a^k
a^(k-1) = m/a < N <= m
X = 2 (1 + a + ... + a^k) + 2 (1 + a + ... + a^(k-1)) + N
= 2 (a^(k+1) - 1) / (a-1) + 2 (a^k-1)/(a-1) + N
= 2 (am-1)/(a-1) + 2(m-1)/(a-1)+N
X/N <= 2a^2/(a-1) + 2a/(a-1) + 1
= (2a^2+3a-1)/(a-1)
= 2a + 5 + 4/(a-1)
Let a-1 = b.
X/N <= 2b + 7 + 4/b.
On differentiating this function, we see that it has a minimum at b=sqrt(2)
Hence taking b = sqrt(2) (hence a = 1 + sqrt(2)), we get X/N <= 7 + 4 * sqrt(2), which is approximately 12.657, only slightly better than the 13 we got with a=2.
Don't know if a better bound may be obtained through some other method though
Actually X/N ratio could be kept at constant by increasing the distance exponentially .... 1,2,4,8 etc steps.
ReplyDeleteHave not solved the problem completely yet, so only stating the observation.
Break the moves into stages, where in each stage we move in only one direction. Let a_i denote the number of steps we move in the i-th stage.
ReplyDeleteIf we choose a_i = F_{i+2}, the (i+2)-nd Fibonacci number, then one can easily calculate X and N using the standard identities involving those numbers. In the (k+1)-st stage, the maximum value of X/N is achieved with
X = a_1 + a_2 + ... + a_k + a_k + 1 = F_2 + F_3 + ... + F_{k+1} + F_{k+1} + 1 = F_{k+3} + F_{k+1} - 1
and
N = |a_1 - a_2 + a_3 + ... + (-1)^k a_{k-1}| + 1 = F_k + 1.
Again using the recurrence relation, we get X/N = 1 + (3F_{k+1} - 2)/(F_k+1). Since F_{k+1}/F_k tends to the golden ratio g as k tends to infinity, the limit of this ratio equals 3g + 1. With this guess, one can then easily show by induction that (3F_{k+1} - 2)/(F_k+1) < 3g + 1 for all k > 1.
This shows that 3g+1 (which roughly equals 5.85409) is an upper bound. Of course, this line of thought does not shed any light on how to find a lower bound.
Move 1 step left, a steps right, then a^2 steps left, etc.
ReplyDeleteWorst case is that point is just beyond one of the boundaries. Suppose you reach it on the (k+1)th iteration.
X = 1+a+a^2+...+a^(k-1)+a^k+a^k1
= (a^k-1)/(a-1)+2a^k+1
= (2a^(k+1)-a^k+a-2)/(a-1)
N = |1-a-a^2+...+(-a)^(k-1)|+1
= |1+(-a)^k|/(1+a)+1.
We are worse off when N is smaller, so in the worse case N = (a^k-1)/(a+1)+1
= (a^k+a)/(a+1)
X/N = [(2a^(k+1)-a^k+a-2) * (a+1)]/[(a-1) * (a^k+a)]
As k becomes large, we can ignore the piddi extra terms that come in addition to a^k type stuff. Then divide both num. and denom. by a^k
X/N ~ (2a - 1) (a+1) / (a-1).
= 2a+3 + 2/(a-1)
This has min. value of 9 when a is 2, by differentiation etc.
I disagree with Tejaswi's answer because on this line:
ReplyDelete> N = |a_1 - a_2 + a_3 + ... + (-1)^k a_{k-1}| + 1 = F_k + 1.
It seems that N looks a_(k-2), so F_(k-1)
Agree with wonderwice. Actually, my bad with the conventions. With F_0 = 0 and F_1 = 1, I should have written a_i = F_{i+1}. So with the correction wonderwice noticed, we would instead get 3g + 4 = 8.85409 as an upper bound.
ReplyDeleteTejaswi: Why 3g+4?. Shouldn't it be g(3g+1)? That comes to something like 9.472.
ReplyDeleteIf we go by the induction method, F_{k+3} + F_{k+1} = F_{k+2} + 2F_{k+1} = 3F_{k+1} + F_{k} = 4F_{k} + 3F_{k-1}. This way we get the ratio as 4g + 3, which is again 9.47213596.
Moreover, this is also what we get from the formula 2a+3 + 2/(a-1) with a being the golden ratio, because using the fibonacci series is for all practical purposes the same as using a geometrical series with the golden ratio being the common ratio.
Thanks for the solutions. Of course we have not found the lowest bound in the solutions. But the common framework in which all the solutions lie is that
ReplyDeleteCheck till R1. Then Check till L1. Check till R2. Then Check till L2. and so on.
If you get it in left hand side, X/N = (R1+L1+R2+L2... Li)/L(i-1)
If you get it in the right hand side,
X/N = (R1+L1+R2+L2+.. Ri)/R(i-1)
We have to find an efficient L and R functions.
I too tried a^n and F_n. Can we do better? Thanks
if the street is infinite, the best u can do is a ratio of 9. wonderwice has shown one way to reach this ratio of 9.
ReplyDeleteproof:
its clear that an optimal solution is of form p(1),p(2),p(3),..... where pis are all natural numbers and u move first to point p(1) units from origin on one side, then turn & go to a point p(2) units from origin on other side, and so on.
convince yourself that Worst case occurs at a point just beyond one of the turning points, say at a point distant p(r) +1 units from origin.
define S(r)=p(1)+p(2)+...+p(r)
distance travelled in reaching point p(r)+1 is = 1+p(r)+ 2*S(r+1).
the ratio is 1+ 2*S(r+1)/[p(r)+1].
we want to show that worst ratio >= 9, which is equivalent to showing that supremum S(r+1)/[p(r)+1] >= 4.
let a= limit supremum S(r+1)/[p(r)+1]
recall limit supremum of a sequence A(n) is defined as lim n-> infinity supremum{A(n), A(n+1),A(n+2),....}
its clear that supremum S(r+1)/[p(r)+1] >= limit supremum S(r+1)/[p(r)+1].
so it will suffice if we can show that a >= 4.
since p(r)-> infinity ,so
limit supremum S(r+1)/p(r) = limit supremum S(r+1)/[p(r)+1].
consider an arbitrary positive real number b > a,there will exist natural number N such that S(r+1)/p(r)< b for all r > N.
so, S(r+1)/[S(r) -S(r-1)] < b, if r > N.
now, shift the sequence towards left by N-1 units i.e. S(i)=S(i+N-1),
so we now have a sequence S(r) such that S(r+1)/[S(r) -S(r-1)] < b, if r > 1.
now we claim that b >=4, for suppose to the contrary that b < 4.
define L= sqrt(b) and cos (y)=L/2 where 0 < y < pi/2.
let k be a natural number such that sin (ty) > 0 for 0 < t < =k, and sin ((k+1)y) <= 0. we shall derive a contradiction by showing that S(k+2) <=0, as detailed below.
we shall now use inductive reasoning to show that
S(r+1) < = L^(r-1)[S(2) sin (ry)- S(1) L sin ((r-1)y)]/sin y, for 1 < r < =k+1.
[.....above expression on RHS in fact gives a solution of recurrence equation S(r+1)= b[S(r)-S(r-1)], if inequalitis are switched to equalities....]
for r=2, above hypothesis can be directly verified,
suppose the hypothesis above is true for r=j, where 2 <= j < (k+1)
so, S(j+1) <= L^(j-1)[S(2) sin (jy)-S(1) L sin ((j-1)y)]/sin y.
by considering a shift by 1 unit in starting point of sequence, we must have
S(j+2)<= L^(j-1)[S(3) sin (jy)-S(2) L sin ((j-1)y)]/sin y.
since sin jy > 0, substituting S(3)<=b[S(2)-S(1)] in the above inequality, after using elementary trognometry identity i.e. sin(u+v)=sin u cos v +sin v cos u,, the induction hypothjesis will be easily proved for r=j+1.
so, hypothesis is true for r =k+1.
i.e. S(k+2)<= L^k [ S(2) sin (k+1)y- S(1) L sin ky ]/ sin y.
But sin (k+1)y <=0,So we get S(k+2) <=0, which is absurd.
this contradiction shows that b > =4.
since b was arbitrary and a < b, we conclude a >= 4 . this is what we wanted to show.
Let L be the line joining you and _|_ to the row of doors.Suppose the max angle which the correct door subtends at L is x. Suppose you start at an angle y to line L towards the row.The worst case is that the correct door lies at one end of the row.Now there are two possibilities :
ReplyDelete1) The correct door and the you are both on the same side of L.
2)The correct door is on the opposite side of L.
Both cases have equal probability.
Length of L=Ncosx
Length of path you travel from initial position to the position where you first reach the row = N(cosx)/(cosy)
Once you reach the row, there are again two possibilites.
1)You move towards the correct door
2)You move towards the opposite end of the correct door.
Both have equal probability.
Case 1: Correct door on same side, you move towards it.
Total length travelled = X1 = Nsinx-N(cosx)(tany)
Case 2: Correct door on same side, you move away from it.
Total length travelled = X2 = 3Nsinx+N(cosx)(tany)
Case 3: Correct door on the other side, you travel towards it.
Total length travelled = X3 =N(cosx)(tany)+Nsinx
Case 4: Correct door on the other side, you travel away from it.
Total length travelled = X4 =3Nsinx-N(cosx)(tany)
Probability of each event = 0.25.Therefore expected distance travelled in the worst case scenario = 0.25(X1+X2+X3+X4).
On adding all Xs, we get Xtotal/N = (cos x/cosy)+2*sinx
Limit x tends to 90 degrees, we get Xtotal/N = 2.