Chessboards, Hats, and Chinese Poetry : Some Rigorous and Not-So-Rigorous Mathematical Results 數裡有詩？ 詩裡有數！ C. L. Liu 　劉炯朗.

Presentation on theme: "Chessboards, Hats, and Chinese Poetry : Some Rigorous and Not-So-Rigorous Mathematical Results 數裡有詩？ 詩裡有數！ C. L. Liu 　劉炯朗."— Presentation transcript:

1 Chessboards, Hats, and Chinese Poetry : Some Rigorous and Not-So-Rigorous Mathematical Results
數裡有詩？ 詩裡有數！ C. L. Liu 　劉炯朗

2 Hats Chessboards Poetry Mathematics

3 It all begins with a chessboard

4 Covering a Chessboard 21 domino 88 chessboard Cover the 88 chessboard with thirty-two 21 dominoes

5 Enumeration …… Number Theory, Probability, Statistics, Physics, Chemistry, …

6 Archimedes’ Stomachion Puzzle
17,152 ways How do I love thee, Let me count the ways. － Elizabeth Barrett Browning

7 Enumeration 一蓑一笠一扁舟 一丈竿頭一只鈎 一水一拍似一唱 一翁獨釣一江秋
一卷煙，一片山，幾點雲影， 一道水，一條橋，一支櫓聲， 一林松，一叢竹，紅葉紛紛； 　　　滬杭車中∣徐志摩 一蓑一笠一扁舟 一丈竿頭一只鈎 一水一拍似一唱 一翁獨釣一江秋 　　　一字詩∣康熙

8 Enumeration …… Symmetry : Polya’s Theory of Counting
Tyger! Tyger! Burning bright, In the forests of the night. What immortal hand or eye Could frame thy fearful symmetry? － William Blake

9 對 聯 　天對地　雨對風 　爸爸對公公 　白板對紅中 　雷隱隱　雨濛濛 　小姑喚大嫂 　晚輩稱尊翁 　人間清暑殿 　天上廣寒宮

10 對 聯 落花人獨立 微雨燕雙飛 又是春殘也 如何出翠幃 落花人獨立 微雨燕雙飛 寓目魂將斷 經年夢亦非 那堪愁向夕 蕭颯暮蟾輝
　 　　《春殘》　翁宏 落花人獨立 微雨燕雙飛

11 對 聯 無可奈何花落去 似曾相識燕歸來 一曲新詞酒一杯 去年天氣舊池臺 夕陽西下幾時回 無可奈何花落去 似曾相識燕歸來 小園香徑獨徘徊
　 《浣溪沙》　晏殊 無可奈何花落去 似曾相識燕歸來

12 對 聯 一二三四五六七 忠孝仁愛禮義廉 兆 漢 　贈劉兆漢校長 億萬千百 唐元明清 （忘八） （無恥）

13 迴 文 Palindrome Madam Able was I ere I saw Elba

14 迴 文 詩 潮迴暗浪雪山傾 遠浦漁舟釣月明 橋對寺門松徑小 檻當泉眼水波清 迢迢綠樹江天曉 靄靄紅霞海日晴 遙望四天雲接水 碧波千點數鷗輕

15 迴文 對聯 中山歸隱客隱歸山中 斗六高材生材高六斗 上海自來水來自海上

16 A Truncated Chessboard
21 domino Truncated 88 chessboard Cover the truncated 88 chessboard with thirty-one 21 dominoes

17 Proof of Impossibility
21 domino 人有悲歡離合， 月有陰晴圓缺， 此事古難全。 　　水調歌頭－蘇軾 Truncated 88 chessboard Truncated 88 chessboard Impossible to cover the truncated 88 chessboard with thirty-one dominoes.

18 Proof of Impossibility
Impossible to cover the truncated 88 chessboard with thirty-one dominoes. There are thirty-two white squares and thirty black squares. A 2 1 domino always covers a white and a black square.

19 Proof of Impossibility
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Impossible to cover the truncated 88 chessboard with thirty-one dominoes. There are thirty-two white squares and thirty black squares. A 2 1 domino always covers a white and a black square.

