作者TimcApple (肥鵝)
看板Math
標題[其他] 2021 新年數學題目
時間Fri Jan 1 00:15:15 2021
https://reurl.cc/N6zekQ
一共 10 題和 2021 有關的題目
祝各位新年快樂ow o
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.10.12.204 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1609431322.A.092.html
1F：推 MisatoMitumi: 用心推! 01/02 07:33
2F：→ MisatoMitumi: 想比對一下原po預設的答案，第一題上下倒過來看， 01/02 07:33
3F：→ MisatoMitumi: 動三根火柴棒有1201+01=1202 01/02 07:34
4F：推 MisatoMitumi: 第八題看來是rank 1，然後第一小題給的是generator 01/02 07:40
5F：推 Starvilo : 2.2^11-3^3不知是否最小 01/02 13:03
6F：推 reye : 樓上，我的答案和你一樣 01/02 17:20
7F：推 alan23273850: 回5.6樓，第二題的證明才是真正有趣的。 01/02 19:27
8F：推 MisatoMitumi: Q3先給一個157步的參考路徑（不過確定有更佳解） 01/03 19:57
9F：→ MisatoMitumi: （只列出取階乘的數字）2021->26->2116->973->268-> 01/03 19:58
10F：→ MisatoMitumi: 124->1726->53226->3059->36191->35910->32820->110 01/03 19:59
11F：→ AnnaOuO : 看不懂樓上數字變化.. 01/05 11:37
12F：推 LPH66 : 以第一個箭頭為例, 2021 取階乘後開十二次平方根得 01/05 12:11
13F：→ LPH66 : 約 26.13, 在這裡向下取整得 26; 下一步是 26! 01/05 12:13
14F：→ ejialan : M大列的數列經過取階乘->取n次平方根->高斯記號 01/05 12:13
15F：→ LPH66 : 其開三次平方根後得約 2116.91 向下取整得 2116 01/05 12:13
16F：→ LPH66 : 依此類推 01/05 12:13
17F：→ ejialan : n依序為12 3 11 10 8 6 10 16 11 15 15 16 01/05 12:18
18F：推 LPH66 : OK, 第三題寫程式跑個開頭就看到為何確定有更佳解了 01/05 18:39
19F：→ LPH66 : 26 可以不用上面說的 14 步獲得: 2021 不先做階乘 01/05 18:40
20F：→ LPH66 : 而是開兩次根號再取整得 6, 階乘 720 開方取整得 26 01/05 18:41
21F：→ LPH66 : 這樣只需要 6 步就能到 26 了 01/05 18:41
22F：推 LPH66 : 然後這支程式找到以下這個 88 步解: 接 26, 走 01/05 18:52
23F：→ LPH66 : 26-[4]>46-[4]>4062-[13]>37-[4]>496-[8]>24427 01/05 18:53
24F：→ LPH66 : -[14]>784453-[21]>110; -[n]> 表開 n 次平方再取整 01/05 18:54
25F：→ LPH66 : 不過這依然無法保證是最佳解, 因為程式計算關係 01/05 18:56
26F：→ LPH66 : 中間取階乘只在 < 10^15 的整數上用, 無法確定當 01/05 18:57
27F：→ LPH66 : 允許更大數時有沒有可能有更少步數的解 01/05 18:58
28F：→ LPH66 : 啊更正一下, -[n]> 表示階乘後開 n 次平方再取整 01/05 19:20
29F：→ LPH66 : 漏提了階乘步驟 XD 01/05 19:20
30F：推 MisatoMitumi: 88比預期的要低很多啊... 我是從110逆推的，所以202 01/05 20:05
31F：→ MisatoMitumi: 1->26可以更短是結束前才發現的XD 01/05 20:05
32F：→ MisatoMitumi: LPH大有辦法處理到(10^15)!附近嗎？我自己的方法是 01/05 20:08
33F：→ MisatoMitumi: 類似試著建立(10^5)內的有向圖，然後跑Dijkstra最短 01/05 20:08
34F：→ MisatoMitumi: 路徑，不過找到路徑就停了 01/05 20:08
35F：推 MisatoMitumi: 原來如此，計算Log(n!)的複雜度不是O(n)，看來我太 01/05 20:16
36F：→ MisatoMitumi: 沒效率了 01/05 20:16
37F：推 LPH66 : 對, 我原本以為大概也要 O(n), 不過想說這總和看著 01/05 21:50
38F：→ LPH66 : 像是個積分, 那似乎能用∫log(n) ~ n log(n) 估計 01/05 21:50
39F：→ LPH66 : 然後一查才發現拉馬努金有給出過很好的近似公式 01/05 21:51
40F：→ LPH66 : 大致形狀是 n log(n) - n + log(n 的三次式) 01/05 21:53
41F：→ LPH66 : 所以能算的 n 就變成 double 能表達的整數 ~9e15 了 01/05 21:54
42F：→ LPH66 : 不算到極限是因為不太能掌握精確度... 01/05 21:55
43F：→ LPH66 : 然後我沒有明確建圖, 而是把 階乘→開方 n 次→取整 01/05 21:58
44F：→ LPH66 : 這樣的 n+2 步對不同的 n 值散出去 01/05 21:59
45F：→ LPH66 : 核心還是 Dijkstra 但就是有踩到哪些點再記那些點 01/05 22:00
46F：推 MisatoMitumi: 原來如此，公式有趣！不過wiki給的誤差大約是1/1400 01/05 23:08
47F：→ MisatoMitumi: n^3，算是有點怕... 不知道現在找到最佳解頂多88步 01/05 23:08
48F：→ MisatoMitumi: 的話，爆出最佳解有沒有機會... 01/05 23:08
49F：推 LPH66 : 話說第九題我做出這個結果: 01/06 11:28
51F：→ LPH66 : 是不是最後那個條件有點太鬆了...? 01/06 11:29
52F：→ LPH66 : 等式只能推得領導係數我覺得是故意設計的 01/06 11:31
53F：→ LPH66 : (那個形式實在太剛好了) 所以猜是後一條件放太寬 01/06 11:31
54F：→ TimcApple : 嗯 是設計失誤 我第一個等式解錯了 01/09 10:54