作者utomaya (烏托馬雅)
看板puzzle
標題[中譯] PuzzleUp 2009 (10) Coins
時間Wed Sep 23 21:48:15 2009
首頁：
http://www.puzzleup.com/2009/?home
時限：2009/09/17（四）19:00～09/22（二）18:59
答案可上傳５次，但每改１次扣２０分（基本分為１００分）
在比賽期間內可隨時回答，但只有在時限內回答者有額外加分
◆Coins
某個國家中，只要
最多2枚硬幣，就可以表達出1至50元的數值(1和50皆包含在內)
在這個國家中，所有種類的硬幣幣值，其總和的最小可能值為何？
假設題目要求的是可以表達1~8元的數值
硬幣最小總和為8元，分別是1元, 3元, 和4元
1元 = 1個1元硬幣
2元 = 2個1元硬幣
3元 = 1個3元硬幣
4元 = 1個4元硬幣
5元 = 1個1元硬幣 + 1個4元硬幣
6元 = 2個3元硬幣
7元 = 1個3元硬幣 + 1個4元硬幣
8元 = 2個4元硬幣
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 219.70.180.112
※ 編輯: utomaya 來自: 219.70.180.112 (09/23 22:21)
1F：推 EIORU:1.3.9.27? 09/24 09:51
2F：推 puzzlez:樓上在說答案？0.0" 不過那不可能是正解 因為最多是36元 09/24 10:02
3F：推 puzzlez:哦 不對 最多是 54元......湊不出50.... 09/24 10:09
4F：推 chung6hc:3的平方數列, 5塊就要超過2枚了... 09/24 10:32
5F：推 turing:聯想到「所有的偶數都是兩質數的和」的「猜想」。 09/24 10:46
6F：推 puzzlez:反正可以肯定答案小於200...(廢話)...( ￣ c￣)y▂ξ 09/24 10:46
7F：推 puzzlez:turing的猜想，可惜奇數沒有照顧到:-(如果是三枚就好了 09/24 10:47
8F：推 puzzlez:啊，突然想到一件事@@" 來驗算看看... 09/24 10:50
9F：推 turing:這不是「turing的猜想」，這是數論界急於證明的事情。 09/24 10:53
10F：→ turing:在數學界尚未證明及未找到反證前都稱之為「猜想」。 09/24 10:54
11F：推 puzzlez:我是指你說的猜想啦=.=" 不過真的讓我靈光一閃.... 09/24 10:55
12F：→ turing:費馬最後的定理在Andrew Wiles證明之前其實應稱為「猜想」 09/24 10:57
13F：推 puzzlez:可惜...用「50之前的質數」還是太多了.... 09/24 10:59
14F：→ pikacha:我可以說直覺猜的答案嗎?感覺這寫個程式就能解出來?! 09/24 16:01
15F：推 puzzlez:還是不要吧...因為我靠直覺之後...後來的答案都比它大@@" 09/24 16:02
16F：推 puzzlez:所以搞不好那個直覺...真的是對的@@"...有那麼簡單嗎？ 09/24 16:03
17F：推 tp:---- 09/24 16:55
不好意思，為了競賽的樂趣，請不要寫出答案，不管你的答案是錯或是對
幫你mark掉，請不要介意
18F：推 stimim:在小一點 09/24 18:33
※ 編輯: utomaya 來自: 219.70.180.112 (09/24 18:53)
19F：→ utomaya:我提供一個想法，假設有n種幣值的硬幣 09/24 19:48
20F：→ utomaya:那麼 一個硬幣的值有n種，2個硬幣的值最多有n^2種 09/24 19:50
21F：→ utomaya:假設他們都剛好不重覆，那麼最多可形成n+n^2個值 09/24 19:51
22F：→ utomaya:n+n^2 ≧50, n的最小值為7，小於7種幣值的，根本不用考慮 09/24 19:53
23F：推 stimim:還要再除二，因為可以交換 09/24 20:29
24F：→ utomaya:喔 對喔! 那應該是n+n^2/2 ≧ 50, n的最小值是9 09/24 21:02
25F：→ utomaya:寫錯...是n的最小值是10才對 10+10^2/2=60≧50 09/24 21:04
26F：推 Poggle: C(n,2) + n + n ≧ 50 09/24 21:37
27F：→ Poggle:兩枚不重覆、兩枚相同、只有一枚 => n≧9 應該這樣?! 09/24 21:37
28F：推 puzzlez:9個點一共只能連45條線，所以n不會等於9，至少是10.... 09/24 23:17
29F：→ utomaya:P大寫得才是對的 我剛才也發現自己少考慮了一種 09/25 00:04
30F：→ utomaya:所以應該是(n^2+3n)/2 ≧ 50 n最小是9 09/25 00:06
31F：推 LPH66:不過 n=9 時一共只有54種拿法 要選到不重覆有點難... 09/25 01:26
32F：推 puzzlez:嗯Poggle說的沒錯，如果有N種幣值，則3種組合方式為： 09/25 14:14
33F：推 puzzlez:1.只付一枚：N種 2.付兩枚相同幣值：N種 3.付兩枚不同幣 09/25 14:15
34F：推 puzzlez:N(N+1)/2種 所以一共有N+N+N(N+1)/2 種=N(2+(N+1)/2) 09/25 14:18
35F：推 puzzlez:當N=8時，共有8(2+4.5)=52 就已經超過50了.... 09/25 14:20
36F：推 puzzlez:=.= 我打錯公式了 是 N(N-1)/2...... 09/25 14:26
37F：推 puzzlez:N(2+(N-1)/2)種 所以N=9時, 9(2+4)=54...是9沒錯... 09/25 14:27
38F：推 puzzlez:我猜答案不會超過15種吧.... 09/25 14:30
39F：推 turing:題目問的是總和最少，而不是數量最少 09/25 16:24
40F：推 puzzlez:15種的最小組合是120 離 150 很接近 猜15種左右很合理 09/25 17:25
41F：推 Poggle:其實量多不一定是不好 (如果能讓其他硬幣運用更有效率的話) 09/25 21:52
42F：→ Poggle:也許數列上你捨棄了某個數，會讓之後一個更大的數產生需求 09/25 21:52
43F：→ Poggle:而一個25可是輸給三個8的，盡可能減少大數才是正途 :) 09/25 21:52
44F：推 puzzlez:最簡單的方法就已經不超過150了，15種的最小答案是120... 09/25 22:08
45F：推 puzzlez:就算想取超過15種也很難吧...難道你們目前的答案有超過嗎 09/25 22:08
46F：→ utomaya:有耶 我超過120了 09/25 22:12
47F：→ utomaya:你有驗算嗎? 最多2枚硬幣可以組成1到50 一一驗算之 09/25 22:13
48F：推 puzzlez:=.=" 超過120很正常啊...我是說難道你們都超過15種？ 09/25 22:14
49F：推 puzzlez:120基本上一定會超過的吧 那是取1~15的總和... 09/25 22:15
50F：→ utomaya:沒超過15種 09/25 22:15
51F：推 puzzlez:取15種最小的方式是取1~15（當然這不可能是答案）總和120 09/25 22:16
52F：推 puzzlez:所以你取15種的話 基本上總和一定會超過120 09/25 22:17
53F：推 puzzlez:已知最笨的方法 其總和為 145 所以總和絕不能超過它 09/25 22:19
54F：→ utomaya:我有一個直覺的方法 14種 但總和是193...超大的值 09/25 22:22
55F：推 puzzlez:咦？我以為145的答案還滿直覺的耶...真的很難想另一種 09/25 22:25
56F：推 turing:我寫了一個程式，目前已經跑了半天了，還跑不出來。 09/26 00:38
57F：→ turing:不過我也想到了p大的145的解答。 09/26 00:40
58F：→ turing:經過一番推導和stimim的提醒找到了比tp大「少一點」的答案 09/26 00:42
59F：→ turing:趕在第一天的期限到之前上傳答案... 09/26 00:43
60F：推 ars1an:剛寫了個程式跑完了，找出比之前上傳還少2的答案…orz 09/26 04:36
61F：推 puzzlez:這題的難度還真高啊.....:-( 09/26 06:59
62F：→ utomaya:我忽然發覺這題的意義了 這題其實是第2題運水問題的延伸 09/26 10:06
63F：→ utomaya:一樣有2個中繼點 要把水運到終點(50) 09/26 11:31
64F：推 werul:好難@@ 09/26 21:24
65F：推 EIORU:我想到---- 09/26 22:17
66F：→ EIORU:再---- 09/26 22:19
sorry，幫你把答案mark掉
67F：→ FACE90006:大家都好厲害唷 我都沒想法Q.Q 09/26 22:31
※ 編輯: utomaya 來自: 219.70.180.112 (09/26 23:29)
68F：推 tp:我大概知道"少一點"是少哪裡了 09/27 16:01