高校数学議論

【問題提起】加算と2倍のレパートリー

未解決問題,数学,数学A

243

はじめに

こんにちは、高3のぱぺです。
ちょうどさっき気になったことをここで問題提起として提示しておきます。

本題

問題

以下問題です。

整数$1$に対して、以下の$2$つの操作を計$n$回 (操作$A$のみを$n$回、操作$B$のみを$n$回も可)だけ行ったとき、その計算結果としてあり得る整数の個数を$n$で表せ。

【操作】
・操作$A$「$1$を加える」
・操作$B$「$2$倍する」

普通の電卓で「$+ \; 1 \; =$」「$\times \; 2 \; =$」をどんどん打っている感じですね。

実験

・$n=1$ のとき
$\hspace{3em} \begin{aligned} 1+1 &\rightarrow 2 &\quad(A)\\ 1\times2 &\rightarrow 2 &\quad (B)\\ \end{aligned}$
$\quad$ したがって、$1$個$(2)$

このとき、最初の操作は$A$でも$B$でも変わらないため、以降「$2$に操作を計$n-1$回行う」ものとして考える。

・$n=2$ のとき
$\hspace{3em} \begin{aligned} 2+1 &\rightarrow 3 &\quad(A)\\ 2\times2 &\rightarrow 4 &\quad (B)\\ \end{aligned}$
$\quad$ したがって、$2$個$(3,4)$

・$n=3$ のとき
$\hspace{3em} \begin{aligned} 2+1+1 &\rightarrow 4 &\quad(AA)\\ 2\times2+1 &\rightarrow 5 &\quad (BA)\\ 2+1\times2 &\rightarrow 6 &\quad(AB)\\ 2\times2\times2 &\rightarrow 8 &\quad (BB)\\ \end{aligned}$
$\quad$ したがって、$4$個$(4,5,6,8)$

・$n=4$ のとき
$\hspace{3em} \begin{aligned} 2+1+1+1 &\rightarrow 5 &\quad(AAA)\\ 2\times2+1+1 &\rightarrow 6 &\quad (BAA)\\ 2+1\times2+1 &\rightarrow 7 &\quad(ABA)\\ 2\times2\times2+1 &\rightarrow 9 &\quad (BBA)\\ 2+1+1\times2 &\rightarrow 8 &\quad(AAB)\\ 2\times2+1\times2 &\rightarrow 10 &\quad (BAB)\\ 2+1\times2\times2 &\rightarrow 12 &\quad(ABB)\\ 2\times2\times2\times2 &\rightarrow 16 &\quad (BBB)\\ \end{aligned}$
$\quad$ したがって、$8$個$(5,6,7,8,9,10,12,16)$

$n=1,2,3,4$ では$2^{n-1}$個あるようです。

・$n=5$ のとき
$\hspace{2.23em} \begin{aligned} &2+1+1+1+1 &\rightarrow 6 &\quad(AAAA)\\ &2\times2+1+1+1 &\rightarrow 7 &\quad (BAAA)\\ &2+1\times2+1+1 &\rightarrow 8 &\quad(ABAA)\\ * \; &2\times2\times2+1+1 &\rightarrow 10 &\quad (BBAA)\\ &2+1+1\times2+1 &\rightarrow 9 &\quad(AABA)\\ &2\times2+1\times2+1 &\rightarrow 11 &\quad (BABA)\\ &2+1\times2\times2+1 &\rightarrow 13 &\quad(ABBA)\\ &2\times2\times2\times2+1 &\rightarrow 17 &\quad (BBBA)\\ * \;&2+1+1+1\times2 &\rightarrow 10 &\quad(AAAB)\\ &2\times2+1+1\times2 &\rightarrow 12 &\quad (BAAB)\\ &2+1\times2+1\times2 &\rightarrow 14 &\quad(ABAB)\\ &2\times2\times2+1\times2 &\rightarrow 18 &\quad (BBAB)\\ &2+1+1\times2\times2 &\rightarrow 16 &\quad(AABB)\\ &2\times2+1\times2\times2 &\rightarrow 20 &\quad (BABB)\\ &2+1\times2\times2\times2 &\rightarrow 24 &\quad(ABBB)\\ &2\times2\times2\times2\times2 &\rightarrow 32 &\quad (BBBB)\\ \end{aligned}$
$\quad$ したがって、$15$個$(6,7,8,9,*10,11,12,13,14,16,17,18,20,24,32)$

ここで重複が出ました$(*10)$。このため、$n=5$のときは$16$個ではなく$15$個となります。