組合數(shù)學(xué)PPT課件

《組合數(shù)學(xué)PPT課件》由會(huì)員分享，可在線閱讀，更多相關(guān)《組合數(shù)學(xué)PPT課件（67頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、2021/6/16 1組 合 數(shù) 學(xué)2021/6/16 21、 對(duì) 應(yīng) 法2021/6/16 3定 理 對(duì) 于 兩 個(gè) 有 限 集 合 M 與 ， 若 存 在 從 M 到 N 的 單 射 ， 則 | NM ； 若存 在 從 M 到 N 的 滿 射 ， 則 | NM ； 若 存 在 從 M 到 N 的 雙 射 ， 則 | NM 。 當(dāng) 計(jì) 算 有 限 集 合 M 中 的 元 素 個(gè) 數(shù) 比 較 困 難 時(shí) ， 我 們 設(shè) 法 建 立 M 到 另 一 個(gè) 有限 集 合 N 上 的 雙 射 ， 如 果 N 中 的 元 素 個(gè) 數(shù) | N 容 易 算 出 ， 于 是 由 | NM ， 得出 M 中 的

2、 元 素 個(gè) 數(shù) ， 這 種 計(jì) 數(shù) 方 法 稱 為 映 射 方 法 ， 或 者 稱 為 配 對(duì) 法 。 2021/6/16 4例 1-1. 設(shè) 凸 n邊 形 的 任 意 3條 對(duì) 角 線 不 相 交 于形 內(nèi) 一 點(diǎn) ， 求 它 的 對(duì) 角 線 在 形 內(nèi) 的 交 點(diǎn) 總 數(shù) 。 2021/6/16 5例 1-1 設(shè) 凸 n邊 形 的 任 意 3 條 對(duì) 角 線 不 相 交 于 形 內(nèi) 一點(diǎn) ， 求 它 的 對(duì) 角 線 在 形 內(nèi) 的 交 點(diǎn) 總 數(shù) 。 解 : 依 題 意 ， 一 個(gè) 交 點(diǎn) P由 兩 條 對(duì) 角 線 l與 m 相 交 而得 ， 反 之 ， 兩 條 相 交 的 對(duì) 角 線

3、l與 m， 確 定 一 個(gè) 交 點(diǎn) P， 而P與 （ l， m） 可 建 立 一 一 對(duì) 應(yīng) 。 又 因 兩 條 相 交 的 對(duì) 角 線 l與 m 分 別 由 凸 n邊 形 中 兩 對(duì)頂 點(diǎn) A， B和 C， D連 接 而 成 ， 故 （ l， m） 又 可 與 4頂 點(diǎn)組 （ A， B， C， D） 建 立 一 一 對(duì) 應(yīng) ， 即 有 P （ l， m） （ A， B， C， D） 因 此 ， 形 內(nèi) 對(duì) 角 線 的 交 點(diǎn) 總 數(shù) =凸 n邊 形 的 4 頂 點(diǎn) 組 的組 數(shù) = 4nC 。 2021/6/16 6 例 1-2 給 定 一 個(gè) 正 整 數(shù) n。 有 多 少 個(gè) 滿 足 條

4、件 ：ndcba 0 的 四 元 有 序 整 數(shù) 組 ),( dcba 。 2021/6/16 7例 1-2 給 定 一 個(gè) 正 整 數(shù) n。 有 多 少 個(gè) 滿 足 條 件 ： ndcba 0 的 四 元 有 序 整 數(shù) 組 ),( dcba 。 解 ： 作 映 射 )4,3,2,1(),(: dcbadcbaf 于 是 f 是 從 集 合 0|),( ndcbadcbaA 到 集 合41|),( / ndcbadcbaB的 一 個(gè) 映 射 ， 容 易 驗(yàn) 證 這 個(gè)映 射 是 一 一 對(duì) 應(yīng) ， 所 以 | BA 。 由 于 | B 就 是 集 合 4,2,1 n 的 四 元 子 集 的

5、個(gè) 數(shù) ， 即 Cn4 4 ， 從 而CnA 4 4| 。 2021/6/16 8例 1-3 試 證 ： 從 49,2,1 中 取 出 6個(gè) 不 同 的 數(shù) ， 使 得 其 中 至 少 有 兩 個(gè) 相 鄰 ， 共 有CC 644649 種 取 法 。 證 明 ： 首 先 ， 集 合 49,2,1 M 的 所 有 不 同 6元 子 集 的 個(gè) 數(shù) 為 C649， 但 是 ， 其 中 6個(gè) 數(shù) 互 不 相 鄰 的 子 集 5,4,3,2,1,1, 1621 iaaaaa ii （ 1） 記 滿 足 （ 1） 式 的 所 有 6元 子 集 的 集 合 為 A， 并 令 ),(),(: 621621

6、bbbaaaf （ 2） 其 中 .6,5,4,3,2,1,1 iiab ii (3) 易 知 621 , bbb 互 不 相 同 ， 且 441 621 bbb 。 容 易 驗(yàn) 證 ， 由 式 （ 2） 和 （ 3） 定義 的 映 射 是 由 集 合 A到 集 合 44,2,1 S 的 所 有 不 同 6 元 子 集 的 集 合 B 的 一 個(gè) 一 一 對(duì)應(yīng) ， 從 而 有 CBA 644| 。 易 知 命 題 成 立 。 2021/6/16 92. 構(gòu) 造 法 2021/6/16 10例 2-1 (自 編 題 ) 設(shè) 20,2,1 M ， A是 M 的 子 集 且 滿 足 條 件 :當(dāng) A

7、x 時(shí) ， Ax2 且Ax3 。 則 A中 元 素 的 個(gè) 數(shù) 最 多 是 多 少 ？ 解 ： 用 )(An 表 示 集 合 A所 含 元 素 的 個(gè) 數(shù) 。 由 題 設(shè) 容 易 用 枚 舉 法 驗(yàn) 證 ， 16,8,4,21 M 中 至 少 有 兩 個(gè) 元 素 不 屬 于 A， 20,15,10,52 M 中至 少 有 兩 個(gè) 元 素 不 屬 于 A， 14,73 M 中 至 少 有 一 個(gè) 元 素 不 屬 于 A。 現(xiàn) 考 慮 18,12,9,6,34 M ，容 易 驗(yàn) 證 4M 中 至 少 有 兩 個(gè) 元 素 不 屬 于 A， 分 情 況 討 論 ： （ 1） 4M 中 至 少 有 三

8、個(gè) 元 素 不 屬 于 A， 則 12312220)( An 。 （ 2） 4M 中 有 兩 個(gè) 元 素 不 屬 于 A， 由 題 設(shè) ， A12,9,6 ， A18,9,6 ， A18,12,6 ，A18,12,9 ， 則 必 有 A3 ， 且 A18,12,3 ， 從 而 A1 ， 則 121212220)( An 。 綜 合 （ 1） 和 （ 2） ， 所 以 至 少 有 8個(gè) 數(shù) 不 屬 于 A。 即 12)( An 。 另 一 方 面 ， 可 取 20,19,17,16,13,11,9,7,6,5,4,1A ， A滿 足 題 設(shè) 條 件 ， 此 時(shí) 12)( An 。 所 以 ， )

