Problem 1680

1. **Define the problem in terms of $\nu_2$:**
For a nonzero integer $k$, denote by $\nu_2(k)$ the maximal nonnegative integer $t$ such that $2^t \mid k$. Given $n$ pairwise distinct integers $a_1, a_2, \ldots, a_n$, we need to show that there exists an integer $x$, distinct from $a_1, \ldots, a_n$, such that among $\nu_2(x - a_1), \ldots, \nu_2(x - a_n)$ there are at least $n/4$ odd numbers and at least $n/4$ even numbers.

2. Strategy:
We will determine $x$ modulo $2$, then $4$, $8$, and so on. We will create two buckets, one labeled "even" and the other labeled "odd". If at some point $\nu_2(x - a_i)$ is determined, then place it in the bucket labeled with its parity.

3. Inductive Step:
Suppose we have decided that $x \equiv r \pmod{2^{m-1}}$ and want to determine it modulo $2^m$. We choose between $r$ and $r + 2^{m-1}$. Depending on our choice, the ones with the other choice get placed in one of the buckets, and this bucket to which it is placed keeps alternating each time.

4. Game Analogy:
We can use a game analogy to prove the stronger statement. Consider the following game with $4n$ pebbles and two boxes labeled $1$ and $-1$ respectively. On the $n$-th turn, Alice partitions the remaining pebbles into two groups, and Bob chooses one of them and places them in the box labeled $(-1)^n$. Suppose Alice can only partition such that one group is empty, finitely many times. We need to prove that Bob can ensure that at the end, each box contains at least $n$ pebbles.

5. Inequality Maintenance:
Bob plays such that he always ensures the inequality:
$$-5n \le b - 2a \le n$$
where $a$ is the number of pebbles in the box $(-1)^n$ and $b$ is the number of pebbles in the box $-(-1)^n$.

6. Verification:
To show that Bob can always play such that this inequality holds, consider the following:
- Suppose we had $-5n \le b - 2a \le n$ and say the partition is $x$ and $4n - a - b - x$.
- If the inequalities fail on the same side (upper or lower bound), we need:
$$a - 2(b + x) > n \quad \text{and} \quad a - 2(4n - a - x) > n$$
Adding these, we get:
$$b - 2a < -5n$$
which is a contradiction.
- Similarly, if we had:
$$a - 2(b + x) < -5n \quad \text{and} \quad a - 2(4n - a - x) < -5n$$
Adding these, we get:
$$b - 2a > n$$
which is also a contradiction.
- The only way this fails is if we have:
$$a - 2(b + x) > n \quad \text{and} \quad a - 2(4n - a - x) < -5n$$
This gives:
$$3a + 2x < 3n < 3(a - 2b - 2x) = 3a - 6b - 6x$$
so:
$$6b + 8x < 0$$
which is a contradiction again. Therefore, Bob can indeed play such that this always holds.

7. Conclusion:
At the end, we have $a + b = 4n$, so:
$$b - 2(4n - b) \le n \implies b \le 3n$$
Thus, $a$ has at least $n$ pebbles. Similarly:
$$4n - a - 2a \ge -5n \implies a \le 3n$$
so $b$ has at least $n$ pebbles too. Hence, we are done.

$\blacksquare$