20 Modulo-2 Arithmetic 1 2 3 4 5 6 ….. even odd white black on off

21 Coloring the Vertices of a Graph
vertex edge

22 2 - Colorability A necessary and sufficient condition :
No circuit of odd length

23 3 - Colorability

24 3 - Colorability The problem of determining whether a graph is 3-colorable is NP-complete. ( At the present time, there is no known efficient algorithm for determining whether a graph is 3-colorable.)

25 Fermat’s Last Theorem x n + y n = z n
2-colorability is tractable, 3-colorability is unknown. 2-satisfiability is tractable, 3-satisfiability is unknown. Fermat’s Last Theorem x n + y n = z n n = 2 there are integer solutions = 5 2 n  3 no integer solution

26 寡 多 三 狀元 榜眼 探花 金牌 銀牌 銅牌 三振出局 三寸金蓮 三言兩語 天無三日晴，地無三里平 孟母三遷 三過家門而不入
　適中 狀元 榜眼 探花 金牌 銀牌 銅牌 三振出局 　寡 三寸金蓮 三言兩語 天無三日晴，地無三里平 　多 孟母三遷 三過家門而不入 一日不見如隔三秋 彼得三次不認耶穌

27 4 - Colorability : Planar Graphs
Kuratowski’s subgraphs All planar graphs are 4-colorable. How to characterize non-planar graphs ? Genus, Thickness, …

28 A Defective Chessboard
Triomino Any 88 defective chessboard can be covered with twenty-one triominoes

29 Defective Chessboards
Any 88 defective chessboard can be covered with twenty-one triominoes Any 2n2n defective chessboard can be covered with 1/3(2n2n -1) triominoes Prove by mathematical induction

30 Mathematical Induction
The first domino falls. If a domino falls, so will the next domino. All dominoes will fall ! To see the world in a grain of sand, And heaven in a wild flower, Hold infinity in the palm of your hand, And eternity in an hour.                        　　－ William Blake

31 Proof by Mathematical Induction
Any 2n2n defective chessboard can be covered with 1/3(2n2n -1) triominoes Basis : n = 1 Induction step : 2 n+1 2 n 2 n+1

32 The Wise Men and the Hats
…… If there are n wise men wearing white hats, then at the nth hour all the n wise men will raise their hands. Basis : n =1 At the 1st hour, the only wise man wearing a white hat will raise his hand. Induction step : Suppose there are n+1 wise men wearing white hats. At the nth hour, no wise man raises his hand. At the n+1st hour, all n+1 wise men raise their hands.

33 The Wise Men and the Hats
One white hat 1st hour : hand raised Two white hats 1st hour : silence 2nd hour : hands raised Five white hats 1st hour : silence 2nd hour : silence 3rd hour : silence 4th hour : silence 5th hour : hands raised 以銅為鑑，可正衣冠； 以古為鑑，可知興替； 以人為鑑，可明得失。 　　　　　新唐書－魏徵傳

34 I Don’t Know x • y x + y x = 4 , y = 13
Two Integers, 1 < x, y < 51 x • y x + y I don’t know. I knew you would not know. However, neither do I. Now, I know. Now, I know. Now, I know. x = 4 , y = 13

35 Sound of Silence 水泉冷澀弦凝絶，凝絶不通聲漸歇， 別有幽愁暗恨生，此時無聲勝有聲。 琵琶行－白居易
　　　　　　　　　　　琵琶行－白居易 To communicate through silence is a link between the thoughts of man.                          － Marcel Marceau  Hello darkness, my old friend, I've come to talk with you again.           The Sound of Silence － Simon & Garfunkel 

36 Information Theory Measure of Information
Self Information : I (x) = - lg p (x) Mutual Information : I (x, y) = - lg p (x) + lg p (x | y)

37 Another Hat Problem No strategy In the worst case, all men were shot.
In the worst case, half of the men were shot. Design a strategy so that as few men will die as possible.

38 Another Hat Problem 0 1 1 0 …….… 1 1 1 0 .……… 1 = 1 1 0 .……… 1 = 0 1
……….. …….… 　.……… = 1 ……… = 0 1 0 ……… = 1 1

