Don't lose your marbles

Probability Level 5

Let $p = 2017$ be a prime. Suppose that the number of ways to place $p$ indistinguishable red marbles, $p$ indistinguishable green marbles, and $p$ indistinguishable blue marbles around a circle such that no red marble is next to a green marble and no blue marble is next to a blue marble is $N$ . (Rotations and reflections of the same configuration are considered distinct.) Given that $N = p^m \cdot n$ , where $m$ is a non-negative integer and $n$ is not divisible by $p$ , and $r$ is the remainder of $n$ when divided by $p$ , compute $pm + r$ .

The answer is 3913.

1 solution

Alan Yan
Jan 14, 2018

The ordering will look like groups of red marbles and green marbles where each group is separated by a blue marble. Let $k$ be the number of red groups and summing over $1 \leq k \leq p-1$ , we have $N = 3 \sum_{k = 1}^{p-1} \binom{p-1}{k-1} \binom{p-1}{k} \binom{p}{k} = 3p \sum_{k = 1}^{p-1} \frac{1}{k} \binom{p-1}{k-1}^2 \binom{p-1}{k}.$ Furthermore, $\sum_{k = 1}^{p-1} \frac{1}{k} \binom{p-1}{k-1}^2 \binom{p-1}{k} \equiv \sum_{k = 1}^{p-1} \frac{(-1)^k}{k} \equiv - \sum_{k =1}^{p-1} \frac{1}{k} \binom{p-1}{k-1} \equiv \frac{2 - 2^p}{p} \pmod p$ So, $m = 1$ and $r \equiv \frac{3(2 - 2^p)}{p} \equiv 1896 \pmod p.$ Hence, the answer is $2017 + 1896 = \boxed{3913}$

Don't lose your marbles

The answer is 3913.

1 solution

0 pending reports