32
$\begingroup$

Note: This problem remains unsolved, as of 4 Feb 2018, so do try it out


This a variation of this question by @Gamow

Suppose there are $100$ lions and $100$ zebras. The lions function together as a team, and so do the zebras. The lions place themselves first on an infinite plane, and the zebras place themselves next. Game proceeds turn-wise, one turn for the lion team, one for the zebra team. On each turn, a single zebra or lion (depending on which team's turn it is) moves by up to $100$ metres. Lions win if a single zebra is eaten.

Zebras will try to ensure this doesn't happen. Do the lions' have a strategy that works irrespective of the zebras' one?

P.S. @Veedrac's result is definitely helpful (whether or not you understand the math) if you are attempting to solve this.

$\endgroup$
  • $\begingroup$ If the movements are limited to the grid than any move out of the strip will maintain the distance from the chasing lion. Clearly when the number of lions is small it is easy for zebras to escape. When the number of lions is high the potential strategy would be to get behind one zebra. The advantage of the lions over the zebras could be based on the fact the a single move of a lion may close the range to couple of zebras. The lions strategy will be to use several to chase and the rest to create a trapping line. $\endgroup$ – Moti Mar 5 '15 at 6:52
  • 1
    $\begingroup$ A lone zebra is surrounded by 100 lions. The lions may choose their initial positions, but must start at least D distance away. The zebra decides D. I believe (but cannot prove) that the zebra can escape. $\endgroup$ – Lopsy Mar 5 '15 at 22:47
  • 1
    $\begingroup$ @Lopsy But there are 100 zebras, which are harder to protect than a lone one. $\endgroup$ – ghosts_in_the_code Mar 6 '15 at 7:55
  • 1
    $\begingroup$ Is there a winning condition for zebras? $\endgroup$ – Daniel May 17 '15 at 20:04
  • 2
    $\begingroup$ @moonbutt74 No, they are just two kinds of objects (which I have given animal names). $\endgroup$ – ghosts_in_the_code Sep 2 '15 at 14:09

10 Answers 10

16
+50
$\begingroup$

I have no idea who can win, but I do want to clear up one point that some other people seem to be overlooking. Namely, the lions can always surround some plurality of zebras so any strategy to keep the zebras on the outside is doomed by construction.


Let $n \ge 100$ be the number of zebras and the number of lions.

Let $\text{net}$ be the convex hull of the lions.

Let $C_\text{net}$ be the largest origin-centred circle that is contained within this convex hull. This may not exist, in which case we consider it to be of radius 0.

Let $C_\text{zebra}$ be the minimal origin-centred bounding circle for some subset $Z$ of the zebras.

Zebra Net

Claim:

The lions can force $\text{radius}(C_\text{net}) > k \cdot \text{radius}(C_\text{zebra})$ for some $k > 10$ and a nonzero subset $Z$ regardless of the zebras' strategy and initial placement.

As $n$ is increased, you can have an arbitrary number of zebras inside $C_\text{zebra}$ with an arbitrary number of lions on the perimeter of $\text{net}$ and $k$ can be arbitrarily increased.

Proof:

Without loss of generality, assume the lions go first.

Consider a circle centred on the origin containing all of the initial positions of the zebras and lions. Let its radius be $\delta$ and let $\omega \gg \delta$ and $\omega \gg 100$.

Have some small subset of lions of cardinality at least $l \ge 3$ move to equidistributed points at radius $\omega$.

We select some small number $z$ of zebras and examine the maximum radius of $C_\text{zebra}$ which doesn't contain $z$ zebras. This is obviously the maximum radius of the $z$th-smallest distance from the origin to each zebra.

Evidently, this is maximized by having $z - 1$ zebras not move and having $n - z + 1$ zebras move an equal distance from an initial offset of $\delta$. There are rounding errors since the distance might not be a multiple of 100, but since $\omega \gg 100$ this is unimportant.

Thus we have that the radius is at best $\frac{l \cdot (\omega + 2\delta + 100)}{n - z + 1} + \delta + 100$ where $l \cdot (\omega + 2\delta + 100)$ is approximately the distance moved by the zebras in the time it took the lions to get into place. This approximates to $\frac{l \cdot \omega}{n - z + 1} + \delta$.

The radius of $C_\text{net}$ relative to $\omega$ is worst in the case of a triangle, in which case it is $\omega / 2$.

This means that $k$ is at worst

$$ \frac{\text{radius}(C_\text{net})}{\text{radius}(C_\text{zebra})} \approx \frac{\omega / 2}{\frac{l \cdot \omega}{n - z + 1} + \delta} $$

For $n = 100$, $z = 3$, $l = 3$, we have

$$ \frac{\omega}{\frac{3}{49} \omega + 2 \delta} \approx \frac{\omega}{\frac{3}{49} \omega} \approx 15 $$

Obviously as $n$ increases, the fraction $\frac{l \cdot \omega}{n - z + 1}$ will decrease. By increasing $\omega$ in terms of $\delta$ you can thus make this arbitrarily large even for arbitrary $l$ and $z$. A rigorous proof is up to the reader.


So "trapping" a zebra is easy... what matters is if you can do anything with that knowledge.

$\endgroup$
  • $\begingroup$ Totally agree with your assessment. I would put it in different term. A single lion can move "100 faster" than the zebra 100 pack. The challenge is not if, but as you concluded - how? $\endgroup$ – Moti Mar 8 '15 at 7:03
  • 2
    $\begingroup$ Thanks for figuring this out. A lot of the answers are not of any use, yours is helpful. $\endgroup$ – ghosts_in_the_code Mar 8 '15 at 16:41
  • $\begingroup$ @Veedrac Can you tighten the net? Two avenues seem promising: (1) average speed of lions vs zebras if there are more zebras inside than lions on the perimeter; and (2) sum of time taken for all lions to travel directly to some point (or some zebra?) in the net compared with sum of time taken for all zebras to escape the original or shrinking perimeter. $\endgroup$ – Lawrence Mar 15 '15 at 23:49
  • $\begingroup$ @Veedrac Where do you define $\omega$? $\endgroup$ – Lawrence May 17 '15 at 23:26
  • $\begingroup$ @Lawrence "and let $\omega \gg \delta$ and $\omega \gg 100$". It's just an arbitrary large constant if I remember correctly. $\endgroup$ – Veedrac May 17 '15 at 23:36
4
$\begingroup$

My final assumption is

zebras can win

following this strategy :

The zebras choose to be uniformly distributed on a circle, distanced sufficiently from lions' center of gravity - which the circle is the centered on.

They will not be doomed to lose the game given:

  • Any zebra is instructed to escape by following the vector in the direction parallel to $\sum \vec{l_i b}+\vec{z_i b}$ where $l_i$ are the lions' coordinates, $z_{i}$ are the closest other zebras' coordinates and $b$ is the zebra itself.

  • When any zebra feels a lion being closest to it, it should take turn to move.
    In technical terms, this is when it has the smallest $d = \min ||\vec{l_i b}||$.

This solution can prevent

  • any zebra to be stranded by two lions both sides or
  • any zebra to be amassed in same spot with another zebra

because the unique condition where any zebra is condemned to death is that

$$ \sum (\vec{lb} + \vec{zb}) = \vec{0} $$

or that a single $\vec{zb} = \vec{0}$ or $\vec{lb} = \vec{0}$.

The solution is illustrated here:

Lions and zebras with vectors between them.

This little simulation can clarify my proposition for two zebras and two lions.


This part is a reply for @Veedrac

Considering 6 zebras and 6 lions, I could implement this simulation in which by I might not surround any zebra since the zebras are fleeing the lions' center of gravity. I made this simulation open-source to unconvict myself from any cheating.

Here is a simulation for 6 zebras and 6 lions.

Note: Try to move the cursor slowly centimeter by centimeter because there is some kind of weird bug in that code. I couldn't handle it due to my inexperience with this type of scripting language.

Secondly, I don't really believe that Veedrac's theory is really fruitful because zebras are always escaping any kind of fencing that lions try to impose.

Lets assume $k$ lions succeeded in surrounding one lion.

Let $r$ be the radius of that circle and $2 \pi r$ is the perimeter.

Any successful encirclement is when the length of each arc between two lions is gradually shrinked until it is no more than 100m with a zebra still inside the circle.

When $k$ lions made a unitary $u = 100\text{m}$ step, the zebra would have made $ku$ steps.

When a zebra is doomed to be caught, the radius equals $\frac{(k-1)}{k} r$, the perimeter of the circle is $2 \pi \frac{(k-1)r}{k}$ and the length of each arc is $\frac{2 \pi \frac{(k-1)r}{k}}{k}$

The condition where a zebra is caught is $\frac{2 \pi \frac{(k-1)r}{k}}{k} \leq u = 1$ and the maximal length of the circle's radius is $\frac {k^2}{2\pi(k-1)}$.

When there are $k = 100$ lions, $r \approx 16u=1600\text{m}$, which can be avoided when we consider an enough large difference between the zebras' and lions' accumulation center before the game starts.

$\endgroup$
  • $\begingroup$ But the lion in the second column could chase his zebra for a number of moves, until he is significantly below the zebra in column 4. If the zebras then stick to their strategy, and assume that the one closest to a zebra moves first, then the lion from col 2 could then move across into col 4 and turn around and it would then be really easy. The additional lions break this solution for the zebras and it actually becomes one of the easiest for the lion. They could last a while moving side to side but this would allow the lions to move alternately and trap the zebra. $\endgroup$ – Ryan Durrant Mar 6 '15 at 11:14
  • $\begingroup$ @Ryan Durrant thx for noticing it , iv changed the content $\endgroup$ – Abr001am Mar 6 '15 at 13:25
  • $\begingroup$ "this solution can prevent any zebra to be stranded by two lions both sides" → What exactly do you mean by this? It is provably possible for three lions to form a triangle with which a single zebra is contained. $\endgroup$ – Veedrac Mar 7 '15 at 20:01
  • 1
    $\begingroup$ @Agawa001 What is a rayon? Do you mean radius? $\endgroup$ – Veedrac Mar 9 '15 at 22:34
  • 2
    $\begingroup$ I don't think I agree your conclusion is particularly strong, but the simulation is definitely helpful! $\endgroup$ – Veedrac Mar 10 '15 at 11:39
3
$\begingroup$

Theoretically on an infinite plane the zebras can be set up so that the lions are unable to reach them. For a start they could start lightyears away and then continue to move away.

There might be certain situations in which the lions can win, for examlpe if the zebras were placed randomly in non-optimal positions then one would almost certainly get caught. But if the zebras are placed in well thought out locations, then regardless of the lions location no one lion can ever catch a zebra, it would just continue to move away.

One way a lion might attempt to beat this, would be to imagine that the zebras set up to surround the lions, meaning they can not get trapped, if a lion were to chase one zebra until the lion itself was outside of the zebras, it could then turn around and push a zebra back towards the other lions this could work as only one zebra can move to avoid the lion. If we assume that the closest zebra moves then the lion simply has to ensure it stays closer to the first zebra until it is outside of the circle/line/square the zebras are attempting to surround the lions with. This doesn't have to be a regular shape, and they could be more or less randomly spread out, but as soon as the lion gets to the other side, by maintaining a small distance it will eventually get a fair way past. It can then turn around. until the distance between it and the first zebra exceeds that of any other zebra and the nearest lion.

The first lion (A) would have to be selected such that another zebra (X) is nearby but farther from the next lion (B) than most of the other zebras are from their respective lions.

When Lion A then turns back, another zebra (Y) will move as he will be closest to a lion. This has to be chosen such that X is not the next closest to a lion.

The same strategy can then be used by other lions to circle the zebra X, by chasing another Zebra Z they can position them selves around zebra X who doesn't get a chance to move until surrounded. They can then close in. The lions can move in any direction, and if we assume that the zebras move to the farthest point from the lion, this allows them to push them around. More than one lion can move to push around the same zebra, and since they can also force other zebras to move by getting closer to them, they will eventually be able to surround a zebra.

$\endgroup$
  • $\begingroup$ Veedrac's answer might help. $\endgroup$ – ghosts_in_the_code Mar 30 '17 at 8:48
3
$\begingroup$

The zebras are bound to win!

REASON

As the lions place themselves first and the grid is infinite the zebra's can place themselves at a distance greater than 1 km (1 km is exaggerated, any distance =< than 200m will do) from the closest lion and make sure that they are not in between any lions.

EXAMPLE 1

Let there be 1 zebra and 1 lion.

In such a case the zebra will place itself at a distance of =< 200m ; and will always manage to get away

Conclusion: Zebra wins

EXAMPLE 2

Let there be two lions and two zebras

In such a case after the lions have placed themselves, the zebras will place themselves in such a manner so that they are NOT in between two lions and the minimum distance from both lions is 200m

The lion may come closer to the zebras and separte them, however it will need the support of the 2nd lion to surround it, and in the time the 2nd lion will come for support, the 2nd zebra will get away

Conclusion: Zebras win

SIMILARLY EVEN IF THERE ARE 100 LIONS AND 100 ZEBRAS, THE ZEBRAS WILL USE THE SAME EXACT STRATEGY, AND HENCE MANAGE TO WIN EACH AND EVERY TIME

Until and unless the grid is finite and the number of lions and zebras is tweaked, the solution won't change.

$\endgroup$
  • 1
    $\begingroup$ I don't see how your strategy generalizes even for three zebras. For example, why can't one lion chase one zebra until the lion is on a line with two other zebras, and then chase the closer of the two zebras until it reaches the other zebra, when the two zebras cannot escape from the one lion, as they move more slowly together. $\endgroup$ – JiK Feb 17 '15 at 17:00
  • $\begingroup$ Initially the zebra will not be in the same horizontal strip as any lion.Whenever a lion enters the vertical strip in which the zebra is present then the zebra will flee vertically. And if the lion chooses the 2nd zebra then it will further have to move horizontally till it reaches a point so that the zebra is in the same vertical strip as itself, here again the zebra will flee vertically if the lion chooses to chase it. $\endgroup$ – The Dragonista Feb 17 '15 at 17:18
  • $\begingroup$ What strips are you referring to? Do you mean the strategy used in the answer to the original question? $\endgroup$ – JiK Feb 17 '15 at 17:53
  • $\begingroup$ Yes, its basically the same strategy! $\endgroup$ – The Dragonista Feb 17 '15 at 17:56
  • 3
    $\begingroup$ @TheDragonista Having the zebras locked to a horiontal line will not work, even for 2 lions and zebras. Have lion 1 chase zebra 1 in zebra 1's strip for one turn. Then have lion 2 chase zebra 2 for significantly longer than the distance between zebra 1's line and zebra 2's line. At this point lion2 can enter zebra 1's strip and cause zebra 1 to be sandwitched between the two lions. $\endgroup$ – Taemyr Feb 19 '15 at 8:29
1
$\begingroup$

I'm believe the zebra's can always win as before. The main reason being that the plain is infinite, and that the zebra's place themselves second. How they do this is simply the same was as in the previous question. Each zebra makes its on strip in which if there was only 1 lion, they would all be safe. the issue is that there is 100 lions, but this doesn't matter. Since any number of points (less than infinite) can be scaled down to a single point given infinite space.

So once all the lions have placed themselves, the zebra's need to be places such that they 100 lions can be considered to be a single point below all of the zebra's strips. Although this might not seem physically possible (since we are dealing with limits with infinity), in the world of math it could be resolved to a solution. Unfortunately my math hat doesn't seem to be around so I can't provide the proper proof to this concept. (Hopefully someone else would be able to verify this to possibly conclude this problem)

As a side note. You stated that:

Note that once a zebra gets encircled by the lions, he is bound to lose. So the aim for the lions could be to create a wide ring around a single zebra.

But you did not provide any proof to this. I believe this can be throwing some people off as they could be going down a false path, unless this is a rule that you are creating as another win situation.

$\endgroup$
  • $\begingroup$ +1 for the statement by OP without proof. Although the strip method won't work, even with two lions. The lion can all go to one strip, then one goes upward till the horizontal distance to the vertical line in which the zebra on the strip to the right of current strip is half the vertical distance to the zebra on the strip to the right. Then another lion goes downward until the zebra to the right is between the two lions. Then both lions go to the vertical line the zebra to the right is in. Both lions will reach the line before the zebra to the right can escape. Then it can be captured easily. $\endgroup$ – justhalf May 18 '15 at 4:19
  • $\begingroup$ @justhalf I didn't specify how wide a ring, or how many lions are required. I myself don't know. $\endgroup$ – ghosts_in_the_code Sep 30 '15 at 12:25
  • $\begingroup$ @ghosts_in_the_code: Then I think it's better to remove that hypothesis. $\endgroup$ – justhalf Apr 29 '16 at 3:02
0
$\begingroup$

The lions can eventually win.

Let's take a kind of bad starting position for the lions: they are in a line, the zebras are in a line perpendicular to the lions, but 1km from one of the ends (capital T, top bar is zebras, lions are upright bar, and a space between).

Let's say then the lions move into an upward parabola. Well, the zebras are gonna be quite a bit further out. Even then, the ends of the lion parabola can move upward enough that eventually they will be higher than some zebras. Repeat to get move lions above some zebras. Eventually, you will be able to box a zebra in.

$\endgroup$
  • 1
    $\begingroup$ If the lions are quite apart, the zebras could pass through the parabola wall. If the wall is tight (and small), the zebras can go round it. As the zebras place themselves later, they could start with a scattered position. $\endgroup$ – ghosts_in_the_code Feb 19 '15 at 10:06
  • 1
    $\begingroup$ I am not sure this is the right strategy but it is clearly based on a good assumption: When one lion is moving there is a challenge to decide which zebra to move, since the distance is closed to more than one zebra. $\endgroup$ – Moti Mar 5 '15 at 6:55
0
$\begingroup$

I don't think that the lions can win on an infinite plane. First, draw a circle around the lions, the smallest one needed to encircle all the lions. Now, draw another circle whose radius is 10^r light years, where r is the radius of the lion circle in meters. Put the zebras equidistantly on this outer circle.

Whichever zebra is nearest the moving lion moves directly outwards.

I can't see a strategy that the lions could use to overtake the zebras. Suppose one lion goes after one zebra. The zebra moves outwards in response. Suppose the lion goes after that zebra until he hits the zebra's starting point. Then do same with another lion, going after a zebra two zebras away from the first one. Then can you perhaps trap the zebra in the middle? Seems to me that the middle zebra would at some point become the closest and start to move away.

$\endgroup$
  • 1
    $\begingroup$ To make things easier to visualise, I'll just talk about 12 zebras on a clockface. So a lion in the centre of this circle heads to the zebra at the 12 o'clock position. It keeps heading that way for, say, 3 times the radius (R) of that initial zebra circle. At that point it starts heading in a 3 o'clock direction, the 12 o'clock zebra is still the closest so continues to move in a 12 o'clock direction. After the lion has moved a decent distance the 12 zebra is no longer the closest, and instead the 1 o'clock zebra moves. But moving 'outwards' means it is heading towards that moving lion. $\endgroup$ – Mashton Feb 18 '15 at 11:09
  • $\begingroup$ If you've gotten to three times the radius of the circle, you've passed a point where another zebra is closer, in which case it would have moved instead of the original one. Not so? $\endgroup$ – BobRodes Feb 19 '15 at 3:32
  • 1
    $\begingroup$ No, the Zebra that the lion started chasing will be the closest until the lion stops chasing it. $\endgroup$ – Taemyr Feb 19 '15 at 8:23
  • $\begingroup$ @Taemyr For 100 zebras, Mashton's strategy works well, since the angle between any 2 zebras is only $3.6^{\circ}$. $\endgroup$ – ghosts_in_the_code Feb 19 '15 at 10:08
  • 1
    $\begingroup$ @ghosts_in_the_code I was replying to BobRodes. Mashton's strategy fails for 4 zebras, I think it suceeds for any number greater than this. $\endgroup$ – Taemyr Feb 19 '15 at 10:13
0
$\begingroup$

The lions will win.

Because:

Assuming the zebras take their optimal strategy, which would be to create a circle an arbitrary distance out from the center of the lions. Let's say that the zebras make such a large circle that any distance a lion is from the center is negligible, so we can say they are all at the direct center of the circle. This will look like this:enter image description here
with the lions at the red dot in the center (assume its a point, as explained above) and the zebras around the circle.

When they move:

A single lion moves directly north, going for the zebra at that spot on the circle (let's call it zebra A). That zebra would in turn move away, and the lion would keep moving in that direction. At some point, the lion would be closer to one of the adjacent zebras to the one it is following (let's call them B and C), however it would keep moving in a straight line toward the original zebra. To keep safe, all three of those zebras would have to move out in their respective path. For this lion strategy, the lion would keep moving in the straight line following zebra A, so B and C could stay in the same spot, but that doesn't matter. Either way, the lion would get far enough outside the original circle (if B and C don't move) or the arc that B and C make (if they move in their respective paths) that it would either catch up to A or get to a point where it can get to a point that is in between B/C and the center of the circle. If it catches up to A then the lions would obviously win. If it gets to a point that is on the opposite side of B/C and the center of the circle (all the other lions), then it would have that zebra trapped. So the lions win. Here are a couple pictures to explain:enter image description hereenter image description here
The only other thing that the zebras could do is have B and C each move out of their path (the straight path from the center of the circle). If this were to happen, they would eventually get in the way of the zebra that is on that side of them. In this case the lion could just go straight toward those zebras, and having both zebras in a (relatively) close location, they would be trapped because the lion could move faster (only one lion and two zebras escaping, so lion moves 100m and then each zebra must move 100, so lion moves 200 for each 100 per zebra).

