###### tags: `數學問題`
$\begin{align}\end{align}$
# 排列組合

### 1. 復華數培 二試第12題
萊特大兵必須將一組4個數字的密碼ABCD傳回總部，但密碼若被暗中攔截而識破的話，那就糟糕了！為了安全考量，他傳送了以下9組4位數字的密碼，如果每組數字中至少有一個數字出現在正確的位置，則正確的密碼為何？
$\boxed{2186}\;\boxed{4351}\;\boxed{4521} \;\boxed{5127}\;\boxed{5916}\;\boxed{6384} \;\boxed{6924}\;\boxed{8253}\;\boxed{8517}$

---
(1) 若千位2，將千位其他數字，與2在其他位置的情況劃掉；
$\boxed{2186}\;\boxed{\not{4}351}\;\boxed{\not{4}5\not{2}1} \;\boxed{51\not{2}7}\;\boxed{5916}\;\boxed{6384} \;\boxed{6924}\;\boxed{8253}\;\boxed{8517}$
由4521、5127知百位5，個位7，與6924矛盾；(2)若千位4，由6384、6924知百位十位為32或98，與8253不合；(3)若千位5，考慮4351，4521，8253，8517四數，其中有1，2，3，7四個數字可選擇，由4521、8517知1不合，由4351、8253知3不合，由8517知個位數字為7，但由4351、8253的百位數字知不合，因此(3)情況不合。(4)若千位6，

## 鴿籠原理

*注意重點：(1)如何構造籠子；⑵ 多用於證明存在性的問題；

### 構造籠子導致不存在性的矛盾。
---

1. $在邊長為2的正三角形中任意放5個點，證明：至少有兩個點之間的距離不大於1。$
2. $在邊長為6的正三角形中任意放11個點，證明：至少有兩個點之間的距離小於或等於\sqrt{3}$
3. $把301個1\times1的正方形放入一個10\times10的正方形內，證明：$
$(1).存在1個點，至少被4個1\times1的正方形所覆蓋$
$(2).存在1個點，至多被3個1\times1的正方形所覆蓋$

---
## $6$ 顆不同的球，放入 $4$ 個不同的箱子中，每箱至少 $1$ 球。

---

正面算：
$(3，1，1，1)$ 和 $(2，2，1，1)$ 兩種情形，
$$C^6_3C_1^3C_1^2C_1^1\cdot\frac{1}{3!}\cdot4!+C_2^6C_2^4C_1^2C_1^1\cdot\frac{1}{2!2!}\cdot 4!=480+1080=1560$$反面算：
利用排容原理，全部 $-$ 至少有 $1$ 個空箱 $+$ 至少有 $2$ 個空箱 $-$ 至少有 $3$ 個空箱
$$4^6-C_1^4\cdot 3^6+C_2^4\cdot 2^6-C_3^4\cdot 1^6=4096-2916+384-4=1560$$

---
## $7$ 顆不同的球，放入 $3$ 個相同的箱子。
---

$(7,0,0),(6,1,0),(5,2,0),(5,1,1),(4,3,0),(4,2,1),(3,3,1),(3,2,2)$
$1+7+C_2^7+C^7_2+C^7_3+C^7_4C^3_2+C^7_3C^4_3/2+C^7_3C^4_2/2=1+7+21+21+35+105+70+105=365$
另外
可以看成 $(3^7-3)/3!+1=365$

---

## 某公司有 $6$ 位員工，負責今天商品展覽會早上及下午的值班，公司在商品展覽會設置 $A、B$ 兩個攤位，早上需要 $4$ 位員工，其中 $2$ 人值班 $A$ 攤位，另外 $2$ 人值班 $B$ 攤位；下午也需要 $4$ 位員工，其中 $2$ 人值班 $A$ 攤位，另外 $2$ 人值班 $B$ 攤位。公司想要依照下列三個原則來安排值班工作：
(甲) 每一個人不可以同時安排同一個攤位的早上、下午值班
(乙) 每一個早上值班其中一個攤位，下午可以值班另一個攤位
(丙) 兩個攤位的早上及下午值班人員可以不用 $6$ 位員工全部都有安排
根據上述原則，公司對於員工在商品展覽會的值班工作安排共有$\underline{\qquad\qquad}$種方法。

---

( ) 內的是前面算式的意思

上午的值班：$C^6_2\times C^4_2 (6 人選 4 人值班 A，剩下的 4 人選 2 人值班 B ) =90$；

下午的值班：
\begin{align}
& C_2^2(2個值班B的都值班A)\times C^4_2(因此剩下4人任選2人值班B)\\
+&C_1^2(2個值班B的恰1人值班A)\times \\
&C_1^2(剩下的4人中，因為有2人值班過A，因此只能從沒值班過A的2人選1人與他一起值班A)\times\\
&C_2^3(值班過A的2人再算進來，變成3人選2人值班B)\\
+&C_0^2(2個值班B的人都不值班A)\times\\
&C_2^2(剩下的4人，因為有2人值班過A，因此只能從沒值班過A的2人中選2人值班A)\times\\
&C_2^2(值班過A的2人再算進來，剩最後2人值班B)\\
=&6+12+1=19
\end{align}因此方法數為 $90\times19=1710$

---