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
29.03.2019 18:32
Just for clarification the set $A$ is consective numbers from $1$ to $2^n$ or powers of two?
29.03.2019 18:56
I think it is consecutive numbers, because for $n=2$, $\{1,2,4\}$ doesn't work.
30.03.2019 06:21
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
20.08.2019 17:01
Pathological wrote:
The set reminds me of IMO 2019 P4
20.08.2019 17:41
GammaBetaAlpha wrote: Pathological wrote:
The set reminds me of IMO 2019 P4 Wait why? Could you elaborate?
16.02.2020 21:07
MessingWithMath wrote: GammaBetaAlpha wrote: Pathological wrote:
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.
20.02.2020 10:08
Pathological wrote:
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$.
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.
24.05.2020 05:24
Nice and fun problem!! Pathological wrote:
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!
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}$.
. 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.
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\}$.