Find the smallest positive integer $N$ such that there are no different sets $A, B$ that satisfy the following conditions. (Here, $N$ is not a power of $2$. That is, $N \neq 1, 2^1, 2^2, \dots$.) $A, B \subseteq \{1, 2^1, 2^2, 2^3, \dots, 2^{2023}\} \cup \{ N \}$ $|A| = |B| \geq 1$ Sum of elements in $A$ and sum of elements in $B$ are equal.
Problem
Source: KJMO 2023 P7
Tags: number theory
05.11.2023 15:47
Answer:$2^{2023}+2^{2022}$ Let $N=2^{\alpha_1}+2^{\alpha_1}+...+2^{\alpha_k}$ and $\alpha_i >\alpha_j \iff i>j$. If $\alpha_1 \leq 2022$, then take $A=\{N,2^{\alpha_1},2^{\alpha_2},...,2^{\alpha_{k-1}}\}$ and $B=\{2^{\alpha_k},2^{\alpha_{k-1}+1},2^{\alpha_{k-2}+1},...,2^{\alpha_1+1}\}$ These sets hold the conditions. So $\alpha_1\geq 2023$. If $\alpha_2\leq 2021$, then take $A=\{N,2^{\alpha_2},2^{\alpha_3},...,2^{\alpha_{k}}\}$ and $B=\{2^{\alpha_1},2^{\alpha_2+1},...,2^{\alpha_k+1}\}$ These sets holds. So $\alpha_2\geq 2022$. We have $N\geq 2^{2023}+2^{2022}$ Now, let's prove that when $N=2^{2023}+2^{2022}$, there are not sets which satisify the conditions. $WLOG$ let $N \in A$.Let $S(X)$ be the sum of the elements of $X$.$S(A)>2^{2023}$ and we know that $2^{2022}+...+1<2^{2023}$ so $2^{2023} \in B$. Let the elements of $A$ other than $N$ be $2^{a_1},2^{a_2},...,2^{a_l}$ and the elements of $B$ other than $2^{2023}$ be $2^{b_1},2^{b_2},...,2^{b_{l}}$. \[2^{a_1}+...+2^{a_l}=2^{2022}+2^{b_1}+...+2^{b_l}\]We can assume that none of $a_i$ is equal to $b_j$. If all $a_i'$s are smaller that $2022$, it's obvious that $LHS$ would be smaller. Let $a_1=2022$. \[2^{a_2}+...+2^{a_l}=2^{b_1}+...+2^{b_l}\]$a_i$ and $a_j$ are different and $b_i$ and $b_j$ are different if $i$ is not equal to $j$. Let $b_l$ be the smallest one among all $b_i'$s. $v_2(RHS)=b_l$ but $v_2(LHS)\geq b_l+1$ or $v_2(LHS \leq b_l-1)$. Contradiction