42306 任兩數差都不在同一組的分組問題

先看一個假設性的科幻問題 :

來訪的外星人傳送了 7 個容量足夠大的安全保管箱, 並通知另有 1000 顆編有序號的微型炸彈也會隨機陸續傳送到地球。這些炸彈一傳到地球就會啟動, 地球人必須在下一顆微型炸彈傳送到前, 將它放入某一個保管箱中。如果兩個不在保管箱中的炸彈都已啟動就會立刻引爆; 但是必須遵守一個嚴格的規則 : 『同一個保管箱中的任兩顆炸彈序號的差, 不能也在該保管箱中。』否則也會引爆所有的炸彈。如果這 1000 顆微型炸彈都能安全的投入保管箱, 他們才願意和聰明的地球人建立友好關係。

前幾顆炸彈的出現當然不是問題, 隨著每個箱中的炸彈愈多, 再投入的限制就愈多, 也許有人會想到二分法, 有計畫地先把後一半 501 到 1000 等 500 顆炸彈放入同一個保管箱, 因為這 500 顆炸彈的序號差分別是 1 到 499, 所以分到同一箱是安全的, 所以第一箱就解決了一半的問題。但是前一半 1 到 500 再也不能投入第一箱了, 所以第一箱就必須封存起來。依此方法第二箱是 251 到 500, 第三箱是 126 到 250, $\cdots$ 愈到後面的箱子能裝的炸彈數量愈來愈少, 不用精算就覺得箱子不太夠, 我們必須想一個更有效的方法, 這時候能拯救地球的, 大概要靠數學家和電腦工程師了。

為解決這個問題, 我們先訂一個初步的研究計畫 :

把正整數從 1 到 $m$ 依『同組中任兩數的差都不在該組』的規則逐一分入 $n$ 組, 務必使 $n$ 最小; 或固定 $n$ 而使 $m$ 達到最大, 這樣的 $n$ 和 $m$ 有什麼數學關係？

資訊工程的朋友可以把這個問題寫成電腦遊戲來讓多數人參與 :

把編有 1, 2, 3 $\cdots$ 序號的球, 逐一投入也編有序號的盒子, 如果投入的球和該盒中已有的球序號差也在該盒中, 就算 game over。每當使用的盒數已投入最大的球數, 就算過了一關, 並出現下一個盒子, 得以繼續遊戲。

我們很容易分析前幾球 :

1 號球當然投入 1 號盒中, 可以記為 $B_1=\{1\}$。
因為 $2-1=1$, 所以 2 號求不能投入 1 號盒中, 只能投入 2 號盒, 記為 $B_1=\{1\}$, $B_2=\{2\}$。所以只有 1 個盒子時, 只能投入 1 個球, 這樣就算過了第一關。
考慮 3 號球, 因為 $3-1=2$, $3-2=1$, 無論投入 1 號盒或 2 號盒都不會 game over, 但對 4 號球的處理卻產生不同的影響。如果 $B_1=\{1, 3\}$, $B_2=\{2\}$, 4 號球無論投入哪一盒都將 game over; 所以必須在 $B_1=\{1\}$, $B_2=\{2, 3\}$ 的情況下, 4 號球才能投入 1 號盒, 而成為 $B_1=\{1, 4\}$, $B_2=\{2, 3\}$。
考慮 5 號球時, 因為 $1+4=5 $, $2+3=5$, 我們也將發現, 無論投入 1 號或 2 號盒, 遊戲都會 game over。所以 5 號球一定要投入 3 號盒, 且確定 2 個盒子最多只能投入 4 個球。

如果問 $m$ 個球最少要用多少個盒子, 這顯然是多對一的函數, 表達起來不太明確; 就不如定義 $f(n)=$『$n$個盒子可以投入球數的上限』=$m$, 而且第 $n+1$ 盒的第一個球也確定就是第 $m+1$ 號球。稍有經驗的人大概也能估計到, $f(n)$ 應該是個幾何級數的函數。

