解 難 之 趣 屯 門 區 小 學 數 學 比 賽 專 題 特 刊 第 十 九 屆 二 零 零 九 年 四 月 二 十 五 日 在 數 學 競 賽, 有 一 些 用 途 廣 泛 的 數 學 原 / 定 理, 由 於 它 們 的 陳 述 很 簡 單, 所 以 很 少 以 獨 立 的 專 題 來 討 論 ; 今 次, 我 們 選 了 幾 個 原 理 跟 同 學 分 享 加 法 原 理 做 一 件 事, 完 成 它 可 以 有 n 類 辦 法, 在 第 一 類 辦 法 中 有 m 1 種 不 同 的 方 法, 在 第 二 類 辦 法 中 有 m 種 不 同 的 方 法,, 在 第 n 類 辦 法 中 有 m n 種 不 同 的 方 法, 那 麼 完 成 這 件 事 的 不 同 方 法 的 數 目 為 N = m + m +... + m 1 n 例 1: 從 甲 地 到 乙 地, 可 以 乘 火 車 公 共 汽 車 輪 船 前 往 如 果 每 天 分 別 火 車 有 5 班, 汽 車 有 4 班, 輪 船 有 3 班, 那 麼, 每 天 從 甲 地 到 乙 地 共 有 多 少 種 不 同 的 走 法? 解 答 : 無 論 選 甚 麼 交 通 工 具, 都 是 同 一 類 的 東 西 ; 也 就 是 說, 你 可 以 選 擇 乘 火 車 汽 車 或 輪 船, 但 是 選 了 任 何 一 類 後, 就 不 能 再 選 其 他 的 了, 所 以, 按 加 法 原 理, 不 同 的 走 法 共 有 5 + 4 + 3 = 1 種 乘 法 原 理 乘 法 原 理 : 做 一 件 事, 完 成 它 需 要 分 成 n 個 步 驟, 做 第 一 步 有 m 1 種 不 同 的 方 法, 做 第 二 步 有 m 種 不 同 的 方 法,, 做 第 n 步 有 m n 種 不 同 的 方 法, 那 麼 完 成 這 件 事 的 不 同 方 法 的 數 目 為 N = m m... m 1 n 例 : 從 A 地 到 D 地, 途 中 要 經 過 B C 兩 地 從 A 地 到 B 地 有 3 條 路, 從 B 地 到 C 地 有 條 路, 從 C 地 到 D 地 有 4 條 路, 那 麼 從 A 地 到 D 地 有 多 少 種 不 同 的 走 法? 解 答 : 從 A 地 到 B 地 有 3 種 走 法, 到 達 B 地 後, 對 應 著 每 一 種 走 法, 又 有 種 不 同 的 走 法 可 以 到 達 C 地 最 後, 從 C 地 又 會 有 4 種 不 同 的 走 法 可 以 到 達 D 地, 所 以 從 A 地 去 D 地, 共 有 3 4 = 4 不 同 的 走 法 為 要 更 清 楚 地 闡 明 上 例, 我 們 不 妨 令 從 A 地 到 B 地 的 3 條 路 為 x 1 x x 3, 從 B 地 到 C 1
地 的 條 路 為 y 1 y, 從 C 地 到 D 地 的 4 條 路 為 z 1 z z 3 z 4, 如 下 圖 然 後, 以 表 列 方 式 表 示 出 可 能 的 走 法 : x 1 1 1 1 1 1 1 1 1 1 1 1 1 x x 3 1 3 3 1 3 3 1 3 3 1 4 4 1 4 4 1 4 4 明 顯 地, 共 有 3 8 = 4 種 不 同 的 走 法 這 裏 要 注 意 區 分 加 法 原 理 和 乘 法 原 理, 要 做 一 件 事, 完 成 它 若 是 有 n 類 辦 法, 是 分 類 問 題, 第 一 類 中 的 方 法 都 是 獨 立 的, 因 此 用 加 法 原 理 ; 做 一 件 事, 需 要 分 n 個 步 驟, 步 與 步 之 間 是 連 續 的, 只 有 將 分 成 的 若 干 個 互 相 聯 繫 的 步 驟, 依 次 相 繼 完 成, 這 件 事 才 算 完 成, 因 此 用 乘 法 原 理 這 樣 完 成 一 件 事 的 分 類 和 步 是 有 本 質 區 別 的, 因 此 也 將 兩 個 原 理 區 分 開 來 從 上 述 兩 例 可 知, 加 法 原 理 和 法 原 理 常 應 用 於 數 路 線 ( 另 一 種 常 見 的 比 賽 題 目 是 地 圖 染 色 的 問 題 ) 的 問 題 上, 讓 我 們 看 看 下 列 例 題, 深 入 了 解 這 兩 個 原 理 的 使 用 方 法 例 3: 如 右 圖, 由 A 點 到 C 點 有 多 少 條 不 同 的 路 線?( 每 條 路 線 不 可 經 過 同 一 點 次 或 以 上 ) ( 第 5 屆 屯 門 區 小 學 數 學 比 賽 個 人 賽 第 19 題 ) 解 答 : 由 於 點 數 不 多, 路 線 很 少, 我 們 不 妨 以 樹 形 圖 列 出 可 行 的 不 同 路 線 所 以, 共 有 6 條 不 同 的 路 線 這 裡, 我 們 利 用 加 法 原 理 將 可 能 的 路 線 進 行 歸 類, 在 路 線 不 多 的 情 況 下, 樹 形 圖 能 夠 將 所 有 可 能 的 路 線 清 楚 呈 現
例 4: 如 右 圖, 由 A 點 到 G 點 有 多 少 條 不 同 的 路 線?( 每 條 路 線 不 可 經 過 同 一 點 次 或 以 上 ) ( 第 6 屆 屯 門 區 小 學 數 學 比 賽 個 人 賽 第 3 題 ) 解 答 : 明 顯 地, 從 A 點 到 B 點 有 種 不 同 的 走 法, 現 在, 考 慮 中 間 的 圖 形, 將 圖 形 簡 化 如 下 : 從 B 點 到 F 點, 途 經 1 點 的 走 法 有 3 個 可 能 :BCF BDF BEF 途 經 點 的 走 法 有 4 個 可 能 :BCDF BEDF BDCF BDEF 途 經 3 點 的 走 法 有 個 可 能 :BCDEF BEDCF 所 以, 從 B 點 到 F 點, 共 有 3 + 4 + = 9 條 不 同 路 線 從 F 點 到 G 點 只 有 一 條 路 可 走, 所 以 從 A 點 走 到 G 點, 共 有 9 = 18 條 不 同 的 路 線 例 5: 右 圖 是 某 城 市 的 街 道 圖, 若 從 A 地 到 B 地, 規 定 只 能 由 上 到 下 或 由 左 到 右 走, 共 有 多 少 種 不 同 的 走 法? 解 答 : 這 是 一 題 典 型 利 用 加 法 原 理 去 數 路 線 的 題 目 先 考 慮 簡 單 的 情 況, 由 於 規 定 只 能 由 上 到 下 或 由 左 到 右 走, 如 下 圖 一, 從 A 點 到 C D 點 只 有 1 種 走 法, 而 按 加 法 原 理, 走 到 E 點 就 有 種 走 法 同 理, 到 達 F G 點 只 有 1 種 走 法,H I 點 有 3 種 走 法, 而 到 達 J 點 就 有 6 種 走 法 ( 下 圖 二 ) 圖 一 圖 二 圖 三 如 此 類 推, 得 圖 三, 走 到 B 點 共 有 70 種 不 同 的 走 法 除 了 數 路 線 問 題 外, 地 圖 染 色 問 題 亦 常 用 到 加 法 原 理 和 乘 法 原 理, 讓 我 們 看 看 下 列 例 6: 右 圖 中,A B C D E 五 個 區 域, 以 紅 黃 藍 三 色 去 塗, 相 鄰 區 域 塗 上 不 同 顏 色, 共 有 多 少 種 塗 法? ( 第 13 屆 屯 門 區 小 學 數 學 比 賽 個 人 賽 第 19 題 ) 解 答 : 首 先, 可 以 紅 黃 藍 任 一 顏 色 去 塗 A 區 由 於 B C 區 與 A 相 連, 而 B C 兩 區 亦 相 連 接, 所 以 可 塗 在 B 區 的 顏 色 3
減 到 種, 塗 在 C 區 的 減 到 1 種 雖 然 E 區 並 不 與 B 區 相 連, 理 論 上 可 選 的 顏 色 有 種, 但 這 樣 做 的 話,D 區 將 無 法 著 色, 所 以, 可 塗 上 的 顏 色 數 目 如 下 : 按 乘 法 原 理, 共 有 3 1 1 1 = 6 種 不 同 的 塗 色 方 法 例 7: 從 1 至 500 中, 不 含 數 字 3 的 數 有 多 少? 解 答 : 在 一 位 數 中, 不 含 數 字 3 的 數 有 8 個, 即 1 4 5 6 7 8 9 在 兩 位 數 中, 個 位 不 含 數 字 3 的 數 有 9 個 可 能 (0 1 4 5 6 7 8 9), 十 位 不 含 數 字 3 的 數 有 8 個 可 能 (1 4 5 6 7 8 9), 所 以 不 含 數 字 3 的 兩 位 數 有 9 8 = 7 個 在 三 位 數 中, 個 位 不 含 數 字 3 的 數 有 9 個 可 能, 十 位 不 含 數 字 3 的 數 也 有 9 個 可 能, 百 位 不 含 數 字 3 的 數 有 3 個 可 能 (1 4), 連 同 500 在 內, 不 含 數 字 3 的 三 位 數 有 9 9 3 + 1 = 44 個 所 以, 按 加 法 原 理,1 至 500, 不 含 數 字 3 的 數 共 有 8 + 7 + 44 = 34 看 過 比 賽 的 例 子 後, 讓 我 們 想 一 想 在 日 常 生 活 會 遇 到 的 問 題 例 如, 在 一 次 舊 同 學 的 聚 會 中, 有 11 個 人 與 會, 若 果 他 們 每 人 都 跟 其 他 人 握 手 一 次, 那 麼, 他 們 共 握 手 多 少 次 呢? 或 者 同 學 會 說 : 太 老 套 了! 我 們 聚 會 不 握 手 啊! 那 麼, 要 舉 辨 一 次 15 人 參 加 的 象 棋 比 賽, 以 單 循 環 賽 制 進 行, 一 共 要 比 賽 多 少 場 呢? 如 果, 同 學 是 足 球 愛 好 者, 你 有 想 過 英 格 蘭 超 級 足 球 聯 賽 每 一 個 球 季 共 比 賽 多 少 場 呢? 首 先, 我 們 先 要 知 道 英 格 蘭 超 級 足 球 聯 賽 共 有 0 支 球 隊 參 予, 以 雙 循 環 賽 制, 每 支 球 隊 都 會 主 場 迎 戰 其 他 球 隊 一 次, 亦 要 作 客 出 戰 其 他 球 隊 一 次 那 麼 每 支 球 隊 都 要 作 賽 ( 0 1) = 38場, 故 此, 整 季 就 要 比 賽 0 38 = 380 場 單 循 環 賽 制 就 是 每 兩 個 參 加 者 只 比 賽 一 場, 那 麼,15 人 參 加 的 象 棋 比 賽, 每 人 就 要 比 賽 15 1 = 14 場, 但 我 跟 你 比 賽 與 你 跟 我 比 賽 是 相 同 事, 所 以 15 人 參 加 的 比 賽 共 要 比 15 (15 1) 賽 = 105場 其 實, 每 個 人 都 跟 其 他 人 握 手 一 次, 與 比 賽 一 場 是 一 樣 的, 所 以 11 人 的 聚 會 中, 11 10 他 們 共 握 手 = 55次 不 過, 我 們 可 以 這 樣 想 : 將 11 人 編 號 為 1-11, 第 1 號 與 其 他 10 人 握 手 後 就 離 開 了, 這 樣 他 共 握 了 10 次 手 然 後, 在 這 10 人 中, 第 號 重 複 第 1 號 的 動 作, 他 就 會 握 手 9 次 了 如 推 類 推, 直 到 最 後 剩 下 人 握 手 1 次 這 樣, 他 們 共 握 手 10 (10 + 1) 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + + 1 = = 55次 4
鴿 巢 原 理 鴿 巢 原 理 (Pigeonhole principle), 又 名 抽 屜 原 理 (box (drawer) principle) 最 先 由 德 國 數 學 家 狄 利 克 雷 (Dirichlet) 於 1834 年 在 其 著 作 Schubfachprinzip ("drawer principle" or "shelf principle") 中 提 出 其 中 一 種 簡 單 的 表 述 法 為 : (I) 若 有 n 個 籠 子 和 n+1 隻 鴿 子, 所 有 的 鴿 子 都 被 關 在 鴿 籠 裡, 那 麼 至 少 有 一 個 籠 子 有 至 少 隻 鴿 子 或 者 這 麼 說 : ( 摘 自 維 基 共 享 資 源 ) (II) 若 有 n 個 籠 子 和 kn+1 隻 鴿 子, 所 有 的 鴿 子 都 被 關 在 鴿 籠 裡, 那 麼 至 少 有 一 個 籠 子 有 至 少 k+1 隻 鴿 子 雖 然 鴿 巢 原 理 看 起 來 很 容 易 理 解, 但 有 時 使 用 鴿 巢 原 理 會 得 到 一 些 很 有 趣 的 結 論 : 例 如 : 香 港 最 少 有 兩 個 人 頭 髮 數 一 樣 多 因 為, 常 人 的 頭 髮 數 目 在 15 萬 左 右, 可 以 假 定 沒 有 人 有 超 過 100 萬 根 頭 髮, 但 香 港 人 口 大 於 100 萬 如 果 我 們 讓 每 一 個 鴿 巢 對 應 一 個 頭 髮 數 字, 鴿 子 對 應 於 人, 那 就 變 成 了 有 大 於 100 萬 隻 鴿 子 要 進 到 至 多 100 萬 個 巢 中 所 以, 結 論 很 明 顯 另 一 個 例 子 : 盒 子 裡 有 10 隻 黑 襪 子 1 隻 藍 襪 子, 你 需 要 拿 一 對 同 色 的 出 來 假 設 你 總 共 只 能 拿 一 次, 而 且 拿 的 時 候 還 看 不 到, 那 你 至 少 應 該 拿 幾 隻 出 來, 才 能 保 證 有 一 雙 同 色 的 呢? 可 能 有 人 會 脫 口 而 出 13 隻! 其 實 3 隻 就 可 以 了, 因 為 顏 色 只 有 兩 種 ( 鴿 巢 只 有 兩 個 ), 而 三 隻 襪 子 ( 三 隻 鴿 子 ), 結 論 就 明 顯 了 更 不 直 觀 的 例 子 : 有 n 個 人 ( 至 少 人 ) 互 相 握 手 ( 隨 意 找 人 握 ), 必 有 兩 人 握 手 次 數 相 同 這 裡, 鴿 巢 對 應 於 握 手 次 數, 鴿 子 對 應 於 人, 每 個 人 都 可 以 握 0 1 n 1次 手 但 0 和 n 1不 能 同 時 存 在, 因 為 如 果 一 個 人 不 和 任 何 人 握 手, 那 就 不 會 存 在 一 個 和 所 有 其 他 人 都 握 過 手 的 人 所 以 鴿 巢 是 n 1個, 但 有 n 個 人 (n 隻 鴿 子 ), 按 原 理 必 有 一 個 鴿 巢 最 少 有 隻 鴿 子 好 了, 讓 我 們 也 從 過 去 的 比 賽 題 目 中, 好 好 學 習 一 下 鴿 巢 原 理 的 應 用 例 8: 一 個 袋 裡 有 紅 珠 6 粒, 黃 珠 8 粒, 藍 珠 10 粒 最 少 要 抽 出 多 少 粒 珠 才 可 保 證 有 3 粒 是 同 一 顏 色?( 第 6 屆 屯 門 區 小 學 數 學 比 賽 個 人 賽 第 4 題 ) 解 答 : 這 個 簡 單 的 題 目 想 像 一 下 最 差 的 情 況, 先 抽 到 紅 珠 黃 珠 藍 珠 各 位, 到 抽 出 第 7 粒 珠 的 時 候, 不 論 是 紅 黃 藍 任 何 一 種 顏 色, 都 會 馬 上 符 合 3 粒 同 色 的 要 求, 所 以 最 少 要 抽 出 7 粒 才 可 保 證 有 3 粒 珠 同 一 顏 色 其 實, 按 鴿 巢 原 理 的 第 二 個 版 本, 假 定 3 種 顏 色 是 鴿 巢, 那 麼 抽 出 的 珠 數 為 3 + 1 = 7 時, 就 會 保 證 有 + 1 = 3 粒 珠 在 同 一 鴿 巢 ; 即 是 同 顏 色 鴿 巢 原 理 的 應 用 看 似 簡 單, 不 過, 它 應 用 到 證 明 上 卻 是 非 常 利 害 的! 讓 我 們 看 看 下 面 的 例 子, 以 及 兩 位 數 學 天 才 因 為 這 原 理 而 相 識 的 趣 事 5
例 9: 在 邊 長 為 4 的 正 方 形 內, 隨 意 放 進 9 個 點, 試 證 明 其 中 必 有 3 點, 它 們 構 成 的 三 角 形 的 面 積 不 大 於 解 答 : 因 為 9 = 4 + 1, 所 以 由 鴿 巢 原 理 解 (II), 設 有 4 個 鴿 巢, 則 可 保 證 至 少 有 一 個 鴿 巢 的 點 數 不 少 於 3 個 我 們 將 正 方 形 分 為 4 等 份 這 是 最 有 可 能 得 到 面 積 大 於 的 做 法, 若 果 分 得 不 平 均 的 話, 很 容 易 就 會 得 到 面 積 少 於 的 三 角 形 ( 如 圖 一 ) 令 其 中 一 份 包 含 3 個 點 ( 如 圖 二 和 圖 三 ): 圖 一 圖 二 圖 三 明 顯 地, XYZ 的 面 積 必 定 少 於 長 方 形 ABCPQ 內 最 大 的 三 角 形 面 積! 而 這 個 三 角 形 的 1 面 積 ABP 的 面 積, 即 (4)(1) = 得 證 例 10: 在 一 間 能 容 納 1500 個 座 位 的 戲 院 裏, 證 明 如 果 戲 院 坐 滿 人 時, 一 定 最 少 有 五 個 觀 眾 是 同 月 同 日 生 的 解 答 : 現 在 假 定 一 年 有 三 百 六 十 五 天 想 像 有 一 個 很 大 的 鴿 巢, 這 巢 有 編 上 一 月 一 日, 一 月 二 日, 至 到 十 二 月 三 十 一 日 爲 止 的 標 誌 的 間 隔 假 定 現 在 每 個 間 隔 都 塞 進 四 個 人, 那 麽 4 365 = 1460 個 人 是 進 去 籠 子 的 鴿 子, 還 剩 下 1500 1460 = 40 人 只 要 任 何 一 人 進 入 鴿 子 籠, 就 有 五 個 人 是 有 相 同 的 生 日 了 例 11: 有 n + 1個 不 相 同 的 正 整 數, 它 們 全 都 小 於 或 等 於 n, 證 明 當 中 一 定 有 兩 個 數 是 互 質 的 解 答 : 讓 我 們 先 想 一 想 簡 單 的 情 況 : 假 設 n = 3, 則 我 們 有 3 + 1 = 4 個 數, 這 些 數 全 都 少 於 或 等 於 3 = 6 取 其 中 3 個 數 為 4 6, 它 們 均 有 相 同 的 大 於 1 的 公 因 子, 故 此, 任 何 兩 數 均 不 是 互 質 的 但 餘 下 還 須 取 一 個 數, 這 時 不 論 取 1 3 5, 均 會 得 出 兩 數 互 質 ; 取 1 的 話, 則 1 互 質, 取 3 的 話 則 3 或 3 4 互 質 當 n 之 值 較 小 時, 這 個 問 題 看 似 明 顯, 但 當 n 變 得 很 大 時, 我 們 怎 樣 去 一 一 驗 證 呢? 我 們 當 然 不 用 一 一 驗 證, 只 要 利 用 鴿 巢 原 理, 假 設 有 n 個 鴿 巢, 在 第 1 個 鴿 巢 中 放 1 和 在 第 個 鴿 巢 中 放 3 和 4 在 第 3 個 鴿 巢 中 放 5 和 6 在 第 n 個 鴿 巢 中 放 n 1和 n 若 從 這 n 個 鴿 巢 中 隨 意 抽 出 n + 1 個 數, 其 中 最 少 有 一 個 盒 子 的 兩 個 數 均 會 被 抽 出 由 此, 可 知 這 n + 1個 數 中 必 定 有 一 對 連 續 數, 而 明 顯 地 連 續 數 是 互 質 的 這 樣, 問 題 便 輕 易 被 解 決 了! 這 條 問 題 由 匈 牙 利 大 數 學 家 保 羅. 艾 狄 胥 (Paul Erdős, 1913-1996) 向 當 時 年 僅 11 歲 的 波 沙 (Louis Pősa) 提 出, 而 小 波 沙 思 考 不 足 半 分 鐘 便 能 給 出 正 確 的 答 案, 他 的 解 答 又 是 那 麽 巧 妙 和 6
精 采, 令 艾 狄 胥 讚 歎 不 已 路 易 波 薩 (Louis Pősa) 是 匈 牙 利 的 年 青 數 學 家,14 歲 時 已 能 夠 發 表 相 當 深 度 的 數 學 論 文 大 學 還 沒 有 讀 完, 就 已 獲 得 科 學 博 士 的 頭 銜 他 的 媽 媽 是 一 個 數 學 家 他 小 時 受 母 親 的 影 響, 很 愛 思 考 問 題 母 親 看 他 對 數 學 有 興 趣, 也 鼓 勵 他 在 這 方 面 發 展 她 給 他 一 些 數 學 遊 戲, 或 數 學 玩 具 啓 發 他 獨 立 思 考 問 題 在 母 親 的 循 循 善 誘 之 下, 他 在 讀 小 學 時 已 經 自 己 拿 高 中 的 數 學 書 來 看 了 ; 但 真 正 訓 練 他 成 爲 一 個 數 學 家 還 是 匈 牙 利 鼎 鼎 有 名 的 大 數 學 家 保 羅. 艾 狄 胥 (Erdős Pál, 在 英 語 中 作 Paul Erdős), 匈 牙 利 籍 猶 太 人, 發 表 論 文 高 達 1475 篇 ( 包 括 和 人 合 寫 的 ), 是 當 代 發 表 論 文 數 最 多 產 的 數 學 家 ( 僅 次 於 歐 拉 ); 曾 和 511 人 合 寫 論 文 艾 狄 胥 四 處 遊 歷, 探 訪 當 地 的 數 學 家, 與 他 們 一 起 工 作, 合 寫 論 文 他 很 重 視 數 學 家 的 培 訓, 遇 到 有 天 份 的 孩 子, 會 鼓 勵 他 們 繼 續 研 究 艾 狄 胥 經 常 沉 思 數 學 問 題, 視 數 學 為 生 命, 他 經 常 長 時 間 工 作, 老 年 仍 每 日 工 作 19 小 時, 酷 愛 飲 咖 啡, 曾 說 數 學 家 是 將 咖 啡 轉 換 成 定 理 的 機 器 因 為 艾 狄 胥 和 別 人 合 寫 的 論 文 實 在 太 多 了, 所 以 有 人 定 義 了 艾 狄 胥 數 ( 簡 稱 艾 數 ) 艾 狄 胥 的 艾 數 為 0, 與 他 直 接 合 作 寫 論 文 的 人 的 艾 數 為 1, 與 艾 數 為 1 的 人 合 寫 論 文 的 人 艾 數 為, 依 此 類 推 艾 狄 胥 在 數 論 圖 論 等 數 學 分 支 有 很 深 入 的 研 究, 他 把 一 生 獻 給 數 學, 從 來 沒 有 想 到 結 婚, 只 和 自 己 的 母 親 爲 伴, 他 經 常 離 開 自 己 的 祖 國 到 外 國 去 作 研 究 和 演 講 在 東 歐 國 家 裏 像 艾 狄 胥 能 這 樣 隨 意 離 開 自 己 的 國 家 進 出 西 方 世 界 的 數 學 家 並 不 太 多 他 到 處 以 數 學 會 友, 他 在 數 學 方 面 的 多 産, 以 及 在 解 決 問 題 上 有 巧 妙 的 方 法, 使 他 在 世 界 數 學 界 上 享 有 甚 高 的 聲 譽 對 於 他 的 祖 國 來 講, 他 重 要 的 貢 獻 不 單 是 在 數 學 的 研 究, 而 是 他 一 回 到 自 己 的 國 家 就 專 心 致 志 地 培 養 年 青 一 代 的 數 學 家, 告 訴 他 們 外 國 目 前 數 學 家 注 意 的 問 題, 擴 大 他 們 的 視 野 有 一 次 他 從 國 外 回 來 後, 聽 到 朋 友 講 起 有 一 個 很 聰 明 的 小 東 西, 在 小 學 能 解 決 許 多 困 難 的 數 學 問 題, 於 是 就 登 門 拜 訪 這 小 鬼 的 家 庭 波 薩 的 家 人 很 高 興 請 艾 狄 胥 教 授 共 進 晚 餐 在 喝 湯 的 時 候, 艾 狄 胥 就 是 以 例 11 來 考 一 考 坐 在 他 旁 邊 的 1 歲 小 孩 的 能 力 這 小 鬼 不 到 半 分 鐘 的 思 考, 就 很 快 給 出 這 個 問 題 的 解 答 他 的 解 答 又 是 那 麽 巧 妙, 使 得 艾 狄 胥 教 授 歎 服 認 爲 這 是 一 個 難 得 的 英 才, 應 該 好 好 地 培 養 艾 狄 胥 以 後 系 統 地 教 這 小 鬼 數 學, 不 到 兩 年 的 時 間 波 薩 就 成 爲 一 個 小 數 學 家 了 習 題 1. 書 櫃 裡 有 中 文 書 6 本, 數 學 書 4 本, 英 文 書 5 本, 科 學 書 3 本, 從 中 任 選 一 本, 共 有 多 少 種 不 同 的 取 法? 7
. 從 A 地 到 B 地 有 道 路 如 下 圖 所 示 只 能 向 前, 從 A 地 到 B 地 有 多 少 條 不 同 路 線? ( 第 13 屆 屯 門 區 小 學 數 比 賽 個 人 賽 第 15 題 ) 3. 如 果 一 個 四 位 數 與 三 位 數 的 和 是 1999, 並 且 四 位 數 和 三 位 數 是 由 7 個 不 同 數 位 組 成 的, 那 麽 這 樣 的 四 位 數 最 多 有 多 少 個? 4. 如 右 圖, 由 X 點, 經 相 連 的 黑 線, 向 上 或 向 右 行, 到 達 Y 點, 共 有 多 少 條 不 同 的 路 線? ( 第 11 屆 屯 門 區 小 學 數 比 賽 個 人 賽 第 5 題 ) 5. 如 右 圖 所 示,A B C D E 五 個 區 域 分 別 用 紅 藍 黃 白 綠 五 種 顔 色 中 的 某 一 種 著 色. 如 果 使 相 鄰 的 區 域 著 不 同 的 顔 色, 問 有 多 少 種 不 同 的 著 色 方 式? 6. 在 1 至 500 中, 不 含 數 字 0 1 的 數 共 有 多 少 個? 7. 用 1 元 元 5 元 的 硬 币 凑 成 100 元, 共 有 多 少 种 不 同 的 凑 法? 8. 從 3 4 5 7 9 這 6 個 數 學 中, 取 個 數 寫 成 分 數, 共 有 多 少 個? 其 中 真 分 數 有 多 少 個? 最 簡 分 數 又 有 多 少 個? 9. 10 名 運 動 員 進 行 乓 乓 球 賽 ( 每 局 11 分 賽 制 ), 每 兩 名 運 動 動 員 要 比 賽 一 場, 每 場 比 賽 3 局 勝, 全 部 比 賽 結 束 後, 所 有 各 局 比 賽 最 高 分 數 為 15:13, 那 麼, 最 少 有 多 少 局 的 比 分 相 同? 10. 下 圖 列 出 香 港 南 京 和 北 京 之 間 的 交 通 方 法, 現 在 由 南 京 出 發, 再 回 南 京, 途 中 須 經 過 香 港 但 不 可 經 過 南 京, 又 不 准 走 重 複 的 路 線, 問 共 有 多 少 種 不 同 的 去 法?( 第 十 屆 屯 門 區 小 學 數 比 賽 個 人 賽 第 5 題 ) 北 京 乘 飛 機 乘 火 車 乘 火 車 南 京 乘 飛 機 11. 1A 班 的 同 學 要 從 8 名 候 選 人 中 選 出 若 干 位 同 學 成 為 班 會 幹 事, 如 果 每 個 同 學 只 能 投 票 任 選 兩 名 候 選 人, 那 麼 班 上 最 少 應 有 作 少 個 學 生, 才 能 保 證 必 有 兩 個 或 以 上 的 同 學 投 相 同 兩 名 候 選 人 的 票? 乘 飛 機 乘 火 車 香 港 乘 船 1. 紅 黃 藍 綠 的 球 分 有 3 5 7 個 混 在 一 起 在 黑 暗 裡 看 不 見 的 情 況 下, 想 從 這 些 球 中 取 出 兩 對 不 同 顏 色 的 球, 問 最 少 要 取 出 多 少 個 球 才 能 保 證 達 到 要 求? 8
答 案 1. 按 加 法 原 理, 取 法 共 有 6 + 4 + 5 + 3 = 18 種. 將 路 線 圖 稍 作 整 理, 得 右 圖 : 雖 然 點 數 不 少, 但 可 走 的 路 線 也 不 是 很 多, 我 們 利 用 樹 形 圖 ( 下 圖 ) 去 數 路 線 : 圖 中 括 號 的 數 字 顯 示 從 A 點 走 到 B 點 的 可 能 走 法, 所 以 共 有 1 + + + 4 + 4 = 13條 路 線 3. 依 題 意 得 出 下 列 算 式 : 1 A B C + D E F 1 9 9 9 由 於 1 已 定, 相 應 的 8 也 就 不 能 用 ( 因 為 1 + 8 = 9) 明 顯 地, 這 算 式 沒 有 進 位 這 樣, 對 於 D 來 說, 有 3 4 5 6 7 9 共 7 種 選 擇 (D 不 能 取 0, 否 則 不 是 三 位 數 ), 每 一 種 選 擇 都 有 相 應 的 D 對 於 E 來 說, 在 剩 下 的 數 中 有 6 種 選 擇, 每 一 種 選 擇 都 有 相 應 的 B; 如 果 D 選 了, 那 麼,A 必 定 是 7, 這 時,E 只 有 6 個 可 能 最 後, 對 於 F 來 說, 在 剩 下 的 數 中 有 4 種 選 擇, 每 一 種 選 擇 都 有 相 應 的 C 最 後, 根 據 乘 法 原 理, 共 有 7 6 4 = 168 種 4. 這 是 一 題 稍 加 改 變 的 數 路 線 問 題 由 於 有 些 路 口 不 通, 依 例 5 得 下 圖 : 所 以, 共 有 4 條 不 同 路 線 9
5. 對 這 五 個 區 域, 我 們 分 五 步 依 次 給 予 著 色 : I. 區 域 A 共 有 5 種 著 色 方 式 ; II. 區 域 B 因 不 能 與 區 域 A 同 色, 故 共 有 4 種 著 色 方 式 ; III. 區 域 C 因 不 能 與 區 域 A,B 同 色, 故 共 有 3 種 著 色 方 式 ; IV. 區 域 D 因 不 能 與 區 域 A,C 同 色, 故 共 有 3 種 著 色 方 式 ; V. 區 域 E 因 不 能 與 區 域 A,C,D 同 色, 故 共 有 種 著 色 方 式 於 是, 根 據 乘 法 原 理 共 有 5 4 3 3 = 360 種 不 同 的 著 色 方 法 6. 在 一 位 數 中, 不 含 數 字 0 1 的 數 共 有 8 個, 即 3 4 5 6 7 8 9 在 二 位 數 中, 個 位 不 含 0 1 有 8 個 可 能, 十 位 不 含 0 1 也 有 8 個 可 能, 所 以 不 含 數 字 0 1 的 二 位 數 有 8 8 = 64 個 在 三 位 數 中, 個 位 不 含 0 1 有 8 個 可 能, 十 位 不 含 0 1 也 有 8 個 可 能, 百 位 不 含 0 1 的 只 有 3 個 可 能 ( 3 4), 所 以 不 含 數 字 0 1 的 三 位 數 有 8 8 3 = 19 個 所 以, 按 加 法 原 理, 在 1 至 500 間, 不 含 數 字 0 1 的 數 共 有 8 + 64 + 19 = 64 7. 處 理 這 樣 的 問 題, 我 們 應 該 先 分 類 再 應 用 加 法 原 理 : I. 只 用 一 種 硬 幣 去 組 合 100 元 有 3 種 方 法, 即 用 100 個 1 元 或 50 個 元 或 0 個 5 元 ; II. 1 元 和 元 的 組 合 : 其 中 元 的 個 數 可 以 從 1 枚 到 49 枚 均 可, 有 49 種 方 法 ; III. 1 元 和 5 元 的 組 合 : 其 中 5 元 的 從 1 枚 到 19 枚 均 可, 有 19 種 方 法 ; IV. 元 和 5 元 的 組 合 : 其 中 5 元 的 有 4 6 18 共 9 種 方 法 ; V. 1 5 元 的 組 合 : 因 爲 5 = 1+, 若 果 用 19 個 5 元 組 成 95 元, 那 麼 最 後 5 元 的 組 合 可 以 是 1 + = 1 3 + = 5, 故 此 有 個 可 能 10 = 5 = 1 + 4, 以 18 個 5 元 組 成 90 元, 最 後 的 10 元 可 以 是 1 + 4 = 1 4 + 3 = 1 6 + = 1 8 + 1 = 10, 有 4 個 可 能 15 = 1+ 7, 以 17 個 5 元 組 成 85 元, 這 樣 最 後 的 15 元 可 以 是 1 + 7 = 1 3 + 6 = 1 5 + 5 =... = 1 13 + 1 = 15, 共 有 7 種 可 能 ; 我 們 會 發 現, 除 去 n 5元 以 外, 組 成 餘 額 ( 100 5n) 的 可 能 組 合 恰 好 等 於 可 以 使 用 最 多 元 的 個 數! 由 於 95 = 1+ 47, 故 此, 以 1 個 5 元, 餘 下 的 95 元 用 1 元 和 元 組 成 的 方 法 共 有 47 個, 所 以 用 1 5 元 組 成 100 元 的 方 法 共 有 + 4 + 7 + 9 + 1 + 14 + 17 + 19 + + 4 + 7 + 9 + 3 + 34 + 37 + 39 + 4 + 44 + 47 = 461 種, 分 類 再 相 加 : 共 有 3 + 49 + 19 + 9 + 461 = 541 種 方 法 8. 從 這 6 個 數 中 取 出 個 數 寫 成 分 數 時, 選 分 子 或 分 母 時 會 有 6 種 選 法, 然 後, 決 定 了 分 子 或 分 母 後, 再 選 1 數, 會 有 5 種 選 法, 根 據 乘 法 原 理, 這 樣 的 分 數 有 6 5 = 30 個 6 5 根 據 握 手 的 例 子, 在 這 樣 的 分 數 中, 真 分 數 和 假 分 數 各 佔 一 半, 有 = 15 個 3 在 真 分 數 中, 和 都 不 是 最 簡 分 數, 所 以 最 簡 分 數 應 有 15 = 13 4 9 10
10 9 9. 根 據 乘 法 原 理,10 名 運 動 員 共 賽 = 45 場 比 賽, 每 場 比 賽 最 少 賽 局, 所 以 最 少 共 賽 90 場 比 賽 每 局 比 賽 可 出 現 的 賽 果 為 0:11 1:11 9:11 等 10 個 可 能, 若 果 出 現 deuce, 則 可 能 的 比 分 為 10:1 11:13 1:14 13:15 等 4 個 可 能 90 所 以 每 局 同 分 的 情 況 最 少 有 [ ] + 1 = 7 場 14 10. 這 是 一 條 很 有 趣 而 且 充 滿 陷 阱 的 題 目, 除 了 要 使 用 加 法 原 理 和 和 乘 法 原 理 外, 還 要 很 小 心 地 處 理 個 給 予 的 條 件 ; 一, 不 可 經 過 南 京 ; 二, 不 准 走 重 複 的 路 線 這 樣, 有 以 下 5 個 可 能 的 路 線 : I. 南 京 香 港 南 京 從 南 京 到 香 港 有 3 種 不 同 的 走 法, 回 程 不 淮 重 複 路 線 ( 也 就 是 說, 若 果 乘 飛 機 從 南 京 到 香 港, 回 程 就 不 能 乘 飛 機 了 ; 因 此, 可 選 擇 的 回 程 方 法 必 須 減 少 1 種 ), 只 有 種 走 法, 所 以 有 3 = 6 種 走 法 II. 南 京 北 京 香 港 南 京 從 南 京 到 北 京 有 種 不 同 的 走 法, 再 到 香 港 有 種 不 同 的 走 法, 最 後 返 回 南 京 有 3 種 法, 所 以 共 有 3 = 1 種 不 同 的 走 法 III. 南 京 香 港 北 京 南 京 這 個 情 況 與 上 相 同, 故 有 3 = 1 種 不 同 的 走 法 好 了, 上 述 3 種 是 正 常 的 情 況 由 於 不 走 回 頭 路 這 條 件 容 許 了 以 下 種 不 正 常 的 走 法 : IV. 南 京 北 京 香 港 北 京 香 港 南 京 從 南 京 到 北 京 有 種 走 法, 北 京 到 香 港 也 有 種 走 法, 但 再 回 北 京, 由 於 先 前 已 選 了 火 車 或 飛 機, 回 程 時 不 能 選 擇 相 同 的 走 法, 所 以 只 得 1 種 走 法 ; 同 理, 再 由 北 京 回 南 京 也 只 有 1 種 走 法 所 以 共 有 1 1 = 4 種 不 同 的 走 法 V. 南 京 香 港 北 京 香 港 北 京 南 京 與 上 述 相 同 的 想 法, 共 有 3 ( 1) (3 ) = 1 種 不 同 的 走 法 最 後, 共 有 6 + 1 + 1 + 4 + 1 = 46 種 不 同 的 走 法 11. 解 決 這 條 題 目 的 關 鍵, 就 是 要 設 計 出 給 當 的 鴿 巢 因 為 每 個 同 學 只 能 從 8 名 候 選 人 中 任 選 人 來 投 票, 所 以, 選 舉 方 法 的 數 目 就 是 鴿 巢 的 數 目 了 為 清 楚 地 說 明 每 個 同 學 可 能 的 選 擇, 將 8 名 候 選 人 名 為 A B C D E F G H, 這 樣, 可 能 的 結 果 如 下 : A B C D E F G H A AB AC AD AE AF AG AH B BA BC BD BE BF BG BH C CA CB CD CE CF CG CH D DA DB DC DE DF DG DH E EA EB EC ED EF EG EH F FA FB FC FD FE FG FH G GA GB GC GD GE GF GH H HA HB HC HD HE HF HG 由 於 選 擇 AB 與 BA 是 一 樣 的, 所 以 共 有 1 + + 3 + 4 + 5 + 6 + 7 = 8 種 可 以 的 選 擇 如 果 把 8 種 不 同 的 選 擇 看 作 8 個 鴿 巢, 那 麼 同 一 個 鴿 巢 的 同 學 所 選 的 兩 名 候 選 人 就 會 相 同, 按 原 理 (I),1A 班 最 少 要 有 8 + 1 = 9 人 11
1. 從 最 壞 的 情 況 去 想, 先 取 出 紅 黃 藍 綠 色 的 球 各 1 個, 然 後 一 直 取 出 綠 色 球, 這 樣, 從 第 5 個 取 出 的 球 就 能 配 成 一 對 綠 色 球 ; 但 直 到 最 後 1 個 綠 色 被 抽 出 卻 仍 只 得 一 對 同 顏 色 的 球 最 後, 第 11 個 球 被 抽, 不 論 是 甚 麼 顏 色 也 能 組 成 第 二 對 同 顏 色 的 球 所 以, 最 少 要 取 出 11 個 球 才 能 保 證 達 到 要 求 參 考 文 獻 1. 李 英 哲 主 編 (1995) 新 編 小 學 數 學 應 用 題 大 全 六 年 級 分 冊 沈 陽 : 沈 陽 出 版 社. 師 達 主 編 (003) 新 概 念 學 科 競 賽 完 全 設 計 奧 賽 急 先 鋒 題 庫 小 學 五 年 級 數 學 北 京 : 中 國 少 年 兒 童 出 版 社 3. 張 君 達 主 編 (199) 北 京 數 學 奧 林 匹 克 小 學 材, 五 年 級 試 用 北 京 : 北 京 師 範 學 院 出 版 社 4. http://zh.wikipedia.org/w/index.php?title=%e9%b4%bf%e5%b7%a%e5%8e%9f%e7%9 0%86&variant=zh-hk 5. http://zh.wikipedia.org/w/index.php?title=%e4%bf%9d%e7%bd%97%c%b7%e5%9f%8 3%E5%B0%94%E5%BE%B7%E4%BB%80&variant=zh-tw 6. http://zhidao.baidu.com/question/68989.html 7. http://www.aoshu.com/sansi/daoyin4/006-11-1/aoshu4786d830b163.shtml 8. http://www.math15.com/mo/70.html 9. http://news.juren.com/00711/4960.html 10. http://www.608088.com/show-1505-1.html 顧 問 老 師 : 梁 志 明 謝 慧 黃 萬 安 黃 偉 智 楊 振 雄 袁 仲 強 1