There are eight different symbols designed on $n\geq 2$ different T-shirts. Each shirt contains at least one symbol, and no two shirts contain all the same symbols. Suppose that for any $k$ symbols $(1\leq k\leq 7)$ the number of shirts containing at least one of the $k$ symbols is even. Determine the value of $n$.
Problem
Source: 8-th Taiwanese Mathematical Olympiad 1999
Tags: induction, combinatorics unsolved, combinatorics
20.01.2014 01:55
Let us consider a set $S$ of symbols with $|S| = n> 1$, and a set $\mathcal{T}$ of T-shirts with $|\mathcal{T}|=t>0$ having the stated property, which clearly establishes an injection $i\colon \mathcal{T} \to \mathcal{P}(S)\setminus \{\emptyset\}$ given by $i(T) = \{s\in S \mid s\in T\}$. We will also define $j\colon S \to \mathcal{P}(\mathcal{T})$ by $j(s) = \{T \in \mathcal{T} \mid s\in T\}$ (as a byproduct, we will prove that $j(s) \neq \emptyset$ for any $s\in S$, and that $j$ is an injection also, but for the moment we don't need all that). We are given that for any set $\emptyset \neq K\subsetneq S$ we have $\displaystyle \left | \bigcup_{s\in K} j(s) \right |$ even. In particular $|j(s)|$ is even for any $s\in S$, and so, by induction on $|K|$, $\displaystyle \left | \bigcap_{s\in K}j(s) \right |$ is shown to be even for all $1\leq |K| \leq n-1$, since by PIE \[\left | \bigcup_{s\in K} j(s) \right | = \sum_{\ell=1}^{|K|-1} \left ( (-1)^{\ell-1} \sum_{\stackrel {|L| = \ell} {\stackrel {L\subseteq K} {}}} \left | \bigcap_{s\in L} j(s) \right |\right ) - (-1)^{|K|} \left | \bigcap_{s\in K} j(s) \right |.\] Let us now consider a $M\in \mathcal{T}$ of maximal $|i(M)|>0$. If it were $|i(M)|< n$, then since $\displaystyle M \in \bigcap_{s\in i(M)}j(s)$, with $\displaystyle \left |\bigcap_{s\in i(M)}j(s)\right |$ even, it follows $\displaystyle \bigcap_{s\in i(M)}j(s)$ contains another $T\neq M$, with $i(M) \subsetneq i(T)$, thus $|i(T)| > |i(M)|$, absurd, therefore $|i(M)| = n$, i.e. $i(M) = S$, or equivalently $i^{-1}(S) \in \mathcal{T}$. Assume now that for some $1\leq k < n$ we have $i^{-1}(S') \in \mathcal{T}$ for all $S'\subseteq S$ with $|S'|>k$; we just proved $k=n-1$ is such. Take any set $K\subset S$ with $|K|=k$, and notice that $\displaystyle \bigcap_{s\in K}j(s)$ contains the $2^{n-k} - 1$ T-shirts $i^{-1}(S')$ for all $K\subsetneq S'\subseteq S$. For parity reasons, it must contain yet at least another element, which can only be $i^{-1}(K)$. Therefore $i^{-1}(K) \in \mathcal{T}$ for all such $K\subset S$ with $|K|=k$, and by induction we proved our assumption for all $1\leq k < n$. The end result of all this is that $i$ is also surjective, thus $\boxed{t = |\mathcal{T}| = |\mathcal{P}(S)\setminus \{\emptyset\}| = 2^n - 1}$. Conversely, this unique $\mathcal{T} = \{i^{-1}(K) \mid \emptyset\neq K \subseteq S\}$, the set of all possible (non-empty) T-shirts, having $2^n-1$ elements, has the stated property, since for any set $\emptyset \neq K\subsetneq S$ of symbols with $1\leq |K| = k \leq n-1$, the number of T-shirts containing at least one symbol from $K$ is $(2^n-1) - (2^{n-k} - 1) = 2^{n-k}(2^k-1)$, an even number.