Generating Numbers with Unary Functions

公開日: 2021-05-09
最終更新日: 2021-05-12

共立出版の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$ を生成する手順が存在することを証明してください.