作者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/cn.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