從上面分析前 5 球的過程可以確定 $f(1)=1$, $f(2)=4$。當 $n=3$ 時經過多次嘗試操作, 至少有下列三種分組的方式 :

甲 $B_1=\{1, 4, 7, 10, 13\} $, $ B_2=\{2, 3, 11, 12\} $, $ B_3=\{5, 6, 8, 9\}$ 。
乙 $B_1=\{1, 4, 10, 13\} $, $B_2=\{2, 3, 7, 11, 12\} $, $B_3=\{5, 6, 8, 9\}$ 。
丙 $B_1=\{1, 4, 10, 13\} $, $ B_2=\{2, 3, 11, 12\} $, $B_3=\{5, 6, 7, 8, 9\}$ 。

無論哪一種分法, 都明顯表示 14 號球必須投入 $B_4$, 也就是說 $f(3)=13$ 似乎是成立的。

以下我們用高中生很熟悉的數學歸納法來建立 $f(n)$ 的函數 :

已知 : $f(1)=1$, $f(2)=4$, 設 $f(k)=m$ 即存在一種分組 : \begin{eqnarray*} B_1&=&\{1, \ldots\}\\ B_2&=&\{2, \ldots\}\\ B_3&=&\{5, \ldots\}\\ &\vdots&\\ B_k&=&\{k_1, k_2 , k_3, \ldots\}\hskip 6cm~ \end{eqnarray*} 且最大數 $m$ 存在某 $B_i$ 中。

對每一 $B_i=\{i_1, i_2, \ldots, i_t\}$ 中的任意兩數 $x, y$ 必須確保 $x$ 和 $y$ 的差必不屬於 $B_i$ 及對每一 $B_i$ 必存在有 $i_u$, $i_v$ 使得 $i_u+i_v=m+1$, 這才表示每一個盒子都不能再投入第 $m+1$ 球。

則當 $n=k+1$ 時,

令 $B_{k+1}' =\{m+1, m+2, \ldots, 2m, 2m+1\}$ 再將每一個 $B_1$ 到 $B_k$ 擴充為 $B_i' =B_i\cup B_i''$,

其中 $B_i=\{i_1, i_2, \ldots, i_t \}$,

$\qquad$ $B_i''=\{i_1+2m+1, i_2+2m+1, \ldots, i_t+2m+1\}$

即將 $m+1$, $m+2$, $\ldots, 2m, 2m+1$ 全部投入第 $k+1$ 盒, 且對 $2m+2$ 到 $3m+1$ 的 $x$ 號球, 投入 $x-(2m+1)$ 所在的那一盒, 或者說將原 $B_i$ 除了原有的數之外每一個數均再加上 $(2m+1)$, 擴充為兩倍, 所以這 $k+1$ 盒可以投入的最大數為 $3m+1$。

即 $f(k+1)=3m+1$。

以 $k=3$ 時的丙種解為實例來說明 : \begin{eqnarray*} \hbox{丙}&&B_1=\{1, 4, 10, 13\},\\ &&B_2=\{2, 3, 11, 12\} ,\\ &&B_3=\{5, 6, 7, 8, 9\}\hbox{。}\\ \end{eqnarray*} 則 $k=4$ 時, 因為 $m=13$, 所以 $2m+1=27$, $3m+1=40$ 則 \begin{eqnarray*} &&B_4=\{14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27\}\hbox{。}\\ &&B_1=\{1, 4, 10, 13, 28, 31, 37, 40\} ,\\ &&B_2=\{2, 3, 11, 12, 29, 30, 38, 39\} ,\\ &&B_3=\{5, 6, 7, 8, 9, 32, 33, 34, 35, 36\}\hbox{。} \end{eqnarray*}

現在我們必須檢查每一 $B_i$ 中的任兩數差, 是否不在該集合中;及每一 $B_i$ 中是否必存在兩數和為 $3m+2$。

