Weekend Mathematics／問題／問題75

７５．最終結果は？

ある正の整数を計算するとき、次のような決まりがあります。
　(整数　→　正の整数　と修正します。ごめんなさい。3/3)

１．その整数が３で割り切れるときは、３で割ります。
２．その整数が３で割り切れないときは、１を足します。

上の決まりを守って、整数が１になるまで続けます。

(1)２４は何回の計算で１になりますか。
(2)５０は何回の計算で１になりますか。
(3)３回の計算で１になる整数をすべてあげなさい。

おまけ
(4)どんな正の整数から始めても、必ず１にたどりつくことを証明しなさい。

解答・その１

（ペンネ−ム：瑞樹）

(1)２４→８→９→３→１　となり、４回 (2)５０→５１→１７→１８→６→２→３→１　となり、７回

解答・その２

（ペンネ−ム：Y.M）

(1)〜(3)までは地道に計算しました。

ところで今回の問題と似たような問題が、今学校でやっている問題集の、 千葉大学の問題として出ていました。 こちらは3の倍数ではなく「2の倍数」でしたが・・・。

解答・その３

（ペンネ−ム：teki）

（１）　４回
（２）　７回
（３）　６、８、２７

（１）は、２４→８→９→３→１　の４回です。
（２）は、５０→５１→１７→１８→６→２→３→１　の７回です。
（３）は、３×（３−１）、３×３−１、３×３×３の３つが該当します。

解答・その４

（ペンネ−ム：モルモット大臣）

まず3で÷演算をA, 1を＋する 演算をBとします。

(1) A(24)=8→B(8)=9→A(9)=3→A(3)=1の4回の演算で1になります。

(2) B(50)=51→A(51)=17→B(17)=18→A(18)=6→A(6)=2→B(2)=3→ A(3)=1の7回

(3)ここで1に対する演算はもし行うとすればB(1)=2→B(2)=3→A(3)=1と3回で1に戻りま すが1は最初から演算の最終目標であるので省きます。
そこで逆算をしていきます。3回目で1になるためには2回目の演算結果が3であり3回 目の演算がAである必要があります。このため2回目の演算がAの場合は1回目の演算結 果は9である。また2回目の演算がBの場合は1回目の演算結果は2である必要がありま す。よって1回目の演算結果の場合は2または9となります。 AまたはBの演算で2または9となれば良いのですから

(1回目の演算結果が2の場合)
　　Aの演算結果なら最初の数は2×3=6
　　Bの 演算結果なら最初の数は1であるので1回目で1になるため不適

(1回目の演算結果が9の場合)
　　Aの演算結果なら最初の数は9×3=27
　　Bの 演算結果なら9-1=8

解答・その５

（ペンネ−ム：午年のうりぼう）

（１）、（２）

整数	計算の回数
	１	２	３	４	５	６	７
２４	８	９	３	１
５０	５１	１７	１８	６	２	３	１

上表より、　２４は　４回、５０は　７回　の計算で１になります。　…（答）

（３）

左図より、３回の計算で１になる整数は、

　　２７，８，６，１　…（答）

です。
（ちなみに、全ての整数を計算した場合でも、答えは上の４つのみです。 ?∵　負の整数でこの計算をやると、（４）より、一度も正の整数が出ないで、最後は０になります。０は３で割り切れるので、１が足せません。?）

（４）　Ｇｉｖｅ　Ｕｐ　です……?Ｔ＿Ｔ?。

解答・その６

（ペンネ−ム：杖のおじさん）

(1)24→8→9→3→1　　　　４回です。

(2)50→51→17→18→6→2→3→1　　　　　　７回です。

(3)整数ｎは１以上で１を加算してその整数ｎになるものと３で割ってその整数ｎになるものの２通りあります。 図に書くときは、逆に書きますので、１を基点として一方を１を引いて書き、 一方に３をかけて書いていきます。３回目の数字の中で、整数１をこえるものを数えます。

従って、６，８，２７です。

(4)整数ｎを３で割り割り切れるとあまりは０となり、割り切れないとあまりは１または２となります。 割り切れるまで１を加算いたしますので、最終結果は１となります。 どんな整数から始めても必ず１になることは次の様にして確かめました。

1	2	3	1
4	5	6	2	3	1
7	8	9	3	1
10	11	12	4	5	6	2	3	1
13	14	15	5	6	2	3	1
16	17	18	6	2	3	1
19	20	21	7	8	9	3	1
22	23	24	8	9	3	1
25	26	27	9	3	1
･･･	･･･	･･･	･･･	･･･
(3n-2)	(3n-1)	3n	n	･･･

上の図４列目の数列はｎとなっていますので、どんな整数ｎから始めても１になることが確認できます。

解答・その７

（ペンネ−ム：夢夜（むよ））

（１）まずは実験的に解きましょう。
２４＞８（１．）＞９（２．）＞３（１．）＞１（１．）
４回ですね。

