高中數學奧賽講義：集合.pdf

高中數學奧賽 高中數學奧賽 集合講義 強化訓練和參考答案集合講義 強化訓練和參考答案 內容綜述內容綜述 本講先介紹了以下一些重要的概念 集合 子集 兩集合相等 真子集 并集 交集 相對補集 然后介紹了著名的容斥原理 接著介紹了以下幾個定律 零律 分配律 排中 律 吸收律 補交轉換律 德 摩根律 然后通過 6 道例題分析了一部分集合題目的解題方法與技巧 同學們應在熟悉以上定 義 定理 定律的基礎上仔細分析例題材解法 爭取可以獨立解決訓練題 要點講解 要點講解 1 基本理論 1 基本理論 除了課內知識外 我們補充以下知識 相對補集 稱屬于 A 而不屬于 B 的全體元素 組成的集合為 B 對 A 的相對補集或差集 記作 A B 容斥原理 以表示集合 A 中元素的數目 我們有 其中為 n 個集合稱為 A 的階 n 階集合的全部子集數目為 A B C 為三個集合 就有下面的定律 1 分配律 2 零律 3 排中律 4 吸收律 5 補交轉換律 6 德 摩根律的相對形式 京師博雅園 w w w j s y b y x t c o m 例題分析 例題分析 例 1例 1 對集合 1 2 n 及其每一個非空了集 定義一個唯一確定的 交替和 如 下 按照遞減的次序重新排列該子集 然后交替地減或加后繼的數所得的結果 例如 集 合的 交替和 是 9 6 4 2 1 6 的 交替和 是 6 5 1 的交替和是 2 那么 對于 n 7 求所有子集的 交替和 的總和 分析分析 n 7 時 集合 7 6 5 4 3 2 1 的非空子集有個 雖然子集數目有 限 但是逐一計算各自的 交替和 再相加 計算量仍然巨大 但是 根據 交替和 的 定義 容易看到集合 1 2 3 4 5 6 7 與 1 2 3 4 5 6 的 交替和 是 7 可 以想到把一個不含 7 的集和 A 與的 交替和 之和應為 7 那么 我們也就很容易 解決這個問題了 解解 集合 1 2 3 4 5 6 7 的子集中 除去 7 外還有個非空子集合 把 這個非空子集兩兩結組后分別計算每一組中 交替和 之和 結組原則是設 這是把結合為一組 顯然 每組中 交替和 之 和應為 7 共有組 所以 所有 交替和 之和應該為 說明說明 我們在這道題的證明過程中用了這類題目最典型的解法 就是 對應 的方法 對應 的方法在解決相等的問題中應用得更多 例 2 例 2 設 A 1 2 2n 證明 A 的任意 n 1 階子集中 存在兩個數 一個可 被另一個整除 分析分析 對于 2n 個數中取 n 1 個數 我們應該有一個直覺就是把這 2n 個數分成 n 組 每組都必然滿足題目條件 那么由抽屜原則命題就解決了 證明 證明 前 2n 個自然數中 共有 n 個奇數 根據自然數的一種有用的表達形式 n 2k 1 2 L 為非負整數 考查 A 的下列 n 個子集 京師博雅園 w w w j s y b y x t c o m 容易看到 考慮 A 中任意 n 1 個元素 根據抽屜原則知 至少有兩個元素是上述 n 個集合中同一 個集合中的元素 這兩個數中 必有一個可被另一個整除 說明說明 把一個集合分成若干個兩兩不交的子集的并 也則分拆 這種分拆的方法在解 決集合的問題時為常用方法之一 例 3 例 3 某班對數學 物理 化學三科總評成績統(tǒng)計如下 優(yōu)秀的人數 數學 21 個 物理 19 個 化學 20 個 數學物理都優(yōu)秀 9 人 物理化學都優(yōu)秀 7 人 化學數學都優(yōu)秀 8 人 這個班有 5 人任何一科都不優(yōu)秀 那么確定這個班人數以 及僅有一科優(yōu)秀的三科分別有多少個人 分析 分析 自然地設 A 數學總評優(yōu)秀的人 B 物理總評優(yōu)秀的人 C 化學總評優(yōu)秀的人 則已知 A 21 B 19 C 20 這表明全班人數在 41 至 48 人之間 僅數學優(yōu)秀的人數是 可見僅數學優(yōu)秀的人數在 4 至 11 人之間 同理僅物理優(yōu)秀的人數在 3 至 10 人之間 同理僅化學優(yōu)秀的人數在 5 至 12 人之間 解解 略 說明說明 先將具體的實際生活中的問題數學化 然后根據數學理論來解決 這個問題不僅是競賽中常見情況 也是在未來學習中數學真正有用的地方 例 4 例 4 n 元集合具有多少個不同的不交子集對 京師博雅園 w w w j s y b y x t c o m 分析 分析 我們一般想法是對于一個子集 求出與它不交的子集個數 然后 就可以求出總的子集對來了 解解 如果子集對是有序的 即在子集對中可以區(qū)分第一個子集與第二個 子集 則第一個子集若是 k 個元素 第二個子集就由其余 n k 個元素組成 可能 的情況是種 而這時第一個集合的選取的可能情況應為種 那么 k 從 o 變到 n 總的情況可能就是 如果子集對是無序的 即兩個子集相同但次序不同的子集對不認為不同 則對有序子集對中有一對 是由兩個空集組成 而對其它個有序對 每一對中交換兩個子集的次序 得到的是同一個無序子集對 因此有個無序子集對 其中至少有一個 子集非空 于是無序子集對的總數為 分析二 分析二 我們可以從元素的角度來思考問題 對一個元素來說 它有三 種不同的選擇 在第一個集合中 在第二個集合中 或者不在兩個集合中 解法二解法二 在計算有序對的數目時 對每一個元素來說有三種可能 它或 在第一個子集 或在第二個子集 或不在其中任意一個子集 因此不同的不交有 序子集對的總數 以下同解法一 說明 說明 本題為 1973 年捷克的競賽題 對題目的不同分析使我們得到了 差異很大的兩個解法 解法一從題目要求想起 很容易想到 但解出最后解卻不 見得那么簡單 而解法二的想法是類似于集合分析的想法 很難想到 但想出后 比較容易求解 兩個解法對比一下正體現了數學思維的兩方面 一個是純代數想 法 以計算的方法替代對題目更深層次的研究 另一個則是控掘題目本身的內在 關系 找出最合適的解答 我們當然推薦第二種做法 例 5 例 5 1992 位科學家 每人至少與 1329 人合作過 那么 其中一定有 四位數學家兩兩合作過 分析 分析 在與一個人 A 合作的人中我們找到 B 再說明一定有人與 A 和 B 都合作過為 C 最后再說明有人與 A B C 都合作過為 D 那么 A B C D 就是 找的人了 證 明證 明 一 個 人A 不 妨 設B與 之 合 作 那 么 即 C 與 京師博雅園 w w w j s y b y x t c o m A 和 B 均合作過 分別表示與 A B 合作過的人的集合 同樣地 所以存在 則 A B C D 就是所求 證畢 說明說明 把一個普通的敘述性問題轉化為集合的語言描述的問題通常為解 題的關鍵之處 也是同學們需加強的 例 6 例 6 集合 X 由 n 個元素構成 對兩個子集 求得集合 的元素個數 證明 所有求得個數之和為 分析分析 我們先考慮一個簡單情況 n 2 這時有四個集合 記為 交集情況就是 那么對于 n 很大時 我們有的不只是 4 個集合卻可以以此形式分組 證明 證明 因為集合 X 總共有個不同子集 所以不同的有序子集對共有 將所有子集對分為個 4 元組 其 中表示子集的補集 X A 交換子集對的 4 元組中子集對的次序 得到的 是同一個四元組 事實上 由子集對得到的 4 元組與由得到的完 全相同 且 說明 說明 復雜的問題先考慮簡單的特殊的情況是一種最常用的方法 從中 找到共性后就很容易得到原題目有答案了 強化練習強化練習 1 一個集合含有 10 個互不相同的十進制兩位數 證明 這個集合必有兩個 無公共元素的子集合 這兩個子集元素和相等 2 是否存在兩個以非頁整數為元素的集合 A B 使得任一個非負整數都可 以被 A B 之中各取一數之和唯一表出 京師博雅園 w w w j s y b y x t c o m 3 對每個使得在 n 元集合中 可以取出 k 個子集 其中 任意兩個的交非合 4 能否把分成兩個積相等的不交集合 參考答案 參考答案 1 10 個元素的集合共有個非空子集 每一個這個集合的 非空子集中數字之和小于 由抽屜原則知 必有兩個子集 它們 有相同的元素和 設為滿足題目要求條件 2 十進制為第 1 位 為第 i 位 考慮如下的 A B A 為奇位為 o 的那些非負整數組成 B 為偶位為 o 的那些非負整數組成 不難驗證這樣的 A B 是符合題目要求的 3 在集合中取定一個元素 并只考慮含的子集 這類子集的個數為集合的子集的個數 即為 因此 另 一方面 設從集合 X 至少取出個子集 將集合 X