Math Challenge by mfb #1

[mfb]

Greg asked me to post it myself.

RULES:

1) In order for a solution to count, a full derivation or proof must be given. Answers with no proof will be ignored.
2) It is fine to use nontrivial results without proof as long as you cite them and as long as it is "common knowledge to all mathematicians". Whether the latter is satisfied will be decided on a case-by-case basis.
3) If you have seen the problem before and remember the solution, you cannot participate in the solution to that problem.
4) You are allowed to use google, wolframalpha or any other resource. However, you are not allowed to search the question directly. So if the question was to solve an integral, you are allowed to obtain numerical answers from software, you are allowed to search for useful integration techniques, but you cannot type in the integral in wolframalpha to see its solution.CHALLENGE:

You and a zombie are on a circle with 40,000 km circumference. You both cannot leave the circle, you can only move along the circle in both directions. The zombie will always move towards you at a constant speed of 4 km/h - at every moment it takes the direction where you are less than 20000 km away. If it reaches you, you die.
During the day (16 hours), you can move at a maximal speed of v (larger than 4 km/h). If you get very close to the zombie during the day, you can see it and turn around to avoid it. During the night (8 hours), you have to sleep and cannot move. The zombie does not sleep.

You start in the morning directly after waking up. The zombie starts at an unknown location along the ring. What is the minimal speed v to make sure you can stay safe forever, and how do you do that?
Solved by jbriggs444

At this minimal speed, can you guarantee to get a bit of rest during the day eventually?
Solved by jbriggs444

Can you guarantee to find the zombie?

 

[jim mcnamara]

Dumb question:

it takes the direction where you are less than 20000 km away

should that read:
it takes the direction where you are less than or equal to 20000 km away.
Otherwise at 20000 it takes no direction?

 

[QuantumQuest]

Dumb question:
should that read:
it takes the direction where you are less than or equal to 20000 km away.
Otherwise at 20000 it takes no direction?

I'll give my take if it is of any help. When zombie is at 20000 km away from man, they're on opposite sites on the circle so if man does not move at this instant, zombie will move in a random (arbitrarily chosen) direction. If the man moves either direction at this instant, zombie will choose the distance less than 20000 km. At any other instant there will always be a distance between zombie and man less than 20000 km, whether man is moving away or towards zombie.

 

[mfb]

Events that happen with probability zero can be neglected. Otherwise, just let the zombie randomly choose a direction. It doesn't really matter.

 

[jbriggs444]

The human starts at dawn and has 16 hours to run before sleeping. His strategy is to pick a direction and run. Call this direction east. This leaves a "safe" zone to his west. After a time he turns and runs back the way he came, leaving a second "safe" zone to his east. If he sees the zombie during his eastward run, he will abort and run west. His strategy from that point forward is obvious.

Any alternate strategy which fails to run at maximum speed eastward, which alters direction needlessly or which fails to run at maximum speed westward will leave a smaller "cleared" area and is obviously sub-optimal.

Let t denote the time (in hours) between dawn and turnaround ( 0 < t < 16 ).
Let v be the human's velocity. ( v > 4 or all is lost ).

All positions in km and all velocities in km/h.

The human's first night's campsite will thus be located ##tv - (16-t)v = (16-2t)v## east of his starting point. If he is to leave an adequate cleared zone in his wake to the west, this must be at least as far as a zombie can shamble in one day, ##96##. This gives us a first inequality:

$$(16-2t)v >= 96$$

In order to leave a safe zone in his wake on the westward part of his run, the human must cover in 16-t hours as much ground as the zombie can cover in an additional 8 hours (24-t hours total).

This gives us a second inequality.

$$(16-t)v >= 4(24-t)$$

If we solve these inequalities for t, we arrive at:

$$t >= 8 + \frac{48}{v}$$

and

$$t <= 16 - \frac{32}{v - 4}$$

Note that our slight visibility ensures that strict equality is a win for the human. Hence >= rather than > and <= rather than <.

By inspection, these constraints can be feasibly satisfied for v large but cannot be satisfied for v small. As a sanity check on the logic so far, we can see that for v large, one can run east for a bit more than 8 hours then west for a bit less than 8 hours and sleep for the night at the west edge of a huge cleared swath, tightly satisfying the first constraint. Or one can run east for a bit less than 16 hours then west for a few moments, sleeping for the night at the east edge of a huge cleared swath, tightly satisfying the second constraint.

The minimum v is obtained when both constraints are satisfied tightly. Graphically, one could draw a feasible t (vertical) versus v (horizontal) graph and see an intersection point on the left where the two feasibility boundaries intersect. This would be a linear programming exercise except for the fact that the constraints are not linear.

In any case, we set the two feasibility boundaries equal to one another and obtain the equation:

$$8 + \frac{48}{v} = 16 - \frac{32}{v-4}$$

Multiplying through by ##v(v-4)##, this gives us a quadratic to solve

$$8v^2 - 32v + 48v - 192 = 16v^2 - 64v - 32v$$

After cranking and grinding on that, we get:

$$v^2 - 14v + 24 = 0$$

And applying the quadratic formula we wind up with ##v=2## or ##v=12##

We already know that v=2 is infeasible -- we'd be eaten. Discard that as a spurious solution.

At v=12 we are at the feasibility boundary of the first inequality: ##t > 8 + \frac{48}{24}##. We spend 12 hours heading east at 12 kph.