EDIT:

I guess a better way to word this would be that the single lion goes toward the center zebra of 3 that are closest together, angle-wise. No matter how the zebras are set up, at least 3 zebras must be adjacent and separated by angles of 3.6 degrees or less. One zebra could be on the opposite side of the lions from the other zebras, in which case the lion would go for a zebra that has the least sum of angles between itself and the two adjacent zebras. If the zebras were separated by 3.6 degrees each, then this would be the optimal strategy for them, however they would still lose. They wouldn't lose if this angle is greater than or equal to 90 degrees, because no matter how far out the lion goes, it's distance to cut off any zebra will always be longer than the distance the zebra must go to get to that same point, so it will never catch any of the zebras. For any angle less than 90 degrees between each zebra, the lion can get to a point far enough away from the circle that it will be able to "cut off" one of the adjacent zebras to the one it was following. If the adjacent zebra that the lion targets decides to cut over, it will be cutting into the path of another one of the zebras, and if two of these zebras are in the same path, then it will be simple for a lion to get one of them because the lion can move 200m for each 100m moved by each zebra.

$\endgroup$
  • $\begingroup$ First of all, I'm not sure your logic is right, but maybe it is. Second, the zebras are allowed to place themselves after the lions have done so. If a circular formation does not work, they might have a better way to position themselves. $\endgroup$ – ghosts_in_the_code May 18 '15 at 5:14
  • $\begingroup$ Okay I sort of reworded it to address that. $\endgroup$ – MisterEman22 May 18 '15 at 5:35
  • $\begingroup$ I think you need to go into more detail about how to finish off the zebras once a they are between the moving lion and the other lions. Merely saying the zebras are "trapped" doesn't seem sufficient. Is there some state from which you could show a concrete winning strategy for the lions that would catch a zebra in a computable amount of time? $\endgroup$ – supercat Mar 31 '17 at 20:37
  • $\begingroup$ It seems like the lions should be able to win, but I can't figure out a strategy for them to actually do so. It would seem like a zebra that has to escape toward other zebras or lions would be in a losing situation, but I can't figure out any metric which would decrease at a rate sufficient to show that it would reach a winning value in finite time (rather than asymptotically approaching some non-winning value). $\endgroup$ – supercat Apr 4 '17 at 14:39
