Find all family $\mathcal{F}$ of subsets of $[n]$ such that for any nonempty subset $X\subseteq [n]$, exactly half of the elements $A\in \mathcal{F}$ satisfies that $|A\cap X|$ is even.
Problem
Source: Kürschák competition 2019 P2
Tags: combinatorics
17.02.2020 05:49
17.02.2020 05:58
CantonMathGuy wrote:
$\mathcal{F}=\emptyset$ is another solution, as you mentioned that $|\mathcal{F}| \in \{0, 2^n\}$.
17.02.2020 06:09
Ti-Ci wrote: $\mathcal{F}=\emptyset$ is another solution, as you mentioned that $|\mathcal{F}| \in \{0, 2^n\}$. CantonMathGuy wrote: The only solutions are $\textcolor{red}{\mathcal{F}}$ empty and $\mathcal{F} = \mathcal{P}([n])$
17.02.2020 06:17
CantonMathGuy wrote: Ti-Ci wrote: $\mathcal{F}=\emptyset$ is another solution, as you mentioned that $|\mathcal{F}| \in \{0, 2^n\}$. CantonMathGuy wrote: The only solutions are $\textcolor{red}{\mathcal{F}}$ empty and $\mathcal{F} = \mathcal{P}([n])$ Sorry for my stupid misread BTW, your sol is pretty nice!
18.12.2020 09:09
22.12.2020 23:59
08.09.2022 04:07
$F$ includes either all or no subsets. Double-count the number of subsets $(A,B)$, where $A\in F,b\in [n]\setminus \phi,|A\cap B|\equiv 0\pmod{2}$. If $F$ does not include the empty set, we end up obtaining $\frac{|F|}{2}\cdot 2^n-1=|F|(2^{n-1}-1)+2^{n-1}\rightarrow |F|=2^n$. Else, we have $\frac{|F|}{2}\cdot 2^n-1=|F|(2^{n-1}-1)\rightarrow |F|=0$.
26.02.2024 13:24
The answer is $\mathcal{F}=\emptyset$ and $\mathcal{F}=\mathcal{P}([n])$; these clearly work. Suppose $\mathcal{F}$ is nonempty. Take any working $\mathcal{F}$ and consider the polynomial in $n$ variables $$P(x_1,\ldots,x_n)=\sum_{A \in \mathcal{F}}\prod_{i \in A} (1-2x_i).$$For any nonzero $X \in [n]$, plugging in its obvious representation as a $\{0,1\}^n$ vector into $P$ should yield zero, since $\prod_{i \in A} (1-2x_i)$ is $1$ if $|A \cap X|$ is even and $-1$ otherwise. Thus $P$ vanishes at every point in $\{0,1\}^n$ except for $(0,\ldots,0)$, where it equals $|\mathcal{F}|$. So now $$P(x_1,\ldots,x_n)-|\mathcal{F}|\prod_{i=1}^n (1-x_i)$$vanishes at every point on $\{0,1\}^n$. If $\mathcal{F}$ does not contain $[n]$ then we get an immediate contradiction by combinatorial nullstellensatz owing to a maximal degree term of $-|\mathcal{F}|(-1)^nx_1\ldots x_n$, and otherwise the coefficient of the maximal degree term $x_1\ldots x_n$ is $(-2)^n-|\mathcal{F}|(-1)^n$. To avoid the same combinatorial nullstellensatz contradiction we must therefore have $|\mathcal{F}|=2^n$, which finishes. $\blacksquare$
29.02.2024 16:22
\begin{align*} \text{problem condition} &\iff \sum_{X \in \mathcal{F}}(-1)^{\lvert A \cap X\rvert}=0\text{ for nonempty $A$} \\ &\iff \widehat{\mathbf{1}_{\mathcal{F}}}(A) = 0\text{ for nonempty $A$} \\ &\iff \mathbf{1}_{\mathcal{F}} \text{ is constant} \\ &\iff \mathcal{F} = \varnothing \text{ or } \mathcal{F} = \mathcal{P}([n]) \end{align*}