『これも未解決問題？』

『これも未解決問題？』解答

◆広島県　清川　育男さんからの解答。

【問題１】

　自然数の最初の数１になることが予想されます。

答え　１

【問題２】

１）　６÷３＝２。２＋１＝３。３÷３＝１
２）　８＋１＝９。９÷３＝３。３÷３＝１
３）２７÷３＝９。９÷３＝３。３÷３＝１

答え　６，８，２７

【問題３】

１のとき　０回。

２のとき　２＋１＝３。３÷３＝１。２回

Ｎを３以上の自然数とする。

Ｎ÷３を考える。

割り切れるとき　Ｎ÷３＝Ｎ１。Ｎ＞Ｎ１
余り１のとき　Ｎ＋１＝Ｎ１。Ｎ１＋１＝Ｎ２。Ｎ２÷３＝Ｎ３
Ｎ＞Ｎ３。
余り２のとき　Ｎ＋１＝Ｎ１。Ｎ１÷３＝Ｎ２
Ｎ＞Ｎ２。

　上記のように少なくとも３回の操作で元の数より小さくすることが出来る。
この操作によって最小となる数をＰ（１ではないとする。）とする。
Ｐは少なくとも３回の操作によってＰより小さい数Ｑにすることが出来る。
これは矛盾である。
したがって、最小の数は１となる。

【問題４】

一般式で表わすのは難しいようです。
数列サイトのデータベースにありません。

回数１２３４５・・・Ｎ

数３９２７８１２４３・・・３^N

任意の数を３進法で表わす。

１）２＝２

　　＞＞＞　　２

３＝１×３¹

　　＞＞＞　　１０

３は１回で１にすることが出来る。


　　１０
－）　２
――――――――
　　　１

求める回数　１＋１＝２。

２）１００＝１×３⁴＋２×３²＋１

　　＞＞＞　　１０２０１

２４３＝１×３⁵

　　＞＞＞　１０００００

２４３は５回で１にすることが出来る。　　　　　　　　　


　　１０００００
－）　１０２０１
　　――――――――
　　　１２０２２

各桁の和に５を加えることで求められることが出来る。
５＋１＋２＋２＋２＝１２。

上記のように３進法で表わしそれより大きい３^N（最小のＮ）から引き算をして、その各桁の和にＮを加えることで求めることが出来る。

以上です。

　しかし、これでは実際に操作して求めるのと余り変わりありませんね。
大きな数になると計算間違いの可能性は少なくなると思います。　　　

【コメント】

【問題１，２】はご指摘の通りです。
【問題３】は最小となる数をＰとするところが少し問題かもしれません。
ただ自然数が限りなく小さくなることはないので、明らかですか。

【問題４】は面白いですね。
証明はどうすればよいのでしょう。

◆神奈川県　今村　義彦さんからの解答。

問題[1]から[3]は省略する。

問題[4]の答案：

一般式であらわすことを試みる。

1) N = 1

　0 times

2) N = 2

　(2 + 1)/3 ; 2 times

3) N = 3

　3/3 ; 1 times

4) N = 4

　((4 + 1 + 1)/3 + 1)/3 ; 5 times

5) N = 5

　((5 + 1)/3 + 1)/3 ; 4 times

6) N = 6

　(6/3 + 1)/3 ; 3 times

7) ここで、Nをk桁の３進数の一般式で表現すると、

N = k-1
Σ
j = 0 a(j)×３^j

となる。但し、a(j)は３進数表現における数値表記係数とする。
例えば10進数表現の197は21022と表記するものとする。

(3⁴ * 2 +3³ * 1 + 3¹ * 2 + 2)

この場合、各係数はa(4)=2, a(3)=1, a(2)=0, a(1)=2, a(0)=2ということになる。

３で割り切れるとは、３進数表記でa(0)==0のことを表し、割り切れない場合に１を加えるとは
a(0)==１, あるいは２の場合である。

そして、a(0)が0になるまでa(0)に１を加え続けて、a(1)に桁上げを行なう。
上記の例でいうと、21022から21100に変換する作業である。

さて、一旦a(0)が０であれば、３で割り始める。
３進数表記上で右シフトすることを表す。
例題では、21100から211に変換する作業である。
以上の操作を１になるまで繰り返す。

つまり、211 -> 212 -> 220 -> 22 -> 100 -> 10 -> 1

以上のことから、次のことが言える。
つまり、割算(除算)は３進数表現での桁数分実行し、また、足し算(加算)は、各桁の３の補数の係数の和に１を加えたものとなる。
Nの補数を

k-1
Σ
j = 0 b(j)×３^j..... (1)

とすると、加算の回数は

k-1
Σ
j = 0 b(j)+ 1 ..... (2)

となる。但し、b(j)は３進数表記の２の補数である。

例題では、21022に対して、５桁であるから除算を５回、２の補数は01200であるから加算を(1+2+1)４回実行する。

以下、順次説明する。

まず、加算の回数であるが、自然数Nに対して３進数表記の最高位(msb)のみを１とするような数にすることが第一の目的である。
この操作をわかりやすくするために、次のようにNを表す。

N = １×３^k - k-1
Σ
j = 0 b(j)×３^j －１....(3)

これを例題に当てはめると、

　21022 = 100000 - 1200 - 1

となる。(1)式からほぼ自明であるが、

Nが１×３^{k- 1}と表される以外は(3)式が成立するので、以下の操作で最終的に1に変換することができる。

初回に１を加える。
その後、毎回の操作においてNの最下位lsb(N(0))に１をb(j)回加えることによって０となる。
b(j)が０の場合は加えることなく、３で割る。(右シフトをおこなう。)
最終的に１が導かれる。

答え：

加算を k-1
Σ
j = 0 b(j)+ 1 回

除算を k 回

但し、b(j)はNの３進数表現の３の補数表記の各係数。
kは３進数表現時の桁数。

　『これも未解決問題？』へ

　数学の部屋へもどる

回数	１	２	３	４	５	・・・	Ｎ
数	３	９	２７	８１	２４３	・・・	３^N