0
$\begingroup$

Let's assume a single zebra is caught in an infinitely large "circle" of L lions, which move just on the sides of this shape. This might not be the optimal lion position and movement, but it is reasonable enough to start with I believe.

For 6 it can be shown that simply approaching any lion will require neighboring lion to approach that lion to fix the hole. Obviously this cannot work, the other hole on the other side of lion being approached remains.

For 12, they can fix the hole but 2 lions approaching that one will make 2 other holes where zebra can escape. Get halfway to that lion and then run through the hole. The same happens from 24 on, except in 2 steps - halfway to that lion, then halfway to the other lion, then escape through another hole... The more lions you add, the less lions can and need to move, but you still keep making holes for zebra's escape. You can continue for many more lions with the same conclusion - lions are too sparse to catch the zebra. In fact you would require infinitely many lions. Think electrons on surface shading that one inside as to how they should move.

Can lions move more optimal? With infinite distance, nope. If that lion that is being approached moves towards the zebra, or anything else, hole will be just bigger and make escape easier. Sure, with finite distances they could perhaps catch the zebra in the circle, but this isn't relevant in this case - zebras can start infinitely apart from each other, so lions will have to be "more infinitely" from the zebras to trap them.

So, if zebras are to be eaten, you need to trap more than one.

Now there are 2 open questions:

