Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

A group of ten bandits stand in a flat desert, with no pair the same distance apart. Tensions grow, and at the crack of dawn each bandit fires a single bullet at the bandit closest to him. All have perfect aim and all those that are hit are killed.

Must one of them live to tell the tale? How many of them could possibly survive?

share|improve this question
    
@Maylor might be a stupid question - they can have only 1 shot? – Alex Mar 3 at 22:52
    
    
One shot. oops. – rnaylor Mar 3 at 23:06
1  
I'm thinking something like 3 in a triangle and the rest surrounding that triangle. I think there's a way to get 7 to survive but I'm not good enough at geometry to prove it – Slepz Mar 3 at 23:54
1  
One more comment: In a truly flat desert, the "crack of dawn" will happen for the easternmost bandit before it happens for the westernmost bandit. In the American Southwest, where this is presumably happening, "dawn" moves west at about 1250 feet per second. – Aric TenEyck Mar 4 at 15:50
up vote 19 down vote accepted

Up to 7 can survive (but it is possible that none do).

For maximum survival, set up a pentagon and a square such that each gunman is closer to the center of their shape than the other corners. Then, have the same person be closest to each center. All the corners shoot the center, and the two centers shoot the same corner.

All seven other corners survive.

Rough diagram:

Living

For minimum survival, just pair them all off. Everybody shoots their partner, and they all die. (These pairs are not actually parallel, since the distances along each side can't be the same, but that's easy enough to make happen)

Dying

The theoretical maximum would be 8 - since the two closest gunmen must shoot each other. However, for this to work, we need everybody else to be closest to one of those two gunmen. There's no way to have two people be closer to the center than each other if their angle around the center is less than or equal to 60*, so hexagons are right out. Thus, we would need two pentagons such that one's corner is another's center. Unfortunately, this causes some of the corners to be nearer to the corners of the other pentagon than their own center.

Example of failure:

Failure

share|improve this answer
    
The reasoning needed to exclude 8 as a solution (you don’t exclude 9 or 10 either, but those are easy) is a bit flimsy. I’ll try to edit a more rigorous proof in today. – Édouard Mar 4 at 7:27
    
It does exclude 9 and 10, since the two closest gunmen always shoot each other. The proof that 8 fails is a little hand wave-y, though - you'd need to demonstrate that given two people A and B, there's no way to assemble 8 more people such that each is closer to A or B than the other 7, and none of them are closer to A or B than A and B are to each other. I think this is already impossible, not even taking into account the different distances requirement. – Zerris Mar 4 at 14:09
    
Yep, I somehow skipped the sentence which excluded it. To be blunt, it’s not very clear either. – Édouard Mar 4 at 15:37
    
Theoretically, if 9 people were somehow arranged such that they all shared the same closest target, then 9 shots would hit one bandit, but THAT bandit must still fire at his own closest target, meaning that at least 1 of the other 9 must also die. Therefore the maximum number of survivors must be a value less than 9. – JessieArr Mar 4 at 17:29
1  
It is absolutely clear that $9$ and $10$ are excluded. I think sometimes a little 'reader discernment' is advised. – Fimpellizieri Mar 4 at 19:47

Maximization

The maximum value of dead bandits clearly is $10$ (so that all are dead). For instance, put five bandits at the points $(100,0)$, $(200,0)$, $(400,0)$, $(800,0)$, $(1600,0)$ and five bandits at the points $(100,1)$, $(200,2)$, $(400,4)$, $(800,8)$, $(1600,16)$. Then no pair is the same distance apart, and the five pairs with equal $x$-coordinates kill each other.


Minimization

The minimum value of dead bandits is more difficult to determine. We reformulate the minimization problem as:

Given a set $S$ of $10$ points in the plane, such that the distances between them are all distinct. For each point $p\in S$ we mark the point $q\in S-\{p\}$ that is nearest to $p$. Find the least possible number of marked points.

(1) We observe that each point $x\in S$ is the nearest to at most five other points in $S$. Indeed, for any six points $p_1,\ldots,p_6$ one of the angles $\angle p_ixp_j$ is at most $60^{\circ}$, in which case the distance $p_ip_j$ is smaller than one of the distances $xp_i$ and $xp_j$.

(2) It follows that at least two points are marked.

(3) Now suppose that exactly two points, say $x$ and $y$, are marked. Then $x$ is the closest point to $y$, and $y$ is the closests point to $x$. So by the observation (1) the remaining eight points in $S$ split into two groups $S_x$ and $S_y$ of four points each, so that their closest points are $x$ and $y$ respectively.

Denote $S_x=\{a_1,a_2,a_3,a_4\}$ and $S_y=\{b_1,b_2,b_3,b_4\}$, so that the angles $\angle a_ixa_{i+1}$ are successively adjacent as well as the angles $\angle b_iyb_{i+1}$, and so that $a_1$ and $b_1$ lie on one side of the line through $xy$ while $a_4$ and $b_4$ lie on the other side of this line.