39 Coding Theory Representation of information in alternate forms for
efficiency reliability security Algebraic Coding Theory Cryptography

40 山在虛無縹緲間 四　猜唐詩一句 欲罷不能 四　猜成語一句

41 　贈胡萬川主任 斗酒十千同醉月芳華廿九共惜花 惜花春早起 愛月夜遲眠　 十千為萬

42 Yet, Another Hat Problem
A person may say, 0, 1, or P(Pass) Winning : Nobody is wrong, at least one person is right Losing : One or more person is wrong Strategy 1 : Everybody guesses Probability of winning = 1/8 Strategy 2 : First and second person always say P. Third person guesses Probability of winning = 1/2

43 Strategy 3 : More people ? Best possible ?
observe call 00 01 10 11 1 P pattern call 000 001 010 011 100 101 110 111 PP1 P1P 0PP 1PP P0P PP0 More people ? Best possible ? Probability of winning = 3/4 Generalization : 7 people, Probability of winning = 7/8 Application of Algebraic Coding Theory

44 A Coin Weighing Problem
Twelve coins, possibly one of them is defective ( too heavy or too light ). Use a balance three times to pick out the defective coin.

45 Another Coin Weighing Problem
Thirteen coins, possibly one of them is defective ( too heavy or too light ). Use a balance three times to pick out the defective coin. However, an additional good coin is available for use as reference. Application of Algebraic Coding Theory Adaptive Algorithms Non-adaptive Algorithms

46 Yet, Another Hat Problem
Hats are returned to 10 people at random, what is the probability that no one gets his own hat back ? 張冠李戴

47 Recurrence Relations 1, 1, 2, 3, 5, 8, 13, … fn = fn-1 + fn-2
Fibonacci Numbers bn = 0.92 bn-1 bn = 0.42 bn bn-2 bn = 1.22 bn bn bn-3 b2004 = 0.92 b2003

48 Derangements dn = (n-1) dn-1 + (n-1) dn-2 d1 = 0 d2 = 1
dn : number of derangements of n objects dn = (n-1) dn-1 + (n-1) dn-2 d1 = 0 d2 = 1 d3 = 2 d2 + 2  d1 = 2   0 = 2 d4 = 3 d3 + 3  d2 = 3   1 = 9 …… d10 = 9  d9 + 9  d8 = 1,334,961

49 Derangement of 10 Objects
Number of derangements of n objects Probability

50 頂真格（鈎句，流水句） 雲鬢花顏金步搖 芙蓉帳暖度春宵 春宵苦短日高起 從此君王不早朝 後宮佳麗三千人 三千寵愛在一身
雲鬢花顏金步搖 芙蓉帳暖度春宵　春宵苦短日高起 從此君王不早朝 後宮佳麗三千人 三千寵愛在一身 君臣相顧盡霑衣 東望都門信馬歸　歸來池苑皆依舊 太液芙蓉未央柳　芙蓉如面柳如眉 對此如何不淚垂 　　　　　　　　　 長恨歌∣白居易

51 頂真格（鈎句，流水句） 慟哭六軍俱縞素 衝冠一怒為紅顏 紅顏流落非吾願 逆賊天亡自荒讌 電掃黃巾定黑山 哭罷君親再相見
相見初經田竇家 侯門歌舞出如花 前身合是採蓮人 門前一片橫塘水 橫塘雙槳去如飛 何處豪家強載歸 恨殺軍書抵死催 苦留後約將人誤 相約恩深相見難 一朝蟻賊滿長安 若非壯士全師勝 爭得蛾眉匹馬還 蛾眉馬上傳呼進 雲鬟不整驚魂定 圓圓曲∣吳梅村

52 頂真格（鈎句，流水句） 尋夢？撐一支長篙， 向青草更青處漫溯， 滿載一船星輝， 在星輝斑斕裏放歌， 但我不能放歌，
向青草更青處漫溯， 滿載一船星輝， 在星輝斑斕裏放歌， 但我不能放歌， 悄悄是別離的笙簫； 夏蟲也為我沉默， 沉默是今晚的康橋！ 　　　　　　　 　再別康橋∣徐志摩

