16
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ I don't think so, but I can't prove it. $\endgroup$
    – RonnieChen
    May 2, 2023 at 4:07
  • $\begingroup$ If I encounter more than one Alice at once, do I kill all of them, or only one? $\endgroup$ May 2, 2023 at 14:20
  • $\begingroup$ Just checking: initial speed is 1 unit / hour? $\endgroup$ May 2, 2023 at 14:20
  • $\begingroup$ @kaitlynmm569 All. $\endgroup$
    – Eric
    May 2, 2023 at 14:29
  • $\begingroup$ @ChrisCudmore The specific value of their initial speed doesn't matter, as long as they're identical. It's definitely OK to set it to 1 unit/hour. $\endgroup$
    – Eric
    May 2, 2023 at 14:41

6 Answers 6

11
$\begingroup$

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 strategy sim AlexPolenta 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!

$\endgroup$
1
6
$\begingroup$

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:

a figure showing Bob chasing one clone of Alice

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.

$\endgroup$
4
  • $\begingroup$ I think that one pitfall in this answer is that |BD| should be less or equal than 1 unit (or better, the current Bob speed), otherwise "When Bob reaches point D [...]" would imply that the chased clone has spawned one or more times and that is not handled in following considerations. rot13: vs gurer ner zber guna 1 pybar nebhaq, znlor sbeglsvir qrterrf jvyy abg jbex cebcreyl. $\endgroup$ May 3, 2023 at 10:02
  • $\begingroup$ @10010100102ohno rot13 Guvf nafjre vf bayl cnegvny sbe n ernfba. V'z fnlvat V'z abg fher bs gur orunivbe bs gur flfgrz jvgu zber guna 2 pybarf. Nyfb, V'z fnlvat gung gur rkvfgrapr bs 2+ pybarf vf gur fnzr guvat nf |OQ|>1, juvpu V'ir cebirq gung Nyvpr pna nyjnlf npuvrir $\endgroup$ May 3, 2023 at 11:08
  • $\begingroup$ @AlexPolenta You are right, I've pointed out what you already said. I'm implementing your strategy in a simple simulation ! $\endgroup$ May 3, 2023 at 13:56
  • $\begingroup$ When Alice got more clones in between the recursive step, Alice clones can just let n-1 of them suicide to Bob, right? It's also funny in that Alice clones are trying to be captured in order to slow Bob down XD $\endgroup$
    – justhalf
    May 3, 2023 at 15:27
6
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ An additional useful observation (ROT13): Vs lbh pna pngpu bar fho-Nyvpr bhg bs rirel cnve orgjrra bar fcyvg naq gur arkg, gura gur ceboyrz orpbzrf erphefvir va angher. Jura lbh pngpu bar bs gur gjb Nyvprf, lbh jvyy erznva ng n pbafgnag qvfgnapr sebz gur erznvavat Nyvpr hagvy gur fgneg bs gur arkg ebhaq, jura lbh jvyy ntnva or pbasebagrq jvgu n cnve bs Nyvprf gung ner obgu zbivat ng unys lbhe fcrrq. $\endgroup$
    – MJ713
    May 3, 2023 at 14:26
  • $\begingroup$ I expect the final proof to revolve around rot13(gur erphefvir angher bs gur ubeqrf, jvgu rnpu puvyq ubeqr'f znkvzhz rkgrag orvat pbagnvarq ol vgf cnerag ubeqr'f znkvzhz rkgrag, nf ivfhnyvmrq va uggcf://v.vzthe.pbz/Ov6zMYw.cat. Znlor ol cebivat gung n ubeqr bs rkgrag K pna or renqvpngrq shyyl vs gur uhagre vf zbivat ng fcrrq > K?) - I just haven't been able to piece together a sound proof from it $\endgroup$
    – JHR
    May 3, 2023 at 14:41
  • 2
    $\begingroup$ "If the current timestep is $t$, then there will be up to $2^{T-t}$ clones in the horde." Is this a typo? Shouldn't it be $2^{t-T}$ clones? $\endgroup$
    – Eric
    May 4, 2023 at 11:40
  • $\begingroup$ @Eric Good catch - you are right, and that definitely invalidates my proof. I'll roll it back to my initial partial answer. Thanks for the correction! $\endgroup$
    – JHR
    May 4, 2023 at 11:44
3
$\begingroup$

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:

diagram of a Bob chasing a binary tree fractal of Alices

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.

$\endgroup$
12
  • $\begingroup$ "...and we are effectively back to the beginning again." No, we are not. There's a hidden assumption. Suppose at time t you with speed v are at distance d from the center of a group of Alices, and the amount of time it takes (starting from time t) to eliminate the group is at least T. Now everything else equal, but change t to some s$\gt$t, and denote the least amount of time it takes (starting from time s) to eliminate the group to be S. The hidden assumption is we must have S$\geq$T, for any s$\gt$t. Can you prove it without resorting to infinite regression? $\endgroup$
    – Eric
    May 7, 2023 at 2:13
  • 1
    $\begingroup$ I totally made it up by myself. I enjoy creating original pursuit-evasion problems. There are no other solution avenues I know of. With regard to @justhalf 's comment, the same problem still remains, namely exactly which half Bob eliminate each time? Nearest half? How's that defined? More explanation is appreciable. $\endgroup$
    – Eric
    May 8, 2023 at 0:14
  • 1
    $\begingroup$ @Eric: Thanks for the response. Yes, that new problem is very interesting! I can see how straightline answers aren't the best, as the Alices will want to react to which one Bob is going after. You should post it at some point ... $\endgroup$ May 8, 2023 at 4:04
  • 1
    $\begingroup$ +1 The exponential binary tree strategy needs its own place in simulations list. Hope that helps to complete your proof! jsfiddle.net/dhxmu1nL $\endgroup$ May 8, 2023 at 23:50
  • 1
    $\begingroup$ I believe the new problem will be highly technical, requiring strict definitions to avoid ambiguity or confusion. I posted it on math.stackexchange math.stackexchange.com/questions/4695772/…. But I will post it here if they can't come up with some good idea there. $\endgroup$
    – Eric
    May 9, 2023 at 14:03
0
$\begingroup$

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.

$\endgroup$
1
  • 6
    $\begingroup$ Note that as stated in the question, your goal is not to eliminate Alice, but to "put a celling on the number of copies". $\endgroup$
    – Eric
    May 2, 2023 at 8:22
-6
$\begingroup$

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:

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

$\endgroup$
4
  • 2
    $\begingroup$ The chase is happening in the plane, not on a line. I don't think your reasoning applies for the plane (Copied Alice could each go a different direction) $\endgroup$ May 2, 2023 at 15:14
  • $\begingroup$ ohhh I see the issue. That makes the problem make much less sense to me haha $\endgroup$ May 2, 2023 at 15:17
  • $\begingroup$ Also, distance is a positive quantity, there is no such thing as negative distance. $\endgroup$
    – justhalf
    May 3, 2023 at 14:53
  • $\begingroup$ @justhalf I used -1 with the idea that they were traveling on a line, and not separate directions, meaning that -1 would refer to starting 1 unit behind Alice. I explained this in my post. $\endgroup$ May 4, 2023 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.