HMMT 二月 2006 · 冲刺赛 · 第 12 题

HMMT February 2006 — Guts Round — Problem 12

[7] For each positive integer n let S denote the set { 1 , 2 , 3 , . . . , n } . Compute the number n of triples of subsets A, B, C of S (not necessarily nonempty or proper) such that A is a 2006 subset of B and S − A is a subset of C . 2006 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . th IX HARVARD-MIT MATHEMATICS TOURNAMENT, 25 FEBRUARY 2006 — GUTS ROUND The problems in this batch all depend on each other. If you solve them correctly, you will produce a triple of mutually consistent answers. There is only one such triple. Your score will be determined by how many of your answers match that triple.

解析

For each positive integer n let S denote the set { 1 , 2 , 3 , . . . , n } . Compute the number n of triples of subsets A, B, C of S (not necessarily nonempty or proper) such that A 2006 is a subset of B and S − A is a subset of C . 2006 4012 Answer: 2 Solution: Let A , B , C be sets satisfying the said conditions. Note that 1 ∈ A o o o o implies that 1 ∈ B and 1 ∈ / S − A so that 1 may or may not be in C . Also, o 2006 o o 3 1 ∈ / A implies that 1 ∈ S − A ⊂ C while 1 may or may not be in B . Thus o 2006 o o o there are four possibilities for the distribution of 1, and since the same argument holds 2006 4012 independently for 2, 3, . . . , 2006, the answer is 4 or 2 .