Find all positive integers $n$ such that it is possible to split the numbers from $1$ to $2n$ in two groups $(a_1,a_2,..,a_n)$, $(b_1,b_2,...,b_n)$ in such a way that $2n\mid a_1a_2\cdots a_n+b_1b_2\cdots b_n-1$. Proposed by Alef Pineda
Problem
Source: Mexico National Olympiad Mock Exam 2019 P4
Tags: number theory, Divisibility
16.10.2019 18:00
Suppose wlog that $a_1=2n$. Then the required condition is $b_1 \cdots b_n \equiv 1 \pmod{2n}$. This is only possible if the $b_i$ are precisely the odd numbers $1,3, \ldots, 2n-1$. If $n$ has an odd prime divisor $p$, then $b_i=p$ for some $i$ and thus $b_1 \cdots b_n -1$ is not divisible by $p$. Hence $n$ is necessarily a power of $2$. If $n=1$ then $2 \mid 2+1-1$, hence this is a solution. If $n=2$ then $1 \cdot 3 -1$ is not divisible by $2n=4$, thus this is not a solution. For $n=2^a$ with $a \geq 2$ it is easy to show by induction that $b_1 \cdots b_n = \prod_{k=1}^{n} (2k-1) \equiv 1 \pmod {2n}$. Consequently, the solutions are $n=1$ and $n=2^a$ for $a \geq 2$.
16.10.2019 19:09
That's right, but actually, the induction is less trivial than the rest of the steps you mentioned.
16.10.2019 20:29
Another way to see that $1 \cdot 3 \cdot 5 \cdots (2^k-1) \equiv 1 \pmod{2^k}$ for $k \ge 3$ is to pair inverse elements together. This annihilates all the factors except the self-inverse ones, and it's not hard to prove that they are $\pm 1$ and $\pm (2^{k-1} + 1)$. Then we obtain \[1 \cdot (-1) \cdot (2^{k-1} + 1) \cdot \big(-(2^{k-1}+1)\big) = (2^{k-1}+1)^2 = 2^{2k-2} + 2^k + 1 \equiv 1 \pmod{2^k}\]as desired. We can check that this is also true for $k=1$, but not true for $k=2$.
17.10.2019 14:32
The proof by induction goes as follows: For $n=2^a, a=2$ we have $1 \cdot 3 \cdot 5 \cdot 7 = 105 = 13 \cdot 8 + 1$, hence the statement is true. Now if $\prod_{k=1}^{2^a} (2k-1) \equiv 1 \pmod {2^{a+1}}$ for some $a \geq 2$, then $$\prod_{k=1}^{2^{a+1}} (2k-1) = \prod_{k=1}^{2^a} (2k-1)(2^{a+2}-(2k-1)) \equiv (-1)^{2^a} \prod_{k=1}^{2^a} (2k-1)^2 \equiv \prod_{k=1}^{2^a} (2k-1)^2 \pmod {2^{a+2}}.$$Since $x \equiv 1 \pmod {2^{a+1}}$ implies $x^2 \equiv 1 \pmod {2^{a+2}}$, the claim follows from the induction hypothesis.