Given a positive integer $n \ge 2$. Find all $n$-tuples of positive integers $(a_1,a_2,\ldots,a_n)$, such that $1<a_1 \le a_2 \le a_3 \le \cdots \le a_n$, $a_1$ is odd, and (1) $M=\frac{1}{2^n}(a_1-1)a_2 a_3 \cdots a_n$ is a positive integer; (2) One can pick $n$-tuples of integers $(k_{i,1},k_{i,2},\ldots,k_{i,n})$ for $i=1,2,\ldots,M$ such that for any $1 \le i_1 <i_2 \le M$, there exists $j \in \{1,2,\ldots,n\}$ such that $k_{i_1,j}-k_{i_2,j} \not\equiv 0, \pm 1 \pmod{a_j}$.
Problem
Source: 2022 China TST, Test 3 P3
Tags: modular arithmetic, algebra, number theory, combinatorics, abstract algebra
CANBANKAN
30.04.2022 18:17
Let $a$ be the number of odd terms in $a_i$. The answer is $2^a|a_1-1$ only.
Call points $(x_1, \cdots, x_n)$.
Claim: The maximum number of points that can be placed in $\times_{j=1}^n \mathbb{Z}_{a_j}$ is at most $\frac{1}{2^n} (a_1-1) \prod\limits_{j=2}^n a_j$
Proof: we induct on $n$.
Base Case: $n=1$, clear
Inductive Step: For $i=0,\cdots, a_n-1$, let $X_i$ denote the union of planes $x_n=2i, x_n=2i+1$. By inductive hypothesis, we can put at most $2^{1-n} (a_1-1)a_2 \cdots a_{n-1}$ points in $X_i$ (since which row you put don't matter). Summing $X_i$ over $0\le i\le n-1$ counts everything twice, and dividing by 2 yields the desired result.
Therefore this problem is about characterising all equality cases.
Claim: it suffices to solve the problem when $a_i$ is odd for all $i$.
Proof: if $a_i$ is even then we can split into $X_0, X_1, \cdots, X_{a_i/2-1}$ and use induction to complete our construction. Alternatively, if $(a_1,\cdots,a_{i-1}, a_{i+1},\cdots, a_n)$ fails, then $(a_1,\cdots,a_n)$ fails by mimicking the inductive argument.
At this point M must be an integer since it is an upper bound, so $2^n|a_1-1$ is necessary.
Now I claim this is also sufficient. We first solve the problem for $a_1=\cdots=a_n=k2^n+1$. On the line $x_2=c_2, x_3=c_3, \cdots, x_n=c_n$ for fixed $c_2,\cdots,c_n$ place points with $x_n\in \{0,2,\cdots, 2(k-1)\} + 2k\sum\limits_{j=1}^{n-1} 2^{j-1}c_{j+1}$.
We will prove there is no conflict between $x_2=c_2, \cdots, x_{n}=c_{n}$ and $x_2=c_1+e_2, \cdots, x_{n-1}=c_{n-1}+e_{n}$ for $e_j\in \{-1,0,1\}$ for $2\le j\le n$ and $e_j$ are not all zero.
Note the set of points on $x_2=c_2+e_1, \cdots, x_{n}=c_{n}+e_{n-1}$ is precisely the set of points on $x_2=c_2, \cdots, x_{n}=c_{n}$ shifted by $2k \sum\limits_{j=1}^{n-1} 2^{j-1}e_{j+1}$. Note $0<|\sum\limits_{j=1}^{n-1} 2^{j-1}e_{j+1}|\le 2^{n-1}-1$. For simplicity let $Y=\sum\limits_{j=1}^{n-1} 2^{j-1}e_{j+1}$
Let $[X,X+2k-2]$ be the interval of points on the line $x_2=c_2, \cdots, x_{n}=c_{n}$, then $[X+2kY, X+2kY+2k-2]$ is the interval of points on the line $x_2=c_2, \cdots, x_n=c_n$. WLOG $Y$ is positive, and we can easily check there is no conflict when $1\le Y\le 2^{n-1}-1$ by only checking $Y=1, Y=2^{n-1}-1$.
Now we extend to $a_2,\cdots,a_n$ being odd integers at least $a_1$. To go from $(a_1,\cdots,a_{i-1}, a_i, a_{i+1}, \cdots,a_n)$ to $(a_1,\cdots,a_{i-1}, a_i+2, a_{i+1}, \cdots,a_n)$, we place the same set of points on $x_i=a_i-1$ on the plane $x_i=a_i+1$ and the same set of points on $x_i=a_i$ to $x_i=a_i+2$. This way, there is no conflict with a fixed $x_i$, no conflict between planes $x_i=a_i-1, x_i=a_i$ implies no conflict between planes $x_i=a_i, x_i=a_i+1$ and no conflicts between $x_i=a_i+1, x_i=a_i+2$, and no conflict between planes $x_i=1, x_i=a_i$ implies no conflict between planes $x_i=1, x_i=a_i+2$, completing the extension step.
At each step, for a fixed value of $x_2,\cdots,x_n$ there are exactly $k=\frac{a_1-1}{2^n}$ points, so this construction works.