（２）５０＞５１（２．）＞１７（１．）＞１８（２．）＞６（１．）＞２（１．）＞３（２．）＞１（１．）
７回ですね。

（３）計算方法は１回につき必ず２通りあります。
ところで、整数は正ですから、３で割る以上は０にならないので、最後は必ず１．が適用されます。 また、（２．）（２．）（１．）の組み合わせに当てはまるのは１しかないので除外します。 よって考えられるのは下の組み合わせです。
　　８＞９（２．）＞３（１．）＞１（１．）
　　６＞２（１．）＞３（２．）＞１（１．）
　　２７＞９（１．）＞３（１．）＞１（１．）
ゆえに答えは６、８、２７です。

（４）ところで何を証明すればいいのでしょうか？
それは「計算方法で３で割る操作があることから、どんな値も有限回数の計算の後に３で割られて必ず減少し、値は最後に１になる」ことを示せばいいのです。
数学的帰納法で証明します・・・証明中のnは自然数（ただし２以上）とします。

(base)n＝２，３の時は下のようにすぐに１になることが確認できます。
　　２＞３（２．）＞１（１．）
　　３＞１（１．）

(step)n>３の時にはnをある自然数mを用いて表すと、
n=3m,3m-1,3m-2で表されます。
このとき、nの定義から常にn>mですので有限回の操作でnからmに計算できるかを確認すればいいのです。

(i)n=3mの時
　　n=3m＞m（１．）
(ii)n=3m-1の時
　　n=3m-1＞3m（２．）＞m（１．）
(iii)n=3m-2の時
　　n=3m-2＞3m-1（２．）＞3m（２．）＞m（１．）

（１）（２）では足す回数（２．の適用回数）は下のようにして求めるのでしょうか。

• （２．）を適用する回数を求める解法
  
  （１）まずは３進数（ｔ）に変換します。
  　　　２４＝２２０（ｔ）、５０＝１２１２（ｔ）
  
  （２）３進数の最下位の０でない桁から最上位の桁までの数を調べ、各桁の値の総和を求めます。 これならば、どのような値でも正しい解答を得られます。 （先に挙げた例ですと、桁数＝３、総和＝４なので演算適用回数は３×２＋１−４＝３となります） なお、ここでいう最上位の位はもちろん０でない値が格納されているとします。
  
  （３）（桁数）×２＋１−（総和）で適用する回数が求まります。
  　　　（答え）２４＝１回、５０＝３回
  
  なお（３）の式は、要は３進数の処理で繰り上がりを含めて最上位（より１つ上の位）に１、後は０となるようにするための計算です。最上位より１つ上の位だけに１とすれば後は３で割るごとに１桁ずつシフトするということになります。（計算機の２進数シフト演算処理の応用ですね。）
  
  
• （１．）を適用する回数はガウス記号（値より大きい最小の整数。ここでは角括弧で表します）を用いれば、[log3 (n-1)]＋１（３は対数の底、またn>1）で表されます。
  

解答・その８

（ペンネ−ム：wasmath）

まず，問題文についてですが， (4)で必ず1にたどりつくことがはっきりする前に， 「1になるまで（作業を）続ける」というのはおかしいのではないでしょうか？ 「1でない限り作業を続け，1になれば作業をやめる」などの表現の方が 適切だと思いますが，いかがでしょう。

(1)，(2)，(3)をさぼって，(4)だけ解くことにします。

(4) 題意を整理すると，任意の自然数Nに対して，数列｛a_n｝を

　　　　　a₁=N， a_nが3で割り切れるとき a_n+1=a_n/3
　　　　　a_nが3で割り切れないとき a_n+1=a_n+1

で定めるとき， a_n=1となる自然数nが存在する　・・・・・・(*) ことを示せばよい。

いま，自然数を

1| 2，3 | 4，5，・・・，9 | 10，・・・

とグループ分けし， m番目のグループに属する自然数が 3^m-2より大きく， 3^m-1 以下になるようにする。 （m=1のとき3^m-2は整数でないが，つじつまは合っている。）

任意の自然数Nに対して

　　　　3^m-2＜N≦3^m-1

を満たす自然数mは（Nごとに）必ず存在するので， (*)が成り立つ ことをこのmについての数学的帰納法で証明する。

１°m=1すなわちN=1のとき(*)が成り立つのは自明。
２°（3^m-2，3^m-1 ] のとき(*)が成り立つとして， 3^m-1＜N≦3^m とする。 Nは

　　　　N=3q+r　（qは非負整数， r=0，1，2）

と表される。

r=0のとき，3で割って

　　　　3^m-2＜q≦3^m-1

r=1のときは，実際には 3^m-1＜3q+1≦3^m -2 であるから，

　　　　3^m-2＜q+1≦3^m-1

r=2のときも同様に， 3^m-1＜3q+2≦3^m -1 より

