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