Given an integer N, find the size of smallest set S such that there exists an antichain of size N among the subsets of S.
The relation between groups of cities A and B served by two spoons can be equivalently stated as: A-B is not empty and B-A is not empty, which is same as A ⊄ B and B ⊄ A.
People could obtain the solution by
- guess work, or,
- evaluating the first few few terms and then using oies to get the required sequence, or,
- reinventing proof of Sperner’s Theorem.
The statement and proof of Sperner’s Theorem is given below in very simple language.
Given the Sperner’s Theorem, we would still need to find smallest M such that M choose ⌊ M/2 ⌋ is at least N. For N ≤ 1018, M ≤ 64, and therefore, one could compute these values offline(or online in his code itself), and do a binary search to lookup the best value. Time complexity O(T).
Proof of Sperner’s Theorem
Given a set S of size M, you want to pick a family F of subsets of S (i.e. F ⊂ 2S) such that no set in the family is subset of another set in the family (i.e. x, y ∈ F ⇒ x ⊄ y). The maximum possible size of such a family of subsets is M choose ⌊ M/2 ⌋
It is clear that if we choose all subsets in the family F to be of same size, k, then the family would satisfy the above property, and its size will be M choose k. This is maximum when k=⌊ M/2 ⌋. Therefore, the bound suggested above can be attained by picking all sbsets of size ⌊ M/2 ⌋. Now it remains to show that this is also the best possible bound.
Lets say we have got a family F of subsets satisfying above property, and it has a1 subsets of size 1, a2 subsets of size 2 … aM subsets of size M.
Then we can generate a permutation of S by selecting a set S’ in F and concatenating a permutation of the elements of S’ with a permutation of the non-members. If |S’| = i, it will be associated in this way with i!(n − i)! permutations. Each permutation can only be associated with at most one set in F. This is because otherwise two different prefixes of a single permutation would be associated with different subsets(say S1 and S2) in F, in which case, one(out of S1 and S2) would be a subset of the other. Therefore, the number of permutations that can be generated by this procedure is
sum [i=1 to M] ai * i! (M-i)!
And the above number is no more than M!. For k=⌊ M/2 ⌋ we already have
sum [i=1 to M] ai * k! (M-k)! ≤ sum [i=1 to M] ai * i! (M-i)! ≤ M!
⇒ sum [i=1 to M] ai ≤ M!/ (k! * (M-k)!)
Can be found here
(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester1/SPOONS.cpp) 2. Sergey's