For a finite set $A$ of positive integers and its subset $B$, call $B$ a half subset of $A$ when it satisfies the equation $\sum_{a\in A}a=2\sum_{b\in B}b$. For example, if $A=\{1,2,3\}$, then $\{1,2\}$ and $\{3\}$ are half subset of $A$. Determine all positive integers $n$ such that there exists a finite set $A$ which has exactly $n$ half subsets.
Problem
Source: 2022 Korea Winter Program Practice Test
Tags: combinatorics, Subset, algebra
Hapi
19.08.2022 12:40
Bump this one$.$
SerdarBozdag
19.08.2022 20:09
We can construct example for powers of two(if n takes the value x then it also takes 2x) with induction
dgrozev
20.08.2022 13:03
$n=2k.$ If $B$ is a half subset of $A$ then $A\setminus B$ is also a half subset of $A$. That is, the number of half subsets must be even. Below is an example of a set $A$ with exactly $2k$ half subsets, $k\in \mathbb{Z}^+.$ Let $0<a_1<a_2<\dots<a_k$ be any set of rapidly increasing positive integers, for instance satisfying $$a_1+a_2+\dots+a_i<a_{i+1}\,,\, i=1,2,\dots,k-1$$Take $S_1\in \mathbb{Z}^+$ big enough and define $$a_{k+1+i}:= S_1-a_{k-i}\,,\, i=0.1.\dots,k-1$$Let $r:=(k-2)S_1.$ Finally, we define our set $A$ to be $$A:=\{r,a_1,a_2,\dots,a_{2k}\}$$It's straightforward to see $S:=\sum_{a\in A}a=2(k-1)S_1$ and $$r+a_i+a_{2k+1-i}=S/2\,,\, i=1,2,\dots,k.$$This means $B_i:=\{r,a_i,a_{2k+1-i}\},i=1,2,\dots,k$ are half subsets of $A$. It can be seen that there is no other half subset that includes $\{r\}$. EDIT. The above example apparently holds only for $k>2$. For $k=1$ and $k=2$ one can take for instance $\{1,2,3\}$ and $\{1,2,4,5\}$ respectively.