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

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

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

---

創作整数問題#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$」という整数のうちで最小のものかどうかは確認していません）

何か法則性がありそうな予感がしますが･･･(´-｀；)