goo blog　サービス終了のお知らせ　

いもあらい。

プログラミングや哲学などについてのメモ。

１０÷８１＝？。

2006-09-08 23:40:00 |  Study...
循環小数に関して、いろいろと面白いことを見つけたので。

計画数学のレポートをやっているときに、電卓を使って割り算をたくさんやってたんですよ。
そしたら、まぁ循環小数がたくさん出てくるわけですが、面白いものが何個かありまして。
しかも、じっくりと考察を加えると、それらが見事に繋がってきて、かなり面白い結果が得られたので。

まず１つ目。
0.081の逆数を求めようと、1÷0.081の計算をやったんですよ。
そしたら、
1÷0.081=12.345679012345…
というふうに、12345679012…と数字が続くものにｗ
で、小数点をちょこちょこといじれば、このエントリのタイトルにもあるとおり、
10÷81=0.12345679012345…
とよりきれいな形になります。
偶然こんな小数が得られたので、ビックリｗ
（８が抜けているのだけが残念ですが←最初気付かなかった＾＾；）

で、２つ目。
0.27、0.53、0.19の三つの数字を、合計がちょうど1になるように調節しようとしていたんですよ。
そのために、その三つの数の和、0.99でそれぞれの数を割るという計算、すなわち、
0.27÷0.99
0.53÷0.99
0.19÷0.99
という計算をしたのですが、その答えは
0.27÷0.99=0.272727…（≒0.27）
0.53÷0.99=0.535353…（≒0.54）
0.19÷0.99=0.191919…（≒0.19）
と、割られる数が繰り返し出てくる循環小数となっています。
たしかに分母が9や99の分数は、分子が繰り返される循環小数になるという事実は知っていたのですが、それが思い浮かばずに、しばらく眺めているうちに割られる数が循環していることに気づいて、ビックリしました。

さてさて、先ほど述べた「分母が9や99の分数は、分子が繰り返される循環小数になっている」というものですが、よく示されるのはこの逆、すなわち、「0.…と…の部分が循環している小数は、（循環している数字）÷（循環している数字の桁数分の9が並んだ数字）である」というもの。
例えば、
0.11111…=1/9
0.3434…=34/99
0.532532…=532/999
といった具合。
こんな感じで、普通は循環小数が与えられて、それを分数に直す、という感じなので、逆に99で割ったときにどういう小数になるのかとかいったところが盲点になっていたわけです。

ところで、普通とは逆の方向から見ることで逆に分かってくることもあります。
数字を9や99で割ると循環する、というのは分かりました。
循環する小数から分数を得る場合には、その数字の桁数と9の並ぶ数は常に同じだったわけですが、それが異なる場合はどうなるのでしょう？
たとえば、
5÷99
とか、
142÷99
とか。

実際に試してくれば話は簡単で、
5÷99=5.0505050…
142÷99=1.434343…
となります。
前者は
5.0÷99
と考えれば、50の繰り返しになりそうです。
後者の場合は、次のように考えられます：

 1.42

    142

      142

        142

 +        …

 ――――――

 1.4343434……


つまり、9の並ぶ数だけ数字を右にシフトして、それを無限個足したもの、というわけです。
実際、前者も同じ書き方で

 5.0

    50

      50

        50

 +       …

 ――――――

 5.0505050…


と表せます。

では、後者のような場合で、繰上りが発生する場合はどうなるのでしょう？
例えば、
714÷99
とか、
597÷99
とか。

実際に計算してみると、
714÷99=7.212121…
597÷99=6.030303…
となります。
これをさっきと同じように書いてみれば、

 7.14

    714

      714

        714

 +        …

 ――――――

 7.11111111 ← 一の位のみ

   1 1 1 1  ← 繰り上がり

 ――――――

 7.21212121…


や、

 5.97

    597

      597

        597

 +        …

 ――――――

 5.92929292 ← 一の位のみ

   1 1 1 1  ← 繰り上がり

 ――――――

 6.03030303…


といった具合に、繰り上がりも反映されていることが分かります。