因為 $B_{k+1}=\{m+1, m+2, \ldots, 2m, 2m+1\}\\$ 所以 $\forall\ x, y\in B_{k+1}$ 則 $1\le |x-y|\le m\\$ 所以 $\forall\ x, y\in B_{k+1}$ 則 $|x-y|\not\in B_{k+1}$
$\forall\ 1\le i\le k $, 因為 $B_i' =B_i\cup B_i''$ $\ $ $=\{i_1,i_2, \ldots, i_t \}\cup \{i_1\!+\!2m\!+\!1, i_2\!+\!2m\!+\!1, \ldots, i_t\!+\!2m\!+\!1\}\\$ 可以簡單的區分為小數部分和大數部分
所以自 $B_i'$ 中任取 $x, y$, 只有三種情形 :
1. 甲. $x, y$ 都來自小數部分, 則 $|x-y|\not\in B_i$ 已是 $n=k$ 時已檢驗過的條件, 且 $|x-y|\le m-1$, 所以 $|x-y| \not\in B_{k+1}$。
2. 乙. $x, y$ 都來自大數部分 , 則設 $x=i_d+2m+1$, $y=i_e+2m+1\\$ 則 $|x-y|=|i_d-i_e |\not\in B_i$, 且 $|x-y|\le m-1$, 所以 $|x-y|\not\in B_i''$。
3. 丙. 若 $x$ 來自小數部分, $y$ 來自大數部分, 設 $x=i_d $, $y=i_e+2m+1 \\$ 則 $|x-y|=y-x=2m+1\pm (i_d-i_e )\\$ 若 $i_d\lt i_e $, 則 $|x-y|=2m+1+(i_e-i_d )$ 將與 $(i_e-i_d )$ 同組 $\not\in B_i\\$ 若 $i_d\gt i_e $, 則 $1\le i_d-i_e\le m-1\\$ 所以 $1-m\le i_e-i_d\le -1\\$ 所以 $2m+1+(1-m)\le (2m+1+i_e )-i_d\le -1+2m+1\\$ 所以 $m+2\le y-x\le 2m\\$ 所以 $y-x\in B_{k+1}\not\in B_i'\\$ 所以 $\forall\ x, y\in B_i' $, 則 $|x-y|\not\in B_i'$。
$\forall\ 1\le i\le k$ 任一 $B_i'$ 中, 因為 $B_i' =B_i\cup B_i''$, 則存在 $x, y\in B_i$ 使得 $x+y=m+1。\\$ 所以存在 $x\in B_i$, $y\in B_i''$, 使得 $x+y=m+1+2m+1=3m+2\\$ 且在 $B_{k+1}$ 中, 明顯存在 $x=m+1$, $y=2m+1$ 使得 $x+y=3m+2$。

所以表示當 $n=k+1$ 時, 投球的上限是 $3m+1$, 根據數學歸納法原理, 我們得到一個遞推的函數關係 :

$f(k+1)=3m+1=3f(k)+1$, 加上 $f(1)=1$, 可以整理出 $f(n)$ 的一般項公式 \begin{eqnarray*} f(n)&=&3f(n-1)+1\\ &=&3(3f(n-2)+1)+1\\ &=&3^2 f(n-2)+3+1\\ &=&3^2 (3f(n-3)+1)+3+1\\ &=&3^3 f(n-3)+3^2+3+1\\ &\vdots&\\ &=&3^{n-1} f(1)+3^{n-2}+\cdots +3^2+3+1\\ &=&\sum_{i=0}^{n-1}3^i\\ &=&\frac 12 (3^n-1) \end{eqnarray*} 到這裡, 我們可以對這個『任兩數差不在同一組』的問題, 得到一個初步的結論 :

$n$ 個盒子最多可以投入 $\dfrac 12 (3^n-1)$ 個球, 且第 $n+1$ 盒的第一球為 $\dfrac 12 (3^n+1)$。