53 頂真格（鈎句，流水句） 風雨送春歸， 飛雪迎春到， 已是懸崖百丈冰， 猶有花枝俏。 俏也不爭春， 只把春來報。 待到春花爛漫時，
飛雪迎春到， 已是懸崖百丈冰， 猶有花枝俏。 俏也不爭春， 只把春來報。 待到春花爛漫時， 她在叢中笑。 　　　　　　　 卜算子詠梅∣毛澤東

54 頂真格（鈎句，流水句） 柳色青 柳色青青 青滿城 滿城風雨煙光送 風雨煙光送遠行 遠行君向歸山路 君向歸山路前去 前去離亭芳草青
離亭芳草青無數 無數山 山彎水潺湲 彎水潺湲行路難 行路難時時往還 往還多是名場客 多是名場客行急 行急無論多少程 無論多少程千百 千百人　戀芳春 人戀芳春不似君 不似君家有老親 家有老親常倚閭 常倚閭　望君馬 望君馬到金台下 到金台下桂花香 桂花香報報高堂 高堂正屆稀齡壽 正屆稀齡壽春酒 春酒遲君衣錦傾 遲君衣錦傾金斗 金斗酌 酌春風 春風人共醉 人共醉融融

55 Permutation 1 2 3 4 a b c d Positions Objects

56 Placement of Non-taking Rooks
1 2 3 4 a b c d Positions Objects

57 Permutation with Forbidden Positions
1 2 3 4 a b c d 1 2 3 4 a b c d Positions Positions Objects Objects

58 Placement of Non-taking Rooks
1 2 3 4 a b c d 1 2 3 4 a b c d Positions Positions Objects Objects

59 At Least One Way to Place Non-taking Rooks
1 2 3 4 a b c d Eva Faye Gigi Helen Adam Bob Carl Dan Positions Girls Boys Objects Theory of Matching/Marriage Stable Marriage Monogamic/Polygamic Marriage 願天下有情人，都成眷屬， 是前生註定事，莫錯過了好姻緣。 　　　　　　　　　老殘遊記－劉鶚

60 Stable Marriages unstable stable 3 1 2 4 1 2 3 4 Eva Faye Gigi Helen
Adam 3 1 2 4 Bob Carl Dan Eva Faye Gigi Helen Adam 1 2 Bob 3 Carl 4 Dan Adam Eva Bob Gigi Bob Faye Carl Helen unstable stable

61 Stable Marriages 為有雲屏無限嬌 鳳城寒盡怕春宵 無端嫁得金龜婿 辜負香衾事早朝 嫁得睢塘賈 朝朝誤妾期 早知潮有信
　　　為有∣李商隱 嫁得睢塘賈 朝朝誤妾期 早知潮有信 嫁與弄潮兒 　　　江南曲∣李益

62 Stable Marriages Theorem : There is always a set of stable marriages.
但願人長久　千里共嬋娟 　　　　　　　　水調歌頭－蘇軾 在天願作比翼鳥　在地願為連理枝 　　　　　　　　長恨歌－白居易 在家願作孖公仔　在鑊願為油炸鬼 Theorem : Monogamy is optimal.

63 ！ 數裡有詩 ？ 詩裡有數 ！ ？

64 怎一個愁字了得 尋尋覓覓，冷冷清清， 淒淒慘慘戚戚。 乍暖還寒時候，最難將息。 三杯兩盞淡酒，怎敵他， 晚來風急。
雁過也，正傷心，卻是舊時相識。 滿地黃花堆積，憔悴損， 如今有誰堪摘。 守著窗兒，獨自怎生得黑， 梧桐更兼細雨，到黃昏，點點滴滴。 這次第，怎一個愁字了得。 　　　　　　　　　　　　聲聲慢∣李清照

65 怎一個愁字了得 愁

66 斛量 一斛明珠萬斛愁， 關山漂泊腰肢細。 　　　圓圓曲∣吳梅林 舟載 只恐雙溪舴艋舟， 載不動許多愁。 　　　武陵春∣李清照

