Prove that there exist a subset $A$ of $\{1,2,\cdots,2^n\}$ with $n$ elements, such that for any two different non-empty subset of $A$, the sum of elements of one subset doesn't divide another's.
Problem
Source: 2019 China TST Test 4 P4
Tags: number theory
Pluto1708
29.03.2019 18:32
Just for clarification the set $A$ is consective numbers from $1$ to $2^n$ or powers of two?
totode
29.03.2019 18:56
I think it is consecutive numbers, because for $n=2$, $\{1,2,4\}$ doesn't work.
Pathological
30.03.2019 06:21
We claim that the set $\{2^n - 2^{n-1}, 2^n - 2^{n-2}, \cdots, 2^n - 2^0\}$ works.
Let $s_2(n)$ denote the sum of the digits of $n$ when written in binary. Note that all sums of $k$ of these numbers have the form $k*2^n - a,$ where $a$ is a number less than $2^n$ with $s_2(a) = k.$ Hence, if there were to be $2$ different subset sums, one of which divides the other, we would have to have $k*2^n - a | l*2^n - b,$ for some $a, b$ with $s_2(a) = k, s_2(b) = l.$
Suppose that this were the case, for contradiction, i.e., there is some $r \in \mathbb{N}$ with $l*2^n - b = r(k* 2^n-a).$
Notice that $r \neq 1$ clearly. By looking (mod $2^n$), we obtain that $b \equiv ra$ (mod $2^n$). Thus, we know that $b$ is simply the last $n$ digits of $ra$ (in binary), and so hence $s_2(b) \le s_2(ra).$ Note that by looking at the number of carries when we add up $r$ copies of $a,$ we obtain that $s_2(ra) \le rs_2(a) - s_2(a) * (\left \lfloor \frac{r}{2} \right \rfloor) = k(r - \left \lfloor \frac{r}{2} \right \rfloor),$ since there are at least $\left \lfloor \frac{r}{2} \right \rfloor$ carries in each of the $s_2(a)$ positions with $r$ ones ($1$ for each copy of $a$). Therefore, if $k \ge 3,$ we have that $l \le s_2(ra) \le kr - k \left \lfloor \frac{r}{2} \right \rfloor \le kr - 3 \left \lfloor \frac{r}{2} \right \rfloor \le kr - r,$ since $r \ge 2.$ However, this implies that $l*2^n - b \le (kr-r)*2^n - b = kr*2^n - r*2^n - b < kr *2^n - ra = r(k*2^n- a),$ contradicting our assumption.
Therefore, we only have to deal with the cases where $k = 1$ or $k= 2.$
When $k = 2,$ we know that $l \le kr - 2 \left \lfloor \frac{r}{2} \right \rfloor \le kr -r + 1,$ and so hence $kr*2^n - ra = l*2^n - b \le (kr-r+1) * 2^n - b = kr*2^n - (r-1)*2^n - b,$ implying that $ra \ge (r-1)*2^n + b.$ Thus, we know that $ra - b \ge (r-1)*2^n.$ However, since we clearly have $ra - b < ra < r*2^n,$ and so hence $ra - b = (r-1)*2^n$ since it's a multiple of $2^n.$ In particular, we know that $a > \frac{r-1}{r}* 2^n \ge 2^{n-1},$ and so we may write $a = 2^{n-1} + 2^j$ for some $0 \le j < n-1.$
Thus, we have that $2^{n+1} - 2^{n-1} - 2^j|(2^n-2^{a_1} + 2^n - 2^{a_2} + \cdots + 2^n - 2^{a_l}),$ where $n > i > j \ge 0.$ By modulo $2^j$, we again have that $a_1, a_2, \cdots, a_l \ge j.$ Note that $3 (2^n - 2^{a_t}) - (2^{n+1} - 2^{n-1} - 2^j) = 2^j - 3 * 2^{a_t}.$ Therefore, we know that $3*2^{a_1} - 2^j + 3 * 2^{a_2} - 2^j + \cdots + 3 * 2^{a_l} - 2^j = 3(2^{a_1} + 2^{a_2} + \cdots + 2^{a_l}) - l*2^j)$ is a multiple of $3*2^n - 2^j.$ However, observe that $0 < 3(2^{a_1} + 2^{a_2} + \cdots + 2^{a_l}) - l*2^j < 3* 2^n - l * 2^j \le 3*2^n - 2^j,$ contradiction.
If $k = 1,$ then let $a = 2^i,$ so that $2^n - 2^i | (2^n-2^{a_1} + 2^n - 2^{a_2} + \cdots + 2^n - 2^{a_l}).$ By modulo $2^i$, it's immediate that $a_1, a_2, \cdots, a_l \ge i.$ Notice that $2^n - 2^i, 2^n - 2^{i+1}, 2^n - 2^{i+2}, \cdots, 2^n - 2^{n-1}$ are congruent to $2^{i+1} - 2^i, 2^{i+2} - 2^i, \cdots, 2^{n-1} - 2^{i}$ modulo $2^n - 2^i.$ Therefore, since these numbers are all positive and sum to less than $2^n - 2^i,$ we clearly attain a contradiction.
bug3
20.08.2019 14:10
${2^{1},2^{2}, ...,2^{n-1},2^{n}-1}$ is solution Set that contain $2^{n}-1$ not divide another set because $2^{1}$$+$$2^{2}$$+$$...$$+$$2^{n-1}$ $=$ $2^{n}-2$ $<$ $2^{n}-1$, another set not divide set that contain $2^{n}-1$ because that a sum is even but sum of set that contain $2^{n}-1$ is odd
GammaBetaAlpha
20.08.2019 17:01
Pathological wrote:
We claim that the set $\{2^n - 2^{n-1}, 2^n - 2^{n-2}, \cdots, 2^n - 2^0\}$ works.
Let $s_2(n)$ denote the sum of the digits of $n$ when written in binary. Note that all sums of $k$ of these numbers have the form $k*2^n - a,$ where $a$ is a number less than $2^n$ with $s_2(a) = k.$ Hence, if there were to be $2$ different subset sums, one of which divides the other, we would have to have $k*2^n - a | l*2^n - b,$ for some $a, b$ with $s_2(a) = k, s_2(b) = l.$
Suppose that this were the case, for contradiction, i.e., there is some $r \in \mathbb{N}$ with $l*2^n - b = r(k* 2^n-a).$
Notice that $r \neq 1$ clearly. By looking (mod $2^n$), we obtain that $b \equiv ra$ (mod $2^n$). Thus, we know that $b$ is simply the last $n$ digits of $ra$ (in binary), and so hence $s_2(b) \le s_2(ra).$ Note that by looking at the number of carries when we add up $r$ copies of $a,$ we obtain that $s_2(ra) \le rs_2(a) - s_2(a) * (\left \lfloor \frac{r}{2} \right \rfloor) = k(r - \left \lfloor \frac{r}{2} \right \rfloor),$ since there are at least $\left \lfloor \frac{r}{2} \right \rfloor$ carries in each of the $s_2(a)$ positions with $r$ ones ($1$ for each copy of $a$). Therefore, if $k \ge 3,$ we have that $l \le s_2(ra) \le kr - k \left \lfloor \frac{r}{2} \right \rfloor \le kr - 3 \left \lfloor \frac{r}{2} \right \rfloor \le kr - r,$ since $r \ge 2.$ However, this implies that $l*2^n - b \le (kr-r)*2^n - b = kr*2^n - r*2^n - b < kr *2^n - ra = r(k*2^n- a),$ contradicting our assumption.
Therefore, we only have to deal with the cases where $k = 1$ or $k= 2.$
When $k = 2,$ we know that $l \le kr - 2 \left \lfloor \frac{r}{2} \right \rfloor \le kr -r + 1,$ and so hence $kr*2^n - ra = l*2^n - b \le (kr-r+1) * 2^n - b = kr*2^n - (r-1)*2^n - b,$ implying that $ra \ge (r-1)*2^n + b.$ Thus, we know that $ra - b \ge (r-1)*2^n.$ However, since we clearly have $ra - b < ra < r*2^n,$ and so hence $ra - b = (r-1)*2^n$ since it's a multiple of $2^n.$ In particular, we know that $a > \frac{r-1}{r}* 2^n \ge 2^{n-1},$ and so we may write $a = 2^{n-1} + 2^j$ for some $0 \le j < n-1.$
Thus, we have that $2^{n+1} - 2^{n-1} - 2^j|(2^n-2^{a_1} + 2^n - 2^{a_2} + \cdots + 2^n - 2^{a_l}),$ where $n > i > j \ge 0.$ By modulo $2^j$, we again have that $a_1, a_2, \cdots, a_l \ge j.$ Note that $3 (2^n - 2^{a_t}) - (2^{n+1} - 2^{n-1} - 2^j) = 2^j - 3 * 2^{a_t}.$ Therefore, we know that $3*2^{a_1} - 2^j + 3 * 2^{a_2} - 2^j + \cdots + 3 * 2^{a_l} - 2^j = 3(2^{a_1} + 2^{a_2} + \cdots + 2^{a_l}) - l*2^j)$ is a multiple of $3*2^n - 2^j.$ However, observe that $0 < 3(2^{a_1} + 2^{a_2} + \cdots + 2^{a_l}) - l*2^j < 3* 2^n - l * 2^j \le 3*2^n - 2^j,$ contradiction.
If $k = 1,$ then let $a = 2^i,$ so that $2^n - 2^i | (2^n-2^{a_1} + 2^n - 2^{a_2} + \cdots + 2^n - 2^{a_l}).$ By modulo $2^i$, it's immediate that $a_1, a_2, \cdots, a_l \ge i.$ Notice that $2^n - 2^i, 2^n - 2^{i+1}, 2^n - 2^{i+2}, \cdots, 2^n - 2^{n-1}$ are congruent to $2^{i+1} - 2^i, 2^{i+2} - 2^i, \cdots, 2^{n-1} - 2^{i}$ modulo $2^n - 2^i.$ Therefore, since these numbers are all positive and sum to less than $2^n - 2^i,$ we clearly attain a contradiction.
The set reminds me of IMO 2019 P4
MessingWithMath
20.08.2019 17:41
GammaBetaAlpha wrote: Pathological wrote:
We claim that the set $\{2^n - 2^{n-1}, 2^n - 2^{n-2}, \cdots, 2^n - 2^0\}$ works.
Let $s_2(n)$ denote the sum of the digits of $n$ when written in binary. Note that all sums of $k$ of these numbers have the form $k*2^n - a,$ where $a$ is a number less than $2^n$ with $s_2(a) = k.$ Hence, if there were to be $2$ different subset sums, one of which divides the other, we would have to have $k*2^n - a | l*2^n - b,$ for some $a, b$ with $s_2(a) = k, s_2(b) = l.$
Suppose that this were the case, for contradiction, i.e., there is some $r \in \mathbb{N}$ with $l*2^n - b = r(k* 2^n-a).$
Notice that $r \neq 1$ clearly. By looking (mod $2^n$), we obtain that $b \equiv ra$ (mod $2^n$). Thus, we know that $b$ is simply the last $n$ digits of $ra$ (in binary), and so hence $s_2(b) \le s_2(ra).$ Note that by looking at the number of carries when we add up $r$ copies of $a,$ we obtain that $s_2(ra) \le rs_2(a) - s_2(a) * (\left \lfloor \frac{r}{2} \right \rfloor) = k(r - \left \lfloor \frac{r}{2} \right \rfloor),$ since there are at least $\left \lfloor \frac{r}{2} \right \rfloor$ carries in each of the $s_2(a)$ positions with $r$ ones ($1$ for each copy of $a$). Therefore, if $k \ge 3,$ we have that $l \le s_2(ra) \le kr - k \left \lfloor \frac{r}{2} \right \rfloor \le kr - 3 \left \lfloor \frac{r}{2} \right \rfloor \le kr - r,$ since $r \ge 2.$ However, this implies that $l*2^n - b \le (kr-r)*2^n - b = kr*2^n - r*2^n - b < kr *2^n - ra = r(k*2^n- a),$ contradicting our assumption.
Therefore, we only have to deal with the cases where $k = 1$ or $k= 2.$
When $k = 2,$ we know that $l \le kr - 2 \left \lfloor \frac{r}{2} \right \rfloor \le kr -r + 1,$ and so hence $kr*2^n - ra = l*2^n - b \le (kr-r+1) * 2^n - b = kr*2^n - (r-1)*2^n - b,$ implying that $ra \ge (r-1)*2^n + b.$ Thus, we know that $ra - b \ge (r-1)*2^n.$ However, since we clearly have $ra - b < ra < r*2^n,$ and so hence $ra - b = (r-1)*2^n$ since it's a multiple of $2^n.$ In particular, we know that $a > \frac{r-1}{r}* 2^n \ge 2^{n-1},$ and so we may write $a = 2^{n-1} + 2^j$ for some $0 \le j < n-1.$
Thus, we have that $2^{n+1} - 2^{n-1} - 2^j|(2^n-2^{a_1} + 2^n - 2^{a_2} + \cdots + 2^n - 2^{a_l}),$ where $n > i > j \ge 0.$ By modulo $2^j$, we again have that $a_1, a_2, \cdots, a_l \ge j.$ Note that $3 (2^n - 2^{a_t}) - (2^{n+1} - 2^{n-1} - 2^j) = 2^j - 3 * 2^{a_t}.$ Therefore, we know that $3*2^{a_1} - 2^j + 3 * 2^{a_2} - 2^j + \cdots + 3 * 2^{a_l} - 2^j = 3(2^{a_1} + 2^{a_2} + \cdots + 2^{a_l}) - l*2^j)$ is a multiple of $3*2^n - 2^j.$ However, observe that $0 < 3(2^{a_1} + 2^{a_2} + \cdots + 2^{a_l}) - l*2^j < 3* 2^n - l * 2^j \le 3*2^n - 2^j,$ contradiction.
If $k = 1,$ then let $a = 2^i,$ so that $2^n - 2^i | (2^n-2^{a_1} + 2^n - 2^{a_2} + \cdots + 2^n - 2^{a_l}).$ By modulo $2^i$, it's immediate that $a_1, a_2, \cdots, a_l \ge i.$ Notice that $2^n - 2^i, 2^n - 2^{i+1}, 2^n - 2^{i+2}, \cdots, 2^n - 2^{n-1}$ are congruent to $2^{i+1} - 2^i, 2^{i+2} - 2^i, \cdots, 2^{n-1} - 2^{i}$ modulo $2^n - 2^i.$ Therefore, since these numbers are all positive and sum to less than $2^n - 2^i,$ we clearly attain a contradiction.
The set reminds me of IMO 2019 P4 Wait why? Could you elaborate?
ComiCabE
16.02.2020 21:07
MessingWithMath wrote: GammaBetaAlpha wrote: Pathological wrote:
We claim that the set $\{2^n - 2^{n-1}, 2^n - 2^{n-2}, \cdots, 2^n - 2^0\}$ works.
Let $s_2(n)$ denote the sum of the digits of $n$ when written in binary. Note that all sums of $k$ of these numbers have the form $k*2^n - a,$ where $a$ is a number less than $2^n$ with $s_2(a) = k.$ Hence, if there were to be $2$ different subset sums, one of which divides the other, we would have to have $k*2^n - a | l*2^n - b,$ for some $a, b$ with $s_2(a) = k, s_2(b) = l.$
Suppose that this were the case, for contradiction, i.e., there is some $r \in \mathbb{N}$ with $l*2^n - b = r(k* 2^n-a).$
Notice that $r \neq 1$ clearly. By looking (mod $2^n$), we obtain that $b \equiv ra$ (mod $2^n$). Thus, we know that $b$ is simply the last $n$ digits of $ra$ (in binary), and so hence $s_2(b) \le s_2(ra).$ Note that by looking at the number of carries when we add up $r$ copies of $a,$ we obtain that $s_2(ra) \le rs_2(a) - s_2(a) * (\left \lfloor \frac{r}{2} \right \rfloor) = k(r - \left \lfloor \frac{r}{2} \right \rfloor),$ since there are at least $\left \lfloor \frac{r}{2} \right \rfloor$ carries in each of the $s_2(a)$ positions with $r$ ones ($1$ for each copy of $a$). Therefore, if $k \ge 3,$ we have that $l \le s_2(ra) \le kr - k \left \lfloor \frac{r}{2} \right \rfloor \le kr - 3 \left \lfloor \frac{r}{2} \right \rfloor \le kr - r,$ since $r \ge 2.$ However, this implies that $l*2^n - b \le (kr-r)*2^n - b = kr*2^n - r*2^n - b < kr *2^n - ra = r(k*2^n- a),$ contradicting our assumption.
Therefore, we only have to deal with the cases where $k = 1$ or $k= 2.$
When $k = 2,$ we know that $l \le kr - 2 \left \lfloor \frac{r}{2} \right \rfloor \le kr -r + 1,$ and so hence $kr*2^n - ra = l*2^n - b \le (kr-r+1) * 2^n - b = kr*2^n - (r-1)*2^n - b,$ implying that $ra \ge (r-1)*2^n + b.$ Thus, we know that $ra - b \ge (r-1)*2^n.$ However, since we clearly have $ra - b < ra < r*2^n,$ and so hence $ra - b = (r-1)*2^n$ since it's a multiple of $2^n.$ In particular, we know that $a > \frac{r-1}{r}* 2^n \ge 2^{n-1},$ and so we may write $a = 2^{n-1} + 2^j$ for some $0 \le j < n-1.$
Thus, we have that $2^{n+1} - 2^{n-1} - 2^j|(2^n-2^{a_1} + 2^n - 2^{a_2} + \cdots + 2^n - 2^{a_l}),$ where $n > i > j \ge 0.$ By modulo $2^j$, we again have that $a_1, a_2, \cdots, a_l \ge j.$ Note that $3 (2^n - 2^{a_t}) - (2^{n+1} - 2^{n-1} - 2^j) = 2^j - 3 * 2^{a_t}.$ Therefore, we know that $3*2^{a_1} - 2^j + 3 * 2^{a_2} - 2^j + \cdots + 3 * 2^{a_l} - 2^j = 3(2^{a_1} + 2^{a_2} + \cdots + 2^{a_l}) - l*2^j)$ is a multiple of $3*2^n - 2^j.$ However, observe that $0 < 3(2^{a_1} + 2^{a_2} + \cdots + 2^{a_l}) - l*2^j < 3* 2^n - l * 2^j \le 3*2^n - 2^j,$ contradiction.
If $k = 1,$ then let $a = 2^i,$ so that $2^n - 2^i | (2^n-2^{a_1} + 2^n - 2^{a_2} + \cdots + 2^n - 2^{a_l}).$ By modulo $2^i$, it's immediate that $a_1, a_2, \cdots, a_l \ge i.$ Notice that $2^n - 2^i, 2^n - 2^{i+1}, 2^n - 2^{i+2}, \cdots, 2^n - 2^{n-1}$ are congruent to $2^{i+1} - 2^i, 2^{i+2} - 2^i, \cdots, 2^{n-1} - 2^{i}$ modulo $2^n - 2^i.$ Therefore, since these numbers are all positive and sum to less than $2^n - 2^i,$ we clearly attain a contradiction.
The set reminds me of IMO 2019 P4 Wait why? Could you elaborate? Because the problem literally asks you about the product of integers in this construction.
ComiCabE
20.02.2020 10:08
Pathological wrote:
We claim that the set $\{2^n - 2^{n-1}, 2^n - 2^{n-2}, \cdots, 2^n - 2^0\}$ works.
I got the same construction, but proved it in a more combinatorial way. First note that every number is uniquely expressible in the form $k2^n-a$, where $0\le a<2^n$. Now for $N=k2^n-a$ let us denote $k$ as $F(N)$ and the number of nonzero digits in the binary representation of $a$ as $S(N)$. And finally, let us denote $D(N)=F(N)-S(N)$. Clearly, a sum of any subset of the set in Construction is an integer for which $D=0$. Here comes the crucial observation. Claim. $D(a+b)\ge D(a)+D(b)$ and the inequality is strict when $a=b$.
Let $a=A2^n-\alpha$ and $b=B2^n-\beta$.
Case 1. $\alpha+\beta<2^n$.
If so happens, we have $F(a+b)=F(a)+F(b)$ and $S(a+b)\le S(a)+S(b)$ where the inequality is strict for $a=b$, and the result follows.
Case 2. $2^n\le\alpha+\beta<2^n\cdot 2$.
In this case, we have $F(a+b)=F(a)+F(b)-1$ and $S(a+b)+1\le S(a)+S(b)$ with strict inequality for $a=b$, because exactly one $2^n$ from the binary expression of $\alpha+\beta$ got carried away to the first part, and has consecuently subtracted $1$ from $F(a+b)$. Again, the result follows.
Now assume there are two sums $A$ and $B$ of subsets, for which we have $A=kB$. Obviously $k\ge 2$ and $D(A)=D(B)=0$. Now $D(A)=D(kB)\ge (k-2)D(B)+D(2B)>(k-2)D(B)+2D(B)=0$. Therefore $D(A)>0$, a contradiction.
bumjoooon
24.05.2020 05:24
Nice and fun problem!! Pathological wrote:
We claim that the set $\{2^n - 2^{n-1}, 2^n - 2^{n-2}, \cdots, 2^n - 2^0\}$ works.
Sum of each subset can be written in forms of $s(a)2^n-a$. Assume there exists $r,a,b$ with $r\times (s(a)2^n -a)=s(b)2^n - b$. $b$ is exactly the remainder of $ra$ divided by $2^n$.
Assuming $a=2^{a_1} + ... + 2^{a_{s(a)}}$, first write $ra = r 2^{a_1} +...+2^{a_{s(a)}}$. Define ‘action’ as erasing two $2^m$ and adding new $2^{m+1}$ for $m<n$. Take action as mush as we can. Then finally, we get the unique expression $ra = 2^n \times t + 2^{b_1}+...+2^{b_s}$.
Since $b$ is the remainder of $ra$ divided by $2^n$, $2^{b_1}+...+2^{b_s}$ is the binary expression of $b$ and $t = (ra-b)/2^n$. Since every action reduces total number of power of $2$, $rf(a) \geq f(b)+ t$ where equality only holds for $r=1$. (When $r \ne 1$, the action is always possible and thus reducing the total number of power of $2$.)
Coming back to the original equation $2^n (rs(a)-s(b))=(ra-b)$, $r$ should be $1$ and $a=b$. Therefore, the constructed set is what we wanted.
CANBANKAN
24.05.2022 07:33
I claim $S=\{2^n-2^j | 0\le j<n\}$ works. Let $s_k=2^n-2^k$ for $0\le k\le n-1$. Suppose $A=\{a_1, \cdots, a_{s_2(x)}\}, x=\sum\limits_{j=1}^{s_2(x)} 2^{a_j}, B=\{b_1, \cdots, b_{s_2(y)}\}, y=\sum\limits_{j=1}^{s_2(y)} 2^{b_j}$ and $\sum\limits_{m\in A} m \mid \sum\limits_{m\in B} m $ Note this is equivalent to $2^n s_2(x) - x \mid 2^n s_2(y)-y$ Suppose $k(2^n s_2(x)-x) = 2^n s_2(y)-y$ Rearranging, $2^n (ks_2(x)-s_2(y)) = kx-y$ Note $2^n\mid kx-y$ and $\frac{kx-y}{2^n}\le k-1$ Also, $s_2(y) < s_2(kx) \le s_2(x)s_2(k)$, so $2^n (k-s_2(k)) s_2(x)) < kx-y$. It follows that $(k-s_2(k))s_2(x) \le k-2$ If $s_2(x)\ge 2$ we get a size contradiction because $k-s_2(k) \ge \frac{k-1}{2}$. It follows that $x=2^t$ for some $t\le n-1$, so $2^n(k-s_2(y))=k2^t-y$. Write $y=2^t y'$ where $y'$ is odd, we get $2^{n-t}(k-s_2(y'))=k-y'$. Howevver, $2(k-s_2(y'))>k-s_2(y')\ge k-y'$, absurd!
JG666
24.05.2022 08:22
Here is a combinatorical way to prove this. One can easily guess the construction is $T = \{2^n-2^0, 2^n-2^1, \cdots, 2^n-2^{n-1}\}$. Assume for the sake of contradiction that there exists $A = \{2^n-2^{a_1}, \cdots, 2^n-2^{a_p}\} \text{ and } B = \{2^n-2^{b_1}, \cdots, 2^n-2^{b_q}\}$ such that $S(A) = kS(B)$. It is equivalent to $2^nq+\sum_{i=1}^p2^{a_i} = k\cdot 2^np + \sum_{i=1}^q2^{b_i}$.
Erase two equal numbers in the form of $2^r(r<n)$ and write $2^{r+1}$. Since $k\ge 2$, one can do the operation at least once.
. After each operation the total number of numbers on the blackboard decreases by $1$. After finite operations, there are only a few $2^n$s and a few powers of 2 less than $2^n$. Note that the any operation doesn't change the sum of numbers on the blackboard. We know binary presentation is unique, therefore when the operation is finally stopped, LHS $\equiv$ RHS. But this obviously is a contradiction, since the total number of numbers on the blackboard has definitely be changed.
NoctNight
09.06.2023 15:05
If $A=B\cup C$ and $\sum_{x\in B}x\mid \sum_{y\in C}y$ then $\sum_{x\in B}x\mid \sum_{y\in C}y+\sum_{x\in B} x=\sum_{z\in A} z$ so it suffices to make $\sum_{z\in A} z$ a prime and $1\not\in A$. But we can make $\sum_{z\in A} z$ any number from $2+3+\cdots +(n+1)$ to $[2^n-(n-1)]+[2^n-(n-2)]+\cdots+2^n$ by shifting $i$ to $i+1$ whenever $i+1\not\in A$. By Bertrand's postulate, we are done as long as the first number is at most half the second (so there will be a prime), i.e. $$2\left(\frac{(n+1)(n+2)}{2} - 1\right) \leq n2^n - \frac{n(n-1)}{2}$$which is true as long as $n^2+3n+2-2+n^2-n \leq n2^n$ or $n+2\leq 2^n$, true for $n\geq 2$. For $n=1$ we take $A=\{1\}$.