如果注意到 $f(4)=\dfrac 12 (3^4-1)=40 $, 即 4 個盒子最多可以投入 40 個球, 這恰和西元 1624 年法國數學家梅齊里亞克 (Claude Gaspard Bachet de Méziriac, 1581$\sim$1638) 提出四個砝碼就能秤出 1 到 40 磅等所有整數磅物品的問題相同, 四個砝碼上限秤 40 磅和分四群的上限 40, 除非問題同構, 否則不可能如此巧合。我們要做的只是如何找到或解釋他們同構的理由罷了。梅齊里亞克的問題, 後來由英國數學家珀西 $\cdot$ 亞歷山大 $\cdot$ 麥克馬洪 (Percy Aiexander MacMahon, 1854$\sim$1929) 推廣到一般情形：『若允許天平兩邊放砝碼, 每一種砝碼只有一個, 則 1, 3, 9, 27, 81,$ \ldots$, $3^n$, $\ldots$ 是最有效的砝碼組合。而對任意待測秤重量正整數 $n$, 只要將 $n$ 表為三進制, 再將係數 2 以 $3-1$ 取代, 即為所需砝碼的唯一選擇, 但係數為負值時該砝碼與被秤物體同一邊。』 ¹ ¹ 註 : 趙文敏教授編著, 寓數學於遊戲第二輯, 頁42$\sim$43, 九章出版社。

這個結論顯示： 1 個砝碼只能秤 1 磅, 2 個砝碼最多能秤 $1+3=4$ 磅, 3 個砝碼最多能秤 $1+3+9=13$ 磅, 4 個砝碼最多能秤 $1+3+9+27=40$ 磅, $n$ 個砝碼最多可秤 $1+3+9+27+\cdots+3^{n-1}=\dfrac 12 (3^n-1)$, 正和我們剛得到的公式完全一樣。

以三進位的砝碼組合, 也可用排列組合的方法來證明。每一顆砝碼可選擇放左邊(設為 1) , 放右邊(設為 $-1$) , 或放棄不用 (設為 0) , 所以 $n$ 顆砝碼有 $3^n$ 種選擇, 扣除全放棄 1 種, 並考慮左右對稱的重複, 所以 $f(n)=\dfrac 12 (3^n-1)$ 是正確的。另一種解法也可假設 $k$ 個砝碼最多能秤到 $m$, 則下一個砝碼應直接跳到 $2m+1$, 因為 $(2m+1)-m=m+1$, 恰是下一個可秤出的連續整數, 所以當這 $k+1$ 顆砝碼全部置於同一側時, 就可以秤出 $m+2m+1=3m+1$ 這就和前面用到的數學歸納法, 不只過程一樣, 連結果和公式都一樣了。

現在我們回頭來看外星人的7個安全箱是否足夠。如果 $n=7$, $f(7)=\dfrac 12 (3^7-1)=1093$, 所以外星人還是滿厚道的, 不只問題是可以達成的, 並且沒有用極限數來為難地球人。只是我們雖然知道問題有解, 可以從第 1 顆炸彈逐一放入編好號的安全箱中; 也有從 $k$ 到 $k+1$ 箱的具體推廣方法, 事先列出 7 個箱子所要投入的全部號碼。但是炸彈是隨機出現, 光是比對近千個數字找到正確的箱子, 恐怕也是一件大工程, 這是遞推公式不好用的地方, 好比要求費氏 (Fibonacci) 數列第 100 項, 如果沒有生成函數, 就必須從 $F_1,F_2,\ldots$ 求到 $F_{98}$, $F_{99}$, 才能算出 $F_{100}$。如果我們能有一種方法, 直接從炸彈編號的序號, 分析出應直接投入的箱子, 就不怕炸彈序號是隨機出現了, 例如第一顆出現 398 號炸彈能不能直接決定投入哪一箱呢？

前面提到珀西 $\cdot$ 亞歷山大 $\cdot$ 麥克馬洪對任意待測重量正整數 $n$ 的處理方法, 是把 $n$ 表為三進制, 再將係數 2 以 $-1$ 取代, 使每一個正整數 $n$ 表為 $n=\sum_{i=1}^k a_i 3^{i-1}$, 其中 $a_i\in \{-1, 0, 1\}$, 來選擇並放置砝碼, 現在既然整數分組和最小砝碼的問題同構, 我們也希望從 $n$ 的三進制的表達, 來研究直接分組的方法。

