There are $N$ permutations $(a_1,a_2,\dots,a_{30})$ of $1,2,\dots,30$ such that for $m\in\{2,3,5\}$, $m$ divides $a_{n+m}-a_n$ for all integers $n$ with $1\leq n <n+m\leq 30$. Find $N$.
I really don't know how to go about this, as since there are 2 ways to place all the modulo twos, three ways to place the modulo threes, etc. 2*3*5 = 30 cases, which is too many for me to handle...
Could someone provide me with an answer and or a solution? Thanks :)
Note: Every number $n\in\{1,2,\dots,30\}$ is uniquely determined by the triple $(n\!\!\mod 2, n\!\!\mod 3, n\!\!\mod 5)$.
Note also: there are exactly 15 numbers in each equivalence class for modulo 2, so if $a_1$ is, say, even, then all of $a_3, a_5, \dots, a_{29}$ will be even as well, otherwise not all of the numbers could be placed. Similarly, all of $a_1, a_4, a_7, \dots, a_{28}$ will be in the same equivalence class modulo three, etc...
Let us look at the first number $a_1$. There are two choices for which equivalence class it is modulo 2, three choices for which equivalence class it is modulo 3, and five choices for which equivalence class it is modulo 5, so we have $2\cdot 3\cdot 5=30$ choices for $a_1$ (as expected).
Notice, that in choosing $a_1$, we wind up forcing what $a_{16}$ could be since there is only one other number in $\{1,2,\dots,30\}$ that is the same as $a_1$ modulo 15. Also, we now force all numbers with index multiple of 2 away to be the same modulo 2, all numbers with index multiple of 3 away to be the same modulo 3, etc... as well as forcing all numbers not multiple of 2 away to be different modulo 2, etc...
Now, look at the number $a_2$. We can no longer choose the same equivalence class modulo 2,3, or 5. There is then one choice for what it is modulo 2, there are two choices remaining for what it is modulo 3, and there are four choices remaining for what it is modulo 5. As with $a_1$, this imposes restrictions on the remaining spaces. Thus, there are $1\cdot 2\cdot 4 = 8$ choices for $a_2$ once $a_1$ has been picked.
The number $a_3$ has only one choice for what it is modulo 2 (it must be the same as $a_1$ modulo 2), it has only one choice for what it is modulo 3 (it cannot be the same as neither of $a_1$ and $a_2$), and it has three choices remaining for what it is modulo 5. Thus, there are $1\cdot 1\cdot 3=3$ choices for $a_3$ once both $a_1$ and $a_2$ have been picked.
Similarly, $a_4$ will have $1\cdot 1\cdot 2=2$ choices and $a_5$ will have $1\cdot 1\cdot 1=1$ choice. Once $a_1,\dots, a_5$ have been picked, every $a_i$ will have a unique triple $(n\!\!\mod 2, n\!\!\mod 3, n\!\!\mod 5)$ and so there is only one choice for each of the remaining positions.
There are thus:
$$30\cdot 8\cdot 3\cdot 2=1440~\text{such sequences}$$
This is very close to what your initial intuition should have told you, except you stopped a bit short. There are $2!$ number of ways to place the modulo 2 classes, there are $3!$ number of ways to place the modulo 3 classes, and there are $5!$ number of ways to place the modulo 5 classes.
As such, there are $2!3!5!=1440$ number of ways, agreeing with or longer tedious answer.
