US-TST 2018 Problem 4

Let $n$ be a positive integer and let $S \subseteq\{0,1\}^{n}$ be a set of binary strings of length $n$. Given an odd number $x_{1}, \ldots, x_{2 k+1} \in S$ of binary strings (not necessarily distinct), their majority is defined as the binary string $y \in\{0,1\}^{n}$ for which the $i^{\text {th }}$ bit of $y$ is the most common bit among the $i^{\text {th }}$ bits of $x_{1}, \ldots, x_{2 k+1}$. (For example, if $n=4$ the majority of $0000,0000,1101,1100,0101$ is 0100 .) Suppose that for some positive integer $k, S$ has the property $P_{k}$ that the majority of any $2 k+1$ binary strings in $S$ (possibly with repetition) is also in $S$. Prove that $S$ has the same property $P_{k}$ for all positive integers $k$.