Puzzleup 2012 (19) Palindromic Number - 拼圖

Dinah avatar
By Dinah
at 2012-12-01T15:21

Table of Contents

我先自首,
1. 在這個版學到program-up這個字
2. 這題我分析了一下沒突破口後就先program-up了
3. 看到j大的文,先是在心裡按了個讚著實感嘆了一下,然後噗哧

====================== 以上廢話,以下嘗試用分析的方式解這題 =================

令答案所需要的最大回文數為N

1. N < 9 * 83 * 741 * 6520 = 3608996040 (最多為十位數)
上面選定開頭的9876後,小的會被後面的百位數拉高比例較多所以9是個位
剩下的543210優先把大的放在最重要的位數,依第幾位數開頭小的優先
2. 以下假設N為10位數
(1) N最前後兩端的位數可能為1, 2, 3 (注意回文數的最高位數 = 最低位數)
a. 若四個結尾有偶數 => N的開頭結尾只能是2
b. 若四個結尾有0 => 不可能是十位回文數 (個位數為零)
c. 若四個結尾有5 => 不可能是十位回文數 (搭偶數如b, 不搭偶數前後會是5)
d. 若結尾是1,3,7,9 => 不可能是十位回文數 (開頭結尾會是9)
所以N為十位數,N的前後兩端位數一定要是2
(2) 十位回文數一定是11的倍數,
且這一定是從百位數來(1位的顯然不可能,偶位數的11倍數是回文一定重複)
百位數中,每個位數不重複、後兩位沒用到9,開頭是3~9,結尾不是0或5有:
308, 341, 352, 374
407, 418, 451, 462, 473
506, 517, 528, 561, 572, 583
627, 638 ,671 ,682
704, 726, 748, 781
803, 814, 836, 847
902, 913, 924, 946, 957, 968
(3) 海巡開頭可能的四個數字,檢查[個位數;{結尾}](結尾0,5都拿掉)
a. {9,8,7,6} => min = 6 * 72 * 814 * 9035 = 3177139680 出局

b. {9,8,7,5} => min = 5 * 72 * 814 * 9036 = 2647909440
結尾{1,2,3,4,6}取三依乘積分類:
2: {1,2,6}, {1,3,4}, {3,4,6}
4: {1,4,6}, {2,3,4} --> 配個位數"8"
6: {1,2,3}, {2,3,6} --> 配個位數"7"
8: {1,2,4}, {1,3,6}, {2,4,6} --> 配個位數"9"
(a) 個位數為8,其他配{1,4,6}結尾,依三位數可能選擇做分類(用過數字排除)
[8,XY,924,XZZY], X:{5,7}, Y:{1,6}, Z:{0,3}
[8,XY,704,XZZY], X:{5,9}, Y:{1,6}, Z:{2,3}
[8,XY,726,XZZY], X:{5,9}, Y:{1,4}, Z:{0,3}
[8,XY,506,XZZY], X:{7,9}, Y:{1,4}, Z:{2,3}
(b) 個位數為8,其他配{2,3,4}結尾
[8,XY,902,XZZY], X:{5,7}, Y:{3,4}, Z:{1,6}
[8,XY,913,XZZY], X:{5,7}, Y:{2,4}, Z:{0,6}
[8,XY,704,XZZY], X:{5,9}, Y:{2,3}, Z:{1,6}
(c) 個位數為7,其他配{1,2,3}結尾 (略)
(d) {2,3,6}
(e) 9 {1,2,4}
(f) {1,3,6}
(g) {2,4,6}
由以上(a)~(g)乘開可知,沒有回文數

c. {9,8,7,4} => max = 9 * 83 * 751 * 4620 = 2591806140
結尾{1,2,3,6}取三依乘積分類:
2: {1,2,6}
6: {1,2,3}, {2,3,6} --> 配個位數"7"
8: {1,3,6} --> 配個位數"9"或"4"

d. {9,8,7,3} => max = 9 * 84 * 751 * 3620 = 2055276720
結尾{1,2,4,6}取三依乘積分類:
2: {1,2,6}
4: {1,4,6} --> 配個位數"8"或"3"(3太小)
8: {1,2,4}, {2,4,6} --> 配個位數"9"

e. {9,8,7,2} => max = 9 * 84 * 751 * 2630 = 1493198280 出局

f. {9,8,6,5} => max = 9 * 83 * 641 * 5720 = 2738890440
結尾{1,2,3,4,7}取三依乘積分類:
1: {1,3,7}
2: {1,3,4}, {2,3,7} --> 配個位數"6"
4: {1,2,7}, {2,3,4} --> 配個位數"8"
6: {1,2,3}, {2,4,7}
8: {1,2,4}, {1,4,7}, {3,4,7} --> 配個位數"9"

