Hard | Strategy |

A spy is located on a one-dimensional line. At time 0, the spy is at location A. With each time interval, the spy moves B units to the right (if B is negative, the spy is moving left). A and B are fixed integers, but they are unknown to you. You are to catch the spy. The means by which you can attempt to do that is: at each time interval (starting at time 0), you can choose a location on the line and ask whether or not the spy is currently at that location. That is, you will ask a question like "Is the spy currently at location 27?" and you will get a yes/no answer. Devise an algorithm that will eventually find the spy

Solution

Here is a detailed solution with images

And here is a short solution by Palak Bhushan

since integer 2-tuples (x,y) are countable, there exists a function f:N->N*N such that f covers all integer 2-tuples. Let f(n)=(f1(n),f2(n)). The algorithm will be to check for location f1(n)+n*f2(n) at time instant n. Given A and B, there exists n0 such that f(n0)=(f1(n0),f2(n0))=(A,B), and thus at time instant n0 we will be checking for location f1(n0)+n0*f2(n0) which is =A+B*n0 -- the actual location of the spy.

And here is a short solution by Palak Bhushan

since integer 2-tuples (x,y) are countable, there exists a function f:N->N*N such that f covers all integer 2-tuples. Let f(n)=(f1(n),f2(n)). The algorithm will be to check for location f1(n)+n*f2(n) at time instant n. Given A and B, there exists n0 such that f(n0)=(f1(n0),f2(n0))=(A,B), and thus at time instant n0 we will be checking for location f1(n0)+n0*f2(n0) which is =A+B*n0 -- the actual location of the spy.

Source: Written Test; leino

Enable Like and Comment Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |