Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$21$ players stand in the circle. Every player chooses aim for the shot - another player. No one can shoot themselves or into the air.

What the probability that there are at least $2$ players that have taken aim at each other?

share|improve this question
    
I think the problem is about the aiming, not the shooting/hitting/missing/killing part. –  Hagen von Eitzen Oct 30 '12 at 21:06
    
Yes, everyone kills with the same probability. –  Xxx Oct 30 '12 at 21:09
    
It's the same - aiming, shooting, killing etc –  Xxx Oct 30 '12 at 21:09
    
The question is still unclear to me. Does each player have a gun and all turns are taken simultaneously, or is there a single gun being passed around the circle? –  Austin Mohr Oct 30 '12 at 21:32
    
everyone has a gun. To clearify let's think we stop the game when everyone aims simultaneously and noone shoots. –  Xxx Oct 30 '12 at 21:40
add comment

2 Answers 2

up vote 1 down vote accepted

The solution is

$$1+\sum_{s=1}^{\lfloor n/1 \rfloor}(-1)^s\frac{n!}{2^ss!(n-2s)!(n-1)^{2s}}$$

with $n=21$

The problem is explained in

http://msor.victoria.ac.nz/twiki/pub/Courses/MATH214_2009T1/Enumeration/214_2009_notes3.pdf

page 20, where it is called Zen stares.

Credits go to the people from www.wiskundeforum.nl (a Dutch math forum).

share|improve this answer
    
are you sure the solution is written wright? –  Xxx Nov 1 '12 at 14:30
    
There was a small mistake. I think it is correct now. –  wnvl Nov 1 '12 at 16:19
add comment

The problem amounts to counting the permutations of $n=21$ elements that have no fixed point (these are the legal configurations, since no one can aim at themselves), and counting how many of these have no $2$-cycle. Each of these numbers can be calculated by a simple recurrence.

First, consider permutations of $n$ elements with no fixed point (that is, derangements). Let $A_{n}$ be the number of derangements of order $n$. Each derangement of $n-1$ elements can be used to produce $n-1$ distinct derangements of $n$ elements, by inserting (in the cycle representation) the $n$-th element in any of $n-1$ locations. In addition, each permutation of $n-1$ elements with exactly one fixed point can be used to produce a unique derangement of $n$ elements (by pairing the new element with the existing fixed point). But the number of permutations of $n$ elements with exactly one fixed point is just $nA_{n-1}$: you must choose the fixed point, then form a derangement of the remaining elements. The result is $$ \begin{eqnarray} A_{n} &=& (n-1)A_{n-1} + (n-1)A_{n-2} \\ &=& (n-1)\left(A_{n-1} + A_{n-2}\right), \end{eqnarray} $$ where $A_{0}=1$. This sequence starts with $1,0,1,2,9,44,265...$ (OEIS:A000166) and $A_{21}=18795307255050944540 \approx (21!)/e$.

The same reasoning can be used to count permutations without fixed points or $2$-cycles. Let $B_{n}$ be the number of these of order $n$. Again, we can produce $n-1$ such permutations of order $n$ from each of order $n-1$; and we can also produce $2$ such permutations of order $n$ from each permutation of order $n-1$ with exactly one $2$-cycle (and no fixed points). The number of permutations of $n$ elements with no fixed points and exactly one $2$-cycle is $\frac{1}{2}n(n-1)B_{n-2}$: you must choose the pair involved in the $2$-cycle, then permute the remaining elements with no $2$-cycles or fixed points. The result here is $$ \begin{eqnarray} B_{n} &=& (n-1)B_{n-1} + (n-1)(n-2)B_{n-3} \\ &=& (n-1)\left(B_{n-1} + \left(n-2\right)B_{n-3}\right), \end{eqnarray} $$ where $B_0=1$. This sequence starts with $1,0,0,2,6,24,160,1140,...$ (OEIS:A038205), and $B_{21}=11399930109077490560\approx A_{21}/\sqrt{e} \approx (21!)/e^{3/2}$.

The probability that no two players are aiming at each other is therefore $$ \frac{B_{21}}{A_{21}} \approx \frac{1}{\sqrt{e}} = 0.60653..., $$ as it is for all reasonably large $n$.

share|improve this answer
add comment

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.