全国各地でインフルエンザが流行していますね。私の周りでもただの風邪だと思ったら実はインフルだった、という人がちらほら出てきています。これからの時期は受験シーズン真っ盛りですから、受験生の皆さんは手洗いうがいは欠かさないようにしましょう。
因みに管理人は毎年、インフルエンザワクチンを接種していません。大昔に（小学生くらい？）したっきりです。多分今年も打ちませんね(笑)。栄養のあるものを沢山食べていれば、そう滅多に罹るものではありません。ただ、寝不足だと免疫が如実に弱るので、睡眠時間だけはしっかり確保したいところです･･･。
創作整数問題#35
《問題#35》
$0$以上$1$以下の既約分数を以下の手順で並べる。
まず分母が$1$となるような既約分数を大小順に並べる。分母が$2$となるような既約分数を大小順に並ぶように列に加える。さらに分母が$3$となるような既約分数を大小順に並ぶように列に加える。･･･これを続けていき、最後に分母が自然数$n$となるような既約分数を大小順に並ぶように列に加える。この数列を$F_n$とする。ただし、$\dfrac{0}{1}$および$\dfrac{1}{1}$は既約分数とみなすものとする。
例えば、$F_1$は$$\dfrac{0}{1}\ \ \dfrac{1}{1}$$となり、$F_3$は$$\dfrac{0}{1}\ \ \dfrac{1}{3}\ \ \dfrac{1}{2}\ \ \dfrac{2}{3}\ \ \dfrac{1}{1}$$となる。数列$F_n$の項数を$f^{\sharp}_n$とするとき以下の問いに答えよ。
（１）$n \geqq 2$ のとき、$f^{\sharp}_n$は奇数であることを示せ。
（２）数列$F_n$の総和が$\dfrac{f^{\sharp}_n}{2}$であることを示せ。
（創作問題）
数学愛好家にはたまらないファレー数列の話題です(笑)。設問自体は控えめになっておりますが、ファレー数列は格子点に関する性質や円に絡んだ性質などが知られる奥深い数列です。
お気付きの方も居られると思いますが、「既約」ということは分子と分母が「互いに素」ということですから、$f^{\sharp}_n$はオイラーのトーシェント関数を用いて記述することができます。これを知っていれば（１）は自明かもしれませんね。
なお、$f^{\sharp}_n$という記号（$F_n$も？）は一般的なものではないので他所では通じません。念のため･･･。
証明問題につき、解答例は次回掲載します。
創作整数問題#34（解き方）
| 任意の正の整数$n$に対して、各位の数字が$1$または$2$のみからなる正の整数であり$2^n$で割り切れるものが存在することを示せ。 |
創作問題とは言っているものの、割と有名な類の問題かもしれませんね。取り敢えず$2^n$で割り切れればよいので、帰納的にそのような数を構成できないか考えることにします。ここで、$2^n$でちょうど割り切れる必要はないことに注意しましょう。
例えば、$\color{green}{2}$、$\color{pink}{1}\color{green}{2}$、$\color{blue}{1}\color{pink}{1}2$、$\color{orange}{2}\color{blue}{1}12$、$\color{brown}{2}\color{orange}{2}112$、$\color{red}{1}\color{brown}{2}2112$、$\cdots$ としていけば、それぞれ$2^n$で割り切れ、かつ、すべての位の数が$1$または$2$のみからなる数を次々と作ることができます。
これを証明しましょう。
《解答例》
任意の正の整数$n$に対して、条件「各位の数字が$1$または$2$のみからなる正の整数であり、$2^n$で割り切れる」を満たす数が存在することを数学的帰納法を用いて示す。
$n=1$ のとき、$2$は条件を満たす。
$n=k$ のとき、ある正の整数$N_k$が条件を満たすとする。即ち、整数$N’_k$によって $N_k=2^k \cdot N’_k$ と表せるとする。
このとき、$$10^k+N_k=2^k(5^k+N’_k)$$であり、$$2 \cdot 10^k+N_k=2^k(2\cdot 5^k+N’_k)$$であるから、$N’_k$が奇数ならば $10^k+N_k$ は$2^{k+1}$で割り切れ、$N’_k$が偶数ならば $2\cdot 10^k+N_k$ は$2^{k+1}$で割り切れる。
よって $10^k+N_k$ または $2\cdot 10^k+N_k$ のいずれか一方は$2^{k+1}$で割り切れるから、$n=k+1$ のときも条件を満たす数が存在する。
したがって数学的帰納法により、任意の正の整数$n$に対して、条件「各位の数字が$1$または$2$のみからなる正の整数であり、$2^n$で割り切れる」を満たす数が存在することが示された。
□
（コメント）
随分あっさりと示すことができました。この議論を見て分かる通り、$0$から$9$までの任意の偶数と奇数のペアで同じことが言えます。例えば「各位の数字が$3$または$4$のみからなる正の整数であり、$2^n$で割り切れる」という条件を満たすものが存在します。
これがもし「$2^n$でちょうど割り切れる」という条件の場合は解答例の構成法では帰納法が使えません。この条件の場合、$n$の小さい方から列挙していくと、
$2=2^1$
$12=2^2×3$
$1112=2^3×139$
$112=2^4×7$
$22112=2^5×691$
$2112=2^6×3×11$
$2122112=2^7×59×281$
$122112=2^8×3^2×53$
$212122112=2^9×53×7817$
$1212122112=2^{10}×3×394571$
$12122112=2^{11}×3×1973$
$111212122112=2^{12}×7×13×17×17551$
$1111212122112=2^{13}×3^2×15071779$
$111111212122112=2^{14}×6781690193$
$211111212122112=2^{15}×3×29×74052907$
$1211111212122112=2^{16}×7×19×138948049$
$11111212122112=2^{17}×3559×23819$
$1111211111212122112=2^{18}×24733×171387781$
$2111211111212122112=2^{19}×101×39869461649$
$12111211111212122112=2^{20}×3^3×7×2393×25537781$
$111211111212122112=2^{21}×3×17676530077$
$\cdots$
となります。（※これらの数が「$2^n$でちょうど割り切れる、かつ、各位の数字が$1$または$2$」という整数のうちで最小のものかどうかは確認していません）
何か法則性がありそうな予感がしますが･･･(´-｀；)
#34について，「各位の数字が $1$ または $2$ のみからなる正の整数で，
$2^n$ で割り切れるものが，$n$ 桁のものとしてちょうど1つある」
こと，より強く，
「各位の数字が $1$ または $2$ のみからなる $n$ 桁の正の整数は，
$2^n$ で割った余りを $2^n$ 未満の任意の負でない整数にできる」($*$)
が成り立ちますね．
(($*$) の証明)
余りが指定されたとき，条件を満たす $n$ 桁の数を得るには，
次の手続きを用いればよい．
指定された余りを $R$ として，下位の数字から順次，以下のように定める．
既に得ている $k$ 桁の数を $S$ とする
(一の位を決める際は，$k=0,\ S=0$ とみなす)とき，
下から $k+1$ 桁目 ($10^k$ の位)は，
$\dfrac{S-R}{2^k}$ が偶数ならば $2$，奇数ならば $1$ とする．
この手続きによれば，帰納的に，下位 $k$ 桁を定めたとき
$R-S$ は $2^k$ の倍数となるので，確かに手続きを進めることができ，
下位 $n$ 桁を定めたときには，$S-R$ は $2^n$ の倍数となり，
$S$ を $2^n$ で割った余りは $R$ となる．
($*$) を用いれば，「$2^n$ でちょうど割り切れる」数の存在も明らかですね．
$n+1$ 桁の数で，$2^{n+1}$ で割った余りが $2^n$ であるものが
条件を満たします．
なお，この手続きで得られる数は，最小性を満たさない場合があります．
一方，「確認していない」と言われてはいますが，
$2^n$ でちょうど割り切れるものとして列挙されている21個の数たちは，
プログラムでチェックしたところ，最小性を満たしているようです．
たけちゃん さん、コメントありがとうございます。
余りを一般化できるというのは面白いですね！
解答例では $R=0$ としたバージョンの構成法で証明していますが、これによれば更に「$2^n$でちょうど割り切れる」数が存在することも直ちに従います。
一方で、各位の数字が$1$または$2$のみからなり、ちょうど$2^n$で割り切れる、という性質を持つ最小の正の整数を効率良く見つける方法はあるのでしょうか。プログラム等でしらみつぶしに調べるしかないのかもしれませんね。
まだまだ発展性のある話題なのだと改めて認識しました。
ご教示頂き感謝致します。