Problem 1958

The $n$-tuples we seek are the ones satisfying the following condition:
if there are exactly $r$ odd numbers in $a_2, \dots, a_n$, then $2^r \mid a_1 - 1$. $(*)$

We first verify the necessity of $(*)$. For this, we drop the condition $a_n \ge a_{n-1} \ge \dots \ge a_1$ and assume that $a_1, \dots, a_r$ are odd and $a_{r+1}, \dots, a_n$ are even. Suppose that we are given the $M$ tuples satisfying the requirement (2). For each $s \in \mathbb{Z}$, denote $B_s = \{i \mid 1 \le i \le M, c_{i,n} \equiv s \pmod{a_n}\}$. Then
$$|B_1| + |B_2| + \dots + |B_{a_n}| = M.$$
Consequently, there exists an index $s$ such that $|B_s| + |B_{s+1}| \ge \frac{M}{a_n/2}$. This means that we can choose at least $\frac{M}{a_n/2}$ tuples such that the differences between their $n$-th coordinates $c_{i,n}$ are all congruent to $0$ or $\pm 1$ modulo $a_n$.

By running the same argument for all the tuples inductively, i.e., to consider the $(n-1)$th coordinates modulo $a_{n-1}$, the $(n-2)$th coordinates modulo $a_{n-2}$, etc., it eventually shows that there are at least $\frac{M}{\frac{a_n}{2} \dots \frac{a_2}{2}} = \frac{a_1-1}{2}$ tuples such that for each two of them, the differences between their $k$th coordinates $c_{i,k}$'s are congruent to $0$ or $\pm 1$ modulo $a_k$, where $2 \le k \le n$. However, the given conditions imply that the difference between the first coordinates of these tuples can not be $0$ or $\pm 1$ (mod $a_1$); there are at most $\frac{a_1-1}{2}$ such tuples. This means that all equalities must hold in the argument above. Namely, for each $t$ we have exactly $\frac{M}{\frac{a_n}{2} \dots \frac{a_t}{2}}$ different tuples. In particular, taking $t = r + 1$ leads to
$$\frac{M}{\frac{a_n}{2} \dots \frac{a_{r+1}}{2}} = \frac{1}{2^r} (a_1 - 1)a_2 \dots a_r \in \mathbb{Z}.$$
It forces that $2^r \mid a_1 - 1$.

In the following, we construct the needed $M$ tuples under the condition $2^r \mid a_1 - 1$. For convenience, we first weaken the condition $a_n \ge a_{n-1} \ge \dots \ge a_1$ to only requiring $a_1 = \min\{a_1, \dots, a_n\}$. Whenever there is any even number in $a_2, \dots, a_n$, say $a_n$ without loss of generality. Suppose that we may construct the needed tuples for $a_1, \dots, a_{n-1}$, say $(c_{i,1}, c_{i,2}, \dots, c_{i,n-1})$ with $1 \le i \le M' = \frac{1}{2^{n-1}}(a_1 - 1)a_2 \dots a_n = \frac{2}{a_n}M$. Then it suffices to take $(c_{i,1}, c_{i,2}, \dots, c_{i,n-1}, 2c)$ with $1 \le i \le M'$ and $1 \le c \le \frac{a_n}{2}$.

Now it remains to prove for the case when all $a_2, a_3, \dots, a_n$ are odd. Let us write $a_1 = 2^n t + 1$ and consider the case when $a_1 = a_2 = \dots = a_n$ first. In this case, $M = t a_1^{n-1}$. Define the function $f(x_1, x_2, \dots, x_{n-1}) = \sum_{i=1}^{n-1} 2^i x_i$ and take the following $M = t a_1^{n-1}$ tuples:
$$(x_1, x_2, \dots, x_{n-1}, f(x_1, \dots, x_{n-1}) + 2^n s),$$
where $x_1, \dots, x_{n-1} \in \{1, 2, \dots, a_1\}, s \in \{1, \dots, t\}$. We now show that these tuples satisfy the desired conditions. Consider the above tuple together with another one: $(x'_1, x'_2, \dots, x'_{n-1}, f(x'_1, \dots, x'_{n-1}) + 2^n s')$. If for every $k$, the difference between their $k$th coordinate $\equiv 0, \pm 1 \pmod{a_1}$, then
$$x_i - x'_i \equiv 0, \pm 1 \pmod{a_1}, \quad i = 1, \dots, n-1; \text{ and}$$
$$\sum_{i=1}^{n-1} 2^{i-1}(x_i - x'_i) + 2^n(s - s') \equiv 0, \pm 1 \pmod{a_1}. \quad (*)$$
The first equality implies that $\sum_{i=1}^{n-1} 2^i(x_i - x'_i)$ can be only congruent to $2^{n-1} - 1, 2^{n-2} - 1, \dots, 1 - 2^{n-1} \pmod{a_1}$. On the other hand, $s - s' \in \{1 - t, 2 - t, \dots, t - 1\}$. So $s$ is forced to be equal to $s'$ by $(*)$, and $\sum_{i=1}^{n-1} 2^{i-1}(x_i - x'_i) = 0 \pmod{a_1}$. By the uniqueness of binary expansion, we get $x_i = x'_i \pmod{a_1}$, which implies that the two tuples are the same. This verifies that the constructed tuples satisfy the needed conditions.

For the general case where $a_1, \dots, a_n$ are all odd numbers, we claim that if $a_2 > a_1$, the construction can be reduced to the case with $a_1, a_2-2, a_3, \dots, a_n$. Hence by induction, it suffices to consider the case where all $a_i$ are equal, which is discussed above.

Assume now there exist $M' = \frac{1}{2^n}(a_1 - 1)(a_2 - 2)a_3 \cdots a_n$ tuples as desired when $a'_1 = a_1, a'_2 = a_2 - 2, a'_3 = a_3, \dots, a'_n = a_n$. We may assume that for each $k$, the $k$th coordinates of all these tuples belong the set $\{0, 1, \dots, a'_k - 1\}$.

We then define the $M = \frac{1}{2^n}(a_1 - 1)a_2a_3 \cdots a_n$ tuples as follows. One can first choose the $M'$ tuples that are already defined. As for $x_2 = a_2 - 2$, we choose to add the tuple $(x_1, a_2 - 2, x_3, \dots, x_n)$ if and only if the tuple $(x_1, a_2 - 4, x_3, \dots, x_n)$ was selected; and for $x_2 = a_2 - 1$, we choose to add the tuple $(x_1, a_2 - 1, x_3, \dots, x_n)$ if and only if the tuple $(x_1, a_2 - 3, x_3, \dots, x_n)$ was selected. It is easy to check that these tuples satisfy our requirement. Also, using the proof for $2^r|a_1 - 1$ by induction, the condition for equality implies the following: Among the $M'$ tuples we have selected before, the number of tuples whose second coordinate is either $a_2 - 1$ or $a_2 - 2$ is $M' \cdot \frac{2}{a_2-2}$. Hence we can the number of new tuples is $M' + M' \cdot \frac{2}{a_2-2} = M$. This completes the construction of the tuples.