排列組合

阿基米德的胃痛拼圖(stomachache puzzle)

阿基米德的胃痛拼圖(stomachache puzzle)
國立台中女中數學科賴信志老師/國立台灣師範大學數學系許志農教授責任編輯

摘要:本篇將介紹一道差一點就消失,而且是世界上最古老的拼圖遊戲…胃痛拼圖。

這裡我們將介紹一道差一點就消失,而且是世界上最古老的拼圖遊戲。在加州史丹福大學同步輻射實驗室,古文物復原專家運用紫外光與數位圖像電腦處理技術,讓阿基米德發明的一道遊戲重現天日。

在1998 年10 月30 日,《紐約時報》頭版登了一則報導:紐約佳士得拍賣會上,有一本其貌不揚的古書,以美金 200 萬的高價成交。從外表看,這本書就像是中世紀某位修士的祈禱書,磨損不堪,布滿燒焦、水漬、發霉的痕跡。然而在祈禱文的下方,隱約可看見幾乎被擦拭掉的、傳抄自古代科學家阿基米德的抄本。

四方連塊的正方形拼圖遊戲

四方連塊的正方形拼圖遊戲 (The Puzzle of Tetrominoes)
國立臺中女中數學科賴信志老師/國立臺灣師範大學數學系許志農教授責任編輯

摘要:多方塊的矩形拼圖(Tiling the rectangle)是一個有趣而常見的拼圖遊戲,它的基本規則是:每一種等面積的多方連塊至少都用一個來拼一個矩形。「四方連 塊」(tetrominoes)是指四個單位正方形以邊與邊相連接而成,並扣除圖形旋轉、鏡射,所形成之五種不同形狀的幾何平面圖形。本文探討四方連塊的 拼圖問題。

多方塊的矩形拼圖(Tiling the rectangle)是一個有趣而常見的拼圖遊戲,它的基本規則是:每一種等面積的多方連塊至少都用一個來拼一個矩形。「四方連塊」(tetrominoes)是指四個單位正方形以邊與邊相連接而成,並扣除圖形旋轉、鏡射,所形成之五種不同形狀的幾何平面圖形,如下圖所示,分別為 L 型、Z 型、O 型、I 型、T 型。

Fubini 原理

Fubini 原理
國立高雄大學應用數學系游森棚副教授/國立高雄大學應用數學系游森棚副教授責任編輯

Fubini 原理
觀察以下的矩陣:

\(\displaystyle\left[\begin{array}{cccccc}1&6&0&4&1&1\\2&0&1&5&0&2\\0&0&7&0&3&3\\2&4&1&2&0&0\end{array}\right]\)

請問所有數字和一共多少?我們可以有系統一點,先求每一橫列的和,得到 \(13, 10, 13, 9\),再把這四個和相加得到 \(13 +10 +13 +9 = 45\)。或者,先求每一直行的和,得到 \(5, 10, 9, 11, 4, 6\),相加得到 \(5+10+9+11+4+6 = 45\)。換句話說,

\(\displaystyle\sum^4_{i=1}\sum^6_{j=1}{a_{ij}}=\sum^6_{j=1}\sum^4_{i=1}{a_{ij}}\)

以上的想法是非常容易的,但這就是 Fubini 原理。

排容原理(Principle of Inclusion and Exclusion)(一)

排容原理(Principle of Inclusion and Exclusion)(一)
國立高雄大學應用數學系游森棚副教授責任編輯

排容原理( Principle of Inclusion and Exclusion, 簡稱PIE),是高中排列組合的第三個,也是最後一個基礎原理(前兩個是「乘法原理(Rule of Product)」與「加法原理 (Rule of Sum)」) 亦有一些書按英文順序直譯為容斥原理(或許這是比較好的翻譯)。

排容原理中的「排」 是指「排除」,「容」是指「容納」。 基本上的想法就是「多退少補」 — 多算的要排除,少算的要加進來。從原文亦可以清楚看出這個原理的精神。

Pages