g. {9,8,6,4} => max = 9 * 83 * 651 * 4720 = 2295321840
結尾{1,2,3,7}取三依乘積分類:
1: {1,3,7}
2: {2,3,7} --> 配個位數"6"
4: {1,2,7} --> 配個位數"8"
6: {1,2,3}

h. {9,8,6,3} => max = 9 * 84 * 651 * 3720 = 1830820320 出局

i. {9,8,5,4} => max = 9 * 83 * 561 * 4720 = 1977996240 出局

j. {9,7,6,5} => max = 9 * 73 * 641 * 5820 = 2451017340
結尾{1,2,3,4,8}取三依乘積分類:
2: {1,3,4}, {1,4,8} --> 配個位數"6"
4: {1,3,8}, {2,3,4}, {2,4,8}
6: {1,2,3}, {1,2,8}, {3,4,8} --> 配個位數"7"
8: {1,2,4}, {2,3,8} --> 配個位數"9"

k. {9,7,6,4} => max = 9 * 73 * 651 * 4820 = 2061547740
結尾{1,2,3,8}取三依乘積分類:
4: {1,3,8}
6: {1,2,3}, {1,2,8} --> 配個位數"7"
8: {2,3,8} --> 配個位數"9"或"4"(4太小)

l. {9,7,6,3} => max = 9 * 74 * 651 * 3820 = 1656222120 出局

m. {9,7,5,4} => max = 9 * 73 * 561 * 4820 = 1776541140 出局

以上c, d, f, g, j, k仿照b的作法應該可以用紙筆在一兩天內爆完...
粗估大約需要乘開8 * 4 * 33 ~ 1000個組合在其中尋找最大的回文數