先用三個砝碼秤 1 到 13 來分析, 將 1 到 13 以 $-1$、0、1 為係數表為三進制：

$1=1$, $2=3-1$, $3=3$, $4=1+3$, $5=9-1-3$, $6=9-3$, $7=1+9-3$, $8=9-1$, $9=9$, $10=1+9$, $11=3+9-1$, $12=3+9$, $13=1+3+9$

再依每個數等號右邊最小的正數來分群：

$B_1：1=1$, $4=1+3$, $7=1+9-3$, $10=1+9$, $13=1+3+9 $, ($3^0$ 是最小的正項)

$B_2：2=3-1$, $3=3$, $11=3+9-1$, $12=3+9 $, ($3^1$ 是最小的正項)

$B_3：5=9-3-1$, $6=9-3$, $8=9-1$, $9=9$, ($3^2$ 是最小的正項)

正好是原問題甲組的解, 我們還要更完整的證明：

對任意正整數 $a, b$ (設 $a\gt b$), 設 $a, b$ 的三進制分別為 $a=\sum_{i=1} a_i 3^{i-1} $, $b=\sum_{i=1} b_i 3^{i-1} $, 其中 $a_i, b_i\in \{-1, 0, 1\}$ 則 $a_i , b_i$ 中至少各有一個 1。設 $a$ 和 $b$ 同屬於 $B_k$ 那一組, 則 $a_k=1$ 且 $b_k=1 $。且 $a=\sum_{i=1}^{k-1} a_i 3^{i-1}+3^{k-1}+\sum_{i=k+1} a_i 3^{i-1}$ 其中 $\forall\ 1\le i\le k-1 $, $a_i\in \{-1, 0\}$, $b=\sum_{i=1}^{k-1} b_i 3^{i-1}+3^{k-1}+\sum_{i=k+1}b_i 3^{i-1}$ 其中 $\forall\ 1\le i\le k-1$, $b_i\in \{-1, 0\}$, 令 $c=a-b=\sum_{i=1}(a_i-b_i ) 3^{i-1} =\sum_{i=1}c_i 3^{i-1}=\sum_{i=1}^{k-1}c_i 3^{i-1}+\sum_{i=k+1}c_i 3^i$ 其中在 $1\le i\le k-1$ 時, $c_i\in \{-1, 0, 1\} $, 在 $i\ge k+1$ 時, $c_i\in \{-2, -1, 0, 1, 2\} $, 則 $3^{k-1}$ 項係數 $=0$ 變成無法跨越的鴻溝。首先考慮我們將一正整數 $n$ 表為三進制時, 係由冪次最低的係數先決定。係數 -2 和 2 要改寫成 -1 或 1, 都只會影響同冪次及更高冪次, 而不再改變已確定的較低冪次的係數。所以我們分成兩段來討論 :

在 $i\le k-1$ 這邊, 若存在最小的 $i$, 使 $c_i=1$, 則 $a-b$ 在 $B_i$ 那組, 不在 $B_k$。若 $\forall\ i\le k $, $c_i\in\{-1, 0\}$;

再考慮 $i\ge k+1$ 這一邊, 我們由最低次方的 $c_i=-2$ 及 $c_i=2$, 往冪次高的方向整理 :

若 $c_{i+1}=-2$, 因為 $(-2)=(1-3)$, 所以 $(-2) 3^i=(1-3) 3^i=3^i-3^{i+1}$ 則 $c_{i+1}=1$, 則 $a-b$ 在 $B_{i+1}$ 那組, 因為 $i\ge k+1$ 所以 $a-b$ 不在 $B_k$中;

