Puzzleup 2013 - 02

In a country circulating coins exist in denominations of 1u (unit), 5u, 10u, 20u, 25u, 50u, and 100u. Your goal is to select X of these coins to make exactly 100u. What is the smallest value of X that makes it impossible to reach your goal?

Note: X > 0

不負責任解題:

第一時間我沒看懂這道題目, 心想不就任何數字都可以達成嗎??

1 coin x 100

2 coins x 50

3 coins (2 x 25, 1 x 50)

....

大概要到101 coins 爆表之後才會不能湊成吧....

但我們如果假設100 是最大可能的數字( 100 coins x 1)

就會發到99 是不可能的, 因為99 個1u 不到100, 但要是其中一枚變成5u, 就會破表100

可是老實說找可能比找不可能容易

因為找可能只要找到一種方法, 但找不可能要找全部的方法再說都達不到

所以我仍然選擇由1 coin 開始試

一開始很好找到組成100的方法

但是到了超過50以後, 會發現每次都會將大量的數字都用在1u, 而且必須是5的倍數(因為其他幣值及達成的目標都是5的倍數)

慢慢的會發現一個規律, 就是20u可以換成2個10u, 1個10u 又可以換成2個5u, 如此就可以快速累積可能的組合, 然後等到到了某個數字時, 你會發現, 那個數字如果全換成1u 不夠, 但是要是退到前一個5的倍數時, 剩下的硬幣即使全換成5u 這種次小的面額, 又會破100的表

然後你就知道那個讓你達不成100u 的最小的數量到底是多少了。

Puzzleup 2013 - 01

There are 8 balls. Four of them weigh X grams each, and the other four weigh Y grams each. Your task is to find two balls having different weights. You have a balance scale with two pans on which you can compare the weight of any number of balls. What is the minimum number of weighings necessary to guarantee to accomplish this task? 

不負責任解題:

題目有點小吊詭, 它不是要你用最少次數『分出哪四個球輕, 哪四個球重』, 而是『找出輕重不同的兩顆球』。

因為可以秤任意數量的球, 又有組合性, 運氣好當然可能第一次秤, 天平兩端各一顆正好輕重不同, 就結束了。但顯然題目希望我們是要能百分之百確定, 而不是期待靠運氣。

通常思路停滯時, 我會倒過來想, 那最糟的情況要到幾次？如果我每次都一個一個對秤, 然後永遠都靠著我過往中大樂透的機會, 那麼我會到第4次才能找到輕重不同的兩球
(每次都秤到相同重量, 然後把一顆可能性去除, 剔除掉3顆後, 第4顆才會和天平另一端輕重不同)

這顯然是個蠢方法

--

如果八顆球分別是ABCDEFGH, 那我如果先拿AB對秤

運氣好AB不同重量就結束 – 1次

AB同樣重量, 就再秤CD, 若CD 不同重量就結束 – 2次

要是AB等重, CD 也等重, 那就秤AB v.s. CD
若AB和CD 不同重, 就挑AB 任一顆和CD任一顆, 一定不同重
若AB 和CD 等重, 就代表ABCD四球一樣重, 也就是 ABCD, EFGH 正好是輕重不同的兩組球, 所以兩組各拿一顆, 一定不同重
3次

如此可以在3次內KO

--

再換個方法

我先拿ABC 和 DEF 對秤

如果等重, 那麼就代表兩組球的組合一定都是 2X1Y 或是 1X2Y
這時我只要再拿AB 對秤
要是重量不同 – 2次
要是重量相同, 那麼任取AB其中一球和C配一定重量不同 – 2次

反之, 若是ABC 和DEF 重量不同
有可能以下4種可能性
(3X, 1X2Y), (3X, 3Y), (2X1Y, 1X2Y), (2X1Y, 3Y) [ABC 和DEF可能為前或後之組合]
接著來秤GH,
其中若是(3X, 3Y), (2X1Y, 1X2Y)這兩種搭配, 那麼剩下的GH一定重量不同 – 2次

但若是GH 等重, 就有可能是(3X, 1X2Y), (2X1Y, 3Y) 其中一組組合,
這時挑組合中比較重的一組任選兩顆和GH對秤
若是(3X, 1X2Y), 則GH 必為2Y, 對上輕重的任選兩顆是2X, 一定較輕
若是(2X1Y, 3Y), 則GH 必為2X, 對上輕重的任選兩顆是2X或1X1Y, 一定平衡或較重
上述第一種情況, 就最後一次對秤的兩組任取一顆一定重量不同 – 3 次
上述第二種情況, 就GH 和3Y兩組任取一顆一定重量不同 – 3 次



但這種題目的思惟往往是 –
1.在你覺得已經是最少的數字還有不同的方法可以達成, 再少一次才會是答案(漂亮的答案不會有另一種可能性)
2.真正最少的答案一定是沒有帶運氣的, 就是每種判斷都應該正好兩次, 沒有一次就可靠運氣達成的。（因為每次的秤都是一次資訊, 資訊只使用一次就結束太浪費了)

我的答案當然就是3-1 = 2次
第一次是兩顆兩顆對秤(AB v.s. CD)

那.....第二次呢??