19
$\begingroup$

Trigger Warning: Murder is mentioned.

Let there be $n>1$ people (players) on a plane, each having a loaded gun and each being a perfect shot (assuming that each bullet is laced with one gram of plutonium-239 to ensure that hit targets do not survive and that the bullets are not penetrative enough to hit multiple bodies). Suppose that the distances between the players are pairwise distinct. At a signal, each player shoots the player closest to him (all the actions occur simultaneously). For those who have studied relativity, I assume that all players are initially at rest with respect to a fixed inertial frame so that it makes sense to discuss the simultaneity of the actions.

What is the minimum possible number of survivors? What is the maximum possible number of survivors? Do the answers change in higher dimensions (or even in other geodesic spaces like the $d$-dimensional torus)?

Below are my speculations.

The minimum is $n\!\!\mod\!2$ (this part is trivial and independent of the geometry of the space). I think the maximum for $n\geq 5$ is $n-\left(2q+s_r\right)$, if $n=10q+r$, where $q$ and $r$ are integers such that $0\leq r<10$, with $s_0=0$, $s_1=s_2=s_3=s_4=1$, and $s_5=s_6=s_7=s_8=s_9=2$. The case $n=10q+5$ seems to be the most difficult case for me. I found a mistake in my original bound, and now the new bound is worse. At the moment, the best bound is that at least $n-2q-s_r$ can survive, where $n=9q+r$ with $q,r\in\mathbb{Z}$ such that $0\leq r<9$, and $s_0=0$, $s_1=s_2=1$, and $s_3=s_4=s_5=s_6=s_7=s_8=2$.
Since a $d$-dimensional Euclidean space can be locally embedded into a $d$-dimensional geodesic space, I don't expect the answers to change (for a given dimension $d$) if the space is not Euclidean. However, the dimension should play a huge role in this shooting game.
EDIT I: After some more thought, I realized the answers may indeed be different in the non-Euclidean case. For example, a player cannot be shot by more than five bullets in the $2$-dimensional Euclidean case, but in a $2$-dimensional hyperbolic space, it seems to be possible that somebody is gunned down by at least six players.
EDIT II: In the $3$-dimensional Euclidean case, I expect the maximum number of survivors to be around $\frac{10}{11}n$. In the $d$-dimensional Euclidean space, this number should be around $\frac{L_d-2}{L_d-1}n$, where $L_d$ is the Kissing number in $d$ dimension.

$\endgroup$
25
  • 2
    $\begingroup$ Minimum possible: zero (n=2p, p couples sitting close to each other and far from other couples). $\endgroup$
    – Evargalo
    Commented Jun 16, 2017 at 12:38
  • 3
    $\begingroup$ @Goodra I don't see why partial answers can't be posted as answers. Please go ahead. $\endgroup$ Commented Jun 16, 2017 at 15:57
  • 2
    $\begingroup$ Consider reframing this question so that it is not about murder. $\endgroup$ Commented Jan 10, 2018 at 16:16
  • 4
    $\begingroup$ no, my argument is that math teachers should not frame their problems around killing people. obviously you're not receptive to the idea, no need to get so defensive. It was a suggestion, not a command. $\endgroup$ Commented Jan 10, 2018 at 17:00
  • 3
    $\begingroup$ @Batominovski Try posting a question where every person rapes the person closest to them, and see how "I am only receptive to suggestions that have actual mathematical values such as suggestions for clarification or terminology" works out for you ;) More seriously, mathematics does not exist in a vacuum, it is a community. While you insist that only the mathematics underlying the question matters, this is manifestly false for you and for anyone else. $\endgroup$ Commented Jan 11, 2018 at 2:17

1 Answer 1

5
+50
$\begingroup$

This answer considers only the original planar version of the game.

We already know that each player of this not very jolly game is shot by at most $5$ players (see, for instance, Lemma 1 here. In the next Lemma 2 this results implies that the maximum possible number $s(n)$ of survivors is at most $4n/5$ for each $n$.

We can improve this bound as follows. We say that a player is hardly killed if he is shot by exactly $5$ players. We need two more lemmas .

Lemma 3. A victim of a hardly killed player is his killer.

Proof. The proof is similar to that of Lemma 1. Suppose to the contrary, that the player located at the point $O$ has been shot by players located at points $A_1,\dots, A_5$ and has shot a player located at a point $A_6$. Draw rays $OA_1,\dots,OA_6$. Then there exist points $A_i$ and $A_j$, $i\not =j$ such that the angle $A_iOA_j\le \pi/3$. Therefore the angle $A_iOA_j$ is not the largest angle of a triangle $A_iOA_j$. Therefore the side $A_iA_j$ is not the largest side of the triangle $A_iOA_j$. If none of $A_i$ and $A_j$ has been shot by $O$ then $|A_iA_j|>|A_iO|$ and $|A_jA_i|>|A_jO|$, a contradiction. So, say, $A_i$ has been shot by $O$. Then $|A_iO|<|A_jO|$ and $|A_iA_j|>|A_jO|$, a contradiction again. $\square$

Lemma 4. There are no pair of hardly killed players such that each player from the pair is a victim of the other.

Proof. Suppose to the contrary, that there is such a pair. Consider a set $S$ consisting of $10$ players constituted by this pair and $8$ players who have shot a player of the pair. Since for each player of the set $S$ his victim also belongs to $S$, if we remove the rest of the players then the players of $S$ would shot the same players as before. That is we obtain a set of $10$ players with only two killed, that is impossible by an answer to a problem G7 from 41st IMO shortlist. $\square$

Now denote the set of the players by $P$ and let $v:P\to P$ be a map such that $v(p)$ is a victim of the player $p$ for each $p\in P$. Let $H\subset P$ be the set of hardly killed players. Lemma 3 states that $v(v(p)=p$ for each $p\in H$, so the map $v|H$ is injective. By Lemma 3 and Lemma 4, $v(H)\subset P\setminus H$.

Assume now that there are $h$ hardly killed players. The each of the remaining killed players was shot by at most $4$ players, so it total there are at least $$\max\{2h,h+(n-5h)/4\}=\max\{2h,(n-h)/4\}\ge 2n/9$$ killed players. Thus $s(n)\le (7/9)n$.

The precise calculation of the maximum yield no better result. Namely, if $n=9q+r$ as in your question then it can be easily checked then $\max\{2h,(n-h)/4\}=2q+r/4$ and $\lceil 2q+r/4\rceil=\lceil 2n/9\rceil$. Nevertheless, this shows that your lower bound for all $r$ but $3$, $4$ is exact and in the remaining cases at most $1$ worse than then above upper bound.

$\endgroup$
1
  • 2
    $\begingroup$ nice argument - straightforward to follow $\endgroup$
    – martin
    Commented Jan 11, 2018 at 1:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .