9
$\begingroup$

$101$ gunmen stand in a field. At high noon, everyone shoots the gunman standing closest to him. If there are several gunmen who are equally close, they shoot the tallest one of them. No two gunmen are the same height.

Prove that there will be a man left standing. In other words, prove that someone will not get shot.

$\endgroup$
  • $\begingroup$ If 2 men are very close each other, do they both die? $\endgroup$ – leoll2 Jun 13 '15 at 18:46
  • $\begingroup$ No, I mean if 2 men are far from the group and close each other, so that their target is the other man, do they both die? In other words, if A aims B and B aims A, do they both die? $\endgroup$ – leoll2 Jun 13 '15 at 18:49
  • 3
    $\begingroup$ @leoll2 Oh, I see! Yes, they do both die! Two people can shoot each other. $\endgroup$ – Mike Earnest Jun 13 '15 at 18:50
  • $\begingroup$ If 2 gunmen are left after all the shooting, do they shoot each other? i.e. are there multiple rounds of shooting? $\endgroup$ – Trenin Jun 15 '15 at 18:25
  • 1
    $\begingroup$ @Trenin No, there is only a single shot fired by each gunman $\endgroup$ – Mike Earnest Jun 15 '15 at 18:54
9
$\begingroup$

Create a functional graph with an edge from each shooter to each victim. A source-free functional graph must be a disjoint union of oriented, possibly degenerate (i.e., 1- or 2-vertex) cycles. This one must contain at least one odd cycle because there are an odd number of vertices. And that cycle is not a 1-cycle because no gunman shoots himself. Call it $(v_0,v_1,\ldots,v_n,v_0)$.

Now either distance or height causes the $v_0$ gunman to prefer $v_1$ over $v_n$; the edge $(v_0,v_1)$ represents a distance no longer than that of $(v_0,v_n)$, and an analogous argument can be applied around the cycle. Thus, by transitivity, all edges represent equal distance. But then shots must have been decided by height, and $v_1$ is taller than $v_n$. Again, this argument can be carried around the cycle (twice because it depends on a relationship between vertices two edges apart, two fortunately not having any common factors with the cycle length) to conclude that all gunmen in the cycle are of equal height. But this contradicts the problem statement, so source-freeness is impossible.

$\endgroup$
  • 2
    $\begingroup$ You don't need that the cycle has odd length - just length of at least $3$. If we have even length, then all the people indexed by $v_{2n}$ will have the same height as will all those indexed by $v_{2n+1}$ (though the two sets might have different height) - which, more generally, proves that the only way everyone could die in such a duel would be if everyone paired up and shot their partner. $\endgroup$ – Milo Brandt Jun 18 '15 at 1:02
1
$\begingroup$

Some definitions:

  • $B$ is a gunmen.
  • $b$ is the distance of $B$ from $A$.
  • $A→B$ means that $A$ shoots $B$.
  • Cycle means that $A→B, B→C, ..., n→A $.

Problem:
Since the number of elements is odd, so there must exist at least a group of 3 (or more) gunmen which shoot themselves, if we want all them killed (aka a cycle). We have to prove that given $n\geq3$ gunmen, no cycle can exist, without violating your conditions (height, distance).

Proof:
We said above that if we want all the men to be dead, there must exist a cycle.
Let's try to build a cycle. First, we take an element $A$, then we add an element $B$ at distance $a$ from $A$.
We want $A→B$ and $B→C$ (not $B→A$), so the element $C$ must be distant from $B$ less than $a$: let's say $C$ is far $b$ from $B$, where $a>b$.
Let's keep adding elements, whose distances are such that $a>b>c>...>z$.
Now, we have to close the cycle, and make sure that $Z$ (the last element) shoots $A$ (the first one), thus the distance $a$ (from $Z$ to $A$) must be smaller than $z$.
We deduce that $a>b>c>...>z>a$, so $a>a$. Paradox!

Here you can visually see what happens when you try to build a cycle, starting from $A$. When you have to close it, it happens that $a<b$, which is in conflict with the hypothesis that $A$ chose $B$. enter image description here

$\endgroup$
  • $\begingroup$ Who downvoted this? Do you think that my proof is incomplete or incorrect? Please give a constructive feedback, not only a downvote! $\endgroup$ – leoll2 Jun 17 '15 at 11:12
  • $\begingroup$ Nice argument and diagram. I'd just suggest a couple of wording changes: (1) Your "We have to prove that given n>=3 gunmen, no cycle can exist," sounds to me like "We have to prove that given n>=3 gunmen, no subset of them can be a cycle," which I don't think you mean; I'd rephrase to "We have to prove that given n>=3 gunmen, they cannot form a cycle,". (2) Replace "Paradox!" with "Contradiction!" $\endgroup$ – Don Hatch Mar 4 '16 at 3:14
1
$\begingroup$

There is no proof that always a gunman will remain standing, unshot and alive, assuming multiple shots are allowed (which was not explicitly stated, and seems quite natural given it's a shootout). I present a counterproof.

Let 101 gunmen stand at the vertices of a regular 101 sided polygon. For any given gunman, he is equally distant to exactly 2 other closest gunmen.
Let the height of each gunman be equal to the gunman's index, in units. (gunman 1 is 1 unit tall, and gunman 101 is 101 units tall, leading to a very large variation!).

Assign gunman 101 to any vertex. Following along one side of the polygon, assign even heights in decreasing order, and along the other assign odd heights in decreasing order.
Thus 98 - 100 - 101 - 99 - 97.
Similarly, at the other end, 5 - 3 - 1 - 2 - 4 - 6. (perspective changed, so ordering changed too)

After the first round of shooting both 1 and 2 live, because 3 shoots 5 and 4 shoots 6. They are the only gunmen to live.
At the second round, gunmen 1 and 2 shoot each other.

$\endgroup$
  • $\begingroup$ Multiple shots are not possible $\endgroup$ – Malady Jun 16 '15 at 0:23
1
$\begingroup$

Proof by induction. Let the two closest people be A and B, and assume that this pair is distinct for now. They shoot at each other, so we may remove A and B and consider the other n-2 people. By induction hypothesis, if the n-2 people shoot amongst themselves someone will live. But some of these people may shoot at A or at B, but this is even better because less bullets will be used at the n-2 people, so at least more people will live. Eventually, since n is odd, we will get to n=1 who shoots nobody.

If there are multiple disjoint pairs of people with the minimum distance, consider them separately. But if there is a network (eg. AB=BC=CD=DA=d) then the shortest person in that network will live because those at distance d from him ... I'm stuck here, sorry

$\endgroup$
  • 1
    $\begingroup$ Welcome to Puzzling SE! Your answer is incomplete, an induction proof requires strictness. Also, if C shoots A, not necessarily A shoots C. Edit your question, or it may deleted! $\endgroup$ – leoll2 Jun 14 '15 at 8:09
  • $\begingroup$ For some reason half of it was cut off. $\endgroup$ – Faraz Masroor Jun 14 '15 at 15:37
1
$\begingroup$

Let's say that the shooters are in a circle in ascending height order. If all shooters are equidistant, then the shots will go from the shortest to the tallest, with the tallest shooting at the 2nd tallest (his choices are his target, or the shortest, and as they are equidistant, not the shortest). Ideally, we'd want the tallest to shoot the shortest.

The only way to do that is to move the tallest closer to the shortest. But, that then makes the shortest target the tallest instead of the 2nd shortest. Well, then move the 2nd shortest closer to the shortest; but then the 2nd shortest shoots the shortest.

So, you can't have everyone dead.

$\endgroup$
  • $\begingroup$ And what if the shooters aren't in a circle? $\endgroup$ – leoll2 Jun 15 '15 at 16:59
1
$\begingroup$

Considering in sequence, where N is the number of gunmen and A, B, C, etc. are individual representations of same:

Trivially:

  • Where N = 1, all gunmen survive as none can shoot themselves.
  • Where N = 2, both gunmen die as no other gunman can be further away.
  • Where N = 3, one gunman must live, as:

Let x, y, and z be the distances A->B, B->C, C->A respectively.
If x=y=z (a triangle or 3-sided polygon), then A, B, and C will all shoot the tallest other person. Since no two gunmen have the same height, one gunman will be shot twice and one will not be shot at all as there are only three bullets.
If x>y>z or x>y=z, then A will shoot B, while B and C will shoot each other. (Rotating the distance assignments incorporates all possible combinations of distances between the three gunmen.)

Extended:

  • Where N = 4 and for all other even numbers of gunmen, it is possible to trivially create a scenario where pairs of gunmen stand next to each other, yet further away from all others; in this scenario all gunmen die, as it is the instance of N = 2 repeated N/2 times.
  • Where N = 5, again one gunman must live:

Let v, w, x, y, and z be the distances between A-B, B-C, etc. respectively (as with N=3).
As with N = 3, if v > w > x > y > z, v > w = x = y = z, or variants of equality where v > (some combination of w,x,y,z), then A will live as no gunman can be closest to A by definition.
If v=w=x=y=z (a 5-sided polygon), then everyone is closest to 2 other people and will shoot the tallest other person. Since no two gunmen have the same height, one must be the tallest, and that person will be shot by both people beside him; since the only way for all gunmen to die is for each gunmen to be shot only once, then someone must live.

This extends out for all odd numbers of gunmen, as the definition of an N-sided polygon is that all the sides (ie distance between gunmen, who are the vertices) be equal. Thus, where N = 101, one gunman must survive.

$\endgroup$
0
$\begingroup$

EDIT: Found out you cannot have multiple rounds, so not a valid answer.

If you can have multiple rounds of shooting, a counter example is trivial.

Take the shortest shooter ($A$) out of the group. Order the rest on the points of a 100 sided regular polygon in order of height.

Place $A$ at the centre of the polygon.

Everyone around the perimeter will shoot at the tallest of their two neighbours. The shortest person on the polygon ($B$) is not targeted by anyone. And neither is $A$. The tallest person is targeted three times - once by $B$, once by the second tallest, and once by $A$.

After all the tall people die, $A$ and $B$ shoot each other.

$\endgroup$
0
$\begingroup$

Assume one needs to prove that 'at least' one man will be left standing?

a scenario in which more than 1 man will be left is as follows

7 gun men standing in formation of a regular hexagon with the tallest one at the center. At noon, everyone at the node will fire at the guy in the center. The guy in the center will fire at the 2nd tallest guy in the group. 5 men standing in the end. (assuming no multiple fires)

We can break the group of gunmen in two groups:

1) Gunmen not standing equidistant with others- they will die in pairs, ie shoot each other.

2) A cluster(s) of gunmen equally close: the tallest one gets killed, and the tallest one kills one more (the 2nd tallest from amgst the ones equidistant from him) i.e. gunmen from this group also die in pairs.

So long as the total number of gunmen is an odd number, there will be one or more left standing after the shootout.

$\endgroup$

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.