PUMaC 2020 · 个人决赛（A 组） · 第 3 题
PUMaC 2020 — Individual Finals (Division A) — Problem 3
题目详情
- Let n be a positive integer, and let F be a family of subsets of { 1 , 2 , · · · , 2 } such that for any non-empty A ∈ F there exists B ∈ F so that | A | = | B | + 1 and B ⊂ A . Suppose that F n n contains all (2 − 1)-element subsets of { 1 , 2 , · · · , 2 } . Determine the minimal possible value of |F| . 1
解析
- Let n be a positive integer, and let F be a family of subsets of { 1 , 2 , · · · , 2 } such that for any non-empty A ∈ F there exists B ∈ F so that | A | = | B | + 1 and B ⊂ A . Suppose that F 1 n n contains all (2 − 1)-element subsets of { 1 , 2 , · · · , 2 } . Determine the minimal possible value of |F| . n Solution : The answer is n · 2 + 1. First we will provide a construction for this answer, inductively. For n = 1, we can obviously construct F = { ∅ , { 1 } , { 2 }} , which has a cardinality 1 of 3 = 1 · 2 + 1. For larger n , we let F be the solution for n − 1 and every set also contains 1 n − 1 n − 1 n the numbers { 2 + 1 , 2 + 2 , · · · , 2 } and let F be the family symmetrical to F in the 2 1 n sense that if we will replace every element x with 2 + 1 − x . Now let F = F ∪ F ∪ 1 2 { } n − 1 n − 1 n − 1 n − 1 n − 1 n ∅ , { 1 } , { 1 , 2 } , · · · , { 1 , · · · , 2 − 1 } , { 2 + 1 } , { 2 + 1 , 2 + 2 } , · · · , { 2 + 1 , · · · , 2 − 1 } . By the inductive hypothesis, F obviously satisfies all the required conditions. Also n |F| = 2 · |F | + 2 − 1 = 1 n − 1 n n n n 2 · (( n − 1) · 2 + 1) + 2 − 1 = ( n − 1) · 2 + 2 + 1 = n · 2 + 1 . Now we will prove this number is minimal. Let F be a family that satisfies the problem m condition, which has the minimal possible number of sets. Obviously this family will contain the empty set. We shall construct a rooted tree T in the following way: the vertices will represent elements of F , and the parent of the vertex that corresponds to the set A ∈ F m m will be a vertex that corresponds to a B ∈ F so that | A | = | B | + 1 and B ⊂ A (there can m be multiple such B , but only a single, arbitrary one will be chosen as the parent). As every vertex except the one that corresponds to the empty set have a parent, T is rooted in that vertex. Now, since we have assumed the minimality of F , we can see that the only leaves m n in this tree are the vertices that correspond to the (2 − 1)-element sets. Let the height of a vertex be the vertex-wise distance from it to the nearest leaf, and deonte the height of the vertex corresponding to A as h . Let the power of a vertex denote the number of leaves in A its subtree, and denote the power of the vertex corresponding to A as x . Now observe the A following: Lemma 1: h ≥ x for any A ∈ F . A A m n n Notice that h = 2 − | A | , so there are exactly h numbers from { 1 , 2 , · · · , 2 } that are A A not in A . We notice that if if the vertex corresponding to C in the subtree of the vertex corresponding to A , then A ⊂ C . This means that the only leaves that can be in this subtree are the ones whose missing element of the corresponding set isn’t in A . From this we derive the desired inequality. Lemma 2: For any A ∈ F let’s denote the number of vertices in the subtree of its cor- m responding vertex with p . Then we have A p ≥ x log x + h − x + 1 . A A A A A 2 We will prove this lemma by induction on the value of x + h . The base case of x + h = 2 A A A A only holds when x = 1 and h = 1, meaning that A corresponds to a leaf, for which the A A lemma is obviously true. Now for the inductive step we lets denote the sons of set A by ∑ k B , B , · · · , B . Obviously, we have h = h − 1 and x = x . In this case we see 1 2 k B A B A k k i =1 k k k k k ∑ ∑ ∑ ∑ ∑ p = 1+ p ≥ x log x + h − x + k +1 ≥ x log x + k · h − x +1 . A B B B B B B B A A k k 2 k k k k 2 k i =1 i =1 i =1 i =1 i =1 2 Now since f ( x ) = x ln x is convex, by Jensen’s inequality we obtain ( ) ∑ ∑ k k ( ) x x x B B A i i i =1 i =1 p ≥ k · log + h − x +1+( k − 1) h ≥ x log +( k − 1) x + h − x +1 . A A A A A A A A 2 2 k k k k − 1 x 2 k − 1 k − 1 A Since x (log + ( k − 1)) = x log ( x ) ≥ x log ( x ), because 2 = (1 + 1) ≥ A A A A A 2 2 2 k k 1 + k − 1 = k by Bernoulli’s inequality (also provable by induction). With this we have proven the lemma. Now applying Lemma 2 to the root vertex we obtain that the amount of vertices is at least n n n n p ≥ 2 · n + 2 − 2 + 1 = n · 2 + 1 . ∅ Proposed by Pavle Martinovi´ c. 3