　　　　3^m-2＜q+1≦3^m-1

したがって， 数列｛b_n｝を

　　　　r=0のときはb₁=q，
　　　　r=1，2のときはb₁=q+1
　　　　b_nが3で割り切れるとき b_n+1=b_n/3
　　　　b_nが3で割り切れないとき b_n+1=b_n+3

という規則で定義すると，帰納法の仮定より

　　　　b_k=1となる自然数k=k(r)が存在する。

このとき

　　　　r=0のときn=k(0)+1
　　　　r=1のときn=k(1)+3
　　　　r=2のときn=k(2)+2

とすれば， a_n=1であるから （3^m-1，3^m ] でも(*)は成り立つ。 １°２°より題意は示された。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　（おわり)

解答・その９

（ペンネ−ム：スチューデント）

（１）２４→８→９→３→１　よって４回
（２）５０→５１→１７→１８→６→２→３→１　よって７回
（３）A→B→３→１の順で変わってきている。
ここで、Bには３で割るか１を足して３になる数なので、９と２のどちらかが入る。

　　（�@）Bが９のとき…うえと同様の理由で２７と８ 　　（�A）Bが２のとき…同じく１か６。

（�@）Mが３の倍数のとき
３で割った、変形後をM’とすると、M＞０より、Ｍ＞Ｍ’
ここで、Ｍ’が条件を満たすとすると、Ｍも条件を満たすので、Ｍが条件を満たさないという仮定に反する。逆にＭ’が条件を満たさないとすると、Ｍが条件を満たさない最小の正の整数であるという仮定に反する。よってこの時Ｍは存在しない。

（�A）Ｍが３で割ると１か２余る場合。
まずは操作によってＭは３の倍数まで１を足される。これを行って３の倍数となったものをＭ”とすると、Ｍ”＝Ｍ＋２（または＋１）／３だから、Ｍ＞１のときＭ＞Ｍ”。

（α）Ｍ＞１のとき、
ここで、Ｍ”が条件を満たすとすると、Ｍも条件を満たすので、Ｍが条件を満たさないという仮定に反する。逆にＭ”が条件を満たさないとすると、Ｍが条件を満たさない最小の正の整数であるという仮定に反する。よってこの時Ｍは存在しない。

（β）Ｍ＝１のとき、
１は条件を満たしているので、Ｍが条件を満たさないという仮定に反する。

解答・その10

（ペンネ−ム：バレー部）

(1)24→8→9→3→1　で４回です。

(2)50→51→17→18→6→2→3→1　で７回です。

(3)１になるためには、３のときに３で割られるしかないので、 まず最後に「３→１」となるのがわかります。ここから逆算していきました。

となるので、６と８と２７です。

(4)すべての数は以下の３つに分類できる。

ｎ≡０(mod　3)・・・�@
ｎ≡１(mod　3)・・・�A
ｎ≡２(mod　3)・・・�B

ｎ＋２≡０(mod　3)　もしくは、
ｎ＋３≡０(mod　3)

解答・その11

（ペンネ−ム：仮面Ｘ）

（１）４回

（２）７回
最大は９と３を通過する２７、最小は３だけを通過する６です。あとは、たす１で９を通過する８です。９を通過するのは他にはありません。３だけを通過するのは６だけです。

（３）６，８，２７

（４）割り終わった後で１番大きくなるのは、１を２回たしてから３で割るときです。２以上の数に２を足してから３で割ると、元の数より小さくなります。元の数の１より大きい部分を３等分した２つを、２つの１にあげるからです。計算を続けていくとどんどん小さくなって１になります。 全部暗算でやりました。当たってるかな〜？

解答・その12

（ペンネ−ム：リナライ）

解答:条件の1、2をそれぞれx、yと置きます

（1）24は3の倍数ですので
　　　　24÷3＝8（ｘ）
8は3の倍数ではありませんが、+1（ｙ）した9は3の倍数なので
　　　　9÷3=3（ｘ）
3は当然3の倍数なので
　　　　3÷3=1（ｘ）
よって、xyxxの順番ですので、1になるには計4回

（2）50は3で割りきれませんが、+1（ｙ）した51は3で割りきれますので
　　　　51÷3=17（ｘ）
17も3で割りきれませんが、+1（ｙ）すると18で割りきれます。
　　　　18÷3=6（ｘ）
6も割りきれるので
　　　　6÷3=2（ｘ）
2は3より少ないので、当然3では割りきれません。 よって+1（y）して3になり
　　　　3÷3=1（ｘ）
よってｙｘｙｘｘｙｘの順番で計7回

（3）3回の計算となる順列は
　　　　ｘｘｘ、ｘｘｙ、ｘｙｘ、ｙｘｘ、ｘｙｙ、ｙｘｙ、ｙｙｘ、ｙｙｙ
の８通りあります。これをそれぞれxの時×3、yの時−1すると

