Problem

Source: 2022 Taiwan TST Round 3 Mock Exam Problem 2

Tags: algebra, Taiwan



Let $n,s,t$ be three positive integers, and let $A_1,\ldots, A_s, B_1,\ldots, B_t$ be non-necessarily distinct subsets of $\{1,2,\ldots,n\}$. For any subset $S$ of $\{1,\ldots,n\}$, define $f(S)$ to be the number of $i\in\{1,\ldots,s\}$ with $S\subseteq A_i$ and $g(S)$ to be the number of $j\in\{1,\ldots,t\}$ with $S\subseteq B_j$. Assume that for any $1\leq x<y\leq n$, we have $f(\{x,y\})=g(\{x,y\})$. Show that if $t<n$, then there exists some $1\leq x\leq n$ so that $f(\{x\})\geq g(\{x\})$. Proposed by usjl