第４３３問の解答
問題［推理、整数の性質］
 |
 |
 |
|
|
ある整数を見て、１４人の人が次々にコメントを残しました。
この１４人の中に２人だけ嘘つきが混じっていて、しかもその２人は続けてコメントしたそうです。 |
|
 |
|
 |
解答例１
長野 美光さん、トトロ＠Ｎさん、アヒーのおじさんさん、あ〜く＠ジュークさん、辻。さん、きょろ文さん、uchinyanさん、hiroさん、エルクさん、小学名探偵さん、N.Nishiさん、M.Hossieさん、他
題意の整数をｘとすると、次の補題が成り立つことに注目します。
（補題１）２〜１５のある整数ｎ、ｍについて、ｍがｎの倍数なら、ｎはｘの倍数である。
ｍ＝ｎ×ｋと表すことが出来ます。従って、もしｍがｘの倍数でないとするとｎがｘの倍数であることと矛盾します。
（補題２）２〜１５のある整数ｎ、ｍについて、ｘがｎおよびｍの倍数ならば、ｘはｎ×ｍの倍数でもある。
こちらは明らかですね。
さて、２、３、４、５、６、７については、それぞれ２倍の４、６、８、１０、１２、１４が２〜１４に含まれるので補題１からｘの倍数となり、嘘ではありません。
また、１０＝２×５、１２＝３×４、１４＝２×７、１５＝３×５と表されるので、これらは全てｘの倍数。
よって、嘘の可能性が残るのは、８、９、１１、１３の４個となりますが、連続しているのは８と９の組み合わせのみです。
よって、ｘは８、９以外のすべての数の倍数で最小のものとなりますので、これらの最小公倍数ということになります。
従って、各数を素因数分解し、各素因数のべき数の最大値を求めることでみると、上表より、
ｘ＝２2×３1×５1×７1×１１1×１３1＝６００６０
と求まります。ｘの約数の個数は、各素因数のべき数＋１の積で表されるので、
（２＋１）×（１＋１）×（１＋１）×（１＋１）×（１＋１）＝９６個
と求まります。答： ９６個
以上
解答例２
ゴンともさん、ハラギャーテイさん、DrKさん、姉小路さん、他
２〜１４までを素因数分解すると下表のようになります。
もし、ｎ＝２k2×３k3×・・・×１３k13×がｘの倍数でないとすると、
どれかの素因数ｍについてxはｍkmの倍数でないことになります。従って、このときのkmは他の数のｍのべき数よりも必ず大きくないといけません。
もしそうでないと、その数の倍数でないことになるからです。このことから、素因数２のべき数が最大である８、素因数３のべき数が最大である９、および１１と１３が嘘の可能性ありということになります。
（その他の解法）
プログラムで求める ・・・ kasamaさん、Revinさん、 他