Let ℓ be a positive integer, and let m,n be positive integers with m≥n, such that A1,A2,⋯,Am,B1,⋯,Bm are m+n pairwise distinct subsets of the set {1,2,⋯,ℓ}. It is known that AiΔBj are pairwise distinct, 1≤i≤m,1≤j≤n, and runs over all nonempty subsets of {1,2,⋯,ℓ}. 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ΔB=(A∪B)∖(A∩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):=∏s∈Sxs. Define pA(x)=∑mi=1x(Ai) and pB(x)=∑ni=1x(Bi). The condition implies that for all v∈{±1}ℓ except for v=(1,1,…,1) we have that pA(v)pB(v)=−1. As both are integer polynomials, we know that pA(v)+pB(v)=0 for v∈{±1}ℓ except v=(1,1,…,1). Additionally, if we define w=(1,1,…,1), then pA(w)+pB(w)=|A|+|B|. Consider the polynomial q(x)=2ℓ(pA(x)+pB(x))−(|A|+|B|)ℓ∏i=1(1+xi).As this polynomial vanishes on {±1}ℓ and has low degree, it must be identically 0. Therefore, |A|+|B|=2ℓ as desired.