ここで、重要なことがあります。
すなわち、この桁をずらして足していく、というのをどんどんやっていったときに、いくら繰り上がりがあろうとも、小数点に近い方の数から数は固定されていってしまう、ということです。
これは、こうやって作っていった数が等比数列の和になっていて、いずれ収束することから明らかかと思われます。
（ただ、この証明が上手く出来なかった・・・だれか上手い具合に出来たらコメントにでも書いてください。）

このことを認めれば、その桁をずらしていく数がたとえ無限小数であっても、その数が循環するものであるならば、ある程度で区切りをつけて、それを足してから、それに対して十分小数点に近いものだけを取れば、それは正しい数字になっていることが分かります。

たとえば、さっきの597÷99をやるとして、

 5.97      5.97

 +  597 → +  5　（小数第３位以降は無視）

 ―――    ――

           6,02　（小数第１位までは正しい）


 5.97        5.97

    597　 →    597　（小数第５位以降は無視）

 +    597    +    5

 ――――    ―――

             6.0302　（小数第３位までは正しい）


といった具合です。

さて、これで準備は完了です。
今改めて、10÷81を考えてみましょう。

10÷81は、よく見てみると、10÷9÷9と同じです。
そこで、今までやってきたことに倣ってまず10÷9をやってみましょう。

これは単純で、

 1.0

   10

    10

     10

      10

 +     10

 ――――

 1.11111…


と、1がずっと続く循環小数になります。

そして、これをさらに9で割るわけですが、さっき示したことを使って、順に桁数を伸ばしていくと、

 1.111111

   111111

    11111

     1111

      111

       11

 +      1

 ――――

 1.234567


 1.1111111111

   1111111111

    111111111

     11111111

      1111111

       111111

        11111

         1111

          111

           11

 +          1

 ――――――

 1.2345679011


 1.11111111111111

   11111111111111

    1111111111111

     111111111111

      11111111111

       1111111111

        111111111

         11111111

          1111111

           111111

            11111

             1111

              111

               11

 +              1

 ――――――――

 1.23456790123455


 1.1111111111111111111111

   1111111111111111111111

    111111111111111111111

     11111111111111111111

      1111111111111111111

       111111111111111111

        11111111111111111

         1111111111111111

          111111111111111

           11111111111111

            1111111111111

             111111111111

              11111111111

               1111111111

                111111111

                 11111111

                  1111111

                   111111

                    11111

                     1111

                      111

                       11

 +                      1

 ――――――――――――

 1.2345679012345679012343


という風に、一番最初に得られた結果にどんどん近づいていきます。

単純な10÷81ですが、こんな風に考えるとなかなか奥が深くて面白いｗ
繰り上がりがある程度の桁までしか影響を与えない、ということの証明が上手く出来なかったことだけが残念ですが。


自己言及問題（バックトラック編）。

2006-07-16 22:27:00 |  Study...
自己言及問題をバックトラック法で解く方法について。

まず、バックトラック法で解くために、この問題を（ある程度まで）定式化します。
そのための考察をしていきましょう。

さて、この問題ですが、重要なのは文字が「記号」であると同時に、「意味」でもある、ということです。
たとえば、２（５）となっていれば、この５というのは「１つの記号」であると同時に、「（２という記号が）５個ある」という意味も持ちます。
そこでまず、この問題の「記号」という側面にのみ注目していきます。

本当は答えが２桁以上になることも許しているのですが、ここでは１桁に限るものとします。
すると、例えば２００６年５月１０日であれば、数字は枠内に全部で２７個（日付で７個、左側の０～９の数字で１０個、カッコの中に書く数字が１０個）となります。
つまり、基本的な考え方としては、２７個の枠があり、そこに０～９の数字を書いていく、となります。
けれど、そこで発想を転換して、２７個のボールを用意して、それを０～９の筒の中に入れていく、という風にしてもいいはずです。
その方法で今後考えていくことにします。