Since all the angles $\angle a_ixa_{i+1}$ and $\angle b_iyb_{i+1}$ are greater than $60^{\circ}$, it follows that $$ \angle a_1xy + \angle yxa_4 + \angle b_1yx + \angle xyb_4 ~<~ 360^{\circ}.$$ Therefore $\angle a_1xy + \angle b_1yx < 180^{\circ}$ or $\angle yxa_4 + \angle xyb_4 < 180^{\circ}$. Without loss of generality, let us assume the first inequality.

(4) Next, note that the quadrilateral $xyb_1a_1$ is convex because $a_1$ and $b_1$ are on different sides of the perpendicular bisector of $xy$. From $a_1b_1 > a_1x$ and $yb_1>xy$ we get the inequalities $\angle a_1xb_1 > \angle a_1b_1x$ and $\angle yxb_1 > \angle xb_1y$. Adding these two inequalities yields $\angle a_1xy > \angle a_1b_1y$. A symmetric argument yields $\angle b_1yx > \angle b_1a_1x$.

These last two inequalities imply $$180^{\circ} > \angle a_1xy +\angle b_1yx > \angle a_1b_1y + \angle b_1a_1x.$$ Hence the sum of the angles of the quadrilateral $xyb_1a_1$ is less than $360^{\circ}$, which is a contradiction. Consequently at least three points are marked.

(5) Finally, the configuration with ten points $(-100,0)$, $(0,0)$, $(101,0)$, $(213,0)$, $(0,110)$, $(0,-111)$, $(-120,110)$, $(-120,-111)$, $(121,110)$, $(121,-111)$ shows that the minimum with three marked points indeed can be attained.


Summary

The maximum number of dead bandits is $10$, and the minimum number of dead bandits is $3$.

share|improve this answer
    
Your inequalities are the wrong direction in the lines involving 360* and 180*. I can't tell how far that propagates, though, so I'm hesitant to correct it for you. – Zerris Mar 5 at 0:13

I believe the max that can survive is 7. Arrange the bandits in approximately two half hexagons. For one hexagon, it's 5 bandits, one at each point and one in the middle. More than a side length away is the other hexagon, parallel, with one exterior point empty. Between the two is the last bandit.

enter image description here

To satisfy the distance clause, just have the outer bandits be closer to the center than each other, and with very small differences the overall situation stands.

share|improve this answer
    
I feel like this ignores "with no pair the same distance apart". – Ian MacDonald Mar 3 at 23:54
    
"no pair the same distance apart". You need to make this hexagon more wobbly – Slepz Mar 3 at 23:55
    
@Slepz Wobbles ftw. – JonTheMon Mar 3 at 23:57
    
still needs some proving. you're basically describing an ellipse where the eccentricity (distance between focal points) is X and the radius less than 2X. For this to work, the perimeter of this ellipse would have to be greater than 14X – Slepz Mar 4 at 0:05

6 survivors is the most. 2 sets of 5. 4 corners and 1 in the middle. All different distances apart from middle, but the 4 outsiders shoot the middle guy and the middle guy shoots the closest corner.

A pentagon and triangle work the same way and if you go with a hexagon you run into issues with the outsiders shooting each other.

share|improve this answer

I can guarantee at least three will survive.

Take one gunman, called Gunman 1. He is separated from Gunman 2 by a distance $X_1$. Gunman 3 is on the other side of Gunman 2, separated by a distance $X_2$, where $X_2<C_1$. Continue doing this until you reach Gunman 7. Each $X_n<X_{n-1}$. Therefore, Gunman $M$ will shoot Gunman $M+1$, with the exception of Gunman 7, who will shoot Gunman $6$.

Now take the remaining three gunmen and place them 90 degrees apart around Gunman 1, forming a sort of cross. Gunman 8 is a distance $A$ from Gunman 1, Gunman 9 is a distance $B$ from Gunman 1, and Gunman 10 is a distance $C$ from Gunman 1. Here, $C\neq A\neq B\neq C$, all of which are greater than $X_1$. They are separated so that the distance between any of these three gunmen is greater than the distance between each gunman and Gunman 1.

Gunman 8, Gunman 9, and Gunman 10 will all shoot Gunman 1 and survive.

I suspect that you could fit more than these three guys around Gunman 1 - and I don't know just how many - but I don't know for sure.


Zerris has found a better related configuration.

share|improve this answer

"Nearest" involves two points, so every pair of bandits would shoot each other. None would survive.

EDIT: Since I was marked down, I'll explain further. The important part is "no pair the same distance apart", which means there would be no overlap on shooting. Folks could only survive if that condition wasn't present, and one or more bandits got two bullets.

share|improve this answer
2  
suppose I place 9 of the gunmen as close as I can without any pair being the same distance apart. I then place the final gunmen so that his distance from every other gunman is greater than any other pair distance (think off to infinity). This final gunman will shoot one of the first nine, but none of those nine will shoot him. – Slepz Mar 3 at 23:52
1  
or imagine with three placed in a non-equilateral triangle. one of them will get shot twice. – Slepz Mar 3 at 23:53
    
It's not clear which subquestion you're trying to answer. Are you describing an example you're thinking of which you think achieves the minimum number of survivors? Or the maximum number of survivors? Or are you saying none would survive no matter what the configuration? – Don Hatch Mar 4 at 3:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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