糖紙換糖問題

請留意第四題

問題：如果你媽媽給你十顆糖，兩張糖紙可以換一顆糖，問你最後最多吃多少顆糖？

近日有新聞一篇，指小一入學面試題目愈見刁鑽。其中上述的數學題更難倒九成大學生。[1]

該篇新聞亦有提及該題的解答：正確答案為十九顆，十張糖紙先換五顆，五張糖紙再多換兩顆，剩一張糖紙，兩張糖紙換一顆，最後的一張糖紙與早前餘下的糖紙換得最後一顆。

以升小的學生而言，能作出如此解答實屬難能可貴，但若以大學生的眼光觀之，這解答卻欠缺一般性——如果媽媽非常慷慨，一開始就給我幾千顆糖，那問題該如何解答？

未知各位有否留意到「兩張糖紙可以換一顆糖」嚴格上該為「兩張糖紙可以換一顆糖加一張糖紙」。這看似無關痛癢，卻是解題的關鍵所在。兩張糖紙可以換一顆糖加一張糖紙，即意味著不論如何過程如何，糖的數量與糖紙的數量之和必定維持不變。

已知一開始有十顆糖（加十張糖紙），而最後肯定會剩下一張糖紙，所以最後手上就應該有十九顆糖［如果你沒有邊換邊吃的話］。一般而言，如果一開始有 N 顆糖（加 N 張糖紙），最後最多就吃到 2N - 1 顆糖了。

按此思路，煩瑣的換糖過程就可以拋諸腦後了，夠精彩吧。只要掌握不變的條件，就能應付無窮的變化，這可謂數學中的「以不變應萬變」呢。

接下來提升一下難度，把題目一般化：如果你媽媽給你 N 顆糖（加 N 張糖紙），p 張糖紙可以換 q 顆糖（加 q 張糖紙），問你最後最多吃多少顆糖？當然，這裡得假設 p > q，否則你媽媽就要破產囉。

設在換糖 t 次後，手上有糖 x 顆及糖紙 y 張。
由於一開始有糖 N 顆，而每換糖一次，糖便多 q 顆，所以 x = N + qt。
由於一開始有糖紙 N 張，而每換糖一次，糖紙便少 p - q 張，所以 y = N - (p - q)t。
以 (x, y) 表達糖及糖紙數量，換糖過程即是 (N, N) -> (N + q, N - (p - q)) -> (N + 2q, N - 2(p - q)) -> ...
當糖紙少於 p 張時，便無法再換糖。換言之，y < p 一旦達成，換糖過程便結束。

有點頭暈？不用怕，舉個實例便一目瞭然。
如果 N = 14、p = 5、q = 3 時，換糖過程就是 (14, 14) -> (17, 12) -> (20, 10) -> (23, 8) -> (26, 6) -> (29, 4)，所以最後可得糖 29 顆（及糖紙 4 張）。

接下來看看有甚麼條件是不變的。從 x = N + qt 和 y = N - (p - q)t 二式之中消去 t，可得 (p - q)x + qy = pN。這個 x 與 y 的關係就是不變的條件，而換糖過程中每一組 (x, y) 都能滿足此方程式。因此，整過換糖過程能以圖像表示。以剛才 N = 14、p = 5、q = 3 的例子而言，x 與 y 的關係就是 2x + 3y = 70，換糖過程則如下圖。

最後補充一點，這個換糖問題其實早在多年前的教育電視已經出現過（因年代久遠，片段貌似是找不到了…）。那是 N = 10、p = 2、q = 1 的簡單版本。節目中更提到其實最多可以吃到二十顆糖，但卻沒有進一步說明，留下最大的疑團［？］。多年來，坊間留傳一個解答：向別人借一張糖紙，加上剩下的一張，便可以換來第二十顆糖，而且還有一張糖紙可供歸還。在這解答中，最後沒有糖紙剩下，可謂物盡其用。乾淨利落，就是引人入勝。

參考：

1.	SUN熱辣：升小面試題考起大學生 [2012-12-05] http://the-sun.on.cc/cnt/news/20121102/00410_097.html