For a nonzero integer $k$, denote by $\nu_2(k)$ the maximal nonnegative integer $t$ such that $2^t \mid k$. Given are $n (\ge 2)$ pairwise distinct integers $a_1, a_2, \ldots, a_n$. 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.
Problem
Source: 2017 Korea Winter Program Practice Test 1 Day 2 #4
Tags: combinatorics, number theory
rmrf
30.01.2017 01:20
Any ideas on this problem?
dgrozev
30.01.2017 13:00
Let $a_j=\overline{a_{j,k}\,a_{j,k-1}\dots a_{j,1}\,a_{j,0}}$ be the binary representation of $a_j,j=1,2,\dots,n$. The idea is to construct $x=\overline{x_kx_{k-1}\dots x_0}$ by determining consecutively in backward order its binary digits. First, we choose $x_0\in\{0,1\}$, such that the number of $1$'s in the set $\{a_{j,0}-x_0 \mid j=1,2,\dots,n\}$ is the less one considering the two possibilities (it may be zero). Suppose $x_0$ is already fixed. Note that this number of $1$'s equals exactly $\#\{j \mid \nu_2(a_j-x)=0\}$. Next, we remove all $a_j$'s with $j\in \{j \mid \nu_2(a_j-x)=0\}$. For the rest ones, we do the subtraction $a_j-\overline{**\dots * x_0}\,,\,i=1,\dots,n$. Suppose the digits $x_0,x_1,\dots,x_{i-1}$ are already chosen. We choose the next digit $x_i$ by a greedy algorithm to maintain the balance(discrepancy) between already determined even and odd $\nu_2(a_j-x)$ as small as possible. Then we remove those $a_j$'s for which $a_j-x$ has $1$ as its $i$-th digit. For the rest ones the tail of $a_j-x$ has at least $i$ zeroes. We proceed in that way till exhaust all $a_j$'s. It is not difficult to see at the end we get $x$ with the desired property. For example, assume the even numbers among $\nu_2(a_j-x)$ are more than $3n/4$ and consider the last time we've increased that number. It will bring us to a contradiction.
L567
18.03.2022 11:59
Nice problem, solved with p_square We'll determine $x$ mod $2$, then $4$,$8$ and so on. Create two buckets, one labelled "even" and the other labelled "odd", if at some point $v_2(x-a_i)$ is determined, then place it in the bucket labelled with its parity. Suppose we've decided that $x \equiv r \pmod{2^{m-1}}$ and want to determine it mod $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 its placed keeps alternating each time. So we'll prove the stronger statement (because we wont use any information what the $a_i$ are going to be mod big powers of two while making choices for smaller ones) Modified statement wrote: Alice and Bob play the following game with $4n$ pebbles and two boxes labelled $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 labelled $(-1)^n$. Suppose Alice can only partition such that one group is empty, finitely many times. Prove that Bob can ensure that at the end, each box contains at least $n$ pebbles.
Suppose we had $-5n \le b - 2a \le n$ and say the partition is $x$ and $4n-a-b-x$, suppose whatever we choose, the inequalities fail this time in the same side (upper or lower bound). Then we need $a - 2(b+x) > n$ and $a - 2(4n-a-x) > n$, but adding, we get $b - 2a < -5n$, a contradiction. Similarly, if we had $a-2(b+x) < -5n$ and $a - 2(4n-a-x) < -5n$, then adding, we get $b-2a > n$, a contradiction. So the only way this fails is if we have $a-2(b+x) > n$ and $a - 2(4n-a-x) < -5n$. But this gives $3a+2x < 3n < 3(a-2b-2x) = 3a - 6b - 6x$ so $6b + 8x < 0$, a contradiction again, so Bob can indeed play such that this always holds.
So at the end, we have $a+b = 4n$, so $b-2(4n-b) \le n \implies b \le 3n$, so $a$ has at least $n$ pebbles. Similarly, $4n - a - 2a \ge -5n \implies a \le 3n$ so $b$ has at least $n$ pebbles too, so we're done. $\blacksquare$