Frog Puzzle
This puzzle was brought to me by Leonid Grinberg.
A frog needs to jump across the street. The time is discrete, and at each successive moment the frog considers whether to jump or not. Unfortunately, the frog has crappy eyesight. He knows there are dangerous cars out there, but he can’t see them. If a car appears at the same moment that he decides to jump, he will die.
The adversary sends cars, hoping to kill the frog. The adversary knows the frog’s algorithm, but can use only a finite number of cars. The frog wants to maximize his chances of survival with his algorithm. The frog is allowed to use a random number generator that the adversary can’t predict. Can you suggest an algorithm for the frog to cross the street and survive with a probability of at least 1 − ε?
Maria Roginskaya:
Do the frog crosses the street in just one jump? In this case if there is just one car the frog should jump at any time with probability epsilon. Then it doesn’t matter for adversary when to send the car (the algorithm is the same att each step). So the probability to get killed at the time the car is send is epsilon.
24 August 2009, 12:52 pmOn the other hand if it is more than one jump and the adversary has at least two cars, he may just wait untill the frog is doing the first jump and then send to cars on the first and second line (so that the frog gets killed weither it jumps or not.
Tanya Khovanova:
Maria,
The frog crosses in one jump. And your solutions works for one car. Unfortunately, the adversary can send many cars.
24 August 2009, 1:00 pmmisha:
Can the frog sit by the road and count the cars?
24 August 2009, 4:51 pmAustin:
Hmm… the problem is unclear, but I can only come up with one interpretation for which a solution is possible but not trivial.
I assume that the adversary has a fixed number of cars, but the frog doesn’t know the number. (If the frog knows there are only N cars, then he has a trivial strategy of jumping at any time with probability ε/N.)
I also assume that the frog CAN tell when a car has passed by, provided he didn’t jump and get killed by it. Otherwise, there is no way for him to learn anything, so he can’t use any strategy more sophisticated than jumping at time t with probability p(t), where the function p is chosen in advance. Under those conditions, and given my previous assumption that the frog doesn’t know how many cars will appear, it’s clear that no algorithm can ensure any specific positive probability of survival for the frog.
Under these assumptions, the frog should jump at any time with probability ε/2^(k+1), where k is the number of cars that have already passed by. Thus he has probability ε/2 of getting killed by the first car, ε/4 of getting killed by the second car, and so forth.
Did I make the right interpretation of the problem?
(I’m reminded of another little puzzle:
A submarine is initially at some position x on the number line, and travels at constant speed y, where x and y are integers. We are able to drop a depth charge on any integer position, once per unit time. If the submarine is hit by a depth charge it will sink. Without knowing x or y, can we be sure of eventually sinking the submarine?
For a more interesting variant, let x and y be arbitrary real numbers, with the rule that the submarine is sunk by any depth charge exploding within a distance of 1/2.)
24 August 2009, 4:56 pmTanya Khovanova:
Austin,
Your interpretation is right and your solution is correct.
24 August 2009, 5:28 pmLeonid Grinberg:
I just want to give credit where credit is due. This problem was originally given to me by Andy Drucker.
25 August 2009, 4:20 pmDaran:
The set of all ordered pairs (x, y) is countable. Place them into a bijective correspondence with the natural numbers, using the usual zig-zag algorithm, or any other method, then, for each n, use the corresponding (x, y) to predict the location of the submarine. You are guaranteed eventually to find the correct (x, y) and sink the sub.
Real number are uncountable, but they can be approximated to any precision using rational numbers, which are countable. So what would happen if you applied the above algorithm to rational (x, y) instead of integral? Clearly this would eventually work if y were rational. It would also work for xome irrational values of y, where a sufficiently good rational approximation can be found quickly. My feeling, thuogh, is that there will be some irrational numbers for which sufficiently good rational appoximations can never be found quickly enough.
If so, then one could improve upon the algorithm by choosing a larger, but still countable, subset of the reals, such as the algebraic numbers. I suspect, though, that there will always be values for y in which the sub could escape.
12 September 2009, 4:29 amDaran:
The first of these statements is questionable. By “larger, but still countable” set, of course, I meant a countable proper superset of the rationals. In the following, I will refer to “rational” and “algebraic” numbers but the argument will apply just as well to any two countable subsets of the Reals.
Consider the two strategies in which we take an particular enumeration of the set of all pairs (Xn, Yn) where Xn is integral and Yn is rational. Then on turn n we depthcharge the integer nearest in value to Xn + n * Yn. Question: what values of (x, y) could the submarine be using, for which this attack would hit? Let Sn be the set of all such pairs. Sn is non-empty because (Xn, Yn) is in Sn. Moreover for any (x, y) in Sn (x0, y) and (x, y0) are in Sn for all x0 in some interval of width 1 containing x, and for all y0 in some interval of width 1/n containing y. Hence Sn is a union of regions of R squared. Finally let S be the union of all Sn. The second of the two sentences quoted conjectures that Sn is not the whole of R squared.
Apply the same argument to an enumeration of the algebraic numbers to obtain another set T also conjectured not to be the whole of R squared.
Question: What does it mean in terms of S and T to say that the algorithm applied to an enumeration of the algebraic numbers is an “improve[ment]” upon that applied to an enumeration of the rationals? If both S and T have finite measure, then I guess one is better than the other if its measure is greater. Alternatively if either S-T or T-S have finite measure then I guess S (or T) is better if the measure of S-T is greater (less) than that of T-S. If neither of these is the case we might ask what proportion of a finite square on R squared is covered by S and T, as the size of the square increases without limit?
It is not clear to me that the algorithm with algebraic numbers will always be an “improvement” under any of these criteria.
12 September 2009, 12:34 pmVICTORIA:
THAT IS NOT THE FROG GAME!!!!!
16 May 2010, 10:23 amMikey:
You have time to play ‘Frogger’???? 😀
17 September 2010, 10:38 pm