There is probably some much easier solution, but I'm going to embarrass myself and post this one. It's easy to show that if $S$ has $P_k$, then $S$ has $P_1$. (Simply pick strings multiple times.) So we show that if $S$ has $P_1$, then it has $P_k$ for all $k$. To this end, we demonstrate that given the 3-majority function $f_1: \{0, 1\}^3 \to \{0, 1\}$, we can construct the $2k + 1$-majority function $f_k: \{0, 1\}^{2k + 1} \to \{0, 1\}$ for any $k$. By induction, it is enough to show that given the $2k + 1$-majority function $f_k$, we may construct the $2k + 3$-majority function $f_{k + 1}$. Our candidate for $f_{k + 1}$ will be a uniformly randomly chosen nested series of $f_k$s with $\ell$ layers, for some $\ell$ to be chosen later; we contend that for $\ell$ sufficiently large, the probability of the candidate failing is less than 1, settling the conclusion. Let $(a_1, \dots, a_{2k + 3}) \in \{0, 1\}^{2k + 3}$ be the input vector. If there are at most $k$ 0s among $a_1, \dots, a_{2k + 3}$, then every application of the $2k + 1$-majority function will return 1, so our candidate is valid in this case. Similar remarks hold when there are at most $k$ 1s. Thus, it is enough to examine the case of $k + 1$ 0s and $k + 2$ 1s: we are aiming for our candidate to return 1. By elementary counting, there are $\tbinom{k + 1}{k + 1} \tbinom{k + 2}{k} = \tfrac{(k + 2)(k + 1)}{2}$ $2k + 1$-subsets of $\{a_1, \dots, a_{2k + 3}\}$ with a majority of 0. Thus, if $\ell = 1$, the probability of our random candidate failing is $\tfrac{(k + 2)(k + 1)/2}{(2k + 3)(2k + 2)/2} = \tfrac{k + 2}{4k + 6} < \tfrac{1}{3}$ for each input. We will show that for $\ell$ sufficiently large, the probability of our candidate failing for each input is less than $\tbinom{2k + 3}{k + 1}^{-1}$; this implies the conclusion. Suppose that for a tower of length $\ell$, the candidate has at most $p_{\ell}$ chance of failure (so $p_1 < \tfrac{1}{3}$). Then by a series of straightforward but lengthy computations, one can deduce $p_{\ell} \to 0$ as one would expect. (If $p_1 < \tfrac{1}{3}$, composing more of them will lead to negligible probabilities of zero outputs.)

In particular, some $\ell$ will force $p_{\ell} < \tbinom{2k + 3}{k + 1}^{-1}$, implying the conclusion by the union bound. Remark. This Schweitzer problem describes the set of all functions obtainable by composing 3-majority functions. The result implies that given the 3-majority function, we can construct the $2k + 1$-majority function for every $k$.

