I'm trying to solve a challenge from Matheletics '13:
Micheal Nobbs is organizing a training camp for identifying new talents in Indian Hockey. The camp witnessed a total of ($3K+1$) players. Each of the players was given a unique number between $1$ and $3K+1$. On the first day of the camp, Micheal Nobbs wants all the players to align in a line for a brief introduction about the camp. He wants that players must align themselves in such a way that:
“For each player $P$, the sum of numbers given to each player standing before $P$ in the line, including the number given to player $P$, should not be divisible by $3$”.
In how many ways the players can align themselves according to the condition given by Michael Nobbs?
The number of ways can be very large, so output the number of ways modulus $1000000007$ i.e. ($10^9 + 7)$.
Small Case: $K=200$
Large Case: $K=10^8$
I have solved some other challenges, where by using mathematical framework I was able to get the right solution or to simplify the proposed problem to a much simpler one. I assume this is the same case since going through all permutations is very time expensive.
Since now I was unable to find a property by which the statement $$3 \nmid \sum_{i=1}^{k} P_{perm_i}, k \in [1, 3K+1]$$ or the whole problem can be simplified.
Can anybody help with a suggestion on how to successfuly solve the problem for small and large case?
Let's just consider the remainders $\pmod3 $, and work from the tail of the line. Since $1+2+3+\cdots+3k+1\equiv1$, we know that the last one should be $\equiv0 \text{ or }2$, because if it is $\equiv 1$, then the the sum from the next one to the first one would be $\equiv 0$. So let's say I choose an arbitrary numbers of $0$'s, then I will have to choose a $2$ eventually. Then after an arbitrary number of $0$'s I will have to choose a $1$ eventually. And so on. But at the end, we need to have two consecutive(just with zeroes between them) ones. So in order to avoid problems, a $1$ has to be at the top of the line. $$2,1,2,1,2,1,\cdots2,1,1$$ With the zeroes interleaving those numbers arbitrarily. There are $k$ zeroes, $k+1$ ones and $k$ twos. So we have to choose $k$ places out of $3k$ avaibable(the top one must be a $1$) to put the zeroes, where order matters, and then fill the remaining spaces with our pattern.Then, permute the $1$s between them and the $2$s between them. So we get the closed form:
$$\text{Orders}=\frac{(3k)!}{(2k)!}(k+1)!k!$$
To optimize the calculation, you can(always in modular arithmetic):
Finally, note that if $2k+1\le10^9+7\le3k$ or $k\ge10^9+6$, the answer will be $0$.