離散數(shù)學(xué)趣味題目
1,Catalan數(shù)
飯后，姐妹洗碗，妹妹把姐姐洗過的碗一個一個放進碗櫥摞成一摞。共有n個兩兩相異的碗，洗前也摞成一摞，也許因為妹妹貪玩，碗拿進櫥子不及時，姐姐就把洗過的碗摞在傍邊：
-
- - - -
— — - -
- - — —
（1）待洗 （2）待摞 （3）已摞
問最后小妹摞起的碗摞可能有幾種方式？
這個題目有個同解題是這樣的：
一隊不同的汽車行進在大街上，它們可以在任何時刻拐進一個死胡同里去加油，然后再出來加入隊伍。問你最后出城時汽車隊列有多少種可能形式？
呵呵，大家想想，有意思呢！
[簡短分析]
這是個有趣的組合問題。組合數(shù)學(xué)是離散數(shù)學(xué)的一部分，研究的是組合計數(shù)問題。圖論原來也是組合數(shù)學(xué)的一部分，后來才分家的.：）。組合計數(shù)的一個指導(dǎo)性技巧是，如果對于一個過程的計數(shù)不好研究，就可以找一個和它有一一對應(yīng)的過程，而且該過程相對很好研究，這不是很美嗎？
你看看，如果碗有n個，姐姐每方下一個，就畫一個“（”，妹妹如果摞一個，就畫一個“）”，如果妹妹不貪玩，剛放下就能放好，串就是“（）（）（）……（）”，對吧？現(xiàn)在你來考慮一下，下次我說答案：）。
汽車車隊也是如此，車進了胡同就畫“（”，出來時再畫“）”，而沒有進胡同的就是“（）”，呵呵，所以同解呢。
離散的問題，技巧性很大，初看問題的解沒有規(guī)律，仿佛量體裁衣般的，但也有指導(dǎo)性的思路對吧？
2，拉姆賽問題
樸素的方式敘述：
r（p，q）是任意給的人群中必有p人相識或必有q人彼此不相識的人群人數(shù)之最小值。例如，r（3，3）=6，就是說，任意個的人群，最少6個人，一定可滿足其中3個人相識，或3個人互相不認(rèn)識。r（p，q）就稱為拉姆賽數(shù)。
圖論的方式敘述：
Any p，q in N,把一個完全圖G用紅與藍兩色進行邊涂色，每條邊一種顏色，其結(jié)果或者有一個紅色p邊形，連同其全部對角線皆為紅色，或者有一個藍色q邊形，連同其全部對角線皆為藍色，G最小的頂點數(shù)，能保證出現(xiàn)上述結(jié)果，就是拉姆賽數(shù)r（p，q）。
經(jīng)過幾代人的努力，加上計算機的幫忙，現(xiàn)在人類求的9個非平凡的拉姆賽數(shù)：
r（3，3）=6，r（3，4）=9，r（3，5）=14
r（3，6）=18，r（3，7）=23，r（3，8）=28
r（3，9）=36，r（4，4）=18，r（4，5）=25
呵呵，你來試試，你能給出哪些拉姆賽數(shù)的推理過程？
[背景趣聞]
關(guān)于求拉姆賽數(shù)的艱巨性，著名匈牙利數(shù)學(xué)家厄爾多斯曾用下面的話比喻：
某年某月某日，一伙外星強盜入侵地球，威脅道，若不能一年內(nèi)求出r（5，5），他們將滅絕人類！面對如此生死關(guān)頭，人類應(yīng)當(dāng)召集全球所有的數(shù)學(xué)家和計算機專家，夜以繼日的計算r（5，5），以求人類免于滅頂之災(zāi)；如果外星人要我們求得r（6，6），我們就別無選擇了，干脆直接開戰(zhàn)，放手一搏：）。
3，夢中情人
約翰的夢中情人長著金黃色的頭發(fā)，藍藍的眼睛，纖細(xì)的身子，高高的個子。他認(rèn)識阿黛爾，貝蒂，卡洛爾和多麗絲四位小姐，其中一位是約翰的夢中情人。（1）只有三位小姐是藍眼睛和細(xì)身材。（2）只有兩位是黃頭發(fā)和高個子（3）只有兩位是細(xì)身材和高個子。（4）只有一位是藍眼睛和黃頭發(fā)（5） 阿黛爾和貝蒂眼睛顏色相同。（6）貝蒂和卡洛爾頭發(fā)顏色相同（7）卡洛爾和多麗絲身材不同（8）多麗絲和阿黛爾身高相同。四位中誰是約翰的夢中情人？
[簡單分析]
呵呵，顯然這是個數(shù)理邏輯問題了�？梢越⑿问交哪Ｐ蛠矸治�，也可以用樸素的推理過程來做。很有意思的，這是離散數(shù)學(xué)的魅力！
http://www.dgxbdz.com/【離散數(shù)學(xué)趣味題目】相關(guān)文章：
離散數(shù)學(xué)-圖論基礎(chǔ)復(fù)習(xí)10-09
離散數(shù)學(xué)-歐拉圖復(fù)習(xí)10-09
離散數(shù)學(xué)-哈密頓圖復(fù)習(xí)10-09
離散數(shù)學(xué)-二部圖復(fù)習(xí)10-09
小學(xué)生數(shù)學(xué)手抄報：趣味數(shù)學(xué)題目08-22
離散數(shù)學(xué)分層次實驗教學(xué)設(shè)計應(yīng)用論文03-26
趣味結(jié)婚對聯(lián)02-22
趣味對聯(lián)故事02-23
趣味對聯(lián)薈萃10-15