My solution was just induction. You can also use binary AND to get the construction of $(2k+1)$-majority from $3$-majority without probability, although that uses exponentially many gates I think. Let $M$ denote the majority function (of any length). First solution (induction) We prove all $P_k$ are equivalent by induction on $n \ge 2$, with the base case $n = 2$ being easy to check by hand. (The case $n=1$ is also vacuous; however, the inductive step is not able to go from $n=1$ to $n=2$.) For the inductive step, we proceed by contradiction; assume $S$ satisfies $P_{\ell}$, but not $P_{k}$, so there exist $x_1, \dots, x_{2k+1} \in S$ whose majority $y = M(x_1, \dots, x_k)$ is not in $S$. We contend that: Claim: Let $y_i$ be the string which differs from $y$ only in the $i$th bit. Then $y_i \in S$. Proof. For a string $s \in S$ we let $\hat s$ denote the string $s$ with the $i$th bit deleted (hence with $n-1$ bits). Now let \[ T = \left\{ \hat s \mid s \in S \right\}. \]Since $S$ satisfies $P_\ell$, so does $T$; thus by the induction hypothesis on $n$, $T$ satisfies $P_{k}$. Consequently, $T \ni M(\hat{x}_1, \dots, \hat{x}_{2k+1}) = \hat y$. Thus there exists $s \in S$ such that $\hat s = \hat y$. This implies $s = y$ or $s = y_i$. But since we assumed $y \notin S$ it follows $y_i \in S$ instead. $\blacksquare$ Now take any $2\ell+1$ copies of the $y_i$, about equally often (i.e.\ the number of times any two $y_i$ are taken differs by at most $1$). We see the majority of these is $y$ itself, contradiction. Second solution (circuit construction) Note that $P_k \implies P_1$ for any $k$, since \[ M( \underbrace{a,\dots,a}_k, \underbrace{b,\dots,b}_k, c ) = M(a,b,c) \]for any $a$, $b$, $c$. We will now prove $P_1 + P_k \implies P_{k+1}$ for any $k$, which will prove the result. Actually, we will show that the majority of any $2k+3$ strings $x_1$, \dots, $x_{2k+3}$ can be expressed by $3$ and $(2k+1)$-majorities. WLOG assume that $M(x_1, \dots, x_{2k+3}) = 0\dots0$, and let $\odot$ denote binary AND. Claim: We have $M(x_1, x_2, M(x_3, \dots, x_{2k+3})) = x_1 \odot x_2$. Proof. Consider any particular bit. The result is clear if the bits are equal. Otherwise, if they differ, the result follows from the original hypothesis that $M(x_1, \dots, x_{2k+3}) = 0\dots0$ (removing two differing bits does not change the majority). $\blacksquare$ By analogy we can construct any $x_i \odot x_j$. Finally, note that \[ M(x_1 \odot x_2, x_2 \odot x_3, \dots, x_{2k+1} \odot x_{2k+2}) = 0\dots0, \]as desired. (Indeed, if we look at any index, there were at most $k+1$ $1$'s in the $x_i$ strings, and hence there will be at most $k$ $1$'s among $x_i \odot x_{i+1}$ for $i=1,\dots,2k+1$.) Remark: The second solution can be interpreted in circuit language as showing that all ``$2k+1$-majority gates'' are equivalent. See also https://cstheory.stackexchange.com/a/21399/48303, in which Valiant gives a probabilistic construction to prove that one can construct $(2k+1)$-majority gates from a polynomial number of $3$-majority gates. No explicit construction is know for this.

