18
$\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$
  • 2
    $\begingroup$ Minimum possible: zero (n=2p, p couples sitting close to each other and far from other couples). $\endgroup$ – Evargalo Jun 16 '17 at 12:38
  • 3
    $\begingroup$ @Goodra I don't see why partial answers can't be posted as answers. Please go ahead. $\endgroup$ – Batominovski Jun 16 '17 at 15:57
  • 2
    $\begingroup$ Consider reframing this question so that it is not about murder. $\endgroup$ – dbx Jan 10 '18 at 16:16
  • 2
    $\begingroup$ Because casually talking about shooting people with radioactive bullets is a weird thing to do, and completely unnecessary mathematically speaking? $\endgroup$ – dbx Jan 10 '18 at 16:29
  • 3
    $\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$ – dbx Jan 10 '18 at 17:00
6
+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$
  • 2
    $\begingroup$ nice argument - straightforward to follow $\endgroup$ – martin Jan 11 '18 at 1:47

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.