**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.

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.