若 $c_{i+1}=2$, 因為 $2=(3-1)$, 所以 $(3-1) 3^i=3^{i+1}-3^i$, 所以 $c_i=-1$, 則 $a-b$ 在冪次更高的 $B_{i+1}$ 那組, 自然不在 $B_k$ 這組。

由上述分析討論得證, 依冪次最小的正係數 1 來分組, 可以保證同一組中任兩數的差都不在同組中。

最後我們可以把連續正整數分組的問題做一個完整的陳述 : 將 1、 2、 3、 $\cdots$、 $m$ 等連續正整數分成 $n$ 組, 使每組中任兩個數的差都不在該組內, 其 $m$ 值的上限為 $f(n)=\dfrac 12 (3^n-1) $。且分組的方法為：將 1、 2、 3、 $\cdots$、 $m$ 等連續正整數, 以 $-1$、 0、 1 為係數表為三進制, 並以 $3^0$、 $3^1$、 $3^2$、$\cdots$、 $3^{n-1}$ 的最小正項為分組依據, 即可得到一種分組法, 但此分組法非唯一解。

現在我們可以直接解決外星人的第一顆編號 398 的炸彈了。 \begin{eqnarray*} \hbox{因為}\quad 398&=&3^5+3^4+2×3^3+2×3^2+2\\ &=&-1+3-3^2-3^4-3^5+3^6 \end{eqnarray*} 因為最小的正項是 $3^1$, 所以 398 號炸彈, 就應該放入編號為 2 的安全箱了！

結語

龍騰文化事業公司 2005 年 10 月出版的『數學新天地』, 有許志農教授主編的問題集：

將 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13 這十三個數字分成三群, 使每群中的任兩個數字差都不在該群內。

這個題目簡單明瞭, 連國中生都可以動手做了。若將題目改為『將一組同花色的撲克牌 $A\sim K$ 分成三堆, 使每堆中的任兩張牌的點數差都不在該堆內。』甚至可以當家庭的休閒益智遊戲了。初看這個題目, 只直覺可能不是唯一解, 等實際動手做, 才發現許多值得討論及推廣的問題。該『數學新天地』提供高中數學教師許多專業上的進修, 不知道許教授提出此問題時, 是否早已有完整的答案, 或許也有不少高中老師曾經解出這個問題。筆者當年解出問題後, 陸續加以推廣, 直到找到以三進制的最小正項為分組依據, 才算有所突破, 其他進位制似乎沒有這種功能, 自己覺得是很難得的經驗, 只是表達過程略嫌複雜, 當年忙於教學無暇整理, 退休後特別記錄下來, 供有興趣的同好參考。因為分組的方法不唯一, 但願還有先進提出其他解法和證明。

尾聲

在解題的嘗試過程中會有一疑問, 如果問題的限制改為：使每組中的任兩數和都不在該組內, 是否有不同的發展。稍一分析就會發現, 若任兩數是指相異兩數, 的確可以增加很多種解法, 但我沒能發現規律。其中的差異在於：若 $b=2 a$ 則 $b-a=a$ 所以 $a$、$b$ 不能在差的限制中同組, 卻可以在和的限制中同組。但若不限制相異兩數, 限制兩數和就和限制兩數差完全一樣了 ² ² 註 : 參考民國 73 年12 月出版的數學傳播季刊第八卷第四期 64-66, 有王湘君老師翻譯自 Staley J. Bezuszka & Margaret J. Kenney : Chaiienges for Enriching the Curriculum :Arithmetic and Number Theory, Math Teacher, April 1983, 250-252. 算術和數論中的「難題」, 第 7 題, 就是以兩數和不在同一組來研究, 文中只推算到分三組時最多到 23, 分四組時最多到 66, 並沒有證明也沒有發展出一般公式。看來問題真的不簡單。。

同一組中任兩數和或差不再在同一組的要求, 類似生物學的避免近親繁殖, 是否可應用於生物研究的配對組合, 或統計的抽樣理論, 或資訊的資料存取處理等等 $\ldots$, 就更希望有人能更深入的探討了。

---本文作者為高雄市中正高中退休教師---