組合學/激勵示例和問題

一個 8x8 的城市網格，其中一條從 A 到 B 的路徑突出顯示。

1. 想象一下一個小型城鎮中心，街道形成一個 8x8 的正方形網格，如示意圖所示。從城鎮中心的某個角落 (A) 到對角線上的另一個角落 (B) 有多少種旅行方式？

2. 在一個棋盤上，有多少種方式可以放置 8 個車，使它們彼此之間不攻擊？

3. 一個講座班至少需要多少名學生才能確保至少有兩名學生生日相同的機率至少為 1/2？

4. 給定 n 個信件和 n 個已貼地址的信封，有多少種方式可以將信件放入信封中，使沒有一個信件在正確的信封中？ (答案是最接近 ${\frac {n!}{e}}$ 的整數).

5. 柯克曼女學生問題：15 個女學生每天分成 5 個小組，每組 3 人。為女學生安排一週的步行路線，使在這段時間內，每對女學生只在小組中一起步行一次。^[1] (一個解決方案提供這裡.)

6. 尤拉軍官問題：給出 36 名軍官，他們屬於 6 個團，並擔任 6 個軍銜。(沒有兩個軍官擁有相同的軍銜和團，如果他們的軍銜相同，那麼他們的團就不同，反之亦然。)這些軍官是否可以排列成一個 6x6 的陣列，使在陣列的任何一行中，每個團和每個軍銜都恰好出現一次？(答案是不可以。)^[2]

7. 拉姆齊遊戲：這個兩人遊戲需要在一張空白紙上畫出 6 個點(其中沒有 3 個點在同一條線上)，然後為玩家提供不同顏色的鉛筆。玩家現在輪流透過畫線連線點來連線點。第一個形成單色三角形的玩家輸掉。問題是：這個遊戲是否可以永遠以平局結束？(答案是不可以。參見這裡.)