Let $\ell$ be a positive integer, and let $m,n$ be positive integers with $m\geq n$, such that $A_1,A_2,\cdots,A_m,B_1,\cdots,B_m$ are $m+n$ pairwise distinct subsets of the set $\{1,2,\cdots,\ell\}$. It is known that $A_i\Delta B_j$ are pairwise distinct, $1\leq i\leq m, 1\leq j\leq n$, and runs over all nonempty subsets of $\{1,2,\cdots,\ell\}$. Find all possible values of $m,n$.
Problem
Source: China TST 2011 - Quiz 2 - D1 - P2
Tags: calculus, derivative, function, algebra, polynomial, modular arithmetic, combinatorics unsolved
24.05.2011 05:49
Please check this answer, I hope that it is good :
30.06.2011 09:03
What does the binary operater between two sets A_i, B_j capital delta (triangle) do?
06.02.2014 15:02
YingHong wrote: What does the binary operater between two sets A_i, B_j capital delta (triangle) do? $ A \Delta B = ( A \cup B ) \setminus ( A \cap B )$
12.06.2015 11:06
I was just trying this problem. Hopeless, gave up. Can anybody post some intuition to these solutions???
22.06.2018 06:03
For each subset $S$ correspond it to the polynomial $x(S) := \prod_{s \in S} x_s.$ Define $p_A(x) = \sum_{i = 1}^m x(A_i)$ and $p_B(x) = \sum_{i = 1}^n x(B_i).$ The condition implies that for all $v \in \{\pm 1\}^{\ell}$ except for $v = (1, 1, \dots, 1)$ we have that $p_A(v) p_B(v) = -1.$ As both are integer polynomials, we know that $p_A(v) + p_B(v) = 0$ for $v \in \{\pm 1\}^{\ell}$ except $v = (1, 1, \dots, 1).$ Additionally, if we define $w = (1, 1, \dots, 1)$, then $p_A(w) + p_B(w) = |A| + |B|.$ Consider the polynomial \[ q(x) = 2^\ell(p_A(x) + p_B(x)) - (|A| + |B|) \prod_{i = 1}^\ell (1+x_i). \]As this polynomial vanishes on $\{\pm 1\}^\ell$ and has low degree, it must be identically $0$. Therefore, $|A| + |B| = 2^\ell$ as desired.