4

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

243
2
$$$$

はじめに

こんにちは、高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$個となります。

おわりに

先ほどの重複がこの先どれだけ出るのか見当もつかないため、とりあえず共有だけしておきます。
どなたか進展のあった方がいたら、ぜひご報告いただければ幸いです。

更新欄

最終更新
2025.6.10(Tue.) 23:30 投稿

投稿日:610
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

高校3年のぱぺです。 文章を作るのは苦手です。数学は好きで、かつ学年の中では数学が得意なほうです。 ここでは、①作問の投稿 ②高校数学のいろいろの投稿 ③「問題解いてみる」系投稿 を行います。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中