9、(An 的 最 大 值 就 是 12。 2021/6/16 11例 2-2（ 2010 清 華 ） 請(qǐng) 設(shè) 計(jì) 一 個(gè) 方 案 ， 對(duì) 1 維實(shí) 數(shù) 軸 上 的 每 一 個(gè) 點(diǎn) 進(jìn) 行 染 色 ， 使 得 距 離 為 1， 2或5的 兩 個(gè) 點(diǎn) 都 不 同 色 ， 要 求 所 使 用 的 顏 色 數(shù) 目 盡 可能 少 。 2021/6/16 12例 2-2（ 2010 清 華 ） 請(qǐng) 設(shè) 計(jì) 一 個(gè) 方 案 ， 對(duì) 1維 實(shí) 數(shù) 軸 上 的 每 一 個(gè) 點(diǎn) 進(jìn) 行 染 色 ，使 得 距 離 為 1， 2或 5的 兩 個(gè) 點(diǎn) 都 不 同 色 ， 要 求 所 使 用 的 顏 色 數(shù) 目 盡 可 能

10、 少 。 解 ： 一 種 顏 色 顯 然 不 行 ， 故 最 少 要 兩 種 顏 色 。 下 證 染 兩 種 顏 色 可 行 。 設(shè) ,|52 ZcbacbaM ， 對(duì) M 中 的 元 素 染 色 ， 當(dāng) cba 為 奇 數(shù) 時(shí)染 紅 色 ， 當(dāng) cba 為 偶 數(shù) 時(shí) 染 藍(lán) 色 。 任 取 Mx ， 設(shè),|52 ZcbacbaxX ， 將 x染 成 藍(lán) 色 ， 對(duì) 于 X 中 的 元 素 ， 當(dāng) cba 為 奇 數(shù) 時(shí) 染 紅 色 ， 當(dāng) cba 為 偶 數(shù) 時(shí) 染 藍(lán) 色 。 任 取 XMy ， 設(shè),|52 ZcbacbayY ， 將 y染 成 藍(lán) 色 ， 對(duì) 于 Y 中 的 元 素 ，

11、 當(dāng) cba 為奇 數(shù) 時(shí) 染 紅 色 ， 當(dāng) cba 為 偶 數(shù) 時(shí) 染 藍(lán) 色 。 重 復(fù) 上 述 過(guò) 程 知 ， 只 用 兩 種 顏 色 就 可 以 講 每 個(gè) 點(diǎn) 進(jìn) 行 染 色 ， 且 距 離 為 1， 2或 5的 兩 個(gè) 點(diǎn) 都 不 同 色 。 2021/6/16 13上 述 解 答 解 釋 如 下 ： 任 取 Mx ， 設(shè) ,|52 ZcbacbaxX ， 將 x染 藍(lán) 色 ， 當(dāng) cba 為 奇 數(shù) 時(shí) 染 紅 色 ， 當(dāng) cba 為 偶 數(shù) 時(shí) 染 藍(lán) 色 。 任 取 XMy ， 設(shè) ,|52 ZcbacbayY ， 將 y 染 藍(lán) 色 ， 當(dāng) cba 為 奇 數(shù) 時(shí) 染 紅

12、 色 ， 當(dāng)cba 為 偶 數(shù) 時(shí) 染 藍(lán) 色 。 然 后 又 是 任 取 YXMp ， 設(shè) ,|52 ZcbacbapP ， 將 p染 藍(lán) 色 ， 當(dāng) cba 為 奇 數(shù) 時(shí)染 紅 色 ， 當(dāng) cba 為 偶 數(shù) 時(shí) 染 藍(lán) 色 。 這 樣 無(wú) 限 重 復(fù) 下 去 ， 可 以 驗(yàn) 證 這 種 方 案 中 ， 距 離 為 1， 2， 5的 任 意 兩 點(diǎn) 都 不 同 色 。 例 如 ， 若 M 中 兩 點(diǎn) cba 52 與 111 52 cba 同 色 ， 且 cba 52 比 111 52 cba 大 2。 所 以 ， cba 52 （ 111 52 cba ） = 2 所 以 ， 0)(5

13、)1(2)( 111 ccbbaa 容 易 知 道 ， 1aa ， 11 bb , 1cc ,則 有 cba = 1)( 111 cba 即 cba 與 111 cba 相 差 1， 它 們 奇 偶 性 不 同 ， 這 與 （ cba 為 奇 數(shù) 時(shí) 染 紅 色 ， 當(dāng) cba 為 偶 數(shù)時(shí) 染 藍(lán) 色 ） 相 矛 盾 。 其 余 類 似 得 矛 盾 。 2021/6/16 143、 遞 推 法2021/6/16 15例 3-1 將 圓 分 成 )2( nn 個(gè) 扇 形 1S ， 2S ， ， nS 。 現(xiàn) 用 m種 顏 色 給這 些 扇 形 染 色 ， 每 個(gè) 扇 形 恰 染 一 種 顏 色

14、 且 要 求 相 鄰 的 扇 形 的 顏 色 互 不 相 同 。問 有 多 少 種 不 同 的 染 色 方 法 ？ 2021/6/16 16解 ： 設(shè) 染 色 方 法 數(shù) 為 na 。 （ 1） 求 初 始 值 。 2n 時(shí) ， 給 1S 染 色 有 m種 方 法 ， 繼 而 給 2S 染 色 有 )1( m 種 方 法 ， 所 以 ， )1(2 mma 。 （ 2） 求 遞 推 關(guān) 系 。 因 1S 有 m種 染 色 方 法 ， 2S 有 )1( m 種 染 色 方 法 ， 3S 有 )1( m 種 染 色 方 法 ， ， 1nS有 )1( m 種 染 色 方 法 ， nS 仍 有 )1(

15、m 種 染 色 方 法 （ 不 保 證 nS 與 1S 不 同 色 ） 。 這 樣 共 有 1)1( nmm 種 染 色 方 法 ，但 這 1)1( nmm 種 染 色 方 法 可 分 為 兩 類 ： 一 類 是 nS 與 1S 不 同 色 ， 此 時(shí) 的 染 色 方 法 有 na 種 ； 另 一 類 是 nS 與 1S 同 色 ， 則 將 nS 與 1S 合 并 為 一 個(gè) 扇 形 ，并 注 意 到 此 時(shí) 1nS 與 1S 不 同 色 ， 故 這 時(shí) 的 的 染 色 方 法 有 1na 種 ， 由 加 法 原 理 得 na + 1na = 1)1( nmm （ n 2） （ 3） 求 na

16、 。 令 nb = nnma )1( ， 由 nb + 11m 1nb = 1mm ， 有 nb 1= 11m （ 1nb ） ， 即 nb 1 為 首 項(xiàng)為 2b 1 11m ， 公 比 為 11m 的 等 比 數(shù) 列 的 第 1n 項(xiàng) 。 nb 1 （ 11m ） （ 11m ） 2n 1)1( 1)1( nn m ， 即 nnma )1( 1)1( 1)1( nn m ， 即 na )1()1()1( mm nn 2021/6/16 17例 3-2 （ 2001 聯(lián) 賽 ） 在 1 個(gè) 正 六 邊 形 的 6 個(gè) 區(qū) 域 栽種 觀 賞 植 物 ， 要 求 同 1區(qū) 域 中 種 同 一 種

17、 植 物 ， 相 鄰 的 2區(qū) 域中 種 不 同 的 植 物 。 現(xiàn) 有 4種 不 同 的 植 物 可 供 選 擇 ， 問 有 多 少種 栽 種 方 案 。 解 ： 在 上 述 命 題 中 ， 取 n=6， m=4， 即 得 6a )14()1()14( 66 =732種 。 2021/6/16 18例 3-3（ 2001 年 CMO 題 ） 將 周 長(zhǎng) 為 24 的 圓 周 等 分 為 24 段 ，從 24個(gè) 分 點(diǎn) 中 選 取 8個(gè) 點(diǎn) ， 使 得 其 中 任 何 兩 點(diǎn) 所 夾 的 弧 長(zhǎng) 都 不 等 于 3和 8。 問 滿 足 要 求 的 8點(diǎn) 組 的 不 同 取 法 有 多 少 種

18、？ 解 ： 設(shè) 24個(gè) 分 點(diǎn) 依 次 為 1， 2， ， 24， 將 24個(gè) 數(shù) 列 成 下 表 ： 1 4 7 10 13 16 19 22 9 12 15 18 21 24 3 6 17 20 23 2 5 8 11 14 表 中 每 行 相 鄰 兩 數(shù) 所 代 表 的 點(diǎn) 所 夾 弧 長(zhǎng) 為 3， 每 列 相 鄰 兩 數(shù) 所 代表 的 點(diǎn) 所 夾 弧 長(zhǎng) 為 8， 故 每 列 至 多 取 一 個(gè) 數(shù) ， 8列 至 多 取 8個(gè) 數(shù) ， 但 一共 要 取 8個(gè) 數(shù) ， 故 每 列 恰 取 一 個(gè) 數(shù) 且 相 鄰 兩 列 所 取 的 數(shù) 不 同 行 。 若 將 每 列 看 作 一 個(gè) 扇

19、形 ， 每 列 中 第 一 、 二 、 三 行 看 作 三 種 顏 色 ，則 由 上 面 例 題 知 ， 8a )13()1()13( 88 =258種 。 2021/6/16 194、 算 兩 次2021/6/16 20例 4-1（ 2006 復(fù) 旦 ） 求 證 ： CC nnnk kn 220 )( 2021/6/16 21例 4-1（ 2006 復(fù) 旦 ） 求 證 ： CC nnnk kn 220 )( 證 明 ： 法 一 （ 母 函 數(shù) 法 ） 因 為 nk kknn xx C0)1( ， 所 以 )()1( 002 knk knnk kknn xxx CC 一 方 面 ， 這 個(gè) 乘

20、 積 中 nx 的 系 數(shù) 為 nk knnknCC0 ， 又 因 為 CC knnkn ， 所 以 200 )( nk knnk knnkn CCC 另 一 方 面 ， 從 展 開 式 nk kknn xx C2 0 22)1( 知 道 nx 的 系 數(shù) 為 Cnn2 ， 因 而 得 CC nnnk kn 220 )( 2021/6/16 22例 4-1（ 2006 復(fù) 旦 ） 求 證 ： CC nnnk kn 220 )( 法 二 （ 構(gòu) 造 模 型 ） 某 班 共 有 n2 名 學(xué) 生 ， 現(xiàn) 從 中 選 出 n個(gè) 學(xué) 生 參 加 某 項(xiàng) 活 動(dòng) ， 顯 然 這 樣的 選 法 共 有 C

21、nn2 種 ； 另 一 方 面 ， 將 這 n2 名 學(xué) 生 分 成 A、 B兩 組 ， 每 組 n個(gè) 學(xué) 生 ， 若 從 A 組 中 選 出 0 個(gè) 學(xué) 生 ， 從 B 組 中 選 出 n 個(gè) 學(xué) 生 ， 有200 )(CCC nnnn 種 選 法 ； 從 A組 中 選 出 1個(gè) 學(xué) 生 ， 從 B組 中 選 出 1n 個(gè)學(xué) 生 ， 有 2111 )(CCC nnnn 種 選 法 ； ； 從 A組 中 選 出 n個(gè) 學(xué) 生 ， 從 B組 中 選 出 0 個(gè) 學(xué) 生 ， 有 20 )(CCC nnnnn 種 選 法 。 由 加 法 原 理 ，CC nnnk kn 220 )( 。 2021/6

22、/16 23（ 2008 南 開 ） 求 CC ji j i 50500 500 50 除 以 31的 余 數(shù) 。 解 ： 因 為 505050150050 2)( CCC )( 5050150050 CCC 1005050150050 2)( CCC ， 展 開 即 1002500 5050500 50 2)(2 k kjji i CCC 引 由 例 4-1 可 知 ， CCk k 501002500 50)( ， 所 以 CCC jji i 501009950500 50 212 由 于 1314950 516293991002121 50100 C , 而 31為 素 數(shù) ， 又 分 子

23、 中 有 93和 62為 31的 倍 數(shù) ， 分 母中 只 有 31為 31的 倍 數(shù) ， 故 C5010021 肯 定 為 31的 倍 數(shù) ， 即 被 31除 余 數(shù) 為 零 。 因 為 194195495499 )131(2)2(2222 ， 由 二 項(xiàng) 式 定 理 ， 19)131( 被 31 除 余 數(shù) 為 1， 所 以19499 )131(22 被 31除 余 數(shù) 為 42 =16。 所 以 ， CCC jji i 501009950500 50 212 被 31除 余 數(shù) 為 16。 2021/6/16 24例 4-2 設(shè) 8,1,10|),( 81 iaaaAS i 或 。 對(duì)

24、于 S 中 兩 個(gè) 元 素 ),( 81 aaA 和),( 81 bbB ， 記 81 |),( i ii baBAd 并 稱 其 為 A和 B之 間 的 距 離 。 問 ： S 中 最 多 能 取 出 多 少 個(gè) 元 素 ， 它 們 之 中 任 何 兩 個(gè)的 距 離 5 ？ 2021/6/16 25例 4-2 設(shè) 8,1,10|),( 81 iaaaAS i 或 。 對(duì) 于 S 中 兩 個(gè) 元 素),( 81 aaA 和 ),( 81 bbB ， 記 81 |),( i ii baBAd 并 稱 其 為 A和 B之 間 的 距 離 。 問 ： S 中 最 多 能 取 出 多 少 個(gè) 元 素

25、， 它 們 之 中 任何 兩 個(gè) 的 距 離 5 ？ 解 ： 設(shè) S 中 最 多 能 取 出 m個(gè) 元 素 ， 它 們 之 中 任 何 兩 個(gè) 的 距 離 5 。 可 以 知 道 ， )2(mod0m 時(shí) ， 22 )2(85 mCm )2(mod1m時(shí) ， )2 1)(2 1(85 2 mmCm 解 之 得 ， 4m 。 下 面 構(gòu) 造 4 個(gè) 元 素 滿 足 條 件 ： )0,0,0,0,0,0,0,0( ； )1,1,1,0,0,1,1,1( ； )0,0,0,1,1,1,1,1( ； )1,1,1,1,1,0,0,0( 所 以 ， 4m 。 2021/6/16 26例 4-3（ 199

26、8， IMO） 在 某 次 競(jìng) 賽 中 ， 共 有 a個(gè) 參 賽 選 手 與 b個(gè)裁 判 ， 其 中 3b 且 為 奇 數(shù) 。 每 個(gè) 裁 判 對(duì) 每 個(gè) 選 手 的 評(píng) 分 只 有 “ 通 過(guò) ”或 “ 不 及 格 ” 兩 個(gè) 等 級(jí) 。 設(shè) k 是 滿 足 以 下 條 件 的 整 數(shù) ： 任 何 兩 個(gè) 裁判 至 多 可 對(duì) k 個(gè) 選 手 有 完 全 相 同 的 評(píng) 分 。 證 明 ： ak bb2 1 。 2021/6/16 27例 4-3（ 1998， IMO） 在 某 次 競(jìng) 賽 中 ， 共 有 a個(gè) 參 賽 選 手 與 b個(gè) 裁 判 ， 其 中 3b 且為 奇 數(shù) 。 每 個(gè) 裁

27、 判 對(duì) 每 個(gè) 選 手 的 評(píng) 分 只 有 “ 通 過(guò) ” 或 “ 不 及 格 ” 兩 個(gè) 等 級(jí) 。 設(shè) k 是 滿 足以 下 條 件 的 整 數(shù) ： 任 何 兩 個(gè) 裁 判 至 多 可 對(duì) k 個(gè) 選 手 有 完 全 相 同 的 評(píng) 分 。 證 明 ： ak bb2 1 。 證 明 ： 首 先 ， 如 果 兩 個(gè) 裁 判 對(duì) 某 個(gè) 選 手 有 相 同 的 評(píng) 判 ， 我 們 就 稱 其 為 一 個(gè) “ 同 意 ” 。由 已 知 ， 任 何 兩 個(gè) 裁 判 至 多 可 對(duì) k 個(gè) 選 手 有 完 全 相 同 的 評(píng) 判 ， 即 任 何 兩 個(gè) 裁 判 最 多 產(chǎn) 生 k個(gè) “ 同 意 ”

28、 。 “ 同 意 ” 的 總 數(shù) 2bkC 。 另 一 方 面 ， 對(duì) 任 意 一 個(gè) 選 手 ， 設(shè) 有 A個(gè) 裁 判 判 他 通 過(guò) ， 而 B個(gè) 裁 判 判 他 不 及 格 ， 其中 BA =b， 則 對(duì) 這 個(gè) 選 手 ， 有 關(guān) 他 的 “ 同 意 ” 的 個(gè) 數(shù) 為 2AC + 2BC = 2 )(22 BABA = 4 )(2)()( 22 BABABA = 4 2)( 22 bBAb 由 于 3b 且 為 奇 數(shù) ， 故 BA 也 應(yīng) 為 奇 數(shù) 。 從 而 2AC + 2BC 4 212 bb = 2)21( b 所 有 “ 同 意 ” 的 個(gè) 數(shù) 2)21( ba ， a

29、2)21(b 2bkC ak bb2 1 。 2021/6/16 285、 容 斥 原 理2021/6/16 29容 斥 原 理 設(shè) ( 1iA i ,2, )n 是 有 限 集 ， 那 么 1 1 1 1nn i i i j i j ki i i j n i j k nA A A A A A A 1 1( 1) nn ii A 容 斥 原 理 設(shè) I 為 全 集 , ( 1iA i , 2 , )n 是 有 限 集 ， 那 么 1 1 1n n ni i ii i iA A I A 1 1n i i ji i j nI A A A 11 ( 1) nni j k iii j k n A A

30、A A 2021/6/16 30例 5-1 （ 錯(cuò) 位 排 列 ） 若 1， 2， ， n的 一 個(gè) 排 列 1i ， 2i ， ， ni 滿 足 1i 1， 2i 2， ， ni n， 則 稱 1i ， 2i ， ， ni 為 1， 2， ， n的 一 個(gè) 錯(cuò) 位 排 列 。 試 求 1， 2， ， n的 所 有 錯(cuò) 位 排 列 的 個(gè) 數(shù) nD 。 2021/6/16 31例 5-1 （ 錯(cuò) 位 排 列 ） 若 1， 2， ， n的 一 個(gè) 排 列 1i ， 2i ， ， ni 滿 足 1i 1， 2i 2， ，ni n， 則 稱 1i ， 2i ， ， ni 為 1， 2， ， n的 一

31、 個(gè) 錯(cuò) 位 排 列 。 試 求 1， 2， ， n的 所有 錯(cuò) 位 排 列 的 個(gè) 數(shù) nD 。 解 ： 將 1， 2， ， n的 所 有 排 列 集 合 記 為 S ， 則 顯 然 S = !n 。 設(shè) jA =（ 1i ， 2i ， ， ni ）|（ 1i ， 2i ， ni ） S 且 jij （ j=1， 2， ， n） ， 于 是 nD =| _1A _2A _nA | | _jA |= )!1( n （ 1 j n） ， | iA jA |= )!2( n （ 1 i j n )， ， | 1iA 2iA riA |= )!( rn （ 1 1i 2i ri n )， ， | 1

