平成１７年３月６日
[流れ星]
第１５１回数学的な応募問題解答
＜解答募集期間：２月１３日～３月６日＞
［規則性の発見］
皆さんは、「コラッツ・角谷予想」をご存じでしょうか。現在のところ未解決のようです。これは次のことです。
「ある２以上の整数についての操作で、
（１）その整数が偶数なら２で割る。
（２）その整数が奇数なら３倍して１を加えて２で割る
を繰り返して行うと、必ず４→２→１に達する」 という問題です。
では、次のように操作を変えて考えます。
「ある与えられた２以上の整数から始めて、次の操作を行う。
（１）その整数が偶数なら２で割る。
（２）その整数が奇数なら１を加える。
（３）その整数が１になるまで、（１）、（２）を繰り返す。
例：１３→１４→７→８→４→２→１
ここで、問題です。一般に２以上の整数ａｎが上の操作で
ａｎ→ａｎ－１→・・・→ａ２→ａ１→１
となったとき、整数ａｎは「操作数」ｎを持つという。
例１：「操作数」３の整数 ８→４→２→１ 、 ３→４→２→１
例２：「操作数」６の整数 １３→１４→７→８→４→２→１
このとき、次の問を考えてください。
問１：「操作数」１の整数、「操作数」２の整数を見つけてください。
問２：「操作数」ｎを持つ整数の個数をｆ（ｎ）としたとき、ｆ（３），ｆ（４），ｆ（５），ｆ（６）を求めてください。
問３：ｆ（ｎ＋２）をｆ（ｎ＋１）とｆ（ｎ）との間に成り立つ漸化式を予想してください。
問４：問３の予想を証明してください。
ＮＯ１「H7K」 2/13: 20時13分受信 更新3/6
ＮＯ２「浜田明巳」2/14: 12時32分受信 更新3/6
エクセルのマクロで，２以上１０００００００以下の整数について計算したところ，
ｆ(ｎ＋２)＝ｆ(ｎ＋１)＋ｆ(ｎ)（ｎ＝１，２，３，………，２１）
が成立する事が分かりました．桁数をもっと増やせば，もっと大きなｎについても成立するでしょう．
つまりFibonacci数列になります．
問１：ｆ(ｎ)＝１←→ｎ＝２， ｆ(ｎ)＝２←→ｎ＝４
問２：ｆ(３)＝２，ｆ(４)＝３，ｆ(５)＝５，ｆ(６)＝８
問３：ｆ(ｎ＋２)＝ｆ(ｎ＋１)＋ｆ(ｎ)
Option Explicit
Const MAX As Long = 10000000
Sub Macro1()
Sheets("Sheet1").Select
Dim f(MAX) As Long
Dim a(MAX) As Long
Dim n As Long
Dim k As Long
For n = 1 To MAX
f(n) = 0
Next
Cells(1, 10).Value = 0
Cells(2, 10).Value = 0
Range("A1").Select
For n = 2 To MAX
a(n) = 0
k = n
While k <> 1
If k Mod 2 = 0 Then
k = k / 2
Else
k = k + 1
End If
a(n) = a(n) + 1
Wend
For k = 1 To 2
If a(n) = k Then
Cells(k, 10).Value =
Cells(k, 10).Value + 1
Cells(k, Cells(k,
10).Value + 10).Value = n
End If
Next k
If a(n) <= MAX Then
f(a(n)) = f(a(n)) + 1
End If
Next n
'
n = 1
While f(n) > 0 And n <= MAX
Cells(n, 1).Value = n
Cells(n, 2).Value = f(n)
If n >= 3 Then
Cells(n, 3).Value =
"=R[-2]C[-1]+R[-1]C[-1]"
Cells(n, 4).Value =
"=IF(RC[-2]=RC[-1]," + Chr(34) + "成立"
+ Chr(34) + "," + Chr(34)
+ "不成立" + Chr(34) + ")"
End If
Range("A" & n).Select
n = n + 1
Wend
Range("A1").Select
End Sub
ＮＯ３「Toru」 2/15: 01時36分受信 更新3/6
k≧2の整数のときk>k/2,k>(k+1)/2であるから、この操作で得られる数は（１たす
時は次に２で割るのとセットで考えれば）減少する自然数の列を作る。よって必ず、
有限回の操作で1に達する。
ことを確認しておいて、
問１
操作数１の整数 ２→１より2
操作数２の整数 ４→２→１より4
問２
操作数３の整数 １回の操作で4になることから3,8
よってf(3)=2
操作数４の整数 １回の操作で3 or 8になることから6,7,16
よってf(4)=3
操作数5の整数 １回の操作で6,7,16になることから5,12,14,15,32
よってf(5)=5
問３ f(1)=1,f(2)=1,f(3)=2,f(4)=3,f(5)=5 フィボナッチになりそうです。
f(n+2)=f(n+1)+f(n) と予想します。
問４ n=1,2,----として、操作数(n+2)の整数のうち偶数のものは操作数(n+1)の任意
の数を２倍したものだからその数はf(n+1)に等しい、奇数のものは、操作(n+1)回の
整数のうち偶数のものから1を引いた数、つまり、操作数n回の任意の数の２倍から１
を引いた数で、その数はf(n)に等しい。よってf(n+2)=f(n+1)+f(n)
ＮＯ４「cbc」 2/15: 07時14分受信
更新3/6
ＮＯ５「KINO」 2/15: 15時50分受信 更新3/6
はじめまして。KINOと申します。 初めて投稿いたします。
楽しい時間を過ごせる，とても面白い問題でした。
No. 151 の解答
問1. 操作数 1 の整数は 2 のみ。
（求める整数 m に施した操作が(1)ならば m/2=1 より m=2,
(2) ならば m+1=1 とならなければならないが，これは不適。）
操作数 2 の整数は 4 のみ。
（一回操作を施したら操作数 1 の整数，すなわち 2 にならなければ ならない。求める整数 m に施した操作が(1)ならば
m/2=2
より m=4,
(2) ならば m+1=2 とならなければならないが，これは不適。）
問2. f(3)=2, f(4)=3, f(5)=5, f(6)=8.
操作数 3 の整数：3, 8.
操作数 4 の整数：6; 7, 16.
操作数 5 の整数：5, 12; 14; 15, 32.
操作数 6 の整数：10; 11, 24; 13, 24; 30; 31, 64.
問3. f(n+2)=f(n+1)+f(n) と予想される。
問1 と問2 の結果を合わせて考えると，f(1)=f(2)=1 であるから
この予想は n=1, 2, 3 のとき成立していることがわかる。
問4. 上の予想を証明する。
以下では，簡単のため 2 以上の整数のことを単に整数と呼ぶことにする。
まず E(n), O(n) でそれぞれ操作数が n である整数のうち
偶数のものの集合と奇数のものの集合を表し， それぞれの集合の要素の個数を e(n), o(n) とおく。
E(n) と O(n) は互いに素であり，それらを合わせたものが操作数 n の整数全体になることから，f(n)=e(n)+o(n)
が成り立つ。
操作数 (n+1) の整数に一度操作を施すと操作数が k の整数になったとすると，もとの整数の操作数は
(k+1) となるから，
n+1=k+1, すなわち n=k でなければならない。
したがって，操作数 (n+1) の整数に一度操作を施すと操作数 n の整数になる。
よって，操作数 n の整数から操作数 (n+1) の整数を全て生成することができる。
次のことに注意する。
整数 x に一回操作を施して整数 y になったとすると，
施す操作は (1) と (2) しかないため，x/2=y または
x+1=y のいずれか のみが成り立つ。
すなわち，一回操作を施して整数 y になる整数は
2y または y-1 の二通りの可能性しかない。
a を E(n) の要素のひとつとすると，2a は偶数，a-1 は奇数である。
操作(1)を 2a に施すと a になり，操作(2)を a-1 に施すと a になる。
すなわち，2a は E(n+1) の要素であり，a-1 は O(n+1) に属する。
一方，b を O(n) の要素のひとつとすると，2b，b-1 は共に偶数である。
これらには操作(1)のみしか施すことができない。その結果は
b と (b-1)/2 になるが，b=(b-1)/2 の解は b=-1 のみであり，
これは不適。よって 2b のみ E(n+1) に属する。
以上により，
e(n+1)=e(n)+o(n), o(n+1)=e(n)
という関係式が成り立つことが示された。
最初の等式より特に e(n+1)=f(n) であることがわかる。
よって，
f(n+2)=e(n+2)+o(n+2)=f(n+1)+e(n+1)=f(n+1)+f(n)
となり，予想した等式が成り立つことが示された。
ＮＯ６「kashiwagi」2/17:07時47分受信 更新3/6
151回解答
問１．操作1回で１となるのは２以外に考えられないので求めるものは２である。又、操作２回
で２となるとは１回の操作で２となれば良いので、これも４しかないことが分かる。条件から２以上の整数とされているので１は不適であることが分かる。
問２．上記結果を逆に辿ればよいので、３回の操作で１となるには１回で４、２回で２となれば良いので３と８の２個である。
後は同様にして、４回の操作：６，７，１７ の３個
５回の操作：５，１２，１４，１５，３２ の５個
６回の操作：１０，１１，１３，２４，２８，３０，３１，６４ の８個
即ち、ｆ（３）＝２、ｆ（４）＝３、ｆ（５）＝５、ｆ（６）＝８ となる。
問３．上記より明らかな様に ｆ（ｎ＋２）
＝ ｆ（ｎ＋１）＋ ｆ（ｎ） の関係が成り立つ。
問４．ｆ（ｎ＋２） ＝
ｆ（ｎ＋１）＋ ｆ（ｎ） 式のｎに１を代入すると問１よりｆ（１）＝１、ｆ（２）＝１であるのでｆ（２）＋ ｆ（１）＝２である。又、問２の結果より ｆ（３）＝２であるので確かにｆ（２）＋
ｆ（１）＝ ｆ（３）が成り立つ。
ここでｎ＝Kの時上記式が成り立つとすると、ｆ（ｋ＋２） ＝ ｆ（ｋ＋１）＋ ｆ（ｋ）＝ ｆ（ｋ＋１）＋ ｆ（ｋ）である。
今、この式の右辺にｆ（ｋ＋１）を加えると、右辺はｆ（ｋ＋１）＋
ｆ（ｋ）＋ｆ（ｋ＋１）となり、ｆ（ｋ＋１）＋ ｆ（ｋ）＝ｆ（ｋ＋２） であるので結局 ｆ（ｋ＋２） ＋ ｆ（ｋ＋１）となる。 これはｆ（ｋ＋２）
＝ ｆ（ｋ＋１）＋ ｆ（ｋ）の関係からｆ（ｋ＋３） である。
因ってｆ（ｋ＋３） ＝
ｆ（ｋ＋２）＋ ｆ（ｋ＋１）が成立する。この式は以下の様に書ける。
ｆ（（ｋ＋１）＋２）
＝ ｆ（（ｋ＋１）＋１）＋ ｆ（ｋ＋１）
即ち、ｎ＝K＋１でも成立することが分かる。以上よりｆ（ｎ＋２） ＝ ｆ（ｎ＋１）＋ ｆ（ｎ）であることが証明された。
Ｎｏ７「kasama」 2/17: 15時04分受信 更新3/6
いつも楽しい問題を作って頂きありがとうございます。
『コラッツ・角谷予想』ですか？本や雑誌でよく見かけます。
何ヶ月か前に、水野先生の『私の一日』でこの予想について書かれていたました。
フェルマの最終定理と同じく、予想の意味するところは、大した知識がなくとも、まぁ我々素人にでも理解できる訳ですが、・・・『私の一日』のリンクを辿って、
証明をチラリと見ましたが、そこに記載されている証明があっているものやら、間違っているものやら、？？？という状態です。
いつの日か解決するといいですね。
さて、今回の問題ですが、『記憶にある数列』になると書いていましたので、フィボナッチ数列かなぁと予想しながら問題に取り組みました。少々強引に証明した
ところがあります。
問1、2
ツリーで表現してみました。
問3
直感的に、ある操作数は1つ前と2つ前の操作数の和と考えられますから
f(n+2)=f(n+1)+f(n) (ただし、f(1)=1、f(2)=1)
と思われます。フィボナッチ数列でしょうか。
問4
問1、2の考察から、操作数の関係はノード①を頂点とした木構造と考えられ、操作の度にノードが分岐して広がります。ノードの分岐パターンは、ノードの数字によって、
奇数⇒偶数
偶数⇒奇数、偶数
の2通りと考えられます。
操作数n(≧1)の整数達は偶数または奇数の何れかであり、それぞれの個数をg(n)、h(n)とします。すると、
g(n+1)=g(n)+h(n)
h(n+1)=g(n)
です。つまり、
g(n+2)+h(n+2)=g(n+1)+h(n+1)+g(n+1)=g(n+1)+h(n+1)+g(n)+h(n)
⇒f(n+2)=f(n+1)+f(n) (ただし、f(1)=1、f(2)=1)
です。よって、f(n)はフィボナッチ数列となります。
No8「中川幸一」
03/06:18時30分受信 更新3/8
