Can you stop copy Alice?

Question

At time 0, Alice and you both move freely at speed 1 on the plane.

As each hour passes, all copies of Alice will subdivide into 2, each moving at half the speed of the parent. So if left alone, at time 1 there will be 2 copies of Alice each moving at speed 1/2, at time 2 there will be 4 copies of Alice each moving at speed 1/4, etc..

If you catch a copy of Alice moving at speed v, you kill it immediately, but your speed will decrease by v permanently.

Alice wishes to multiply without bound. You want to stop her and put a ceiling on the number of copies.

Question: Can you succeed? Does it depend on your distance to Alice at time 0?

---

Note: All participants in this game are to be viewed as points moving on the plane. You catch a copy if your distance is zero.

Answer 1

Edit

2012rcampion observed that we also need to multiply by 2 the distances on the plane

---

Not an answer with a strict proof of the final behavior, but instead a simulation with code that show a possible pattern. You can implement different strategies for both Alice(s) and Bob

https://jsfiddle.net/wLc1mefu/

• Center of canvas is kept on Bob. After 20 sym hours or so, you start to see glitches due to canvas limitations
• The green line represent the nearest target that Bob is chasing

https://jsfiddle.net/4shyrgmt/1/ (bugged because distances are not multiplied by 2, so it simulates a different problem)

Limitations:

• The code is multiplying by two the speed of Bob instead of halving alices' every hour and decrease it by 1 after each killing (for the sake of keep speed in integer domain and limit floating errors)
• Distances are doubled every hour moving Bob and Alices to a x2 of their coordinate vector
• Numerical rounding and floating precision do not guarantee any conclusion about the infinitesimal behavior
• Killing a clone happens when the distance from it is less than the actual Bob speed

Using @ApexPolenta policy for Alice (the default in the code):

of taking +- 45° after each hour, seems to make clones to grow exponentially without bound the only difference here is that Bob is not wise enough to predict alices movement and instead will follow clones.

Using Tyler Seacrest's proof exponential binary tree at 90°

https://jsfiddle.net/dhxmu1nL/

I removed the doubling for each hour keeping the original behaviour because I'd like to catch the fractal pattern, so simulation is a bit more instable numerically. You can zoom in and zoom out. Exponential grow observed.

If you implement any other policy please edit this answer or leave a comment!

Answer 2

Partial answer to prove that

The initial distance to Alice doesn't matter.

For convenience, define the player chasing Alice to be Bob.

Alice's strategy:

For the first hour, just run directly away from Bob.

At the start of the second hour, have one copy turn 45° left and the other copy turn 45° right.

This results in the following figure for one of Alice's clones:

Where B is Bob's position after one hour and A is Alice's. Bob's best move is to chase one clone, and the best he can do is to run at the marked angle $\beta$, obtained via the rule of sines and the fact that he runs twice as fast. (For completeness, the equation is $\frac{\sin(135°)}{|BD|}=\frac{2\sin(\beta)}{|BD|}$)

When Bob reaches point D, the other clone of Alice will be $2|DE|$ away, which is greater than $|BA|$. This is shown empirically in the figure but can also be proved.

$|DE|=\frac{|BD|}{2}\sin(45°)$

$|BD|^2=|BA|^2+\frac{|BD|^2}{4}-|BA||BD|\cos(135°)$ (from cosine law)

After simplification, $|DE|=\frac{1}{6}\sqrt{2}(1+\sqrt{7})(\frac{\sqrt{2}}{2})|BA|$, or about $0.608|BA|$.

In other words,

This strategy has increased the distance between Alice and Bob while also halving their speeds. Regardless of how small the initial distance is, Alice can repeatedly apply this strategy, and at some point, $|BD|$ will be too large for Bob to cover in an hour (Alice will get four clones). This simple analysis breaks down there. I'll have to leave a general proof for someone else to discover.

I'm also unsure of whether 45° is the ideal angle. I just guessed and found the numbers to be sufficient, so I left it at that.

Answer 3

A partial answer/a few observations:

1. The horde of Alice's cannot move a farther distance than $1 + 1/2 + 1/4 + 1/8 + \dots = 2$ (see this geometric series). No Alice clone will ever be farther than $2$ from Alice's starting point (or more accurately, farther than $1$ from wherever Alice is at the first time step).
   More generally, the horde that's generated by splitting a clone moving at $1/2^t$ will never be able to reach farther than $1/2^t$ from its position when splitting.

2. You will always be able to outrun all but 1 of the clones (counting the speed loss from catching clones). The total speed of the clones, dead or alive, will always remain 1, as it is invariant under the given cloning rules. This can be visualized using a tree of the speeds at each timestep: $$ 1\\ 1/2 \qquad\qquad\qquad 1/2 \\ 1/4 \qquad\quad\enspace 1/4 \qquad\quad\enspace 1/4 \qquad\quad\enspace 1/4 \\ 1/8 \quad 1/8 \quad 1/8 \quad 1/8 \quad 1/8 \quad 1/8 \quad 1/8 \quad 1/8 \\ \dots $$ In order for your own speed to equal the speed of the clones $v=1/2^t$ at timestep $t$, you'd have to catch all but one clone. That last clone would be able to outrun you forever.

The final step I am missing to turn this into a full answer is

proving a relationship between the distance to clones and catch up speed. Although you will eventually be able to catch up to all but one of the clones, they may clone unboundedly until you do. It is unclear to me whether you can actually limit the total amount of clones.

Answer 4

I wanted to take a stab at a formal proof, although there is a weak spot explained below. I'll assume Bob starts at a distance of 5/3 from when Alice first splits. Instead of a $45^\circ$ turn, I'll assume both copies of Alice turn $90^\circ$ in opposite directions. Here is a diagram:

Bob is the blue dot (b), and Alice is initially the orange dot (a). As time progresses, the Alices break into a sort of binary tree fractal as shown (the smaller the dot, the later in time that dot appears).

Since Bob is 4/3 distance from the nearest possible Alice, we see that the Alices will divide "more than once" before he reaches them. At that point, let's suppose Bob instantly devours the entire "right group" of Alices. At that point, Bob is a distance of at least 2/3 from the left group. But Bob is also moving twice as slowly, so the distance is effectively 4/3, and we are effectively back to the beginning again. Every time Bob eats half the Alices, at least 4/3 of an hour will have passed, so the Alices reproduce without bound.

The one weakness with this proof is accounting for the case where Bob eats only some of the right group, then heads over to the left group, and then back to the right group again. I think it is pretty intuitive that this will be much worse than focusing on one group at a time, but writing down a rigorous proof for that seems tricky.

Answer 5

I cannot eliminate Alice, unless I start at the same point as Alice.

because

If Alice initially moves directly away from me. It takes me over an hour to catch any fragment of Alice. To capture all of Alice, at some point I must reduce Alice to a single component. At the point of penultimate capture, Alice and I are not colocated and are moving at identical speeds. This is isomorphic to the original problem, because at no point has a measurement of distance been specified or used.

Answer 6

This problem cannot be solved.

Reasoning:

If you start at the same point as Alice, you immediately kill her.
If you start at a point <0 from Alice (ie 1 unit behind her), you will never intersect only one of her at any given time, and therefore always eliminate all of her.
If you start at a point >0 from Alice, you will always be the same speed or faster, and thus never run into her in order to stop her multiplying.

This idea can be seen on a graph, with the assumption that you are starting 1 unit behind her:

X = Time, Y = Distance
You will reach all four of her (each going 1/4 speed) after 2 hours and 40 minutes. This same idea will hold true for any distance you start from her that's less than 0.