Generating Numbers with Unary Functions
共立出版のbit 1989年1月号のナノピコ教室に「関数電卓のパズル」として出題した問題の再掲です．
はじめに
共立出版のbitがMaruzen eBook Libraryで電子書籍として復刻されました．
私も1989年1月号のナノピコ教室に「関数電卓のパズル」として出題しています (解答は1989年4月号)． その出題内容を少し修正して再掲します．
なお，このパズルは以下のページで試すことができます．
関数電卓のパズル (bit ナノピコ教室, 1989年1月号，共立出版)
関数電卓をいじっていて思いついたパズルです．
次のような11種の単項の実数関数が用意されているとします．
$$ \begin{align*} \mathrm{inv}(x) & = 1/x \qquad (x \ne 0) \\ \mathrm{sqrt}(x) & = \sqrt{x} \qquad (x \ge 0) \\ \mathrm{sq}(x) & = x^2 \\ \mathrm{log}(x) & = \log_{10} x \qquad (x > 0) \\ \mathrm{ex10}(x) & = 10^x \\ \mathrm{sin}(x) & = \sin x \\ \mathrm{asin}(x) & = \arcsin x \qquad (-1\le x\le 1,\ -90\le\mathrm{asin}(x)\le 90) \\ \mathrm{cos}(x) & = \cos x \\ \mathrm{acos}(x) & = \arccos x \qquad (-1\le x\le 1,\ 0\le\mathrm{acos}(x)\le 180) \\ \mathrm{tan}(x) & = \tan x \qquad (x \ne 180n+90,\ n\in\mathbb{Z}) \\ \mathrm{atan}(x) & = \arctan x \qquad (-90<\mathrm{atan}(x)<90) \end{align*} $$
等号の左辺はこの問題で使用する記法，右辺は標準的な記法による定義と，定義域・値域です． また，角度の単位はラジアンではなく度 (degree)です．
さて，0 (ゼロ)に対して上記の関数を複数回適用すると，いろいろな値を得ることができます． たとえば， $$ \mathrm{log}(\mathrm{sq}(\mathrm{ex10}(\mathrm{cos}(0)))) = 2 $$ となります．
一般に， $$ f_m(f_{m-1}(\cdots f_2(f_1(x))\cdots )) = y \qquad (m\ge 0) $$ であるとき，関数名の列 $$ f_1 f_2 \cdots f_{m-1} f_m $$ を「$x$ から $y$ を生成する手順」，特に $x=0$ のとき「$y$ を生成する手順」と呼び， $m$ をその「ステップ数」と呼ぶことにします． これは，関数電卓で $x$ が表示されている状態で， 手順に従って関数キーを押していくと $y$ が得られることを意味しています．
たとえば cos ex10 sq log は2を生成する手順です． つまり，0が表示されている状態で，これらの関数キーを押していくと，結果が2となるわけです．
では，最初の問題です．
- 問題1
- 1から20の整数 $k$ に対して，$k$ を生成する手順のうち，できるだけ少ないステップ数のものを求めてください．
一般に，整数 $k$ を生成する手順は複数通り存在します． たとえば，上記の2を生成する手順で，cosの代わりにex10とできます． そこで解答では，最初に1を生成するためのステップには必ずcosを使うようにしてください． また，sqrt, inv, sq を何回か続けて適用する場合は，この順序に従ってください． たとえば，inv sqrtではなくsqrt invとします．
次の二つは証明問題です．
- 問題2
- 任意の整数 $k$ に対して，$k$ を生成する手順が存在することを証明してください．
- 問題3
- 任意の有理数 $r$ に対して，$r$ を生成する手順が存在することを証明してください．