I'm not sure if this works; it seems to? The gist of this solution is induction, and using the $2k+1$-majority function cyclically to replace our old strings with newer strings while preserving the majority of the $2k+3$ strings, and showing that eventually we can make the strings all be equal. (Obviously, if this were implemented in code or something like that, this would be really, really inefficient.) Let $M$ denote the majority function, where we can use it for any odd number of strings. We use the following to generate an algorithm: Claim: Let $k$ be a positive integer and $a_1, \dots, a_{2k+3}$ be any set of binary strings, and denote the $j$th bit of $a_i$ as $a_{i,j}$. Then, define the $2k+3$ strings $b_i=M(a_{i+2}, a_{i+3}, \dots, a_{i+2k+2})$ (indices taken mod $2k+3$), and denote the $j$th bit of $b_i$ as $b_{i,j}$. Then, for some bit place $j$, if at least $k+3$ of the $a_{i,j}$ ($i=1, \dots, 2k+3$) are $1$'s (similarly $0$'s), then all of the $b_{i,j}$ are $1$'s (similarly $0$'s), and if $k+2$ of the $a_{i,j}$ are $1$'s (similarly $0$'s), then at least $k+2$ of the $b_{i,j}$ are $1$'s (similarly $0$'s). This immediately implies that $M(a_1, \dots, a_{2k+3})=M(b_1, \dots, b_{2k+3})$. Proof: Consider each bit place $j$. WLOG let more of the $a_{i,j}$'s be $1$s than $0$s (the proof is similar if it's the other way around). If at least $k+3$ of the $a_{i,j}$ are $1$'s, then note that at least $(k+3)-2=k+1$ out of any $(2k+3)-2=2k+1$ consecutive strings have a $1$ in the $j$th bit, meaning that the majority of any $2k+1$ consecutive strings will have a $1$ in the $j$th bit, meaning that all of the $b_{i,j}$ (which are the $j$th bit of strings that are the majority of $2k+1$ consecutive strings) are $1$'s. Now, if $k+2$ of the $a_{i,j}$ are $1$'s, then note that $b_{i,j}=0$ if and only if both $a_{i,j}$ and $a_{i+1,j}$ are $1$'s (easy to show). The number of such $i$ such that both $a_{i,j}$ and $a_{i+1,j}$ are $1$'s is at most $k+2$ (since $k+2$ of the $a_{i,j}$ are $1$'s), but if there are $k+2$ such $i$ then that means that all of the $a_{i,j}$'s that are $1$'s must also have $a_{i-1, j}$ be $1$'s, meaning that all of the strings that have a $1$ in the $j$th bit must be adjacent, but note that the first and last strings are not adjacent because $k+2<2k+3$, contradiction. Thus, there are at most $k+1$ such $i$, meaning that at least $k+2$ of the $b_{i,j}$ are $1$'s, as desired. $\blacksquare$ Now, to get $P_1$ from $P_k$ is fairly obvious; stuff like $$M(\underbrace{a, \dots, a}_{k}\underbrace{b, \dots, b}_{k},c)=M(a,b,c)$$works (or you can take $\left\lfloor\frac{2k+1}{3}\right\rfloor$ copies of $a$, $\left\lfloor\frac{2k+2}{3}\right\rfloor$ copies of $b$, and $\left\lfloor\frac{2k+3}{3}\right\rfloor$ copies of $c$). Now, we will show that $P_k\implies P_{k+1}$; after this, the induction will follow easily. Let $a_1, \dots, a_{2k+3}$ be any $2k+3$ strings. The nice thing about our claim from above is that the majority in the bits in a certain bit place will be nondecreasing, we can reorder the strings however we want, and if $P_k$ is true, then all of the $b_i$ are in $S$. Thus, for a permutation $\sigma$, define the function/algorithm $A(\sigma)$ to return $(b_1, ..., b_{2k+3})$ where $b_i=M(a_{\sigma(i+2)}, \dots, a_{\sigma(i+2k+2)})$. Now, we follow the following procedure, for $j=1, ..., n$: If all the strings already agree on the $j$th bit, then go to the next bit. Else, if $k+2$ of the strings have a certain bit on the $j$th bit, WLOG $1$, then choose a permutation $\sigma$ such that the sequence $a_{\sigma(1),j}, \dots, a_{\sigma(2k+3),j}$ looks like $1, 0, 1, 0, \dots, 1, 0, 1$, and then apply $A(\sigma)$ to get $(b_1, \dots, b_{2k+3})$, which will replace our $a_i$'s. This will ensure that all the $b_{i,j}$ except for $b_{2k+3, j}$ are $1$s (since $2k+3$ is the only integer $i$ satisfying $a_{\sigma(i), j}=a_{\sigma(i+1), j}=1$). Because $2k+2$ of the strings agree on the $j$th bit, move on to the last condition. Now, if between $k+3$ and $2k+2$ of the strings have a certain bit on the $j$th bit, WLOG $1$, then let $\sigma$ be the identity permutation and apply $A(\sigma)$ to get $(b_1, \dots, b_{2k+3})$, which will replace our $a_i$'s. Due to the first part of our claim, now all of the strings agree on the $j$th bit, so we move on to the next bit. Eventually, when the procedure terminates at $j=n$, we note that all the strings are equal, the majority was preserved the whole time, and the majority of the strings, all of which are in $S$, must be in $S$ (since the majority of $x$ equal strings is $x$ itself). Thus, the majority of any $2k+3$ strings is in $S$, completing the inductive step. (Note that this should still work if $n$ is replaced by infinity, because while it's possible that infinitely many bit places have exactly $k+2$ strings agree, there's only finitely many combinations of $k+2$ strings that can agree on a certain bit place, and we can apply $A(\sigma)$ enough times to cover all such combinations, and then a last application of $A(\sigma)$ will make all the strings equal.)

Let $m$ is an odd positive integer. By $V_m(x_1,x_2,\dots,x_m), x_i\in\{0,1\},i=1,2,\dots,m$ we denote the boolean function (a vote function), which value equals the most common value among its arguments. It's enough to prove the following claim: Let $m_0$ be odd integer, $m_0\geq 3$. Then for any other odd $m\geq 3$, the function $V_m$ can be represented as composition of functions $V_{m_0}$. Indeed if it's true, it can be applied bitwise, at every step (of the composition) we don't leave $S$. Proof of the claim: Two steps. First, $V_3$ can be represented as a composition of $V_{m_0}$. Second step, $V_m$ is a composition of some $V_3$ functions. 1-th step) It can be checked $V_3(x_1,x_2,x_3)=V_{m_0}(x_1,x_2,x_3,x_1,x_2,x_3,\dots)$. 2-nd step) Let $m=2k-1, k\geq 3$. For $k$-odd it holds: \begin{align*} &V_{2k-1}(x_1,x_2,\dots,x_{2k-1})=\\ &V_{k}(V_3(x_1,x_2,V_{2k-3}(x_3,\dots,x_{2k-1})),V_3(x_3,x_4,V_{2k-3}(x_1,x_2,x_5,\dots,x_{2k-1})),\dots\\ &\dots, V_3(x_{2k-3},x_{2k-2},V_{2k-3}(x_{2k-1},x_1,\dots,x_{2k-4}))). \end{align*}For $k$-even, it can be checked: \begin{align*}&V_{2k-1}(x_1,x_2,\dots,x_{2k-1})=\\ &V_{k}(V_3(x_1,x_2,V_{2k-3}(x_3,\dots,x_{2k-1})),V_3(x_3,x_4,V_{2k-3}(x_1,x_2,x_5,\dots,x_{2k-1})),\dots\\ &\dots, V_3(x_{2k-3},x_{2k-2},V_{2k-3}(x_{2k-1},x_1,\dots,x_{2k-4})), V_3(x_{2k-2},x_{2k-1},V_{2k-3}(x_1,\dots,x_{2k-3}))). \end{align*}Applying consecutively the above recurrence formula, yields the result. Comment. The problem can be generalized in the following way. Instead of the used operation "majority", we can consider a more general operation, which can be called a "decision making (function)". A boolean function $f(x_1,x_2,\dots,x_m)$ is called a desision function if: (a) the value of the function changes if we change all of its arguments; (b) the values does not change if we replace any of the arguments by the function value. The problem still holds if the operation "majority" is substituted with some "decision" operation. See this Miklos Schweitzer 2002 problem.

CLAIM 1. If $S$ has property $P_k$ then $S$ has property $P_{k-1}$ Proof. Let $a_1,a_2,...,a_{2k-1}$ be $2k-1$ elements of $S$. By shifting we can WLOG assume that $00...0$ is their major. Now notice that in each digit, there are totally at least $k$ zeros in that digit. Now WLOG assume $a_1=00...011...1$, with $m$ zeros and $n$ ones. Now we show by induction that there exists in $S$ a number $b_i$ with the property that its first $m+i$ digits are zero. Indeed if $b_i\in S$, then since $a_1,a_2,...,a_{2k-1}$ have major $00...0$, there exists some $1\leq j\leq 2k-1$ such that the $m+i+1$ digit of it is zero. Now, the numbers $$a_1,a_2,...,a_{2k-1},b_i,a_j$$has at least $k+1$ zeros in each of its $m+i+1$ digits. This completes the proof of CLAIM 1. $\blacksquare$ CLAIM 2. If $S$ has property $P_k$ then $S$ has property $P_{k+1}$ Proof. Let $a_1,a_2,...,a_{2k+3}$ be $2k+3$ elements of $S$. Again by shifting we can WLOG assume that $00..0$ is their major. Now WLOG assume $a_{2k+3}=11...100...0$, where its first $m$ digits are all ones, and the last $n$ digits are all zeros. Now if there is a digit such that the value of every a's is zero then we can remove that digit. Otherwise, for each $m+1\leq i\leq m+n$, there exists some $f(i)$ such that the $i^{th}$ digit of $a_{f(i)}$ is one. Therefore, the major of the numbers $\{a_{1},a_{2},...,a_{2k+2}\}\setminus\{a_{f(i)}\}$ has its first $m$ digits and the $i^{th}$ digit being zero. Denote this number by $b_i$. Now from CLAIM 1 $S$ has property $P_1$. Therefore, the major of $a_{2k+3},b_{m+1},b_{m+2}$ will have its first $m+2$ digits being zero. Let this number be $c_2$. Then for each $i$, define $c_{i+1}$ by the major of $a_{2k+3},c_{i}$ and $b_{m+i}$. It is easy to see that $c_{n}=00...0$, so we are done.

USA TST 2018 Problem 4 wrote: 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, \dots, x_{2k + 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, \dots,x_{2k + 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 $2k + 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$. Proposed by Joshua Brakensiek

I will use induction on $n$, with the cases of $n=1$ and $n=2$ being clear by manual computations. Now suppose $n-1$, $n\geq 3$ works, and let $S$ be a set of binary strings of length $n$ with property $P_i$ but not $P_j$. Consider a set $S'$ formed by deleting the bits in every element of $S$ in any fixed position. $S'$ clearly has property $P_i$, so by inductive hypothesis it must have property $P_j$. Since $S$ doesn't have property $P_j$, this means that if the majority of some $2i+1$ binary strings in $S$ is denoted by $x$, then for all $1 \leq r \leq n$ the binary string $x_r$ formed by flipping the $r$-th bit in $x$ and keeping everything else is in $S$, but not $x$. Now we can just consider the majority of any choice of $2i+1$ of strings in $\{x_1,x_2,\ldots,x_n\}$ such that no string appears in this choice more than $i$ times, which is always possible if $n \geq 3$. An example of this would be repeating $x_1,x_2,\ldots,x_n$ over and stopping (for example $n=4$ and $i=4$ would give $x_1,x_2,x_3,x_4,x_1,x_2,x_3,x_4,x_1$). It is easy to see that the majority of these strings is just $x$, so $x \in S$, which is a contradiction. Thus such a set $S$ cannot exist, as desired. $\blacksquare$

Fix $n$ and $S$. Define $f(x_1,\ldots,x_{2k+1})$ as the majority of $x_1,\ldots,x_{2k+1}$. Call a $k$ good if has property $S_k$. Suppose $t$ is given to be good. We want to prove every number is good. Note $3$ is good as $$f(x_1,x_2,x_3) = f ( \underbrace{ x_1, \ldots,x_1}_{t},\underbrace{x_2,\ldots,x_2}_t , x_3 ) \in S $$Now fix any $k$ and $x_1,\ldots,x_{2k+1}$. We will show $x = f(x_1,\ldots,x_{2k+1})$ is in $S$. Claim: For any $m$ bits of $x$ (with $2 \le m \le n$), $\exists ~ y \in S$ such that $x,y$ match on those $m$ bits. Proof: We will use induction on $m$. Base case $m=2$ is follows by PHP. Now fix $m+1$ bits, say $b_1,\ldots,b_{m+1}$. We know there are $y_1,y_2,y_3$ such that $y_1,y_2,y_3$ match $x$ on $\{b_1,b_{m+1}\},\{b_1,\ldots,b_m\},\{b_2,\ldots,b_{m+1} \}$, respectively. Then $f(y_1,y_2,y_3)$ matches $x$ on $b_1,\ldots,b_{m+1}$, proving our Claim (recall $3$ was good). $\square$ Taking $m=n$ in the above Claim solves the problem. $\blacksquare$

Induct on $n$, with the base cases of $n = 1,2$ being direct. Suppose its true until $n-1$ and we wish to prove it for $n$. Suppose $S$ has the property $P_k$ for some $k$ but there is an $m$ such that $S$ does not have $P_m$ and say the $2m+1$ strings which make this fail are $s_1, s_2, s_3, \cdots, s_{2m+1}$. Suppose we ignore the $z$th digit of each string, then by the induction hypothesis, since these satisfy $P_k$ and hence $P_m$, we have that there is some string in $S$ which agrees with the majority on all digits except the $z$th one. Doing this for all values of $z$, assume $p_i$ for $1 \le i \le n$ differs from the majority (say this is $z_m$) in the $i$th digit. Since $n \ge 3$, we can choose $p_1, p_2, p_3$ each $\left \lfloor \frac{2k+1}{3} \right \rfloor$ times (and maybe one or two extra of some if needed but whatever). Note that if we consider a single digit, two of $p_1, p_2, p_3$ agree with $z_m$ on this while the other doesn't. Since the number of times they've been chosen is like this, the majority of these $2k+1$ strings is $z_m$ which is not in $S$, contradicting the fact that $S$ had $P_k$, so we are done. $\blacksquare$

Actually, we can view this problem from hypercube! Induct on $n$. For every string $s$ that is not in $S$. If one of its neighbors on $Q_n$ is not in $S$ too, then looking from that direction on hypercube and using the induction hypothesis, $s$ can't express as the majority of strings in $S$. Otherwise, all of $s$ neighbots are in $S$ too, then it can be express as the majority of $2k+1$ strings in $S$, contradiction!

Simply construct inductively by permuting in a spaced out manner the maj of several $\text{maj}(\text{maj}(a, b, c, d, e), f, g)$ to show that $3$ implies $3+5$ implies $3+7$ implies $3+9$ and so on, and everything implies $3$ because $\text{maj}(a, a, a, b, b, c, c) = \text{maj}(a, b, c)$.

Surprised there's not many posts on this.

Define $M$ as the function from a multiset to its majority. Suppose that $P_k$ holds for $k > 1$ on set $S$. It remains to show that $P_{k+1}$ and $P_{k-1}$ hold as well. We first show $P_{k-1}$ holds. Suppose we have strings $x_1, x_2, \dots x_{2k-1}$. Then, we claim that the set of strings \begin{align*} &M(\{x_1, x_2, \dots x_{2k-1}, x_1, x_2\}) \\ &M(\{x_1, x_2, \dots x_{2k-1}, x_2, x_3\}) \\ &\dots \\ &M(\{x_1, x_2, \dots x_{2k-1}, x_{2k-1}, x_{1}\}) \\ \end{align*}has the same majority. Consider each of the $n$ bytes individually. WLOG assume there are more $0$s than $1$s. Then, if there is not exactly one $0$ than $1$ this follows easily. Else, the value of majority on that byte of $M(\{x_1, x_2, \dots x_{2k-1}, x_i, x_{i+1}\})$ can only be $1$ if both $x_i, x_{i+1}$ have a $1$. This can only occur at most $k-2$ times, so the majority remains the same. Furthermore, the majority increases in size. Thus, by repeating the process we can preserve the process while eventually convergine entirely on the same string, which then is in $S$ by the inductive hypothesis. $P_{k+1}$ is similar but instead it involves removing $x_i, x_{i+1}$ to create the new set of strings.

We will do induction on $n$ and also FTSOC $S$ has some property $P_k$ but not $P_m$. Our base cases of $n = 1, 2$ are both true. Then let $\mathcal{I}(s)$ be the operation that deletes the $i$th digit of a given string(s) and let $\mathcal{M}(x_1, \dots, x_{2t + 1})$ be the majority of said set. Since $S$ has property $P_k$, $\mathcal{M}(x_1, \dots, x_{2k+1}) \in S$ so it follows that $\mathcal{I}(\mathcal{M}(x_1, \dots, x_{2k+1})) \in \mathcal{I}(S)$ so by the induction hypothesis, we have $\mathcal{I}(\mathcal{M}(x_1, \dots, x_{2t+1})) \in \mathcal{I}(S)$. Then from this we find that $r = \mathcal{M}(x_1, \dots, x_{2m+1})$ is either $\in S$(contradiction) or it differs in the $i$th digit from $r$. However, we can cyclically vary $t$ to get a set of $2k + 1$ strings that differ in one(not necessarily pairwise distinct) spot. Given that $S$ has property $P_k$, we can take the majority of these strings to obtain $r \in S$, contradiction.

Since $n=1$ is trivial, we use induction on $n$ starting with base case $n=2$. Fixing a value of $i$ and given string $s$, define $s'$ as the string with bit $i$ removed. Assume FTSOC that $S$ does not satisfy property $P_j$ for some $j$. Suppose $m$ is the majority of $\{x_1,\ldots,x_{2j+1}\} \in S$. Since $S'$ is a set of strings with length $n-1$, it does satisfy $P_j$, so $m' \in S'$ but $m \not\in S$. Consequently, the string which differs $m$ only in bit $i$, which we denote as $m^*$, must be in $S$. We then vary $i$. Construct a set of $2k+1$ $m^*$s with $\left\lfloor \frac{2k+1}{n} \right\rfloor$ of each plus some left over. Its majority is then $m$, contradiction. $\blacksquare$

We apply induction on $n$. The base cases $n=1$ and $n=2$ are easy to check by hand. For the inductive step, FTSOC suppose that for some $n$, $S$ has the property $P_j$ but not the property $P_k$. This implies that there are $2k+1$ strings $x_1, x_2, \dots, x_{2k+1}$ such that their majority $y = \mathcal{M}(x_1, x_2, \dots, x_{2k+1}) \notin S$. Then, let the string that only differs from $y$ in the $i$th bit be $y_i$. Claim: For all $i = 1, 2, \dots, n$, $y_i \in S$. Proof: For an arbitrary $i$, let $s'$ be the string $s$ with the $i$th bit deleted. Define a new set \[T = \{s' \mid s \in S\}\] Since $S$ satisfies $P_j$, we know that $T$ also satisfies $P_j$. Thus, $T$ satisfies $P_k$ by the inductive hypothesis. Hence, we know that $y' = \mathcal{M}(x_1', x_2', \dots, x_{2k+1}') \in T$. This implies that there exists $s \in S$ such that $s' = y'$, and because $y \notin S$, we get $y_i \in S$. $\square$ We construct a set with $2j+1$ copies of the $y_i$ distributed roughly evenly among themselves; this set has majority $y$, a contradiction. $\blacksquare$