Let $S = \lbrace A = (a_1, \ldots, a_s) \mid a_i = 0$ or $1, i = 1, \ldots, 8 \rbrace$. For any 2 elements of $S$, $A = \lbrace a_1, \ldots, a_8\rbrace$ and $B = \lbrace b_1, \ldots, b_8\rbrace$. Let $d(A,B) = \sum_{i=1}{8} |a_i - b_i|$. Call $d(A,B)$ the distance between $A$ and $B$. At most how many elements can $S$ have such that the distance between any 2 sets is at least 5?
Problem
Source: China TST 1995, problem 4
Tags: combinatorics unsolved, combinatorics
Nukular
12.08.2008 16:44
Since this has stayed empty for a while... time to pull out the bashing hammer. WLOG $ (0,0,\dots,0) \in S$. Let $ \sigma(a_1,\dots,a_8) = a_1 + \dots + a_8$. Then for every other element $ T \in S$, $ \sigma(T) \ge 5$. Claim 1: There is at most one element T of $ S$ with $ \sigma(T) \ge 6$. Proof: Let $ Q = (1,1,1,\dots,1)$, and suppose $ T,T'$ satisfy $ \sigma(T), \sigma(T') \ge 6$. Then $ d(T,T') \le d(T,Q) + d(Q,T') \le 4$, a contradiction. Claim 2: Suppose $ R,R' \in S$ satisfy $ \sigma(R) = \sigma(R') = 5$. Then the sets $ \alpha(R) = \{k | R_k = 0\}$ and $ \alpha(R')$ are disjoint. Proof: Suppose otherwise, with WLOG $ R_8 = R'_8 = 0$. Then if $ X = (1,1,1,1,1,1,1,0),$ we have $ d(R,R') \le d(R,X) + d(X,R') = 4$, a contradiction. Corollary: There are at most two elements of $ S$ with $ \sigma = 5$. Therefore, $ |S| \le 4$. Lastly, we can choose $ S = \{(0,0,0,0,0,0,0,0), (1,1,1,1,1,1,0,0), (0,0,0,1,1,1,1,1), (1,1,1,0,0,0,1,1) \}$.
FISHMJ25
07.08.2018 23:07
There is nice solution with double counting.Let elements of $S$ be $A_1,\dots,A_x$ and $A_i=(a_{i1}\dots,a_{i8})$. We count in two ways $T$,number of unordered pairs $(a_{ij},a_{tj})$ where $a_{ij}$ and $a_{tj}$ are different ; $T\ge5\binom{x}{2}$ because there are at least $5$ different pairs of numbers in any two $A_i$ and $A_j$.On the other hand $8[x^2/4]\ge T $ because if we observe all $a_{ij}$ for fixed $j$ we see that there are at most $[x^2/4]$ different pairs ( and multiply by $8$ for all $j$-s).Now we have $8[x^2/4]\ge T \ge5\binom{x}{2}$ from which we get $x\le4$. Example is : $ S = \{(1,1,1,1,1,1,1,1), (1,1,1,0,0,0,0,0), (0,0,0,1,1,0,0,0), (0,0,0,0,0,1,1,1) \}$
MadCowChicken3
08.08.2018 03:27
Nice. Also, I was hoping there is a geometric solution. If you replace the $0$'s in the ordered sets with $-1$'s then the problem is equivalent to finding the number of ordered sets (a.k.a vectors) where the dot product between any two of them is less than $0$. Which is equivalent to the vector angle between any two of them is greater than 90 degrees. I don't know if there is a good way to finish this off geometrically though.