ｘｘｘ……1×3×3×3=27
ｘｘｙ……1×3×3−1＝8
ｘｙｘ……（1×3−1）×3＝6
ｙｘｘ……（1−1）×3×3＝0
ｘｙｙ……1×3−1−1＝1
ｙｘｙ……（1−1）×3−1＝−1
ｙｙｘ……（1−1−1）×3＝−3
yyy……1−1−1−1＝−2

おまけの（4）
yを2回繰り返す間に、必然的にxを行う「3で割りきれる」条件を満たすので、常にｘは行われます。 例えば、整数zがあるとすると、z、ｚ＋1、z＋2の中に、必ず一つ3で割りきれる数があります。 また、自然数を3で割ると、必ず数は1に近くなります。 よって、回数に制限が無い限り、正の整数は1に辿りつく事ができます

解答・その13

（ペンネ−ム：figo）

(1) 4回
(2) 7回
(3) 6,8,27
(4) 正数を1でない数xとする(1は計算の必要がないので)

(i)xが3で割り切れる時
　　　　xに2の計算をするとxより小さい数が得られる。

(ii)xを3で割った余りが1の時
　　　　xに1の計算を2回施し、2の計算をするとxより小さい数が得られる。なぜなら

　　　　　x>(x+2)/3
　　　　　3x>x+2
　　　　　2x>2
　　　　　x>1

であるので。

(iii)xを3で割った余りが2の時
　　　　xに1の計算を1回施し、2の計算をするとxより小さい数が得られる。なぜなら

　　　　　x>(x+1)/3
　　　　　3x>x+1
　　　　　2x>1
　　　　　x>1/2

であるので。

(i)(ii)(iii)より、計算を繰り返すといくらでも小さい正数が得られる。1は最も小さい正数であるので、必ず1にたどり着く。

解答・その14

（ペンネ−ム：理一郎坊ちゃん）

３で割る操作を／、１を足す操作を＋とかくことにする。その右に結果をかく。

（１）２４／８＋９／３／１　よって、４回。

（２）５０＋５１／１７＋１８／６／２＋３／１　よって、７回。

（３）Ａ＃Ｂ＄３／１　となるＡを求める。＃、＄は操作／または＋である。
＃＄＝＋＋、＋／、／＋、／／の４通り考えられる。
式を逆にたどると、＃＄＝＋＋のとき、１／３＋２＋１で、Ａ＝１。これは題意に相応しくない。
　　　　　　　　　　　　 ＃＄＝＋／のとき、１／３／９＋８で、Ａ＝８
　　　　　　　　　　　　 ＃＄＝／＋のとき、１／３＋２／６で、Ａ＝６
　　　　　　　　　　　　 ＃＄＝／／のとき、１／３／９／２７で、Ａ＝２７　以上３通り。

（４）すべての正整数は、３の倍数か、３の倍数に１足りないか、 ３の倍数に２足りないかのいずれかである。 したがって、操作＋を１回、または２回行うことですべての整数は３の倍数に帰着できる。 たかだか２を加えれば３の倍数になるのだから、それを３で割った数は、元の数より小さい。 したがって、操作を繰り返せば必ず３に至る。３／１で、必ず１にたどり着く。

よく似た問題ですが、おそらく未解決の問題があります。

「奇の自然数ｎに対して、Ｎ＝３ｎ＋１（偶数）を考え、これを２で割れるだけ割った奇数の商を 先の式のｎに代入する。これを繰り返すと必ず１に至る。」

解答・その15

（ペンネ−ム：巷の夢）

全ての正の整数は３で割れるもの、1余るもの及び2余るものに分けられる。 1〜3について題意に示された計算を行うと、

1の場合　1+1= 2　→　2+1 = 3 → 3/3 = 1 即ち3回計算し、1になる。
2の場合　2+1 = 3 → 3/3 = 1 即ち2回計算し、1になる。
3の場合　3/3 = 1 即ち1回計算し、1になる。

(1) 24/3 = 8 → 8+1 = 9 → 9/3 = 3 この3回に上記1回を加え4回となる。

(2) 全く同様の計算を行うと、2になるまでに5回計算する。因って7回で1になる。

(3) 題意より3×3×3　＝27は題意を満たす。
又、3で割ったものが2となる6も題意を満たす。
9は2回で1となるので、1を加えて9となる8も題意を満たす。
これに当初計算した1を加え、求めるものは　1、6、8及び27である。

(4) これまでの計算でも明らかだが、全ての正の整数を３で割る事を繰り返せば、必ず正の整数である1、2及び3のどれかに帰結する。即ち、どんな正数からこの計算を始めても必ず1に辿り着く。

解答・その16

（ペンネ−ム：暇人）

（１）�@4÷3=8　�A8+1=9　�B9÷3=3　�C3÷3=1　より　4回････（答）

