0
$\begingroup$

Let $N$ be the number of sequences $a_1, a_2, a_3,\ldots,a_{24}$ that satisfy the following conditions.

i) For all $1\le i \le 24$, $1\le a_i \le 24$.

ii) For all $i \equiv 0 \text{ (mod 2)}$, $a_1+a_2+\cdots+a_i \equiv 1 \text{(mod 2)}$.

iii) For all $i \equiv 0 \text{ (mod 3)}$, $a_1+a_2+\cdots+a_i \equiv 2 \text{(mod 3)}$.

If $N=p_1^{a_1}p_2^{a_2}$ where $p_1$ and $p_2$ are prime numbers, find $p_1+a_1+p_2+a_2$.

I found that $a_{i}+a_{i+1} \equiv 0 \pmod{2}$ and $a_i+a_{i+1}+a_{i+2} \equiv 0 \pmod{3}$ for all even $i$ and $i \equiv 0 \pmod{3}$, respectively. Do we have to use the Chinese Remainder Theorem next?

$\endgroup$
  • $\begingroup$ I think you mean $a_i+a_{i+1}\equiv0\pmod2$. And the two congruences don't have to hold for all $i$, just every second/every third $i$, respectively. Is this a contest problem? $\endgroup$ – Greg Martin Oct 7 '16 at 1:48
  • $\begingroup$ @GregMartin Yes, it is. $\endgroup$ – user19405892 Oct 7 '16 at 1:53
  • $\begingroup$ It seems to me that $a_1\equiv a_2\equiv 1\pmod 3$ and simultaneously $a_1+1\equiv a_2\pmod 2$ to go along with what you found, and therefore $a_2=6k+3+a_1$. $\endgroup$ – abiessu Oct 7 '16 at 2:13
0
$\begingroup$

For convenience, let $S_n$ be defined by $$ S_n = a_1 + a_2 + \dots + a_n, $$ so that you conditions become

  • $S_n \equiv 1 \pmod 2$ if $n \equiv 0 \pmod 2$
  • $S_n \equiv 2 \pmod 3$ if $n \equiv 0 \pmod 3$.

We will work in blocks of $6$ numbers at a time. There is no restriction on the value of $a_{6k+1}$ other than that $1 \leq a_{6k+1} \leq 24$, so $a_{6k+1}$ can be any of $24$ different values.

For $a_{6k+2}$, we require that $$ S_{6k+2} = S_{6k+1} + a_{6k+2} \equiv 1 \pmod 2. $$

This means that if $S_{6k+1}$ is even, then the only restriction on $a_{6k+2}$ is that it must be odd, and if $S_{6k+1}$ is odd, then the only restriction on $a_{6k+2}$ is that it must be even. In either case, there are $12$ options for the value of $a_{6k+2}$.

Similarly, the only restriction on $a_{6k+3}$ is that $$ a_{6k+3} \equiv 2 - S_{6k+2} \pmod 3. $$

Since there are $8$ numbers with each possible remainder modulo $3$ amongst the numbers $1, 2, 3, \dots, 24$, we see that there are always $8$ options for the value of $a_{6k+3}$ once all of the previous numbers have been chosen.

Continuing in this way, we see that there are

  • $24$ options for the value of $a_{6k+1}$
  • $12$ options for the value of $a_{6k+2}$
  • $8$ options for the value of $a_{6k+3}$
  • $12$ options for the value of $a_{6k+4}$
  • $24$ options for the value of $a_{6k+5}$
  • $4$ options for the value of $a_{6k+6}$

once all of the previous numbers have been chosen in each case.

Thus there are $24 \times 12 \times 8 \times 12 \times 24 \times 4 = 2^{15} \cdot 3^4$ ways to choose the numbers in each block of $6$ numbers. There are $4$ blocks of $6$ numbers to fill, and so the total number of sequences is $$ \left( 2^{15} \cdot 3^4 \right)^4 = 2^{60} \cdot 3^{16}. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.