With how many lions can you surround how many zebras?

If you trap Z infinitely spaced zebras, can you force them together to finite distances? If you cannot, there will be obviously no meal for lions. Assuming you can, the problem translates to the one of single zebra that is 1/Z speed of L lions in best case for lions. And when/if any zebra gets out of the circle, the remaining ones get faster.

2 zebras have the obvious strategy of "we separate, one gets out first, now there is a single zebra with lions still far enough". For 3 zebras, I think 12-ish lions should work, but this is just a guess.

$\endgroup$
  • $\begingroup$ It's not possible to trap infinitely spaced zebras in finite time, but for any arbitrary spacing of zebras it will possible in finite time for a group of L lions to form a circle around a concentric circle containing group of 50 zebras, such that the ratio of the diameters will be 50/L. So if one were to try to have eight lions surround zebras, then no matter how far apart the zebras start, the lions could reach a state where they were equally spaced around a circle, and the distance between any of 50 zebras and the nearest lion was greater than the distance between lions. $\endgroup$ – supercat Apr 4 '17 at 16:12
  • $\begingroup$ What I can't figure out is how to define an invariant such that once such a state is reached, the zebras will be closer to capture after each move than they were before. $\endgroup$ – supercat Apr 4 '17 at 16:14
0
$\begingroup$

