四公升的水謎題解析--GameSchool遊戲學校

精選謎題列表

其它謎題列表

謎題分類

四公升的水 - 謎題解析

兩個水桶的倒水問題，說穿了， 
不是水桶 A 往水桶 B 一直倒， 
就是水桶 B 往水桶 A 一直倒。 
 <hr />假設水桶 A 跟 B 的容量分別是 a 和 b， 
每次固定用 A 取水然後往 B 倒，B 裝滿時把水倒光， 
而目標是要讓兩個水桶內總共只留下 t 單位的水， 
其中的 a、b、t 都是正整數，a、b 互質並且 t&lt;a+b。 
（以上條件單純是想避開某些太過瑣碎的情況） 
 
令 A 的裝水次數為 x，B 的倒水次數為 y， 
不難列出 ax-by=t，根據<a href="https://zh.wikipedia.org/wiki/%E8%B2%9D%E7%A5%96%E7%AD%89%E5%BC%8F" target="_blank">貝祖定理</a>， 
只要 t 是 gcd(a,b) 的倍數就一定有整數解， 
這保證了只要一直倒就一定能倒出 t 單位的水， 
最後做一下統計就得到 x 跟 y 了， 
但也可透過<a href="https://zh.wikipedia.org/wiki/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95" target="_blank">擴展歐幾里得算法</a>求得 x 跟 y。 
 
舉個例子： 
A 是 24L 的水桶，B 是 31L 的水桶， 
目標是剩下 20L 的水在兩個水桶中， 
可以先列出 24x-31y=20。 
對 24、31 做<a href="https://zh.wikipedia.org/zh-tw/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95" target="_blank">輾轉相除法</a>的過程可知： 
31=24*1+7 -&gt; 7=31*1+24*(-1) 
24=7*3+3 -&gt; 3=24*1+7*(-3) 
7=3*2+1 -&gt; 1=7*1+3*(-2) 
接著從 1=7*1+3*(-2) 回推出： 
1=7*1+[24*1+7*(-3)]*(-2) -&gt; 1=24*(-2)+7*7 
1=24*(-2)+[31*1+24*(-1)]*7 -&gt; 1=31*7+24*(-9) 
最後兩側同乘以 20 並做整理， 
得到 24*(-180)-31*(-140)=20。 
由於 24*(31k)-31*(24k)=0 明顯成立， 
因此 x=31k-180、y=24k-140， 
取 k=6 得到最小次數 x=6、y=4。 
 
前面看似只有討論 A 往 B 一直倒， 
其實要換成 B 往 A 一直倒的情況， 
也就是 a 和 b 的值相互交換， 
只需要把答案稍微變化一下就行了。 
例如前面已知 24*6-31*4=20， 
代表 31*(24-4)-24*(31-6)=20， 
得到 x=20、y=25。 
 <hr />題外話： 
現在看到這種題目， 
作者給的答案如果是 A 往 B 一直倒， 
就一定會有人給出 B 往 A 一直倒的方法， 
如果是 B 往 A 一直倒， 
就一定會有人給出 A 往 B 一直倒的方法。 
那到底哪個比較快呢？ 
願意動一下腦的人應該都能好好比較， 
而不是被精巧的敘述牽著鼻子走，嗯。

備註

關於GS	好玩遊戲		益智謎題		聯絡我們
關於遊戲學校常見問題服務條款隱私政策 146,177,414	自造遊戲 X檔案夢遊先生神秘解謎 CN卡通頻道 GROW成長物品拆解	密室脫逃遊戲方塊益智遊戲偵探解謎遊戲益智冒險遊戲策略棋弈遊戲觀察尋找遊戲其它益智遊戲	邏輯數學找規律 / 找不同空間概念快問快答移動成立創造力	謎語 / 燈謎偵探思考眼腦並用文字拆解圖其他謎題	留言 / 錯誤回報 service@gameschool.cc
					其他
					GS名人榜攻略編輯總表