# Problem Link:

# Difficulty:

easy-medium

# Pre-requisites:

Sperner’s Theorem

# Problem:

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**.

# Explanation:

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**.

If we consider the poset of all subsets of a set S, then the two elements **A** and **B** above are incomparable, therefore all the **N** sub-sets form

an antichain.

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 ≤ 10 ^{18}, 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

Sof sizeM, you want to pick a familyFof subsets ofS(i.e.F ⊂ 2) such that no set in the family is subset of another set in the family (i.e.^{S}x, y ∈ F ⇒ x ⊄ y). The maximum possible size of such a family of subsets isM 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 **a _{1}** subsets of size

**1**, a

_{2}subsets of size

**2**… a

_{M}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 **S _{1}** and

**S**) in

_{2}**F**, in which case, one(out of

**S**and

_{1}**S**) would be a subset of the other. Therefore, the number of permutations that can be generated by this procedure is

_{2}sum [i=1 to M] a

_{i}* i! (M-i)!

And the above number is no more than **M!**. For **k=⌊ M/2 ⌋** we already have

sum [i=1 to M] a_{i} * k! (M-k)! ≤ sum [i=1 to M] a_{i} * i! (M-i)! ≤ M!

⇒ sum [i=1 to M] a_{i} ≤ M!/ (k! * (M-k)!)

# Setter’s Solution:

Can be found here

# Tester’s Solution:

- Mahbub’s

```
(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester1/SPOONS.cpp)
2. Sergey's
```

(http://www.codechef.com/download/Solutions/2013/September/Tester/Tester2/SPOONS.cpp)

# Editorialist’s Solution:

Can be found here, and code used to generate values offline is here