（２）�@50+1=51　�A51÷3=17　�B17+1=18　�C18÷3=6 �D6÷3=2　 �E2+1=3　　 �F3÷3=1 より　７回････（答）

（３）1から逆算すると

　　　

となるので，　６，８，２７････（答）

（４）上記操作のうち，3で割るまでの操作を１操作と考え,これを （A）とすると上記操作は（A）の繰り返しとなる．このとき,

�@）（A）によって得られる整数は1以上である．
（証明）３の倍数にした後,３で割るから明らかである．
�A）２以上の整数は（A）によって元の値よりも小さくなる．
（証明）操作の対象となる整数をｎ,正の整数をｍとすると

ａ）n=3mのとき
　　　　n÷3=mより　m<3m=n
ｂ）n=3m＋1のとき
　　　　n+1=3m+2⇒n+2=3m+3=3(m+1)⇒(n+2)÷3=m+1<3m+1=n
ｃ）n=3m-1のとき
　　　　n+1=3m⇒(n+1)÷3=m<3m-1=n

よってａ）〜ｃ）より�A）が成り立つ． �B）１から始めると１に戻る．
（証明）１＋１＝２⇒２＋１＝３⇒３÷３＝１となり,１に戻る．

以上のことから,どんな正の整数から始めても（A）の繰り返しにより１にたどり着けることがわかる．（証明終）

解答・その17

（ペンネ−ム：BossF）

１．整数が３で割り切れるときは、３で割ります。
２．整数が３で割り切れないときは、１を足します。
計算１を�@、計算２を�Aとします

(1)24�@8�A9�@3�@1　4回

(2)50�A51�@17�A18�@6�@2�A3�@1　7回

(3)最後は必ず�@ですから、
　�@�@�@、�@�A�@、�A�@�@、�A�A�@の４通り
すると、27、6、8、1
１は、不適ですから　6、8、27■

(4)まず、題意の演算Eは、自然数に関して閉じていることに注意します
さて、任意の自然数N_k（≠1)に対しEを行うと、高々２回の�Aの後�@が行われます
が、その結果を N_k+1 とすると
あきらかに N_k＞N_k+1ですから {N_k}は単調減少です。
したがって、任意の自然数Nは、有限回のEの後1になります■

ところで、Nが負の場合は0にたどりつきますね。
[証明]任意の整数N_k（≦-3)に対しEを行うと、高々２回の�Aの後�@が行われますが、 その結果を N_k+1 とすると
あきらかに N_k＜N_k+1＜0　ですから {N_k}は単調増加です。
すなわち、任意の整数N（≦-3)は、有限回のEの後-1か、-2になります。ところ が、-2も�Aにより、-1になります。
さて、-1�A0　■

解答・その18

（ペンネ−ム：夜ふかしのつらいおじさん）

（１）［２４→８→９→３→１］の４回です。

（２）［５０→５１→１７→１８→６→２→３→１］の７回です。

（３）３回の計算で最後は（１．）の決まりでなければなりません。
（２．）の決まりでは０から１増えることになるからです。
決まりが２種類しかないので次の３回の場合しか可能性がありません。

　　　　決まりが（１．１．１．）の場合、［２７→９→３→１］
　　　　決まりが（１．２．１．）の場合、［６→２→３→１］
　　　　決まりが（２．１．１．）の場合、［８→９→３→１］
　　　　決まりが（２．２．１．）の場合、［１→２→３→１］＊

（４）�T．始める自然数が１ならば、もうたどりついています。
　　　　始める自然数が２ならば、［２→３→１］
　　　　始める自然数が３ならば、［３→１］
のように、１にたどりつきます。

　　�U．自然数Ｎは、ｎを自然数として、

　　　　（ａ）３ｎ−２、　（ｂ）３ｎ−１、　（ｃ）３ｎ

のどれかに分類できます。それぞれに決まりの計算をし、初めて３で割るところまでを１つの「まとまりの手続き」とします。するとそれぞれ次のようになります。

　　　　　（ａ）３ｎ−２　→　３ｎ−１　→　３ｎ　→　ｎ
　　　　　（ｂ）３ｎ−１　→　３ｎ　　　→　ｎ
　　　　　（ｃ）３ｎ →　ｎ

Ｎ＝１以外の自然数について、「まとまりの手続き」を行うと元の自然数より必ず小さな自然数となります。

　　　　　（ａ）３ｎ−２＞ｎ　（ｎ＞１，ｎ＝１のときがＮ＝１）
　　　　　（ｂ）３ｎ−１＞ｎ
　　　　　（ｃ）３ｎ＞ｎ

しかもこの自然数ｎを新たにＮと考えると、また（ａ）（ｂ）（ｃ）のどれかに必ず分類できます。 自然数Ｎは有限です。「まとまりの手続き」を行うと必ず元の自然数より小さくなるので何回か「まとまりの手続き」を行えばそのうち１か２か３のどれかになるので、必ず１になってしまいます。

