Prove that $S$ has the same property $P_k$ of $majority$ for all positive integers $k$.

Question

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 $\textit{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$.

This is my progress..

We will prove it by induction .

For base case , take $n=2$, which can be verified by checking .

Suppose it's true for $n=l$ i.e for any $S \subseteq \{0, 1\}^l$ be a set of binary strings of length $l$ ,when satisfying the property $p_k$ that for some positive integer $k$ ,then $S$ will have property $p_k$ for all $k$.

Now we will show that for any $S \subseteq \{0, 1\}^{l+1}$ will be a set of binary strings of length $l+1$ , which satisfies the property that for some positive integer $k$ , $S$ has property $p_k$ , we will show it's true for all $k$

Now Consider a new set $S'$ which formed by deleting the last digit of the strings in $S$ and also consider another new set $S''$ which is formed by deleting the first digit of the strings in $S$

then note that both $S'$ and $S''$ are $ \subseteq \{0, 1\}^l$ will be a set of binary strings of length $l$.

Now since we were given that $S$ satisfies the property that for some positive integer $k$ ,so $S'$ and $S''$ will also satisfy for property $p_k$ for some $k$ and since $S'$ and $S''$ are $ \subseteq \{0, 1\}^l$ are a set of binary strings of length $l$ ,by induction hypothesis $S'$ and $S''$ satisfies property of $p_k$ for all $k$.

After this I couldn't have nice progress. Thanks in advance.

Answer 1

So well, the idea of removing bits from the sequences and forming sets like $S',S''$ sounds cool! However, what you showed that $S',S''$ follow $P_k$ for all $k$s can actually be generalized a bit. Like we would have the same result even if we remove $i$th bit from every binary sequence of $S$. So lets define $$S_i:=\{(a_1a_2\ldots a_{i-1}a_{i+1}\ldots a_{l+1})_2 | (a_1a_2\ldots a_{l+1})_2\in S\}$$ So basically $S'\equiv S_{l+1}$ and $S''\equiv S_{1}$. Now, its easy to see that from the induction hypothesis, $S_i$ satisfies $P_n$ for all $n$. Now, we need to show that $S$ satisfies $P_n$ for all $n$ as well. So FTSOC, assume that $S$ doesn't follow $P_m$ for some $m$. Thus, there exists a sequence of $2m+1$ binary numbers $B_i$ of length $l+1$ for which $$(B_1,B_2,B_3,\ldots, B_{2m+1})\in S^{2m+1}\text{ for which }\mathcal{M}(B_1,B_2,\ldots,B_{2m+1})\notin S$$ where $\mathcal M$ denotes the majority sequence. However, we know that $$\mathcal{M}(B_1(i),B_2(i),\ldots, B_{2m+1}(i))\in S_{i}$$where $B_j(i)$ is the corresponding binary number of $B_j$ of $S$ in $S_i$ (i.e. removing the number at $i$th bit in $B_j$). Let the $i$th bit in $B_j$ be $z_j(i)$ and let, $$A_i:=|\underbrace{\mathcal M(z_1(i),z_2(i),\ldots , z_{2m+1}(i))}_{\text{we call this number $\omega(i)$}}-1|$$Also, let, $$\mathcal{M}(B_1(i),B_2(i),\ldots, B_{2m+1}(i))=(b_1b_2\ldots b_{i-1}b_{i+1}\ldots b_{l+1})_2$$ and hence, $$(b_1b_2\ldots b_{i-1}A_ib_{i+1}\ldots b_{l+1})_2\in S,~\forall i\in\{1,2,\ldots, l+1\}$$ because $\underbrace{(b_1b_2\ldots b_{i-1}\omega(i)b_{i+1}\ldots b_{l+1})_2}_{\text{note that this is nothing but $\mathcal M(B_1, B_2,\ldots, B_{2m+1})$}}\notin S$. Now, by we know that $S$ follows $P_k$ for some $k$. Let $$X_i:=(b_1b_2\ldots b_{i-1}A_ib_{i+1}\ldots b_{l+1})_2$$ and thus, as $(X_1,X_2\ldots, X_{l+1})\in S^{l+1}$ and $l\geq 3$, applying the property $P_k$ on binary numbers $X_1,X_2,X_1,X_2,\ldots , X_1, X_2, X_3$ (here number of $X_1$'s and $X_2$'s used are $k$ each and one $X_3$), we get $$\mathcal{M}(X_1,X_2,X_1,X_2,\ldots , X_1, X_2, X_3)\in S$$however, its easy to note that this majority is nothing but $\mathcal M(B_1,B_2,\ldots ,B_{2m+1})$. Thus, $\mathcal M(B_1,B_2,\ldots ,B_{2m+1})\in S$ which is a contradiction. Thus, $S$ follows $P_k$ for all $k$. This completes the proof.$$\tag*{$\blacksquare$}$$