Re: [问题] 最小芦原倍数 (LYM) 问题

楼主: DreamYeh (天使)   2015-04-15 11:49:33
※ 引述《LPH66 (-6.2598534e+18f)》之铭言:
: 原先芦原伸之的谜题集里的题目是这样的:
: 从 2 ~ 9 当中挑出两个单位数,
: 找出恰使用这两个数位构成的数又同时是他们的公倍数中最小的数。
: 例: 3,5 => 3555
: 试问对所有存在这种公倍数的组合当中,这最小的公倍数最大的是多少?
这一题可列为puzzle
想法如下:首先策略当然是尽量挑9为开头的数,因此先挑出9
接着挑第二个数,本来想挑8?但这样一来所选的数末三位要是8的倍数
因此我们选7
我们可以假设最后的数是类似9999xxx999xxxx99xx
由于需要是9的倍数,因此每一位数加起来必须是9的倍数
考虑7的出现次数,直觉想法就是让他出现9次
最后考虑需要是7的倍数,答案就是7777779779
: 可以看到最一开始的题目就是这题的推广题的特例
: 这个题目当年在 MIT 的 Technology Review 上发表时
: 被称为 LYM (Least Yoshigahara Multiple) 问题
: 直接翻译就是“最小芦原倍数”
: 题目本身不难, 只是列举所有可能性去个别求这个倍数比较繁一点而已
: 那么这里就来考大家这个推广题:
: 如果把原题的限制放宽到 1 ~ 9,也不只取两个的话,
: 这个最大的“最小芦原倍数”又是多少?
: (当然这个公倍数必需只用所取的数字至少各一次)
这题就很开放,因为挑的数不只取两个,又放宽到1~9,
因此最大问题就是可以选的数过多
但我们仍然想些线索,首先注意到,所给的数字不包括0
这意味着如果我们要把1~9都选过,由于1~9的公倍数是2520,
因此所选的数必须是2520的倍数,这造成尾数无可避免的是0!!
尾数是0就违反规则
那就别让0出现,这样的挑法就变成
1.要嘛只挑1,2,3,4,6,7,8,9
2.要嘛只挑1,3,5,7,9
先不考虑后者,这样公倍数才315,构成的数字不大
前者公倍数则为504,如此答案有...
4968713232
这个数为504的倍数,且的确含1,2,3,4,6,7,8,9
(也是合乎条件的最小数)
但很遗憾的,要求“最大数”,那答案我想可能是无限大
以下都是用程式跑出的,都合乎需求:
LVM=49988372616
LVM=49988627136
LVM=49988631672
LVM=49988632176
LVM=49988636712
LVM=49988637216
LVM=49988763216
...........
如果要修正题目,我想最好还是“限制可挑的数字数目、例如原LVM中限制两个”
楼主: DreamYeh (天使)   2015-04-15 11:56:00
499988766312
作者: LPH66 (-6.2598534e+18f)   2015-04-15 20:11:00
呃, 后一题的问法跟前一题是一样的...都是找出所有组合的最小数里面最大的那一个不然单问最大数多大都可以不是吗...
楼主: DreamYeh (天使)   2015-04-15 21:19:00
那这样的话只能用暴力法 囧
作者: LPH66 (-6.2598534e+18f)   2015-04-16 00:44:00
认真说是这样没错, 所以这题要不要贴出来也是想了很久只是结果很有趣所以就还是贴上来了 XD

Links booklink

Contact Us: admin [ a t ] ucptt.com