32、A 2A nA |= !0 =1。 故 由 容 斥 原 理 得 ， nD= S ni iA1 nji ji AA 1 + nn AAA 211）（ = !n - 1nC )!1( n + 2nC )!2( n - 3nC )!3( n + + !01 nnnC）（ = !n （ !)1(!31!21!11 n n ） 。 2021/6/16 32例 5-2 在 不 含 數(shù) 字 0,9的 所 有 n位 自 然 數(shù) 中 ， 同 時(shí) 包 含 數(shù) 字 1， 2， 3， 4,5的 數(shù) 有多 少 個(gè) ？ 這 里 數(shù) 字 可 重 復(fù) ， 5n 。 解 ： 設(shè) I 為 1， 2， 3， 4,5， 6,7,8組

33、 成 的 n位 數(shù) 集 ， iA 為 I 中 不 含 數(shù) 字 )8,2,1( ii的 n位 數(shù) 集 。 I 中 不 全 含 數(shù) 字 1， 2， 3， 4,5的 n位 數(shù) 集 為 ii A51 ii A51=51i iA - 51 ji ji AA + 51 kji kji AAA 51 lkji lkji AAAA ii A51 nnnnn CCC 345675 453525 故 I 中 同 時(shí) 包 含 數(shù) 字 1， 2， 3， 4,5的 n位 數(shù) 的 個(gè) 數(shù) 為 nnnnnn CCC 3456758 453525 2021/6/16 336、 反 證 法2021/6/16 34例 6-1 （

34、 2009 清 華 ） 用 有 限 條 拋 物 線 以 及 它 們 的 內(nèi) 部 能否 覆 蓋 整 個(gè) 平 面 ？ （ 含 焦 點(diǎn) 的 區(qū) 域 稱 為 拋 物 線 內(nèi) 部 ） 2021/6/16 35例 6-1 （ 2009 清 華 ） 用 有 限 條 拋 物 線 以 及 它 們 的內(nèi) 部 能 否 覆 蓋 整 個(gè) 平 面 ？ （ 含 焦 點(diǎn) 的 區(qū) 域 稱 為 拋 物 線 內(nèi)部 ） 解 ： 不 能 。 采 用 反 證 法 ： 假 設(shè) 存 在 n條 拋 物 線 ， 這 n條 拋 物 線 以 及 它 們 的 內(nèi) 部 能 覆 蓋 整 個(gè) 平 面 。 現(xiàn) 在 我 們 任取 一 條 與 n條 拋 物 線

35、的 對(duì) 稱 軸 均 不 平 行 的 直 線 ， 那 么 這n條 拋 物 線 中 的 任 意 一 條 ， 與 該 直 線 或 者 沒 有 交 點(diǎn) ， 或者 相 切 ， 或 者 有 兩 個(gè) 不 同 的 交 點(diǎn) 。 換 句 話 說(shuō) 就 是 每 條 拋2021/6/16 36例 6-2（ 1982 西 德 ） 如 果 一 個(gè) 集 合 不 包 含 滿 足 zyx 的 三 個(gè) 數(shù) x、 y 、 z ，則 稱 之 為 單 純 的 。 設(shè) 12,2,1 nM ， A是 M 的 單 純 子 集 ， 求 | A 的 最 大 值 。 解 ： 令 12,5,3,1 nA ， 則 A是 單 純 的 ， 此 時(shí) 1| n

36、A 。 下 面 ， 證 明 ： 對(duì)任 何 單 純 子 集 A， 有 1| nA 。 用 反 證 法 。 假 設(shè) 2| nA ， 即 A中 至 少 有 2n 個(gè)元 素 ， 設(shè) 為 ： 221 naaa 。 設(shè) A中 有 p 個(gè) 奇 數(shù) paaa 21 和 pn 2 個(gè)偶 數(shù) pnbbb 221 ， 注 意 到 M 中 共 有 1n 個(gè) 奇 數(shù) ， n個(gè) 偶 數(shù) ， 故 2p 。 考 察 11312 aaaaaa p ， 它 們 都 是 正 偶 數(shù) ， 連 同 前 面 假 設(shè) 的pnbbb 221 ， 共 有 nnpnp 1)2()1( 個(gè) 正 偶 數(shù) 。 由 抽 屜 原 理 ， 必有 兩 個(gè) 元

37、 素 相 等 ， 且 只 能 是 某 個(gè) ib 與 某 個(gè) 1aaj 相 等 ， 于 是 ij baa 1 ， 與 A是 單純 的 矛 盾 。 2021/6/16 377、 不 等 式 法2021/6/16 38例 7-1 （ 1982 瑞 典 ） 在 坐 標(biāo) 平 面 上 給 定 集 合 12,12,|),( yxNyxyxM ， 并 將 M 中 的 每點(diǎn) 都 涂 上 紅 、 白 、 藍(lán) 三 色 之 一 ， 試 證 存 在 一 個(gè) 矩 形 ， 它 的 邊 平 行 于 坐 標(biāo) 軸 ， 4 個(gè) 頂 點(diǎn) 都 在 M 中 且 顏色 相 同 。 證 明 顯 然 ， 集 合 M 中 共 有 144 個(gè) 點(diǎn)

38、 且 構(gòu) 成 12 行 和 12 列 的 正 方 形 點(diǎn) 陣 。 由 抽 屜 原 理 知 ， 必 有一 種 顏 色 的 點(diǎn) 至 少 有 48 個(gè) ， 不 妨 設(shè) 紅 點(diǎn) 有 48 個(gè) 。 設(shè) 第 i列 中 共 有 ia 個(gè) 紅 點(diǎn) ， 12,2,1 i ， 于 是481221 aaa 。 將 同 一 列 中 的 兩 個(gè) 紅 點(diǎn) 稱 為 一 個(gè) 點(diǎn) 對(duì) 并 考 察 點(diǎn) 對(duì) 的 數(shù) 目 。 第 i列 上 的 點(diǎn) 對(duì) 有 )1(21 ii aa ， 從 而 點(diǎn)對(duì) 總 數(shù) 為 )(21)(21 12212122221 aaaaaam 24)(21 2122221 aaa 由 柯 西 不 等 式 有 2

39、4)(241 21221 aaam =96-24=72 顯 然 ， 每 個(gè) 紅 點(diǎn) 對(duì) 都 對(duì) 應(yīng) 一 個(gè) 由 兩 點(diǎn) 的 縱 坐 標(biāo) 組 成 的 “ 行 對(duì) ” 。 于 是 由 知 ， 至 少 有 72 個(gè) “ 行 對(duì) ” 。另 一 方 面 ， 由 于 點(diǎn) 陣 共 12 行 ， 共 可 組 成 66212 C 個(gè) 不 同 的 “ 行 對(duì) ” ， 由 抽 屜 原 理 ， 必 有 兩 個(gè) 不 同 列 的紅 點(diǎn) 對(duì) 對(duì) 應(yīng) 于 同 一 個(gè) “ 行 對(duì) ” 。 易 見 ， 以 這 兩 隊(duì) 中 的 4 個(gè) 紅 點(diǎn) 為 頂 點(diǎn) 的 矩 形 即 為 所 求 。 2021/6/16 39 8、 抽 屜 原

40、理2021/6/16 40例 8-1（ 2008 科 大 ） 一 個(gè) 平 面 由 紅 點(diǎn) 、 藍(lán) 點(diǎn) 組 成 ，且 既 有 紅 點(diǎn) 又 有 藍(lán) 點(diǎn) 。 對(duì) 于 給 定 任 意 長(zhǎng) )0( aa ， 證 明 ： （ 1） 平 面 上 存 在 兩 個(gè) 同 色 點(diǎn) ， 距 離 為 a； （ 2） 平 面 上 存 在 兩 個(gè) 異 色 點(diǎn) ， 距 離 為 a。 2021/6/16 41例 8-1 （ 2008 科 大 ） 一 個(gè) 平 面 由 紅 點(diǎn) 、 藍(lán) 點(diǎn) 組 成 ， 且 既有 紅 點(diǎn) 又 有 藍(lán) 點(diǎn) 。 對(duì) 于 給 定 任 意 長(zhǎng) )0( aa ， 證 明 ： （ 1） 平 面 上 存 在 兩 個(gè)

41、 同 色 點(diǎn) ， 距 離 為 a； （ 2） 平 面 上 存 在 兩 個(gè) 異 色 點(diǎn) ， 距 離 為 a。 證 明 ： （ 1） 取 一 個(gè) 邊 長(zhǎng) 為 a的 正 三 角 形 ， 由 抽 屜 原 理 ， 必有 兩 點(diǎn) 同 色 ， 則 這 兩 點(diǎn) 即 為 所 求 。 （ 2） 由 于 平 面 內(nèi) 既 有 紅 點(diǎn) 又 有 藍(lán) 點(diǎn) ， 所 以 可 以 任 取 一 個(gè) 紅點(diǎn) A和 一 個(gè) 藍(lán) 點(diǎn) B ， 又 由 于 平 面 上 所 有 點(diǎn) 均 染 了 兩 色 之 一 ， 所以 這 兩 點(diǎn) A、 B 可 以 由 若 干 條 長(zhǎng) 度 為 a的 線 段 相 連 ， 這 一 定 可以 做 到 。 由 于 A、

42、 B 異 色 ， 則 必 存 在 相 鄰 的 兩 點(diǎn) C、 D， 使 C、D異 色 且 aCD ， 則 C、 D兩 點(diǎn) 即 為 所 求 。 2021/6/16 42例 8-2 (自 編 題 ) 已 知 集 合 100,3,2,1 S ， T 是 S 的 子 集 ， 滿 足 性 質(zhì) ： 對(duì) 于 T 中的 任 意 一 個(gè) 元 素 x， x至 多 與 T 中 其 余 的 2個(gè) 元 素 不 互 素 ， 求 所 有 這 種 集 合 T 的 元 素 個(gè) 數(shù)的 最 大 值 。 解 ： 97,89,83,79,73,71,67,61,59,53,47,43,41,37,31,29,23,19,17,13,11

43、,7,5,3,2A ， 即 A表 示 不 超 過(guò) 100的 所 有 素 數(shù) 。 令 137,117,195,175,313,293,472,4320 AT 容 易 驗(yàn) 證 ， 0T 滿 足 性 質(zhì) ， 且 33| 0 T 。 所 以 ， 33|max T 。 另 一 方 面 ， 假 設(shè) 34|max T 。 不 妨 設(shè) 1T 滿 足 性 質(zhì) ， 且 34| 1 T ， 考 慮 1T 中 所 有 元 素的 最 小 素 因 子 。 顯 然 S 中 其 最 小 素 因 子 大 于 10 的 元 素 本 身 就 是 素 數(shù) ， 而 100以 內(nèi) 的 超 過(guò)10 的 所 有 素 數(shù) 有 21 個(gè) ， 又

44、 容 易 知 道 11 T ， 所 以 1T 中 其 最 小 素 因 子 是 2 或 3 或 5 或 7 的數(shù) 至 少 有 13 個(gè) 。 根 據(jù) 抽 屜 原 理 ， 1T 中 其 最 小 素 因 子 相 同 的 數(shù) 至 少 有 4 個(gè) ， 這 與 1T 中 任 意一 個(gè) 元 素 至 多 與 1T 中 其 余 的 2個(gè) 元 素 不 互 素 矛 盾 。 于 是 34|max T ， 所 以 33|max T 。 2021/6/16 43例 8-3 (1995 年 全 國(guó) 高 中 數(shù) 學(xué) 聯(lián) 賽 ) 將 平 面 上 每 個(gè) 點(diǎn) 都 以 紅 、 藍(lán) 兩 色 之 一 著 色 ， 證明 :存 在 這 樣

45、的 兩 個(gè) 相 似 三 角 形 ， 它 們 的 相 似 比 為1995， 并 且 每 一 個(gè) 三 角 形 的 三 個(gè) 頂 點(diǎn) 同 色 。 2021/6/16 44例 8-3 (1995 年 全 國(guó) 高 中 數(shù) 學(xué) 聯(lián) 賽 )將 平 面 上 每 個(gè) 點(diǎn) 都 以 紅 、藍(lán) 兩 色 之 一 著 色 ， 證 明 :存 在 這 樣 的 兩 個(gè) 相 似 三 角 形 ， 它 們 的 相似 比 為 1995， 并 且 每 一 個(gè) 三 角 形 的 三 個(gè) 頂 點(diǎn) 同 色 。 證 明 ： 在 平 面 上 作 兩 個(gè) 同 心 圓 ， 其 半 徑 比 為 1995。 然 后 作出 9條 不 同 的 半 徑 ， 與 兩

46、 個(gè) 同 心 圓 各 交 于 9個(gè) 點(diǎn) 。 由 抽 屜 原 理 知 ，大 圓 上 的 9個(gè) 點(diǎn) 中 必 有 5個(gè) 點(diǎn) 同 色 。 再 考 察 過(guò) 這 同 色 5點(diǎn) 的 5條半 徑 與 小 圓 的 5個(gè) 交 點(diǎn) ， 由 抽 屜 原 理 知 ， 其 中 必 有 3個(gè) 點(diǎn) 同 色 ，于 是 分 別 以 這 同 色 3點(diǎn) 和 大 圓 上 相 應(yīng) 的 同 色 3點(diǎn) 為 頂 點(diǎn) 的 兩 個(gè) 三角 形 便 滿 足 題 設(shè) 要 求 。 懸 賞 ： （ 獎(jiǎng) 金 ￥ 300元 ） 將 平 面 上 每 個(gè) 點(diǎn) 都 以 紅 、 藍(lán) 兩 色 之一 著 色 ， 證 明 或 舉 出 反 例 :存 在 這 樣 的 兩 個(gè) 相

47、 似 三 角 形 ， 它 們 的相 似 比 為 1995， 并 且 這 兩 個(gè) 三 角 形 的 六 個(gè) 頂 點(diǎn) 同 色 。 2021/6/16 459、 調(diào) 整 法調(diào) 整 法 是 先 證 明 所 求 的 極 值 存 在 ， 然 后 由 問 題 的 直觀 性 ， 猜 想 出 極 值 點(diǎn) 。 最 后 從 反 面 證 明 函 數(shù) 在 其 他 點(diǎn) 不能 達(dá) 到 極 值 ： 假 設(shè) 函 數(shù) 在 另 外 的 點(diǎn) ),( 21 nxxx 處 達(dá) 到極 值 ， 經(jīng) 過(guò) 適 當(dāng) 調(diào) 整 （ 常 常 是 將 小 的 分 量 變 大 ， 大 的 分量 變 小 ） ， 發(fā) 現(xiàn) 函 數(shù) 在 點(diǎn) ),( /2/1 nxx

48、x 處 的 值 更 大 或 更小 ， 從 而 斷 定 它 不 是 極 值 點(diǎn) 。 2021/6/16 46例 9-1 （ 1985 美 國(guó) ） 在 不 減 正 整 數(shù) 序 列 , 21 maaa 中 ， 對(duì) 任 何 正 整 數(shù) m，定 義 |min manb nm 。 已 知 8519 a ， 求 85211921 bbbaaaS 的 最 大 值 。 解 ： 首 先 ， 最 大 的 數(shù) 一 定 存 在 。 由 條 件 有 851921 aaa 。 猜 想 ： 極值 點(diǎn) 是 各 個(gè) ia 盡 可 能 大 且 各 個(gè) ia 相 等 ， 各 個(gè) ib 相 等 。 實(shí) 際 上 ， 若 有)181(1

49、iaa ii， 則 令 1/ ii aa 。 對(duì) 任 何 ij ， 令 jj aa / ， 對(duì) 應(yīng) 的 jb 記 為 jb/ 。那 么 ， 因 為 ii aa 1 ， 所 以 11 ii aa 。 但 1 ii aa ， 故 11 ib ia ， ib ia 1/ 11 iab， jj bb / （ 當(dāng) 1 iaj 時(shí) ） 。 由 此 可 知 ， 調(diào) 整 使 得 1iab 減 少 1，其 余 的 ib 不 變 ， S 的 值 不 減 。 綜 上 所 述 ， 17008518519 S ， 等 號(hào) 在)851,191(1,85 jiba ii時(shí) 成 立 。 2021/6/16 4710、 奇 偶

50、 分 析2021/6/16 48例 10-1 （ IMO 50 預(yù) 選 題 ） 有 排 成 一 列 的 2009張 卡 片 ，每 張 卡 片 一 面 為 金 色 ， 另 一 面 為 黑 色 ， 開 始 時(shí) ， 所 有 卡 片 的 金色 面 朝 上 。 兩 人 交 替 操 作 ， 規(guī) 則 如 下 ： 選 擇 相 鄰 的 50張 卡 片 ，且 最 左 邊 的 一 張 卡 片 的 金 色 面 朝 上 ， 其 翻 轉(zhuǎn) 張 50張 卡 片 。 規(guī) 定最 后 一 個(gè) 按 上 述 規(guī) 則 操 作 的 玩 家 獲 勝 。 問 ： （ 1） 操 作 是 否 一 定結(jié) 束 ？ （ 2） 先 操 作 的 玩 家 是

51、 否 有 獲 勝 策 略 ？ 2021/6/16 49例 10-1 （ IMO 50 預(yù) 選 題 ） 有 排 成 一 列 的 2009張 卡 片 ， 每 張 卡 片 一 面 為金 色 ， 另 一 面 為 黑 色 ， 開 始 時(shí) ， 所 有 卡 片 的 金 色 面 朝 上 。 兩 人 交 替 操 作 ， 規(guī) 則 如下 ： 選 擇 相 鄰 的 50 張 卡 片 ， 且 最 左 邊 的 一 張 卡 片 的 金 色 面 朝 上 ， 其 翻 轉(zhuǎn) 張 50張 卡 片 。 規(guī) 定 最 后 一 個(gè) 按 上 述 規(guī) 則 操 作 的 玩 家 獲 勝 。 問 ：（ 1） 操 作 是 否 一 定 結(jié) 束 ？（ 2）

52、先 操 作 的 玩 家 是 否 有 獲 勝 策 略 ？ 解 ： （ 1） 記 黑 色 面 朝 上 的 卡 片 為 0， 金 色 面 朝 上 的 卡 片 為 1。 對(duì) 2009張 卡 片 的 每 一 種 擺 放 ， 從 左 到 右 讀 與 2009個(gè) 數(shù) 碼 在 二 進(jìn) 制 表 示 下 的非 負(fù) 整 數(shù) （ 首 位 數(shù) 碼 可 以 是 0） 構(gòu) 成 一 一 對(duì) 應(yīng) 。 而 每 次 操 作 該 數(shù) 變 小 ， 因 此 ， 操作 一 定 結(jié) 束 。 （ 2） 只 需 證 明 ： 先 操 作 的 玩 家 沒 有 獲 勝 策 略 。 事 實(shí) 上 ， 將 卡 片 從 右 到 左 進(jìn) 行 編 號(hào) 。 考 慮

53、 編 號(hào) 為 )40,2,1(50 ii 的 集 合 S 。 設(shè) S 中 n次 操 作 后 ， 金 色 面 朝 上 的 卡 片 的 數(shù) 目 是 nU 。 顯 然 ， 400 U ， 且 1| 1 nn UU 。 于 是 奇 數(shù) 次 操 作 后 ， S 中 金 色 面 朝 上 的 卡 片 的 數(shù) 目 是 奇 數(shù) ， 后 操 作 的 玩 家 可以 從 S 中 選 一 張 金 色 面 朝 上 的 卡 片 ， 對(duì) 這 張 卡 片 及 其 右 邊 的 49張 卡 片 進(jìn) 行 操 作 。因 此 ， 后 操 作 的 玩 家 總 能 獲 勝 。 2021/6/16 5011、 極 端 原 理2021/6/16

54、 51例 11-1（ 2010 江 蘇 ） 將 凸 n邊 形 1 2 nA A A 的 邊 與 對(duì) 角 線 染 上 紅 、 藍(lán) 兩色 之 一 ， 使 得 沒 有 三 邊 均 為 藍(lán) 色 的 三 角 形 . 對(duì) k=1, 2, ， n， 記 kb 是 由 頂 點(diǎn)kA引 出 的 藍(lán) 色 邊 的 條 數(shù) ， 求 證 ： 21 2 2n nb b b . 證 明 ： 不 妨 設(shè) 1 2max , , , nb b b b ， 并 且 由 點(diǎn) A 向 1 2, , , bA A A 引 出 b 條藍(lán) 色 邊 ， 則 1 2, , , bA A A 之 間 無(wú) 藍(lán) 色 邊 ， 1 2, , , bA A

55、A 以 外 的 n b 個(gè) 點(diǎn) ， 每 點(diǎn) 至多 引 出 b條 藍(lán) 色 邊 ， 因 此 藍(lán) 色 邊 總 數(shù) ( )n b b 2 2( )2 4n b b n . 故 2 21 2 2 4 2n n nb b b . 命 題 得 證 . 2021/6/16 5212、 數(shù) 學(xué) 歸 納 法2021/6/16 53例 12-1（ 自 編 題 ） 設(shè) )(nf 表 示 平 面 上 任 何 三 點(diǎn) 不 共線 的 n( 4n )個(gè) 點(diǎn) 所 組 成 的 三 角 形 中 ,非 銳 角 三 角 形 個(gè)數(shù) 的 極 小 值 。 設(shè) 0321 ， Cf 344 )4( ，Cf 355 )5(， ， Cnn nf 3

56、)( ， ， 則 數(shù) 列 n 是 遞 增 數(shù) 列 。 征 解 題 ： 是 否 21lim nn ？ （ 獎(jiǎng) 金 ￥ 3000元 ） 2021/6/16 54例 12-1（ 自 編 題 ） 設(shè) )(nf 表 示 平 面 上 任 何 三 點(diǎn) 不 共 線 的 n( 4n )個(gè) 點(diǎn) 所 組 成 的 三角 形 中 ,非 銳 角 三 角 形 個(gè) 數(shù) 的 極 小 值 。 設(shè) 0321 ， Cf 344 )4( ， Cf 355 )5( ， ，Cnn nf 3)(， ， 則 數(shù) 列 n 是 遞 增 數(shù) 列 。 證 明 : 用 數(shù) 學(xué) 歸 納 法 證 明 。 顯 見 34 41 . 假 設(shè) 當(dāng) kn 時(shí) , 1

57、 kk ,當(dāng) 1 kn 時(shí) ,選 取 非 銳 角 三 角 形 個(gè) 數(shù) 取 得 極 小 值 的 1k個(gè) 點(diǎn) ,這 1k 個(gè) 點(diǎn) 組 成 1k 個(gè) “ k 點(diǎn) 組 ” ,顯 然 每 個(gè) “ k 點(diǎn) 組 ” 中 至 少 有 )(kf 個(gè) 非 銳 角 三角 形 ,總 共 至 少 有 )()1( kfk 個(gè) 非 銳 角 三 角 形 ， 因 為 每 個(gè) 非 銳 角 三 角 形 存 在 于 ( 2k )個(gè) “ k點(diǎn) 組 ” (因 為 1k 點(diǎn) 中 除 了 該 三 角 形 三 點(diǎn) 外 還 有 2k 個(gè) 點(diǎn) ,去 掉 2k 個(gè) 點(diǎn) 中 的 任 意 一 點(diǎn) 就與 該 三 角 形 組 成 一 個(gè) “ k 點(diǎn) 組 ”

58、 ) ,即 每 個(gè) 非 銳 角 三 角 形 重 復(fù) 計(jì) 算 了 ( 2k )次 ,故 有 2 )()1()1( k kfkkf 不 等 式 兩 邊 同 時(shí) 除 以 Ck3 1 ， 即 得 kk 1 。 2021/6/16 5513. 游 戲 策 略2021/6/16 56例 13-1. （ 2012， 俄 羅 斯 競(jìng) 賽 ） 開 始 時(shí) 桌 子 上 有 111 塊 等重 的 橡 皮 泥 ， 對(duì) 桌 子 上 的 橡 皮 泥 進(jìn) 行 如 下 操 作 ： 先 將 橡 皮 泥 中的 一 部 分 或 全 體 分 成 若 干 組 ， 每 組 有 相 同 塊 數(shù) 的 橡 皮 泥 ， 然 后將 每 組 中 的

59、 橡 皮 泥 捏 成 一 塊 .已 知 可 以 經(jīng) 過(guò) m次 上 述 操 作 使 得桌 子 上 恰 有 11塊 兩 兩 重 量 不 同 的 橡 皮 泥 .求 m的 最 小 值 . 2021/6/16 57例 13-1. （ 2012， 俄 羅 斯 競(jìng) 賽 ） 開 始 時(shí) 桌 子 上 有 111 塊 等 重 的 橡 皮 泥 ， 對(duì) 桌子 上 的 橡 皮 泥 進(jìn) 行 如 下 操 作 ： 先 將 橡 皮 泥 中 的 一 部 分 或 全 體 分 成 若 干 組 ， 每 組 有相 同 塊 數(shù) 的 橡 皮 泥 ， 然 后 將 每 組 中 的 橡 皮 泥 捏 成 一 塊 .已 知 可 以 經(jīng) 過(guò) m次 上

60、述 操 作使 得 桌 子 上 恰 有 11塊 兩 兩 重 量 不 同 的 橡 皮 泥 .求 m的 最 小 值 . 解 ： m的 最 小 值 為 2. 顯 然 一 次 操 作 最 多 可 以 得 到 兩 種 不 同 重 量 的 塊 .下 面 說(shuō) 明 兩 次 操 作 可 以 達(dá) 到目 的 .不 妨 假 設(shè) 初 始 時(shí) 每 塊 橡 皮 泥 重 量 為 1.第 一 次 操 作 選 出 74塊 橡 皮 泥 分 成 37組 ，每 組 2 塊 .第 一 次 操 作 后 桌 子 上 有 37 塊 重 量 為 1 的 橡 皮 泥 ， 37 塊 重 量 為 2 的 橡 皮泥 .第 二 次 選 出 36塊 重 量

61、為 1的 和 36塊 重 量 為 2的 橡 皮 泥 ， 分 成 9組 ， 每 組 8塊 ，其 中 第 )91( ii 組 中 含 1i 塊 重 量 為 2的 ， i9 塊 重 量 為 1的 橡 皮 泥 .經(jīng) 過(guò) 第 二 次操 作 ， 桌 子 上 有 11 塊 橡 皮 泥 ， 重 量 分 別 是 1， 2， iii 7)1(29 ， 91 i .滿 足 要 求 . 2021/6/16 58例 13-2. （ 2012， 俄 羅 斯 競(jìng) 賽 ） A是 一 個(gè) 正 12 n邊 形 的 頂 點(diǎn) 集 .甲 乙 兩 人 由 甲 開 始 輪 流 每 次 去 掉 A中的 一 個(gè) 點(diǎn) .如 果 某 人 操 作

62、后 A中 剩 下 的 任 意 三 點(diǎn) 都 構(gòu)成 一 個(gè) 鈍 角 三 角 形 的 頂 點(diǎn) 集 ,則 此 人 獲 勝 .問 :甲 乙 兩人 誰(shuí) 有 必 勝 策 略 ? 2021/6/16 59例 13-2. （ 2012， 俄 羅 斯 競(jìng) 賽 ） A是 一 個(gè) 正 12 n 邊 形 的 頂 點(diǎn) 集 .甲 乙 兩 人 由 甲 開始 輪 流 每 次 去 掉 A中 的 一 個(gè) 點(diǎn) .如 果 某 人 操 作 后 A中 剩 下 的 任 意 三 點(diǎn) 都 構(gòu) 成 一 個(gè) 鈍 角三 角 形 的 頂 點(diǎn) 集 ,則 此 人 獲 勝 .問 :甲 乙 兩 人 誰(shuí) 有 必 勝 策 略 ? 解 ： 乙 有 必 勝 策 略 .

63、乙 的 策 略 是 :每 次 在 他 操 作 后 ,如 果 還 剩 下 512 k 個(gè) 頂 點(diǎn) ,則 要保 證 ,在 A的 外 接 圓 上 的 任 意 半 圓 上 都 有 不 少 于 k 個(gè) 頂 點(diǎn) .首 先 ,游 戲 開 始 時(shí) 這 樣 的 條 件滿 足 .假 設(shè) 輪 到 甲 走 時(shí) ,頂 點(diǎn) 順 時(shí) 針 方 向 依 次 還 剩 下 kAAA 210 , ， 3k ， 滿 足 任 意 半圓 上 都 有 不 少 于 k 個(gè) 頂 點(diǎn) 。 不 妨 設(shè) 甲 拿 掉 0A ， 則 乙 拿 掉 kA 。 注 意 到 211 kk AAA 是 銳角 三 角 形 ， 故 甲 不 可 能 獲 勝 。 在 這

64、輪 操 作 中 ， 如 果 在 某 個(gè) 半 圓 上 只 去 掉 了 一 個(gè) 點(diǎn) ， 則在 此 半 圓 上 至 少 還 有 1k 個(gè) 點(diǎn) 。 如 果 半 圓 含 kAA ,0 ， 則 其 上 至 少 還 剩 下 121 , kAAA 或 kkk AAA 221 , 這 1k 個(gè) 點(diǎn) 。 如 此 進(jìn) 行 2n 輪 操 作 后 ， 還 剩 下 5 個(gè) 點(diǎn)43210 , AAAAA ， 輪 到 甲 ， 不 妨 甲 拿 掉 0A ， 注 意 到 421 AAA 是 銳 角 三 角 形 ， 故 甲 不 可能 獲 勝 ， 此 時(shí) 乙 拿 掉 4A 得 到 鈍 角 321 AAA 。 2021/6/16 60

65、1. 已 知 集 合 1 2 1 | ( , , ), 0,1, 1,2, , ( 2)n nS X X x x x x i n n ， 對(duì) 于 ),( 21 naaaA nn SbbbB ),( 21 ， 定 義 A與 B的 差 為 |)|,|,|,(| 2211 nn bababaBA ， A與 B之 間 的 距 離 為 ni ii baBAd 1 |),( . （ ） 證 明 ： , , ,n nA B C S A B S 有 ， 且 ( , ) ( , )d A C B C d A B ； （ ） 證 明 ： , , , ( , ), ( , ), ( , )nA B C S d A

66、B d A C d B C 三 個(gè) 數(shù) 中 至 少 有 一 個(gè) 是 偶 數(shù) ； （ ） 設(shè) nSP ， P 中 有 )2( mm 個(gè) 元 素 ， 記 P 中 所 有 兩 元 素 間 距離 的 平 均 值 為 )(_ Pd ， 則 )1(2)(_ mmnPd 。 2021/6/16 612. 已 知 一 個(gè) 保 險(xiǎn) 柜 由 11 個(gè) 成 員 的 委 員 會(huì) 負(fù) 責(zé) 管 理 ， 保 險(xiǎn)柜 上 加 了 若 干 把 鎖 ， 這 些 鎖 的 鑰 匙 分 配 給 各 個(gè) 委 員 保 管 使 用 。為 了 使 任 何 6個(gè) 委 員 同 時(shí) 到 場(chǎng) 就 能 打 開 保 險(xiǎn) 柜 ， 而 任 何 5個(gè) 委員 同 時(shí) 到 場(chǎng) 都 不 能 打 開 保 險(xiǎn) 柜 ， 最 少 應(yīng) 給 保 險(xiǎn) 柜 加 多 少 把 鎖 ？ 2021/6/16 623. 設(shè) 1995,2,1 M ， A是 M 的 子 集 且 滿 足條 件 :當(dāng) Ax 時(shí) ， Ax15 。 則 A 中 元 素 的 個(gè) 數(shù) 最 多是 多 少 ？ 2021/6/16 634.設(shè) , 21 nxxxM 是 自 然 數(shù) n,2,1 的 一 個(gè) 排列 。 )(Mf