Let $S$ be a finite set, and let $F$ be a family of subsets of $S$ such that a) If $A\subseteq S$, then $A\in F$ if and only if $S\setminus A\notin F$; b) If $A\subseteq B\subseteq S$ and $B\in F$, then $A\in F$. Determine if there must exist a function $f:S\to\mathbb{R}$ such that for every $A\subseteq S$, $A\in F$ if and only if \[\sum_{s\in A}f(s)<\sum_{s\in S\setminus A}f(s).\] Evan O'Dorney.
Problem
Source: ELMO Shortlist 2011, C1
Tags: function, modular arithmetic, combinatorics proposed, combinatorics
dgrozev
04.07.2012 12:45
There is an example of family $F$, such that no function $ f:S\to\mathbb{R} $ can generate it. A counterexample: Let $n=|S|$ and $n \geq 10$ is even but not multiple by $4$. Assume that $S=\{1,2,\ldots,n\}$. Denote: $F' = \left\{ \{i_1,i_2,\ldots, i_{\frac{n}{2}}\} \,|\, i_j \in S,\, i_1+i_2+\ldots+i_{\frac{n}{2}} \equiv 1 \pmod{2} \right\}$. $F=\left\{ A \,|\, A \subset S,\, \exists B \in F', A\subset B \right\} $. It can be seen that $F$ satisfies requirements a) and b) from the problem's clause. Now, let assume that there exists function $ f:S\to\mathbb{R} $ which generate $F$ in the sense of the problem's statement. Let $ f(i_1) \leq f(i_2) \leq \ldots \leq f(i_n) $. Clearly it is not possible all of $f(i)$ to be equal. Thus $A_1 = \{i_1,i_2,\ldots,i_{\frac{n}{2}} \} \in F$. Let denote $B_1 = \{i_{\frac{n}{2}+1},\ldots,i_{n} \} = S \setminus A_1 $. Notice that if $i_s$ and $i_r$ are neighbours, i.e. $|i_s-j_r|=1$ and if $i_s \in A_1,\, i_r \in B_1$ then if we swap $i_s$ with $i_r$ in $A_1$ we will get $A_1' \notin F $. Now consider two sets: $A_2 = \{i_2,i_3,\ldots, i_{\frac{n}{2}} \}$ and $ B_2 = \{i_{\frac{n}{2}+1}, \ldots, i_{n-1} \}$. There exist two indexes $i_s \in A_2$ and $i_r \in B_2$ which are neighbours i.e. $|i_s-i_r|=1$. It is because $n\geq 10$. Consider now set $A=\{i_1,i_2,\ldots,i_{s-1},i_r,i_{s+1},\ldots,i_{\frac{n}{2}} \}$. Using the deffinition of $F$ we get $A \notin F$ but $\sum_{a\in A} f(a) < \sum_{a\in S\setminus A} f(a)$, so $A \in F$, contradiction.
K_Mirrorheart
08.04.2019 17:02
Actually one could find the largest $|S|$ satisfying the statement. For $|S|=6$, assume $S=\{1,2,3,4,5,6\}$, let $F$ contain all the subsets with cardinality $\leqslant 2$, all the subsets with cardinality $3$ and containing $1$ except for $\{1,2,6\}$ and $\{1,3,4\}$. $F$ also contains$\{3,4,5\}$ and $\{2,5,6\}$. It is true that $F$ satisfies a) and b). Assume, for the sake of contradiction that such mapping $f$ exists. Denote by $x_i$ the image of $i$ under $f$. Since $F$ contains$\{3,4,5\}$ and $\{1,2,3\}$, we have $x_1+x_2+x_3<x_4+x_5+x_6$ and $x_3+x_4+x_5<x_1+x_2+x_6$ i.e. $x_3<x_6$. Analogously, $\{2,5,6\}$ and $\{1,4,6\}$ imply $x_6<x_3$, a contradiction. For $|S|=5$, the statement holds by a Belarussian problem (sorry I can't find it). Or one may try a arduous bruteforcing.