I think the question wording gives wiggle room for interpretation and that in turn affects the answer, or at least the proof involved. I could take the wording to mean each animal has to take a turn, lion then zebra, and each one is numbered 1 through 100 with lion 1 going first then zebra 1 then lion 2 zebra 2 so on and so forth, and we assume that these lions and zebras can communicate instantly across vast distances (entangled perhaps?) and also at any one time know where all the other animals were then the lions could pick one zebra to take out and work together to do this, as that particular zebra would only be able to move once every 200 turns meaning eventually it gets yammed.

If however any lion or zebra can have a their team's turn, they cannot communicate with each other and they don't know where the other animals are, whilst being on an infinite plain, I would think you would need to invoke chaos theory (of which the mathematics is slightly beyond me). Even though the movement of the animals could be described as systematic, on that scale and without knowledge of the position or behaviour of the other players each one would essentially be behaving randomly. If we continue on this track of thought we would undoubtedly encounter the uncertainty principle hence we can't actually determine the initial situation of the system (it being complex) and so we cannot accurately predict it's evolution.

I would argue that if any starting situation and turn structure you can think of was done over infinite time with infinite iterations, that eventually a zebra would be caught as I would expect every different outcome to be a possibility, like in the Mark Steel lecture where he runs at the wall a bazillion times and eventually pops through it 'coz quantum'.

$\endgroup$
  • $\begingroup$ So basically the essence of your answer is 'I don't really know'? Your second interpretation is the correct one, and I really don't think we have to specify every single kink in the question. $\endgroup$ – boboquack Apr 2 '17 at 9:26
  • $\begingroup$ My interpretation is that no one really knows $\endgroup$ – Scarabanja Apr 2 '17 at 9:33
  • $\begingroup$ Well, that's what the question's about! To see whether someone can find a good solution. $\endgroup$ – boboquack Apr 2 '17 at 10:21
  • $\begingroup$ @Scarabanja The lions are not numbered, 'turn' just means which team's turn it is, and the team can move the same animal multiple times. $\endgroup$ – ghosts_in_the_code Apr 2 '17 at 11:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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