A set $X$ consisting of $n$ positive integers is called $\textit{good}$ if the following condition holds: For any two different subsets of $X$, say $A$ and $B$, the number $s(A) - s(B)$ is not divisible by $2^n$. (Here, for a set $A$, $s(A)$ denotes the sum of the elements of $A$) Given $n$, find the number of good sets of size $n$, all of whose elements is strictly less than $2^n$.
Problem
Source: Mongolia national olympiad 2024
Tags: combinatorics, number theory, complete residue system
11.04.2024 16:36
Bumping this
11.04.2024 20:01
12.04.2024 06:28
Claim. $X=\left\{a_{1},...,a_{n}\right\}$ is a good set iff there is a permutation $\sigma$ of $\left[n\right]$, s.t. $v_{2}\left(a_{\sigma\left(k\right)}\right)=k-1$ for $k=1,...,n$. Thus the number of good sets with largest element smaller than $2^n$ is $2^0 \cdot 2^1 \cdot ...\cdot 2^{n-1}=2^{\frac{n\left(n-1\right)}{2}}$. Proof of Claim. Set $f\left(x\right)=\prod\limits_{i=1}^{n}\left(1+x^{a_{i}}\right)$, then $X$ is a good set iff $f\left(x\right)\equiv\sum\limits_{j=0}^{2^n-1}x^j\equiv \prod\limits_{k=0}^{n-1}\left(1+x^{2^k}\right)\left(\mathrm{mod}x^{2^n}-1\right)$, which implies $\prod\limits_{k=0}^{n-1}\left(1+x^{2^k}\right)\mid \prod\limits_{i=1}^{n}\left(1+x^{a_{i}}\right)$. Since each $1+x^{2^{k}}$ is irreducible over $\mathbb{Q}\left[x\right]$ (as it is a cyclotomic polynomial; another proof is to use Eisenstein's criterion on $1+\left(1+x\right)^{2^k}$), there exist a permutation $\sigma$ of $\left[n\right]$, such that $1+x^{2^{k-1}}\mid 1+x^{a_{\sigma\left(k\right)}}$, $k=1,...,n$. This implies $v_{2}\left(a_{\sigma\left(k\right)}\right)=k-1$. An induction argument shows the sufficiency part, so we are done.
12.04.2024 18:59
@above why $\prod\limits_{k=0}^{n-1}\left(1+x^{2^k}\right)\mid \prod\limits_{i=1}^{n}\left(1+x^{a_{i}}\right)$
16.04.2024 14:52
Can someone explain why $\prod\limits_{k=0}^{n-1}\left(1+x^{2^k}\right)\mid \prod\limits_{i=1}^{n}\left(1+x^{a_{i}}\right)$
08.05.2024 12:35
Let $f(n)$ denote the answer for n. Clearly, $f(1)=1$ Obviously, if all element are even, then sum $1$ can not be achieved. Thus there is an odd element $a$. Divide by it as residues mod $2^n$ all elements, the condition has preserved. Now we have a $1$ in our set. Call the remaining set $M$. Then the sums of subsets of $M$ are exactly all even residues mod $2^n$. Hence all it's elements are even and we can divide by two. We have returned to $f(n-1)$. Because there are exactly $2^{n-1}$ possible values of $a$, $f(n)=2^{n-1}f(n-1)$. Clearly, $f(n)=2^{\frac{n(n-1)}{2}}$. That is the answer