TURN OF THE CENTURY/懸賞2001解答


 問題 を自然数とする。乗の下4桁が2001のとき、の下4桁は?

 解答 の下4桁は2001
解答者は若林宏氏忍者うどん氏もず氏の3名。全員正解でした。
皆さんに「TURN OF THE CENTURY」をお贈りします。

 若林宏氏
●回答
2001


●証明


○補題
「n^nの末尾m桁はnの下m桁で決まる」
(証明略、ほぼ自明)


これによって、1桁目より順番に決定していけばよい。


1桁目が1になるのは


・1(nは何でもよい)
・9(nは2の倍数)だが、


nの下一桁が9であることとnが偶数であることは矛盾するので、1桁目は1に確定する。


同様に2桁目は0になる。
2桁目を他の数字にすると、nが2の倍数/5の倍数/10の倍数の時に条件を満たすが、いずれも仮定した1,2桁目の条件に矛盾する。


3桁目も同様に0となる。


4桁目については以下の通り。


nの下4桁……n^nの下4桁が2001になる条件
0001……不適
1001……n=2+10a
2001……n=1+5a
3001……n=4+10a
4001……n=3+5a
5001……不適
6001……n=2+5a
7001……n=6+10a
8001……n=4+5a
9001……n=8+10a


上記のうち、左右矛盾しないのはnの末尾が2001のときのみ。
また、nの下4桁が2001の時、必ずn=1+5aの形で書き表されるので、「nの下4桁が2001である」という条件はn^nの下4桁が2001となるための必要十分条件である。


●短評
一番綺麗な答えになって満足しました。見事です。
補題は、
「n^nの末尾m桁は(nの下m桁)^nで決まる」
ですね。
2桁目(3桁目)、4桁目の決め方からはきちんと認識されていことが伺えます。

 忍者うどん氏
解答
2001
問題になるくらいだから想像です。
正直に言うとLongcalcという電卓フリーソフトで確認しました。
下一桁は手計算で1になったけど、2001乗は断念しました。
(10桁電卓では無理だってえの。ばかだねえ)
ですので当然、証明など私の頭では不可能です。


ところで、新しい作品集完成おめでとうございます。
神詰大全の続編を期待していたのですが、すぐに発行されるとは!
神詰大全も毎日で2ヶ月かかり堪能しました。
このところの一族の精力的な活動には敬服いたします。
今回はCDROM版で拝見させていただきます。(ごめんなさい)
ですので住所などは省略します。(懸賞では心苦しい)
これからも、作品や熱き語りなどで楽しませてくださいね。
ではまた。楽しみに待ちつつ…。
想像だろうが電卓を使おうが正解は正解です。


「神詰大全」お申し込みのときの住所を控えてありますので、「TURN OF THE CENTURY」も送付させていただきます。
ぜひ、お受け取りください。
今後もいろいろの作品集を出して行こうと夢想しています。こちらも気長にお待ち下さい。

 もず氏
答えはやはり、2001しかありません。
以下、簡単な証明です。
(証明)
nの下4桁をABCDとします。


2001は奇数なので、nも奇数。つまり、Dは1,3,5,7,9のいずれかです。
しかし、奇数乗して下一桁が1になりうるのは D=1 のときだけです。


次に、n = 1 + 10C +(100の倍数) とおくと、
n^n = 1 + n*10C +(100の倍数)
= 1 + 10C +(100の倍数)
となり、C=0 がわかります。


さらに、n = 1 + 100*AB +(10000の倍数) とおくと、
n^n = 1 + n*100*AB +(10000の倍数)
= 1 + 100*AB +(10000の倍数)
となり、AB = 20 がいえます。
(証明終)
簡単なというより簡潔な証明ですね。
蛇足ながら、上記証明には二項定理が使われています>訪問諸氏


ちなみに作者はまずプログラムを書いて検証したのでした。

/*
 * m = n % 10000 (m ^ n % 10000 = n ^ n % 10000)
 * m ^ g % 10000 = 1
 * m ^ a % 10000 = 2001
 * n = 10000 * x + m = g * y + a
 */

#include <stdio.h>

void main()
{
    long m, g, a, p;

    for (m = 0; m < 10000; m++) {
        if (m % 2 == 0 || m % 5 == 0) continue;
        for (p = 1, g = 1; ; g++) if ((p = p * m % 10000) == 1) break;
        for (p = 1, a = 1; a < g; a++) if ((p = p * m % 10000) == 2001) break;
        if (a == g) continue;
        if (10000 % g != 0 ) printf("!\n");
        else if ((m - a) % g != 0) continue;
        else printf("m = %ld\n", m);
    }
}

戻る