67 白髮三千丈， 離愁似個長。 新妝宜面下朱樓， 深鎖春光一院愁。 問君能有幾多愁， 恰似一江春水向東流。 秋浦歌∣李白 春詞∣劉錫禹
　　　　　　秋浦歌∣李白 新妝宜面下朱樓， 深鎖春光一院愁。 　　　　　　春詞∣劉錫禹 問君能有幾多愁， 恰似一江春水向東流。 　　　　　　虞美人∣李後主

68 凝眸處，從今又添，一段新愁。 一懷愁緒，幾年離索。 寂寞深閨，柔腸一寸愁千縷。 一點芭蕉一點愁。 鳳凰台上憶吹簫∣李清照
　　　　　鳳凰台上憶吹簫∣李清照 一懷愁緒，幾年離索。 　　　　　釵頭鳳∣陸游 寂寞深閨，柔腸一寸愁千縷。 　　　　　點絳唇∣李清照 一點芭蕉一點愁。 　　　　　雙調水仙子夜雨∣徐再思

69 與爾同消萬古愁。 　　　　　　將進酒∣李白 一種相思，兩處閒愁。 　　　　　　一剪梅∣李清照

70 2 > 1 怎一個愁字了得 尋尋覓覓，冷冷清清， 淒淒慘慘戚戚。 乍暖還寒時候，最難將息。 三杯兩盞淡酒，怎敵他， 晚來風急。
雁過也，正傷心，卻是舊時相識。 滿地黃花堆積，憔悴損， 如今有誰堪摘。 守著窗兒，獨自怎生得黑， 梧桐更兼細雨，到黃昏，點點滴滴。 這次第，怎一個愁字了得。 　　　　　　　　　　　　聲聲慢∣李清照 2 > 1

71 少年不識愁滋味， 愛上層樓，愛上層樓， 為賦新詞強說愁。   　 而今識盡愁滋味， 欲說還休，欲說還休， 卻道天涼好個秋。 　　　　　　　　　醜奴兒∣辛棄疾

72

73 Concluding Remarks Mathematics is about finding connections, between
specific problems and more general results, and between one concept and another seemingly unrelated concept that really are related. Poetry finds connections between moon and flowers, spring and autumn, orders and chaos, and happiness and sorrow, and weaves them into a fabric of many splendors.

74 Concluding Remarks In the eyes of a mathematician,
In the eyes of a poet, And through their eyes, In our eyes, The world is a beautiful world, And life a beautiful life.

75 An Algebraic Proof Impossible ! (1+y) x i y j (1+x) xi y j y7
. y2 y 1 (1+x+x x7) (1+y+y y7) – 1 - x7y7 = (1+x)  xi y j + (1+y)  x i y j xi yj Impossible ! Let x = -1 y = -1 -2 = 0 1 x x x7 (1+y) x i y j (1+x) xi y j

76 Step 1 Balance Step 2 Balance Imbalance Step 3 Step 3 1 2 3 4 5 6 7 8
G 9 10 11 Balance Imbalance Step 3 Step 3 12 G 10 9

77 Step 1 Step 2 Imbalance Step 3 Balance Step 3 Imbalance 7 G 1 2 3 4 5
6 8 Step 1 Step 2 Imbalance Step 3 Balance 2 1 Step 3 Imbalance

78 Step 1 Imbalance Step 2 Imbalance Step 3 1 2 3 4 5 6 7 8 1 3 4 5 2 6 4

79 Apples and Oranges Apples Apples Oranges Oranges Take one fruit from one box to determine the contents of all three boxes.

80 Derangements A B C a b c

81 Stable Marriages stable stable 3 1 2 4 1 2 3 4 (1) (4) (2) (2) (1) (2)
Eva Faye Gigi Helen Adam 3 1 2 4 Bob Carl Dan Eva Faye Gigi Helen Adam 1 2 Bob 3 Carl 4 Dan (1) Adam Eva (4) (2) Adam Eva (2) (1) Bob Faye (2) (4) Bob Faye (1) (3) Carl Gigi (2) (3) Carl Gigi (1) (3) Dan Helen (1) (4) Dan Helen (1) stable stable

82 Stable Marriages 3 1 2 4 1 2 3 4 Eva Faye Gigi Helen Adam Bob Carl Dan