まず、１７個のボールは自動的に振り分けられます。
さて、残りの１０個も０～９の筒に振り分けられていくわけですが、０の筒に振り分けられるボールの個数をx_0個、１の筒に振り分けられるボールの個数をx_1個、・・・と表していくことにすると、この個数の合計は当然１０個になります。
すなわち、
Σx_i = 10 (0≦i≦9)
という式が得られます。

次に、「意味」という側面に注目していきます。
x_iの個数が何を意味しているのか、といえば、筒に入っているボールの数がi個の筒がx_i個ある、という意味になります。
なぜなら、iの筒に入っているボールの数はすなわちその枠内にあるiという記号の数を表しているわけですが、x_iの意味するところは、すでに決まってしまっている数字以外でiという数字がx_i回出てくる、つまり、カッコ内にiという数字がx_i回出てくる、ということになります。
このとき、カッコ内にiという数字がx_i回出てくるわけですから、枠内に数字がi個出てくる数字がx_i個ある、という意味になります。
つまり、その和をとってやれば、出てくる数字の個数全体になるわけです。
すなわち、
Σ(i*x_i) = 27 (0≦i≦9)
という方程式が得られます。

具体的な例を出しましょう。
０｜●●●●
１｜●●○○○
２｜●●○○
３｜●○
４｜●○○○
５｜●●○
６｜●●
７｜●
８｜●
９｜●
（●：初期配置数字、○：振り分け数字）
これは２００６年５月１０日のものですが、●が最初から枠内にあった数字、○がカッコの中に振り分けていく数字を意味します。
つまり、最初枠内には０が４つ、１が２つ、２が２つ、３が１つ、・・・、９が１つ、とあったわけです。
ここに○を振り分けていってカッコに入る数字を決めていくわけですが、その積まれている○の数がすなわちx_iに相当します。

さて、どう積んでいくにしろ、○の個数は（１桁と決めた以上）１０個と決まっているわけです。
すなわち、
Σx_i = 10 (0≦i≦9)
です。

それと、上の状態であれば、１には合計５個の丸がついていますが、１つは日付の中の１、１つはカッコのすぐ左にある１です。
残りの３つの意味するところは、カッコ内に３つ、１という数字が入る、という意味です。で、そのとき、カッコに１が入った数字は枠内に１個しか数字がないからカッコに１という数字が入ったわけです。
つまり、筒にボールが１つしか入っていないものが３つある、ということになります。（実際、７、８、９はボールが１つしか入っていません。）
同様に、ボールが２つ入っているのが２こ（３と６）、ボールが３つ入っているのが１つ（５）、ボールが４つ入っているのが３つ（０、２、４）、・・・となっています。
このとき、ボールが１個入っているものが３つあるわけですから、その合計は３個、ボールが２個入っているものが２つあるわけですから、その合計は２×２＝４個、ボールが３個入っているものが１つあるわけですから、その合計は３×１＝３個、・・・と、その合計を出せば、入れたボール全部の数になりますから、
Σ(i*x_i) = 27 (0≦i≦9)
となります。

他にも方程式が導き出せそうなのですが、なかなか・・・
まぁ、とりあえずこれを使って必要条件となるx_0～x_9のセットを出して、十分性も満たすかどうかをチェックすればいいわけです。（十分性のチェックは、入っているボールの数がi個のものがちょうどx_i個であるかを調べればOKです。）

これに基づいたバックトラック法のプログラムは次のようになります：

