ホーム >> 整数 >> 黒板に書かれた数を増やす遊び
hide or visible

問題の説明

数遊びに関する問題です.たとえば,はじめは,黒板に $1,2$ が書かれているので $2(1\times 2)+1+2=7$ を新たに書き足すことができます.すると,今度は $1,2,7$ のうち (重複を許して) $2$ つの整数を選んで,操作を繰り返すことができます.重複を許して,というのは許された操作は $a=b$ として,適用してもよいということです.したがって,はじめの状態から $2(2\times 2)+2+2=12$ を新たに書き足してもよいのです.さて,どのような数たちを黒板に書くことができるでしょうか.数遊びといえど,難しい問題かもしれません.

ヒント

$2ab+a+b$ という式が何やら怪しそうなので,ここから手をつけてみるとよいでしょう.以下,$2$ 種類の解法を紹介します.

がんばって探す解法

ひたすらがんばって探せば見つけられないこともありません.

たとえば,
$(a,b)=(1,2)$ として $7$ がつくれ,
$(a,b)=(1,7)$ として $22$ がつくれ,
$(a,b)=(22,22)$ として $1012$ がつくれ,
$(a,b)=(7,1012)$ として $15187$ がつくれます.

したがって,黒板に $15187$ を書くことはできます.他にも操作の手順は複数存在します.
しかし,このような操作の手順を自力で見つけるのはかなり面倒なことでしょう.そのうえ,もし,問われている数が黒板に書くことができなかったらどうでしょうか.自力でひたすら探していってもいつまでたっても見つけることはできないので,賢い戦略とは言えません.(もちろん,多少手を動かしてみて無理そうだと感じることは重要ですが)

エレガントな解法

黒板に $a,b$ が書かれているとしましょう. $$k=2ab+a+b$$ とおきます.右辺をとりあえず因数分解してみようという発想から,この式を次のように式変形します. $$(2k+1)=(2a+1)(2b+1)$$ この両辺を見てみると,非常に特徴的な等式であることに気づきます.言うまでもなく,左辺と右辺の項はともに $2x+1$ という形をしています.このあたりに何か仕掛けがありそうだという嗅覚が働くと,つぎの解法を思いつけるかもしれません.

まず,問題文中の黒板 (つまり,はじめに $1,2$ が書かれている黒板)を $X$ と名付けます.つぎに新たに別の黒板 $Y$ と関数 $f(x)=2x+1$ を考え,$f(1)=3,f(2)=5$ を黒板 $Y$ に書きます.つまり,黒板 $X$ に書かれた数字を関数 $f(x)=2x+1$ を用いて黒板 $Y$ に移します.
そして,与えられた操作で黒板 $X$ に $2ab+a+b$ を書いたならば,黒板 $Y$ に $f(2ab+a+b)=2(2ab+a+b)+1=(2a+1)(2b+1) \cdots (*)$ を書きます.
すると,黒板 $X$ における操作は黒板 $Y$ における積に対応している!ということがわかります.
準同型写像
さて,黒板 $Y$ では,はじめ $3,5$ が書かれていました.この二つの数から積をとる操作によって,黒板 $Y$ に書くことのできる数は $3^m5^n$ ($m,n \text{は非負整数}$,ただし $(m,n)=(0,0)$ は除く.) と表すことができます.すなわち,黒板 $X$ に書くことのできる数は, $$\frac{3^m5^n-1}{2} (m,n \text{は非負整数},\text{ただし} (m,n)=(0,0) \text{は除く})$$ と表すことができるのです.
$$15187=\frac{3^55^3-1}{2}$$ なので,$15187$ は黒板に書くことができます.

この解法は,冒頭の『どのような数たちを黒板に書くことができるでしょうか.』という問いに完全な答えを与えています.つまり,黒板に書くことのできる数全体の集合は,次の 集合 $U$ だったわけです.
$$U=\{\frac{3^m5^n-1}{2}\ |\ m,n \text{は非負整数},\text{ただし} (m,n)=(0,0) \text{は除く}\}$$

補足

上の解法のような新しい黒板を用意するという発想は一見,突拍子もない奇抜なアイデアに思われるかもしれません.しかし,このアイデアは同型写像という現代数学の道具を通してみればそれなりに自然であるといえます.

黒板 $X$ における操作は,$2$ つの数から新たな数を作り出すもので,このような操作は特に演算とよばれています.(たとえば,足し算やかけ算は馴染み深い演算の例です).そこで,問題の操作を演算っぽく,$a\star b=2ab+a+b$ と書くことにしましょう.すると,関数 $f(x)=2x+1$ を用いると,式 $(*)$ は $$f(a\star b)=f(a)\times f(b)$$ とかけます.このように,ある演算 $\perp$ が定められた集合 $A$ と,ある演算 $\top$ が定められた集合 $B$ の間の写像 $f$ が $$f(a\perp b)=f(a)\top f(b)$$ という関係を満たす時,$f$ を準同型写像と呼びます.特に,全単射な準同型写像を同型写像と呼びます.

つまり,式 $(2k+1)=(2a+1)(2b+1)$ は,『問題で与えられた操作は,$f(x)=2x+1$ という関数で写した世界で考えると積という非常に単純な操作になっている』と解釈できるのです.したがって,操作が単純になった世界,すなわち黒板 $Y$ で考察していくのはこの意味で自然なことといえるのです.