解答・その19

（ペンネ−ム：前髪）

(１)　実際にやってみます。
　　２４→８→９→３→１　より、４回。

(２)　(1)と同様に、
　　５０→５１→１７→１８→６→２→３→１　より、7回。

(３)　１から逆の操作をおこなってみます。
　　１→３→９→２７
　　１→３→９→８
　　１→３→２→６
より、６，８，２７の３パターンのみである。

(４)　ｘ≧１のとき、全ての自然数は
　　　３ｘ−２、３ｘ−１、３ｘ
の３パターンのどれかで書ける。これらは問いの操作により、

1. ３ｘ−２　→　３ｘ−１　→　３ｘ　→　ｘ　（３ｘ−２≧ｘ　等号はｘ＝１のみ。）
2. ３ｘ−１　→　３ｘ→　ｘ　　　　　　　　　　（３ｘ−１＞ｘ）
3. ３ｘ　→　ｘ　　　　　　　　　　　　　　　　　（３ｘ＞ｘ）

以上ですが、どうでしょうか。（４）の考え方としては、フェルマーの「無限降下 法」の気持ちで考えました。ペル方程式のような考え方かなとも思ったのですが。（１から任意の数 が逆操作で作れるか?）
あと、問いの計算を３進法で考えると、｛｝を３進法表示の数字として、
　２４＝｛２２０｝→｛２２｝→｛１００｝→｛１０｝→｛１｝
のように、「下一桁が０なら、それを消去する。それ以外なら１を加える。」の操作と同等になり、任意の自然数の３進法表示から｛１｝に有限回で変形できることもいえます。

解答・その20

（ペンネ−ム：三角定規）

(1)

	�@	�A	�B	�C
24	→8	→9	→3	→1

　　　　　　　　［答］4 回

(2)

	�@	�A	�B	�C	�D	�E	�F
50	→51	→17	→18	→6	→2	→3	→1

　　　　　　　　［答］7 回

(3) 逆にたどれば
　　�B1の前はつねに3，3の前は
　　　　�A-1 9を3で割った，9の前は
　　　　　　�@-1-1 27を3で割った
　　　　　　�@-1-2 8 に1を加えた
　　　　�A-2 2に1を加えた，2の前は
　　　　　　�@-2-1 6を3で割った
　　　　　　�@-2-2 1に1を加えた　← これはない 　　　［答］6，8，27