/*--------------------------------------------------

jiko.c




自己言及問題を無理やり解く



=構文=



% ./jiko numbers



numbersで数字の列を指定（例：2006711）




#include ＜stdio.h＞
#include ＜stdlib.h＞

#define MAX 50

int main(int argc, char *argv[]);
int *arg_analy(char *arg, int *count);
void init_base(int *base, int *numstr, int size);
void init_add(int *add);
int get_ans(int *base, int *add, int level, int total);
int check(int *base, int *add);
void print_ans(int *base, int *add, int *numstr, int size);

int main(int argc, char *argv[]){

    int base[10];

    int add[10];

    int *nums;

    int count;

    int total;

    int flag;

    char *str;


    //初期化

    count = 0;

    if(argc＞=2){

        str = argv[1];

        nums = arg_analy(str, &count);

    }

    init_base(base, nums, count);

    init_add(add);

    total = count + 10; //1*x_2+・・・+8*x_9=totalとなるように


    //検索＆チェック

    flag = get_ans(base, add, 1, total);


    //答えを出力

    if(flag == 0){

        printf("見つかりませんでした。\n");

        return 0;

    }

    else{

        print_ans(base, add, nums, count);

        return 0;

    }


}

int *arg_analy(char *arg, int *count){

    char *str;

    int *nums;


    str = (char *)malloc(2*sizeof(char));

    nums = (int *)malloc(MAX * sizeof(int));

    for((*count)=0; (arg[(*count)] != '\0')&&((*count)＜MAX); ++(*count)){

        sprintf(str, "%c", arg[(*count)]);

        nums[(*count)] = atoi(str);

    }


    return nums;


}

void init_base(int *base, int *numstr, int size){

    int i;


    for(i=0; i＜10; i++){

        base[i] = 1;

    }


    for(i=0; i＜size; i++){

        base[numstr[i]] += 1;

    }


}

void init_add(int *add){

    int i;


    for(i=0; i＜10; i++){

        add[i] = 0;

    }


}

int get_ans(int *base, int *add, int level, int total){

    int i;

    int flag;

    int now_total;

    int add_total;


    now_total = add_total = 0;

    for(i=1; i＜level; i++){

        now_total += (9-i) * add[10-i];

        add_total += add[10-i];

    }


    flag = 0;

    if(level == 9){ //終了判定

        add[1] = 10 -add_total;


        //条件を満たしていなければ上へ返す

        if((add[1]＜0)||(add[1]＞9)){

            add[1] = 0;

            return 0;

        }

        if(now_total != total){

            return 0;

        }


        //チェックをして、結果を返す

        flag = check(base, add);

        if(flag == 0){

            add[1] = 0;

            return 0;

        }

        else{

            return 1;

        }

    }

    else{   //暫定判定

        for(i=0; (i＜10)&&(flag==0); i++){

            add[10-level] = i;

            now_total += (9-level)*add[10-level];

            add_total += add[10-level];

            if((now_total ＜= total)&&(add_total ＜= 10)){    //条件を満たしていたら次へ

                flag = get_ans(base, add, level+1, total);

            }

            //次のために元に戻しておく

            now_total -= (9-level)*add[10-level];

            add_total -= add[10-level];

        }


        //答えが見つかったとき

        if(flag == 1){

            return 1;

        }

        //そうでないとき

        else{

            //元に戻して、上に返す

            add[10-level] = 0;

            return 0;

        }

    }


}

int check(int *base, int *add){

    int i;

    int flag = 1;

    int backet[10] = {0,0,0,0,0,0,0,0,0,0};


    //数が何個あるかを調べてbacket配列へ

    for(i=0; i＜10; i++){

        if((base[i]+add[i])＞9){

            flag = 0;

        }

        else{

            backet[(base[i]+add[i])] += 1;

        }

    }


    //チェックを行う

    for(i=0; i＜10; i++){

        if(add[i] != backet[i]){

            flag = 0;

            break;

        }

    }


    return flag;


}

void print_ans(int *base, int *add, int *numstr, int size){

    int i;


    if(size == 0){

        printf("引数なし");

    }

    for(i=0; i＜size; i++){

        printf("%d", numstr[i]);

    }

    printf("\n");


    for(i=0; i＜5; i++){

        printf("%d( %d ) ", i, base[i]+add[i]);

    }

    printf("\n");

    for(i=5; i＜10; i++){

        printf("%d( %d ) ", i, base[i]+add[i]);

    }

    printf("\n");


}

実行例は次のような感じです。

% ./jiko
引数なし
0( 1 ) 1( 7 ) 2( 3 ) 3( 2 ) 4( 1 )
5( 1 ) 6( 1 ) 7( 2 ) 8( 1 ) 9( 1 )

% ./jiko 2006510
2006510
0( 4 ) 1( 5 ) 2( 3 ) 3( 4 ) 4( 3 )
5( 3 ) 6( 2 ) 7( 1 ) 8( 1 ) 9( 1 )

% ./jiko 2006711
見つかりませんでした。

興味深いのは、２００６年７月１１日だと１桁の範囲で答えを持たなかったことと、２００６年５月１０日のものは、さっきの答えとは別の答えが出力されていること、すなわち、解が一意に定まっていないということ。
あとで改良して答えを全部出力する形にしてみたいと思っているのですが、どれくらい解に一意性が現れないものなのかが気になります。

（追記：2006.7.17、check関数内でセグメントエラーを起こす不具合を修正）


自己言及問題（プログラム編）。

2006-07-15 18:31:00 |  Study...
自己言及問題を解くプログラムに関して。

ちょうど上のリンク先になっているエントリのコメントに、god-tigerさんがプログラムの案を書いてくれていたので、それに関して。

god-tigerさんのアルゴリズムを表現すると、次のようになります：
Step1.A0～A9の変数を用意。
Step2.Ai（0＜=i＜=9）に、A0～A9で数字iが出てくる回数に１加えたものを、順に代入。これを１００回繰り返す。

要は、０の出てくる個数を更新→１の出てくる個数を更新→・・・→９の出てくる個数を更新→０の出てくる個数を更新→・・・
を繰り返すことで、収束させよう、というものです。

ただし、コメントのほうにも書いたとおり、これは収束する保障がありません。
実際、このプログラムを拡張して2007年7月11日の場合について動かしてみましたが、振動してしまいました。（コメント欄参照）

ただ、後述しますが、バックトラック法を用いたプログラムで調べたところ、2007年7月11日はそもそも１桁の範囲では答えを持たない日付のようです。

でも、ならちゃんと答えを持つ日付なら収束するのか、というと、そうとは限らないようです。
実際、ちゃんと答えを持つ2006年5月10日の場合についてプログラムを動かすと、次のような出力になります：

（最初のほう省略）
4 times.
2006.5.10
0 (4) 1 (6) 2 (3) 3 (3) 4 (3)
5 (2) 6 (3) 7 (1) 8 (1) 9 (1)
5 times.
2006.5.10
0 (4) 1 (5) 2 (3) 3 (5) 4 (2)
5 (4) 6 (2) 7 (1) 8 (1) 9 (1)
6 times.
2006.5.10
0 (4) 1 (5) 2 (4) 3 (1) 4 (4)
5 (3) 6 (2) 7 (1) 8 (1) 9 (1)
7 times.
2006.5.10
0 (4) 1 (6) 2 (3) 3 (3) 4 (3)
5 (2) 6 (3) 7 (1) 8 (1) 9 (1)
8 times.
2006.5.10
0 (4) 1 (5) 2 (3) 3 (5) 4 (2)
5 (4) 6 (2) 7 (1) 8 (1) 9 (1)
9 times.
2006.5.10
0 (4) 1 (5) 2 (4) 3 (1) 4 (4)
5 (3) 6 (2) 7 (1) 8 (1) 9 (1)
（以下略）

確認してもらえれば分かりますが、振動してしまっています。
これに順ずる方法（たとえば、更新した数字先を次に変更する（A1に3を入れたら、次はA3更新する、といった感じ）など）も、やはりうまくいかないでしょう。

そこで、バックトラック法を行って答えを探していくことを考えますが、そのためにはまずどう枝刈りを行うのか、ということを考えなければなりません。
そこで出てくるのがこのエントリで書いた式なのですが、それは次のエントリで説明したいと思います。

（こう、○○編とかが続いていくと、高○プリントみたいだｗ）


高校入試の問題より。

2006-07-08 10:13:00 |  Study...
【問題】
（１）平方数を４で割ったあまりは０または１であることを示せ。
（２）全ての辺が奇数であるような直角三角形は存在しないことを示せ。
（高校入試の問題より）

（２）はもう少し強くて、
（２’）全ての辺の長さが整数である直角三角形の直角をはさむ２辺の少なくとも一方は偶数であることを示せ。
だったかも・・・

たしか慶應志木の問題だった気が・・・
まぁ、問題自体を思い出すのにすら一苦労だったので、分からないですが＾＾；

ちなみにこの問題は、（１）の結果を使って（２）がスマートに出るというものです。
まぁ、直接（２）を出してしまってもかまわないのですが、（１）があることでよりスマートになります。


解答編。

（１）について
n=2k(k=0,1,・・・)のとき
　n^2=(2k)^2=4k^2より、４で割ったあまりは０。
n=2k+1(K=0,1,・・・）のとき
　n^2=(2k+1)^2=4k^2+4k+1=4(k^2+k)+1より、４で割ったあまりは１。
以上より、平方数を４で割ったあまりは０または１。//

（２）について
直角三角形の３辺をa,b,c(a＜b＜c、a,b,cは整数)とする。
a,bがともに奇数であると仮定して、矛盾を導く。
（１）より、
　a^2=4i+1　(i=0,1,・・・）
　b^2=4j+1　(j=0,1,・・・）
となる。
三平方の定理より
　a^2+b^2=c^2
であるが、
　a^2+b^2=(4i+1)+(4j+1)=4(i+j)+2
となるから、比較して
　c^2=4(i+j)+2
しかし、これは平方数を４で割るとあまりが０または１となることに矛盾。
したがって、a,bの少なくとも１つは偶数である。（（２’）が示された）
ゆえに、全ての辺が奇数であるような直角三角形は存在しない。//

（２）の解答を見て分かるとおり、もちろん（１）の結果を使わないでもちゃんと背理法さえ使えれば（２）は大丈夫ですね。
なんか、もう少し難しい問題が（３）とかであったような気がしなくもないのですが・・・まぁ、それは分かり次第更新したいです。


Ｎ進自己言及問題（メモ）。

2006-06-15 03:06:00 |  Study...
自己言及問題の拡張に関して。

自己言及問題についてはこちら。

自己言及問題の解析をするために、とりあえずは日付が無く、一般のN進数にして拡張したものについて調べていっています。
すなわち、


 ┌──────────┐

 │この枠内に次の数字が│

 │いくつずつあるかを　│

 │数字で記入しなさい。│

 │０（　）　　１（　）│

 │　　　　　・　　　　│

 │　　　　　・　　　　│

 │　　　　　・　　　　│

 │n-2（　）　n-1（　）│

 └──────────┘



で、各空欄にはN進表記での数字が入る、というものです。

これの２進数の場合は結構調べやすく、いろいろといじることが出来ました。（まだ、納得のいくものにはなってないのと、具体的な式は得られていないのですが。）

今回のエントリでは、とりあえず４進数までの答えで見つけたものをメモしておきます。

２進数


 ┌────────────┐

 │　この枠内に次の数字が　│

 │　いくつずつあるかを　　│

 │　数字で記入しなさい。　│

 │０（１１）　１（１００）│

 └────────────┘



３進数


 ┌────────────┐

 │　この枠内に次の数字が　│

 │　いくつずつあるかを　　│

 │　数字で記入しなさい。　│

 │０（１０）　　１（１０）│

 │２（　２）　　　　　　　│

 └────────────┘



４進数（１）


 ┌────────────┐

 │　この枠内に次の数字が　│

 │　いくつずつあるかを　　│

 │　数字で記入しなさい。　│

 │０（　１）　　１（　２）│

 │２（　３）　　３（　２）│

 └────────────┘



４進数（２）


 ┌────────────┐

 │　この枠内に次の数字が　│

 │　いくつずつあるかを　　│

 │　数字で記入しなさい。　│

 │０（　１）　　１（１１）│

 │２（　２）　　３（　１）│

 └────────────┘



４進数で二通りの答えが出てるのが興味深いです。
（２進数、３進数で上に挙げたもの以外の答えがあるかどうかはまだ示せてないです。２進数はなさそうですが。）