創作整数問題#34解法&創作整数問題#35

全国各地でインフルエンザが流行していますね。私の周りでもただの風邪だと思ったら実はインフルだった、という人がちらほら出てきています。これからの時期は受験シーズン真っ盛りですから、受験生の皆さんは手洗いうがいは欠かさないようにしましょう。

因みに管理人は毎年、インフルエンザワクチンを接種していません。大昔に(小学生くらい?)したっきりです。多分今年も打ちませんね(笑)。栄養のあるものを沢山食べていれば、そう滅多に罹るものではありません。ただ、寝不足だと免疫が如実に弱るので、睡眠時間だけはしっかり確保したいところです・・・。


創作整数問題#35


《問題#35》

0以上1以下の既約分数を以下の手順で並べる。

まず分母が1となるような既約分数を大小順に並べる。分母が2となるような既約分数を大小順に並ぶように列に加える。さらに分母が3となるような既約分数を大小順に並ぶように列に加える。・・・これを続けていき、最後に分母が自然数nとなるような既約分数を大小順に並ぶように列に加える。この数列をFnとする。ただし、01および11は既約分数とみなすものとする。

例えば、F101  11となり、F301  13  12  23  11となる。数列Fnの項数をfnとするとき以下の問いに答えよ。

(1)n2 のとき、fnは奇数であることを示せ。

(2)数列Fnの総和がfn2であることを示せ。

(創作問題)


数学愛好家にはたまらないファレー数列の話題です(笑)。設問自体は控えめになっておりますが、ファレー数列は格子点に関する性質や円に絡んだ性質などが知られる奥深い数列です。

お気付きの方も居られると思いますが、「既約」ということは分子と分母が「互いに素」ということですから、fnはオイラーのトーシェント関数を用いて記述することができます。これを知っていれば(1)は自明かもしれませんね。

なお、fnという記号(Fnも?)は一般的なものではないので他所では通じません。念のため・・・。

 

 

証明問題につき、解答例は次回掲載します。


創作整数問題#34(解き方)



創作問題とは言っているものの、割と有名な類の問題かもしれませんね。取り敢えず2nで割り切れればよいので、帰納的にそのような数を構成できないか考えることにします。ここで、2nちょうど割り切れる必要はないことに注意しましょう。

例えば、212112211222112122112 としていけば、それぞれ2nで割り切れ、かつ、すべての位の数が1または2のみからなる数を次々と作ることができます。

これを証明しましょう。

《解答例》

任意の正の整数nに対して、条件「各位の数字が1または2のみからなる正の整数であり、2nで割り切れる」を満たす数が存在することを数学的帰納法を用いて示す。

n=1 のとき、2は条件を満たす。

n=k のとき、ある正の整数Nkが条件を満たすとする。即ち、整数Nkによって Nk=2kNk と表せるとする。

このとき、10k+Nk=2k(5k+Nk)であり、210k+Nk=2k(25k+Nk)であるから、Nkが奇数ならば 10k+Nk2k+1で割り切れ、Nkが偶数ならば 210k+Nk2k+1で割り切れる。

よって 10k+Nk または 210k+Nk のいずれか一方は2k+1で割り切れるから、n=k+1 のときも条件を満たす数が存在する。

したがって数学的帰納法により、任意の正の整数nに対して、条件「各位の数字が1または2のみからなる正の整数であり、2nで割り切れる」を満たす数が存在することが示された。


(コメント)

随分あっさりと示すことができました。この議論を見て分かる通り、0から9までの任意の偶数と奇数のペアで同じことが言えます。例えば「各位の数字が3または4のみからなる正の整数であり、2nで割り切れる」という条件を満たすものが存在します。

これがもし「2nちょうど割り切れる」という条件の場合は解答例の構成法では帰納法が使えません。この条件の場合、nの小さい方から列挙していくと、

2=21
12=22×3
1112=23×139
112=24×7
22112=25×691
2112=26×3×11
2122112=27×59×281
122112=28×32×53
212122112=29×53×7817
1212122112=210×3×394571
12122112=211×3×1973
111212122112=212×7×13×17×17551
1111212122112=213×32×15071779
111111212122112=214×6781690193
211111212122112=215×3×29×74052907
1211111212122112=216×7×19×138948049
11111212122112=217×3559×23819
1111211111212122112=218×24733×171387781
2111211111212122112=219×101×39869461649
12111211111212122112=220×33×7×2393×25537781
111211111212122112=221×3×17676530077

となります。(※これらの数が「2nでちょうど割り切れる、かつ、各位の数字が1または2」という整数のうちで最小のものかどうかは確認していません)

何か法則性がありそうな予感がしますが・・・(´-`;)

 

“創作整数問題#34解法&創作整数問題#35” への2件の返信

  1. #34について,「各位の数字が 1 または 2 のみからなる正の整数で,
    2n で割り切れるものが,n 桁のものとしてちょうど1つある」
    こと,より強く,
    「各位の数字が 1 または 2 のみからなる n 桁の正の整数は,
    2n で割った余りを 2n 未満の任意の負でない整数にできる」()
    が成り立ちますね.

    (() の証明)
    余りが指定されたとき,条件を満たす n 桁の数を得るには,
    次の手続きを用いればよい.
    指定された余りを R として,下位の数字から順次,以下のように定める.
    既に得ている k 桁の数を S とする
    (一の位を決める際は,k=0, S=0 とみなす)とき,
    下から k+1 桁目 (10k の位)は,
    SR2k が偶数ならば 2,奇数ならば 1 とする.
    この手続きによれば,帰納的に,下位 k 桁を定めたとき
    RS2k の倍数となるので,確かに手続きを進めることができ,
    下位 n 桁を定めたときには,SR2n の倍数となり,
    S2n で割った余りは R となる.

    () を用いれば,「2n でちょうど割り切れる」数の存在も明らかですね.
    n+1 桁の数で,2n+1 で割った余りが 2n であるものが
    条件を満たします.

    なお,この手続きで得られる数は,最小性を満たさない場合があります.
    一方,「確認していない」と言われてはいますが,
    2n でちょうど割り切れるものとして列挙されている21個の数たちは,
    プログラムでチェックしたところ,最小性を満たしているようです.

    1. たけちゃん さん、コメントありがとうございます。

      余りを一般化できるというのは面白いですね!
      解答例では R=0 としたバージョンの構成法で証明していますが、これによれば更に「2nでちょうど割り切れる」数が存在することも直ちに従います。

      一方で、各位の数字が1または2のみからなり、ちょうど2nで割り切れる、という性質を持つ最小の正の整数を効率良く見つける方法はあるのでしょうか。プログラム等でしらみつぶしに調べるしかないのかもしれませんね。

      まだまだ発展性のある話題なのだと改めて認識しました。
      ご教示頂き感謝致します。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

©Copyright 2017-2025 理系のための備忘録 All Rights Reserved.