Let $k$ be a positive integer and $S$ be a set of sets which have $k$ elements. For every $A,B \in S$ and $A\neq B$ we have $A \Delta B \in S$. Find all values of $k$ when $|S|=1023$ and $|S|=2023$. Note:$A \Delta B = (A \setminus B) \cup (B \setminus A)$
Problem
Source: 2023 Turkey TST D2 P4
Tags: set theory, combinatorics
18.06.2023 19:41
Solved with GeNuAlCo_pi and Jbmm2004 Clearly, $A\Delta B = (A\cup B) \setminus (A\cap B) $ which is $A\oplus B$. Notice that, if $C =A\oplus B$ then, $B =A\oplus C$ and $A =C\oplus B$. Now, $|A|=|B|=|A\oplus B|=k \implies |A\cap B| =\frac{k}{2}$. Therefore, $k$ is even for $|S| \geq 2$. Let, $A \in S$. Now, for any other element $X$ in $S$ there will be another unique set $X'\in S$ and $X' \neq X$ s.t. $A\oplus X = X'$, $A\oplus X'= X$ and $X\oplus X' = A$. Therefore we can pairup the elements of $S \setminus \{A\}$ in pairs of $(X, X')$. So, $|S|$ must be odd. Now let, $|S| = 2n+1$ and $k = 2m$. Let, $a \in A$. Now, pairs $(X,X')$ can be constructed s.t. $a \not\in X$ and $a\in X'$. Now let the set of pairs be $T=\{(X_1, X_1'), \dots, (X_n, X_n')\}$. $\text{Claim 1:}$ The set, $S' = \{X_i \mid (X_i, X_i') \in T\}$ is closed under $\oplus$. $\underline{\text{Proof:}}$ Here, $X_i \oplus X_j \in S$ and $a \not \in X_i \oplus X_j \implies X_i \oplus X_j \not\in \{A, X_1',X_2', \dots, X_n'\}$. So, $X_i \oplus X_j \in S'$ $\square$ $\text{Claim 2:}$ The set, $S'' = \{X_i\cap A \mid X_i \in S'\}$ is closed under $\oplus$. $\underline{\text{Proof:}}$ It's trivial that $(X_i \cap A)\oplus (X_j \cap A) = (X_i\oplus X_j)\cap A$ and from Claim 1 we get, $(X_i\oplus X_j)\in S' \implies (X_i\oplus X_j)\cap A\in S''$ $\square$ So first, if $k$ works for $|S| = 2n+1$ then, $k$ works for $|S| = n$. And, $|S|$ is always odd. Therefore, $|S|$ must be $2^d-1$ for some $d$. And, by Claim 2 if $k$ works for $|S| = 2n+1$ then, $\frac{k}{2}$ works for $|S| = n$ and $2|k$ for $|S| >1$ So, if $|S| = 2^d -1$ then, $2^{d-1}\mid k$. Therefore, we don’t have solution for $|S| = 2023$ and $2^{9}\mid k$ for $|S| = 1023 = 2^{10}-1$. And the construction is trivial. $\blacksquare$