View topic - How many distinct ways that silence will occur? • Art of Problem Solving

Suppose that there $2n$ people in the circle. Let's join people directly across the circle into $n$ (ordered) pairs. Depending on who the people in such a pair look up to (i.e., left or right neighbor, or the other member of the pair), there are $3\cdot 3 = 9$ different types of pairs possible. However, one of these types always results in screaming (when the people in a pair look up to each other). We focus on the remaining $8$ types and represent them as vertices in a graph $G$ . It is easy to figure out all types of two adjacent (along the circle) pairs in the circle that are compatible (i.e., that can appear in a silent configuration), we represent them as edges in $G$ .

Now, each silent configuration corresponds to a path on $n + 1$ vertices and $n$ edges in $G$ , such that the starting and ending vertices correspond to the same pair but with the order of people reversed. It is easy to compute the number of such paths using the adjacency matrix $A$ (of size $8\times 8$ ) of $G$ . For $n = 2,3,\dots$ the number $s_n$ of silent configurations is:
$30, 156, 826, 4406, 23562, 126104, 675074, 3614142, ....$
They satisfy the following recurrent relation (which is easy to obtain from the characteristic polynomial of $A$ ):
$s_{n + 4} = 8 s_{n + 3} - 16 s_{n + 2} + 10 s_{n + 1} - s_n$
In particular, $s_5 = 4406$ and the required probability equals
$\frac {s_5}{3^{10}} = \frac {4406}{59049}\approx 0.074616$

How many distinct ways that silence will occur?

Login