(4)［証明］
与えられた初期値Nに対し 3ⁿ≦N＜3ⁿ⁺¹ を満たす整数n（n≧0）は一意的に定まる。 このとき，Nを3進数で表すとn + 1桁の数となり，各桁の数を10進数のように左から並べて 　｛t_nt_n-1…t₁t₀｝と表すことにする。ここで，t_n≠0，t_k (k＝0，1，n−1）は0，1，2である。

(�@) Nが3の倍数のとき，t₀＝0で，Nを3で割ることは3進数表示を1桁右にずらす
｛t_nt_n-1…t₁t₀｝→｛t_nt_n-1…t₁｝ことを意味し，n桁の3進数になる。

(�A) Nが3の倍数でないとき，t₀＝1，2。

(Ａ) t₀＝1のとき，Nに1を加えればt₀＝2となり，次の（Ｂ）の場合となる。
(Ｂ) t₀＝2のとき

�@ t_n，t_n-1，…，t₁ がすべて2ならばN＝3ⁿ⁺¹−1 で，これに1を加える
とN＝3ⁿ⁺¹，t_n+1＝1，t_n＝t_n-1＝…＝t₀＝0となる。このNは，この後n＋１回続けて3で割れ，1になる。
�A t_n，t_n-1，…，t₁ に0または1があれば，t_n，t_n-1，…，t₁ のいずれかが1増えることで＋1の影響を吸収できる。そして＋1の後 t₀＝0となり，この後（�@）に帰着する。

問題文をざっと一読して、「あっ、角谷の予想！　あれ？　角谷の予想って証明できたん だっけ？」Yahooで“角谷の予想”をきちんと調べて、「な〜んだ、ちょっとちがうんだ」。 だけど、これができるんだから、“角谷の予想”だって同じ方法で証明できないのかな？　と、しばしいじくってみましたが 、やはり簡単にはいかないようですね。

解答・その21

（ペンネ−ム：Toru）

（１） ?24÷3=8　?8+1=9 ? 9÷3=3 ?3÷1=1 ということで４回

（２） ?50+1=51 ?51÷3=17 ? 17+1=18 ?18÷3=6 ?6÷3=2 ? 2+1=3 ?3 ÷3=1ということで７回

（３） 逆に計算してみると３をかけるか１を引くことになります。 ?1×3=3 ?3-1=2 or 3×3=9 ?2×3=6, 9-1=8, 9×3=27 ということで6,8,27

（４-1） 証明１
与えられた正の整数をN(0)とすると、連続する３つの正整数N(0),N(0)+1,N(0)+2のうちどれかは３で割り切れるので、この商をN(1)とする とN(1)も正の整数で、
　N(0)＞1ならば、N(0)-N(1)≧N(0)-(N(0)+2)/3=(N(0)-1)×2/3＞0よりN(0)＞N(1)、
　N(0)=1ならN(0)=N(1)、
同様にN(1),N(1)+1,N(1)+2のうちどれかは３で割り切れるので、この商をN(2)とするとN(2)＞1ならN(1)＞N(2),N(1)=1な らN(1)=N(2)、同様に N(3),N(4),---と順に決めていくと、一般にN(k)も正の整数で、 N(k)>N(k+1) (N(k)>1),N(k)=N(k+1) (N(k)=1)となる。あらゆる与えられたN(0)に対 してN(0)より小さい正の整数は有限個しかないので十分な回数くり返せば

　　N(0)＞N(1)＞N(2)＞N(3)＞N(4)＞-------＞N(m)=N(m+1)=--------=1

となるようなmが存在することが示された。

（４-2） 証明２
ある正の整数N＞1を与えられた時（N=1の時は明らか）3^n-1＜N≦3ⁿとなるn(n=1,2,---)が存在し、3ⁿ-N=Mとすれば、0≦M＜2×3^n-1より Mを3 進法であらわすとn桁以下になって、これを

　　A₁A₂A₃------A_n (A₁=0,1,A_k=0,1,2(k=2 〜n))

とすると、１０進法では

　　M=A₁×3^n-1＋A₂×3^n-2＋--------＋A_n-1×3＋An

となる。この時

　　N＝3ⁿ―M＝3ⁿ―A₁×3^n-1―A₂×3^n-2−---------−A_n-1×3 −A_n ＝(---((((((1×3−A₁)×3−A₂)×3−A₃)×3−A₄)×3−------−A_n-1)×3)−A_n

だから、Nに1をA_k回（k=n→1）足して3で割る計算をくり返していけば最終的に1とな る。必要な計算の回数は1を足すのがΣA_k(k=1〜n)回,3で割るのがn回で、n+ΣA_k　回。

いつも楽しませてもらってありがとうございます。今回は３進法の問題ですね。たと えば(2)の50は３進法では1212でやっていることは、1の位が0になるまで1をたして、 0をとるくり返しで、1212→1220→122→200→20→2→10→1の７回ということです。 （決まり２）が1を足すのでなくて、1を引くのなら、このまま単純にいけますが、足 す場合は繰り上がりがあったりするので、ちょっと工夫して証明２のようにしてみま した。この場合は50なら1212=10000-1011とすれば、1を足す操作が３回、0をとる（3 で割る）操作が４回で計７回であることがすぐに分かります。最終的に1になるのは、 直感的には当たり前のことのようですが、きちんと証明しようとするとなかなか考え させられました。

解答・その22

（ペンネ−ム：浜田　明巳）

　エクセルのマクロで解きました．

(1) 4回

(2) 7回

(3) 1000000以下の正整数の中では，6，8，27の3個だけでした．

(4) 1000000以下の正整数において成り立つ（マクロが何もなく終了する）ことを示しました．

Option Explicit
Sub Macro1()
    Sheets("Sheet1").Select
    Range("A1").Select
    Dim n As Long
    Dim kotae As Integer
    Dim mondai As Integer
    Dim max As Long
    For mondai = 1 To 2
      If mondai = 1 Then
        n = 24
      Else
        n = 50
      End If
      Cells(mondai, 1).Value = kaisuu(n)
    Next mondai
    '
    max = 1000000 '********
    kotae = 0
    For n = 1 To max
      If kaisuu(n) = 3 Then
        kotae = kotae + 1
        Cells(3, kotae).Value = n
      End If
    Next n
    Cells(4, 1).Value = "このマクロで,n≦" + Str(max) + "のｎにおいて,すべて1になることを示しました."
End Sub
Private Function kaisuu(ByVal n As Long) As Long
    Dim nn As Long
    nn = n
    kaisuu = 0
    While nn <> 1
      kaisuu = kaisuu + 1
      If nn Mod 3 = 0 Then
        nn = nn / 3
      Else
        nn = nn + 1
      End If
    Wend
End Function

解答・その23

（ペンネ−ム：kiyo）

(1)4回

(2)7回

(3)6, 8, 27

おまけ

正の整数をNとする。

1. N==0 (mod 3)　　　N->N/3　→　N>N/3　　　　　　　　１回の操作
2. N==1 (mod 3)　　　N+1+1　→　(N+2)/3　　(N+2)>N>(N+2)/3　　　　３回の操作　　
3. N==2 (mod 3)　　　N+1　→　(N+1)/3　　　(N+1)>N>(N+1)/3　　　　２回の操作　

高々３回の操作で元の数より小さくすることが出来る。したがって、どんな正の整数から始めても、有限回の操作で必ず１にたどりつくことが出来る。

おまけのおまけ

n回の操作で１となる正の整数の個数を、F（ｎ）とする。
F(1)=1,F(2)=2,F(3)=3
F(n+3)=F(n+2)+F(n+1)+F(n)
トリボナッチ数列ですね。

解答・その24

（ペンネ−ム：kirkland）

Ａ君	「(１)、(２)はそのままですよね。24→８→９→３→１で４回と、50→51→17→18→６→２→３→１で７回です。」
先生	「(３)は、どうする？」
Ａ君	「う〜ん、逆から考えていったらいいんじゃないですか。３回目に１になるには２回目は３です。０はだめですよね。２回目に３になるためには、１回目は９か２です。表にまとめた方が早いですね。というわけで６、８、27の３個」 ３回目 ２回目 １回目 はじめ １ ３ ９ 27 ８ ２ ６
先生	「ところで、４回の計算で１になる数は何個か分かるかな？表を書かずに考えよう。まず、すべての数は３で割るとその余りが０か１か２になるね。以下、４回の計算で１になる数全体をＡ４と書くことにしよう。Ａ３、Ａ２等も同様だ。Ａ４に含まれる数のうち、３で割った余りが０のものは何個あるか分かるか？」
Ａ君	「これは簡単。Ａ３の数をそれぞれ３倍したものですから、個数はＡ３全体の個数と同じです。」
先生	「その通り。次はＡ４に含まれる数のうち、３で割って２余る数は？」
Ａ君	「Ａ３に含まれる３の倍数から１引いたものだから、Ａ３の３の倍数の個数と等しい。ということは、Ａ２全体の個数と同じですね。」
先生	「順調、順調。残るは、Ａ４のうち３で割って１余る数だ。」
Ａ君	「Ａ３のうちで３で割って２余る数の個数と等しいので、Ａ１全体の個数と同じです。ということは、Ａ４全体の個数は、Ａ１、Ａ２、Ａ３それぞれの個数の和になって、１＋２＋３＝６個です。 それじゃあ、Ａ５は２＋３＋６＝11個ですね。」
先生	「その通り。小島先生に教わったんだが、トリボナッチ数列という名前らしいよ。さて、おまけの(４) を考えよう。」
Ａ君	「１はもちろんＯＫ、２は２→３→１でＯＫ、３も３→１でＯＫです。」
先生	「すると、４〜９もすべてＯＫだということは分かるかな？」
Ａ君	「適当に１を加えると、４と５は６に、７、８は９に帰着できます。６、９はそれぞれ３で割ると２、３ になります。２、３はすでにＯＫなので、４〜９はＯＫです。」
先生	「次は？」
Ａ君	「10〜27の数は適当に１を加えて３で割ると４〜９になります。４〜９は既にＯＫであるということが 分かっているので、10〜27もＯＫです。この感じで次は、28〜81、82〜243、……と順々にＯＫになっ ていきますね。」
先生	「まあ小学生ならそんな感じでいいだろう。厳密には数学的帰納法というものを用いるんだが。」
Ａ君	「今回は、ギャグもなく真面目に終わっちゃいましたね。うー！ストレスたまるなぁ。」

問題文が不明確でご迷惑をおかけしました。
wasmathさんの

(4)「1になるまで（作業を）続ける」というのはおかしいのではないでしょうか？「1でない限り作業を続け，1になれば作業をやめる」などの表現の方が適切だと思いますが，いかがでしょう。

ですが、ご指摘の通りですね。混乱を招いて申し訳ありませんでした。

(4)について、結果は容易に納得できるのですが、いざ証明となるとなかなかむずかしいですね。 数学帰納法や、背理法なども用いて証明していただきました。 大局的にみれば減少数列であることと、有限であるというところを押さえていただければいいのかなと思います。

kiyoさん、kirklandさんの解答にありますように、 ｎ回の操作で１となる正の整数の個数をF（ｎ）とおく数列を作ると、トリボナッチ数列になります。 考えてみれば確かにそうなのですが、驚きですね。

夢夜さんの３進法表示による計算回数の考察はなかなか興味深く読ませていただきました。

類似の未解決問題をいただきましたので、ここに改めて載せさせていただきたいと思います。

理一郎坊ちゃんから、

「奇の自然数ｎに対して、Ｎ＝３ｎ＋１（偶数）を考え、これを２で割れるだけ割った奇数の商を先の式のｎに代入する。これを繰り返すと必ず１に至る。」

三角定規さんから、

角谷の予想

「２以上の整数をどのように選んでも
　　　　(1)　偶数ならば２で割る．　(2)　奇数ならば３倍して１加える．
という操作を繰り返し行うと，最後は必ず１になる」

E-mail 戻る top