At v=12 we are also at the feasibility boundary of the second inequality ##t < 16 - \frac{32}{12 - 4}##. We spend 4 hours heading west at 12 kph.

We spend the night 144 - 48 = 96 km east of our starting point. A zombie starting just to our west would spend 24 hours at 4 kph to arrive just out of sight at dawn.

We spend the night 48 km west of our turnaround point. A zombie just out of sight at turnaround would spend 12 hours at 4 kph to arrive just out of sight at dawn.

The first day strategy could be repeated ad infinitum. 12 kph is the minimum speed required for safety. Any lower speed is unsafe.

Now, the human has moved at an average speed of 4 kph for the first day. A zombie originally located just to the west could still be lurking just out of sight to the west as the sun rises on the second day. Similarly, a zombie who was just out of sight at turnaround could be just out of sight at the next dawn. So the second day is just as deadly as the first. However one thing that is known is that during the night, a region of 32 kilometers around the antipode of the first night's campsight is clear of zombies. If one keeps working on a generally eastward path, one will eventually either encounter one of these 64 km known clear stretches or find the zombie. Either outcome ensures a chance to rest.

 

[mfb]

A nice solution for the first part.

If one keeps working on a generally eastward path, one will eventually either encounter one of these 64 km known clear stretches or find the zombie.

This is not correct, although I cannot say how exactly without revealing too much of the answer.

 

[jbriggs444]

A nice solution for the first part.
This is not correct, although I cannot say how exactly without revealing too much of the answer.

Drat. It seems inevitably correct.

Edit to elaborate...

The "known clear" opposite region would be 64 km wide at sunrise. As our intrepid human begins his daily run, his antipodal point will be sweeping from the midpoint of that region toward one of its edges -- catching up to the trailing potential zombie at that edge at a rate of 12 - 4 = 8 kph.

In four hours, the antipodal point will be on the boundary of the cleared region. By this time, the cleared region will have grown by 4*8 = 32 km to a total of 96 km wide.

From this point on, the antipodal point will be sweeping across a region which contains potential zombies. As it does so, any [potential] zombie swept across will reverse course. The boundary of the "known clear" region will stop growing. The potential zombies just outside of either edge will all be shambling in the same direction.

Accordingly, for the next eight hours (until the daily turn-around) the antipodal point and the trailing edge of the cleared region will now be separating at 12 + 4 = 16 kph. Eight hours later, at turnaround, the tail of the cleared region will be 16 * 8 = 128 km away from the antipodal point. After turnaround, the antipodal point will be closing on the tail of the region at 12 - 4 = 8 kph. Over the next four hours until nightfall, this will cover 4 * 8 = 32 km. The human starts the night with a "known clear" region which has its trailing edge 128 - 32 = 96 miles from the antipodal point and its leading edge 96 + 96 = 192 miles away.

If our human continues in this manner, a sequence of 96 mile "known clear" zones will be intermingled with 96 mile "danger" zones will begin populating the region ahead of him. Each day, the leading edge of the first cleared zone moves 96 miles toward the human. Each day (if he maintains an eastward pattern), the human will move 96 miles toward the leading edge of the first cleared zone.

After 105 days, the human will either have seen the zombie (and adopted a new strategy) or will encounter the leading edge of the known-clear zone that arose during his first night's slumber.

 

[PeterO]

Drat. It seems inevitably correct.

Edit to elaborate...

The "known clear" opposite region would be 64 km wide at sunrise. As our intrepid human begins his daily run, his antipodal point will be sweeping from the midpoint of that region toward one of its edges -- catching up to the trailing potential zombie at that edge at a rate of 12 - 4 = 8 kph.

In four hours, the antipodal point will be on the boundary of the cleared region. By this time, the cleared region will have grown by 4*8 = 32 km to a total of 96 km wide.

From this point on, the antipodal point will be sweeping across a region which contains potential zombies. As it does so, any [potential] zombie swept across will reverse course. The boundary of the "known clear" region will stop growing. The potential zombies just outside of either edge will all be shambling in the same direction.

Accordingly, for the next eight hours (until the daily turn-around) the antipodal point and the trailing edge of the cleared region will now be separating at 12 + 4 = 16 kph. Eight hours later, at turnaround, the tail of the cleared region will be 16 * 8 = 128 km away from the antipodal point. After turnaround, the antipodal point will be closing on the tail of the region at 12 - 4 = 8 kph. Over the next four hours until nightfall, this will cover 4 * 8 = 32 km. The human starts the night with a "known clear" region which has its trailing edge 128 - 32 = 96 miles from the antipodal point and its leading edge 96 + 96 = 192 miles away.

If our human continues in this manner, a sequence of 96 mile "known clear" zones will be intermingled with 96 mile "danger" zones will begin populating the region ahead of him. Each day, the leading edge of the first cleared zone moves 96 miles toward the human. Each day (if he maintains an eastward pattern), the human will move 96 miles toward the leading edge of the first cleared zone.

After 105 days, the human will either have seen the zombie (and adopted a new strategy) or will encounter the leading edge of the known-clear zone that arose during his first night's slumber.

Careful - you have drifted from kilometres to miles - but we understand what you mean.

 

[mfb]

Edit to elaborate...

Edits are dangerous. I see all new posts, but not all edits if I saw the post before.

Now it is correct (assuming miles=km).