Puzzle Time - Baby Frog

[jon-nyc]

To give a baby frog jumping practice, her four grandparents station themselves at the corners of a large square field. When a grandparent croaks, the baby leaps halfway to that grandparent. In the field is a small round clearing. Can the grandparents get the baby to that clearing, no matter where in the field she starts?

[George K]

@jon-nyc said in Puzzle Time - Baby Frog:

When a grandparent croaks, the baby leaps halfway to that grandparent.

Why would the baby frog run toward a dead grandparent?

[Klaus]

Hm, interesting.

I guess it's possible, and I guess that the "greedy" strategy of, in each step, choosing the grandparent that gets the baby closest to the clearing (*) will get it there.

(*) unless the step is in the same direction as the last one and removes the frog further away from the clearing

[Axtremus]

Yes, I think I have a simple strategy to get the little frog to the middle.

click to show

Zeno’s paradox notwithstanding, I think we can the little frog to the middle as follows:

1. One big frog (the same big frog), call it Big Frog A, keeps croaking until the little frog gets to where the croaking frog is.
2. The other big frog diagonally opposite Big Frog A croaks once to get little frog to the middle.
   

EDIT: Oops, I misread the question and though the clearing is always in the middle, but upon rereading it seems the clearing can be anywhere, so the answer above does not apply.

[Horace]

@Axtremus said in Puzzle Time - Baby Frog:

Yes, I think I have a simple strategy to get the little frog to the middle.

click to show

Zeno’s paradox notwithstanding, I think we can the little frog to the middle as follows:

1. One big frog (the same big frog), call it Big Frog A, keeps croaking until the little frog gets to where the croaking frog is.
2. The other big frog diagonally opposite Big Frog A croaks once to get little frog to the middle.
   

The exact center is occupied by me, politically, but the problem never specified that the target spot is in the middle. It could be on the far left, like many of the rest of you.

[Klaus]

Ah, I think I kind of got it now, with proof.

click to show

The solution is obvious in 1D, that is, if the grandparents are at the end of a line.

To get it to work in 2D, we just solve the two 1D problems independently.

This works because the 2D midpoint ( (x2-x1)/2, (y2-y1)/2) contains the two 1D midpoints.

[brenda]

Thank you for thinking of me and my frogs, Jon.

(You don't have to admit anything. I already know. )

[jon-nyc]

Klaus the target area is not in the middle necessarily. It’s at an arbitrary location. The question is whether you can land on or close to some arbitrary x1,y1

[jon-nyc]

Also its not clear you can solve them independently in that any motion to change the x coordinate will change the y and vice versa except at the very edge (again ignoring Zeno)

[Klaus]

I understood the task.

Let me first describe how to solve the 1D problem. Grandparent GP0 at 0 and GP1 at 1.

For simplicity, assume the frog starts at 0 (otherwise jump to GP0 frequently enough to get arbitrarily close).

Now let's consider the "wave front" of points he can reach after n steps.

In step 1, he can jump to 1/2.

In step 2, he can jump to 1/4 or 3/4.

In step 3, he can jump to 1/8, 3/8, 5/8 or 7/8.

In step 4, he can jump to 1/16, 3/16, ..., 15/16.

In general, in step n, any point of the form (2k-1)/(2^n) can be reached, for k= 1,..., (2^n)/2.

That set is dense in the interval [0,1], hence one can get arbitrarily close to any point.

Now, for the 2D problem, perform the same process in both dimensions at the same time. Let's say you need to get to within epsilon around (x,y).
Just choose an n such that there exist k and p such that ( (2k-1)/2^n, (2p-1)/(2^n)) are in the epsilon circle around (x,y). The process above will give you a sequence of "left/right" instructions for the first dimension and a sequence of "up/down" instructions for the second dimension. "Zip" the two sequences into corner designations (such as "left up"), and voilá!

It works.

[jon-nyc]

SOLUTION: Yes.  The key is to notice that when (say) the SW grandparent croaks, the effect is to replace the field by four quarter-sized square fields, with the baby frog occupying the SW field in exactly the same relative position that she previously had in the whole field.

So the last croak gets our baby into the correct quadrant, and the next-to-last croak into the correct quadrant within that quadrant.  Eventually, going backwards in time(!), the baby frog is croaked into the desired small clearing.

Mathematically speaking, we can make this rigorous by induction.  Cover the field with a 2n x 2n square grid; we prove that from any starting point, the baby frog can be guided to any grid cell we want.

Suppose the target cell is in the SW quadrant.  Expand the whole SW quadrant, including the target cell, so that it now covers the whole field as a 2(n-1) x 2(n-1) grid.

Our induction hypothesis tells us that the baby frog can be croaked into the new, bigger target cell (which is the union of four cells of the original grid).

Now one croak from the grandparent in the SW corner of the field will get the baby to the original target cell.

That concludes our induction proof, and it remains only to apply our conclusion with n large enough so that some cell of the 2n x 2n grid lies entirely inside the clearing that the baby frog is meant to visit.

[Moscow Mathematical Olympiad 1999, Problem D4, contributed by A. I. Bufetov.  Algorithms-oriented readers may have noticed that the proof provides a remarkably efficient scheme: the number of croaks required is logarithmic in the reciprocal of the area of the clearing.]

[Klaus]

@jon-nyc said in Puzzle Time - Baby Frog:

So the last croak gets our baby into the correct quadrant, and the next-to-last croak into the correct quadrant within that quadrant.

That's a nice observation. The "going back in time" trick is neat. But my "going forward in time"/wavefront argument works, too.