2023 AIME II 第 11 题

先试着解答 2023 AIME II 第 11 题,然后核对你的答案与精心整理的解答,解答来自 LIVE by Po-Shen Loh。你也可以参加完整限时模拟考试、查看全部 2023 AIME II 解答,或核对答案

所有题目均经美国数学协会(MAA)官方合法授权使用。

11.

求由 {1,2,3,4,5}\{1, 2, 3, 4, 5\}1616 个不同子集组成的集合族的个数,使得集合族中任意两个子集 XXYY 都满足 XYX \cap Y \neq \emptyset

Find the number of collections of 1616 distinct subsets of {1,2,3,4,5}\{1, 2, 3, 4, 5\} with the property that for any two subsets XX and YY in the collection, XY.X \cap Y \neq \emptyset.

答案:81
知识点:子集图论分类讨论
难度评级:3060
解答:

3232 个子集分成 1616 对互补子集 {X,Xc}\{X, X^{\mathsf{c}}\},任何集合族都不能同时包含一对中的两个集合 (它们不相交)。一个包含 1616 个两两相交子集的集合族因此必须从每对互补子集中恰好选一个;特别地,它包含 {1,2,3,4,5}\{1,2,3,4,5\},且不包含 \emptyset

如果选了某个单元素集 {x}\{x\},那么每个成员都必须与 {x}\{x\} 相交,也就是都包含 xx。每对互补子集中恰好有一个集合包含 xx,所以集合族必须正好是所有包含 xx1616 个子集;这给出 55 个集合族。否则没有单元素集被选中,因此全部五个 44 元子集都在集合族中。55 元集合的任意两个 33 元子集相交;一个 44 元子集只与它的补集不相交;一个被选中的 22 元子集和一个被选中的 33 元子集只有在互为补集时才不相交,而这种情况不可能同时被选中。所以剩下的唯一条件是,被选中的 22 元子集两两相交。

22 元子集看作 K5K_5 的边。两两相交的边集要么所有边都经过同一个公共顶点,要么是一个三角形。 这样的边族数为:空族(11 个)、三角形((53)=10\binom{5}{3} = 10 个)、以及一个星形中的非空边族, 5(241)10=655(2^4 - 1) - 10 = 65 个(减去被两个端点都计数到的 1010 条单边)。总共是 1+10+65=761 + 10 + 65 = 76 个集合族,因此总数为 5+76=815 + 76 = 81

The 3232 subsets split into 1616 complementary pairs {X,Xc},\{X, X^{\mathsf{c}}\}, and no collection can contain both members of a pair (they are disjoint). A collection of 1616 pairwise-intersecting subsets must therefore contain exactly one member of every pair; in particular it contains {1,2,3,4,5}\{1,2,3,4,5\} and not .\emptyset.

If some singleton {x}\{x\} is chosen, every member must meet {x},\{x\}, i.e. contain x.x. Exactly one set in each complementary pair contains x,x, so the collection must be exactly the 1616 subsets containing x:x: this gives 55 collections. Otherwise no singleton is chosen, so all five 44-element sets are in the collection. Any two 33-element subsets of a 55-element set intersect, a 44-element set is disjoint only from its complement, and a chosen 22-element set and a chosen 33-element set are disjoint only if they are complements, which cannot both be chosen. So the only remaining condition is that the chosen 22-element sets pairwise intersect.

Viewing 22-element sets as edges of K5,K_5, a pairwise-intersecting collection of edges either has all edges through one common vertex or is a triangle. The number of such edge families is: the empty family (11), triangles ((53)=10\binom{5}{3} = 10), and nonempty families within a star, 5(241)10=655(2^4 - 1) - 10 = 65 (subtracting the 1010 single edges counted at both endpoints). That is 1+10+65=761 + 10 + 65 = 76 collections, for a total of 5+76=81.5 + 76 = 81.

← 第 10 题#10
完整试卷

其他年份的第 11 题