※ 引述《jurian0101 (Hysterisis)》之銘言:
: ※ 引述《LPH66 (杇瑣)》之銘言:
: : 題目網址: http://www.puzzleup.com/2012/?home
: : http://www.puzzleup.com/2012/puzzle/?260
: : 答題時限: 11月29日7PM-比賽結束(約12月12日)
: : 加分時限: 11月29日7PM-12月4日6:59PM
: : 答對可得基本分100分。答案可上傳5次,每改1次答案從基本分扣20分。
: : 另有兩種加分: 1. 加分時限內答對。例:第N天答對,可加(6-N)分。
: : 2. 題目越困難,加分越多。例:這題有n%的人答錯,答對者加n分。
: : ◆Palindromic Number
: : Using all 10 digits (0-9) only once, one 1-digit, one 2-digit, one 3-digit,
: : and one 4-digit numbers are formed. When these four numbers are multiplied
: : the result is a palindromic number. What can be the maximum value for this
: : palindromic number?
: : 使用 0 到 9 十個數字各一次,構成一位數、兩位數、三位數及四位數各一個。
: : 當這四個數相乘會得到一個迴文數(譯註)。問這個迴文數最大多少?
: : 譯註:迴文數是指正讀反讀都相同的數,如 12321。
: 落落長的一行解 <<<<這叫哪門子一行
: f = (1000 #1 + 100 #2 + 10 #3 + #4) (100 #5 +10 #6 + #7) (10 #8 + #9) #10 &;
: Max[
: f@@@Select[
: Cases[Permutations[Range[0, 9]],
: {Except[0], _, _, Except[0 | 5],
: Except[0], _, Except[0 | 5],
: Except[0], Except[0 | 5],
: Except[0 | 5]}],
: Reverse[IntegerDigits[f @@ #]] == IntegerDigits[f @@ #] &
: ]]
: 好我承認說不上是一行解決 = = 總之起碼有個辦法(雖然稱為暴力解)可確知答案了
: 再回頭來揣摩一下,能不能別跑10!次判別多麼醜陋的方法啊。
: - - - - 洞洞手洞洞腦的分隔線 - - - -
: 乘積最大是十位數9xxx*8xx*7x*6 = 3 xxx xxx xxx,
: 我決定起初要很樂觀的假設結果的乘積是十位數,絕不是因為偷看答案
: 而是因為十位數又是回文數,它一定是11的倍數多了這個線索。
: 排列出的 一位與兩位不可能是11倍數,因此 四位數 或 三位數是11的倍數。
: 此線索保留
: 10位數的乘積以1,2,3開頭,但1,3不合,因為{1,3,5,7,9}挑四個在個位,不可能變出1或3
: 故只有2可能
: 滿足 2 xxx xxx xxx 開頭數字 = 9*8*7*5 或 9*8*6*5
: 因此9和8絕對會被開頭用掉
: 滿足 x xxx xxx xx2 結尾數字 = 1*2*3*7 或 1*3*4*6 或 2*3*6*7(同時用掉6,7不合)
: 所以
: 9 x y 1 9 x y 1
: 8 z 2 8 z 3
: 5 3 5 4
: x 7 剩 0 4 6 x 6 剩 0 2 7
: __________ ____________
: (9,8,5) (1,2,3) 可替換 (9,8,5) (1,3,4) 可替換
: 看似有 3!*3!*3! *2 = 432 種情況,但其實更少,因為有11倍數這條件可以用
: 9**1 以左式為例 ,
: 8*2
: 53 若8** 11倍數,是803
: 7 9** .. 902
: 5** .. 561
: xyyz*803*xz*7 x \in {9,5} && y \in {4,6} && z \in{1,2} 八種
: xyyz*902*xz*7 x \in {8,5} && y \in {4,6} && z \in{1,3} 八種
: xyyz*561*xz*7 x \in {9,8} && y \in {4,6} && z \in{2,3} 八種
: 若三位數非11被數,則四位數必須是
: 11|abcd -> (a-d) ± (b-c) = 0 或 11
: 因b,c \in {0,4,6} -> b-c \in ±{2,4,6}
: 總之四位數只可能是 9042, 8041,8063, 5401, 5203
: 9042*x6y*xy*7 四種
: 8041*x6y*xy*7 ..
: 8063*x3y*xy*7 ..
: 5401*x6y*xy*7 ..
: 5023*x4y*xy*7 ..
: - - - -
: 9**1 剩 0 2 7
: 8*3
: 54
: 6
: xzzy*803*xy*6 八種
: xzzy*924*xy*6 ..
: 9724*x0y*xy*6 四種
: 8701*x2y*xy*6 ..
: 8723*x0y*xy*6 ..
: 5203*x7y*xy*6 ..
: 5027*x7y*xy*6 ..
: OAO,削減到8*2+4*5+8*2+4*5 = 72 種情況了
: 問題是答案不在裡面,所以不做了,掯。
: 因為首位數是 9*8*7*5 或 9*8*6*5 的假定是錯的,因為這兩個只是
: 首位數必定是2的情況。5*6*7*8 和 5*6*7*9 都差一點點適當的排列也是個2字頭
: 結論是答案在5 6 7 9開頭 <-----怎麼可能用這種方法篩出來,一定是
: Program-Up
: Program-Up
: Program-Up
: 不用它的優雅方式難道沒有嗎

--
Tags: 拼圖

All Comments

用骰子選人當鬼

Zora avatar
By Zora
at 2012-11-30T18:29
看到板友既然提出了對應骰子的角,那表示用骰定之後的骰子水平轉角是可以判斷的 如果利用這點的話 七人圍成一圈,骰子丟中間,看某個指定的骰子角指到誰就解決了 規定指到兩人中間的話以右邊(或左邊)為被指到者 但是會有一開始圍圈無法七等分的問題 或是看骰子掉離誰比較近,以骰子的邊長做為測量距離單位 問 ...

用骰子選人當鬼

Edwina avatar
By Edwina
at 2012-11-30T14:31
我們也同時可以證明保證有限次完成的方法是不存在的 考慮 Si, 因為我們只能丟有限次骰子, Si = {a_1, a_2, ..., a_n} ,n 是一個有限的數,a_j 的長度也是有限的, sum (p(a_i)) = 1/7 and p(a_i) = 6^k for some k in Z =a ...

用骰子選人當鬼

Lucy avatar
By Lucy
at 2012-11-30T10:40
※ 引述《DreamYeh (天使)》之銘言: : ※ 引述《DreamYeh (天使)》之銘言: : : 這是我和小朋友教學時候實際遇到的問題,實際上當時沒有得到一個滿意解答 : : 因此來挑戰一下大家頭腦!希望能集思廣益,得到一個最好答案 : : 問題是這樣子的: : :   有七個小朋友,要and#34 ...

用骰子選人當鬼

Rachel avatar
By Rachel
at 2012-11-29T23:32
1. 先證明小於 2 不可能。 如果期望值小於 2,那一定至少有一種情況是投了一次就決定的, (若 E(X) andlt; k 則 X 一定要在某些時候 andlt; k 吧) 但是那種情況本身就佔了 1/6 的機率了,所以不可能。 2. 接下來我們來正式攻擊這個問題,先把解答空間正規化。 因為 ...

用骰子選人當鬼

Jacob avatar
By Jacob
at 2012-11-29T20:31
※ 引述《DreamYeh (天使)》之銘言: : 這是我和小朋友教學時候實際遇到的問題,實際上當時沒有得到一個滿意解答 : 因此來挑戰一下大家頭腦!希望能集思廣益,得到一個最好答案 : 問題是這樣子的: :   有七個小朋友,要and#34;公平and#34;選出一個人出來當鬼 :   :   我們有一顆骰 ...