9
$\begingroup$

A group of robbers are in a standoff. Each robber has two guns that they must point at two other distinct robbers. What is the minimum number of robbers in the standoff so that a situation is possible where no two robbers are mutually shooting at one another?

$\endgroup$
2
  • 2
    $\begingroup$ Welcome to Puzzling, take our tour! Could you please provide proper attribution for this question? $\endgroup$
    – bobble
    Oct 20, 2022 at 18:57
  • 1
    $\begingroup$ Seems like the last clause should be "where no two robbers are mutually pointing at one another". $\endgroup$
    – LarsH
    Oct 21, 2022 at 18:46

4 Answers 4

14
$\begingroup$

There must be at least

5 robbers.

This is because

in order to be able to have at most one gun per robber pair, there must be at least as many pairs as there are guns.
This means $2n \leq \frac{n(n-1)}{2}$, which solves to $5 \leq n$.

For completeness, since everyone insists:

When there are 5 robbers, you can choose any robber and partition the other 4 into two pairs: one pair the robber points at, and the other pair points at the robber. There is, up to permutation of the robbers, only one way to do this: place the robbers in a circle and partition according to which side of the robber the other robbers are on as in @cap's solution.

$\endgroup$
3
  • $\begingroup$ You type faster than me. And you jax'd it! $\endgroup$ Oct 20, 2022 at 19:21
  • 3
    $\begingroup$ That final inequality is in the wrong direction. I also think that even though you've established a lower bound, you haven't shown that it is actually possible with that minimum number of robbers. $\endgroup$ Oct 21, 2022 at 7:55
  • 1
    $\begingroup$ Yea, a good answer will need to construct the situation for n=5, like cap's answer does $\endgroup$
    – justhalf
    Oct 21, 2022 at 11:14
9
$\begingroup$

We need at least

5 robbers.

Each robber has 2 people pointing a gun at him and he needs 2 robbers to point his guns at for a total of at least 5. Imagine they all stand in a circle and each robber points his left gun at the guy to his left and his right gun at the next guy to the left.

enter image description here

$\endgroup$
2
  • 4
    $\begingroup$ I feel like this could use more justification that this is the minimum. While you've shown a valid configuration for the proposed minimum number of robbers, you've only demonstrated that this approach doesn't work for a lower number, not that there is no approach for a lower number $\endgroup$
    – StephenTG
    Oct 20, 2022 at 19:03
  • 1
    $\begingroup$ @ StephenTG good point, I'll make it more explicit. $\endgroup$
    – caPNCApn
    Oct 20, 2022 at 19:06
5
$\begingroup$

Each Robber must choose 2 paths, for 2n used paths.

Once a path is chosen, it is excluded in the reverse direction. That is, A->B precludes B->A.

So the number of paths available is nC2, [Combination formula] or the number of ways we can choose 2 people.

This formula simplifies to n(n-1)/2.

For n = 3, we need 6 paths, and there are 3 available. [No good]
For n = 4, we need 8 paths, and there are 6 available. [No good]
For n = 5, we need 10 paths and there are 10 available. [Good!]

The paths need grows linearly, and the paths available grows quadratically, so there will always be more paths available than needed for larger values of n.

$\endgroup$
0
$\begingroup$

Let's start with the first robber ($R_1$, $n=1$) and work up. She needs $+2$ targets ($n=3$). $R_2$ and $R_3$ can't point at $R_1$, and at least one of them can't point at the other, so at a minimum $+2$ more targets must exist ($n=5$).

We can check whether this is a valid solution by:

having each robber $R_n$ aim at the next two and verifying that $R_n$ is in turn targeted exactly twice: $$R_1 => R_2, R_3$$ $$R_2 => R_3, R_4$$ $$R_3 => R_4, R_5$$ $$R_4 => R_5, R_1$$ $$R_5 => R_1, R_2$$

$\endgroup$
2
  • $\begingroup$ You claim that R2 and R3 can't point at each other, and then post a solution where R2 points at R3 - it is certainly true that both of them can't aim at each other, and this is sufficient for your bound, but your proof as written is flawed. $\endgroup$ Oct 24, 2022 at 16:23
  • $\begingroup$ @AxiomaticSystem ha good catch I misworded that, justification updated. $\endgroup$
    – brichins
    Oct 25, 2022 at 18:56

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