アルゴリズムと計算量の問題

難易度 3期末試験の応用レベル証明問題大学数学アルゴリズムと計算量

$n$ を $3$ 以上の整数とする。相異なる $n$ 個の実数からなる列 $X = (x_{1}, x_{2}, \dots, x_{n})$ が与えられたとき、 $X$ が単調であるかどうか、すなわち「 $x_{1} < x_{2} < \dots < x_{n}$ または $x_{1} > x_{2} > \dots > x_{n}$ 」が成り立つかどうかを判定し、「はい」または「いいえ」を出力する問題を考える。

判定を行うアルゴリズムは決定的であり、入力の値には「2 つの添字 $i, j$ $(i \neq = j)$ を指定して $x_{i} < x_{j}$ かどうかを調べる」比較によってのみアクセスできるものとする。どの比較を次に行うか、いつ停止して何を出力するかは、それまでの比較の結果だけから決まる。

この判定を常に正しく行う任意のアルゴリズムに対し、比較を少なくとも $n - 1$ 回行う入力が存在すること、すなわち最悪の場合の比較回数が $n - 1$ 以上であることを証明せよ。

この問題で使うもの

ソート・探索の最悪比較回数（説明と入口の問題）

この問題を解けるようになるまで（17 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

特定の入力を 1 つ選び、その入力に対して「必ず比較しなければならない対」が $n - 1$ 組あることを示す方針（敵対者論法）で考えましょう。

ヒント 2

入力 $x_{i} = i$ を考えます。 $x_{i}$ と $x_{i + 1}$ を直接比較しなかったとすると、この 2 つの値を入れ替えた入力と区別できないことを使います。

ヒント 3

対 ${i, i + 1}$ が比較されなかったと仮定し、値を入れ替えた入力 $X^{'}$ を作ります。 $X^{'}$ が単調でないこと（ $i = 1$ の場合に $n \geq 3$ を使います）と、 ${i, i + 1}$ 以外の比較の結果が変わらないことを確かめましょう。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

単調な入力 $x_{i} = i$ を選び、隣り合う添字の対 ${i, i + 1}$ が相異なる $n - 1$ 組あることを述べている（1 点）
ある対 ${i, i + 1}$ が比較されないと仮定し、その 2 つの値を入れ替えた入力 $X^{'}$ を作り、 $X^{'}$ が増加列でも減少列でもないことを $i = 1$ と $i \geq 2$ に分けて（ $n \geq 3$ を使って）示している（3 点）
入れ替えた対以外のすべての比較の結果が $X$ と $X^{'}$ で変わらないことを、他の値が $i$ と $i + 1$ の間にないことから示している（2 点）
決定性から $X$ と $X^{'}$ で比較の列と出力が一致することを帰納的に示し、正しい答えが異なることと矛盾させている（3 点）
1 回の比較で 1 組しか調べられないことから、比較回数が $n - 1$ 以上であると結論している（1 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

判定を常に正しく行うアルゴリズムを 1 つ固定する。特定の入力を 1 つ選び、その入力に対してアルゴリズムが相異なる $n - 1$ 組の添字の対をすべて比較しなければならないことを示す。

入力の選び方. 入力 $X$ を $x_{i} = i$ $(i = 1, \dots, n)$ とする。値は相異なり、 $x_{1} < x_{2} < \dots < x_{n}$ なので $X$ は単調であり、正しい出力は「はい」である。添字の対 ${i, i + 1}$ $(1 \leq i \leq n - 1)$ は相異なる $n - 1$ 組である。

主張. アルゴリズムは入力 $X$ に対して、各 $i$ $(1 \leq i \leq n - 1)$ について $x_{i}$ と $x_{i + 1}$ の比較を少なくとも 1 回行う。

背理法で示す。ある $i$ $(1 \leq i \leq n - 1)$ について、入力 $X$ での実行中に $x_{i}$ と $x_{i + 1}$ の比較が一度も行われなかったと仮定する。入力 $X^{'} = (x_{1}^{'}, \dots, x_{n}^{'})$ を、 $X$ の $i$ 番目と $i + 1$ 番目の値だけを入れ替えたもの、すなわち $x_{i}^{'} = i + 1$ , $x_{i + 1}^{'} = i$ , $k \neq = i, i + 1$ では $x_{k}^{'} = k$ とする。 $X^{'}$ の値は $X$ と同じ集合なので相異なり、 $X^{'}$ は正当な入力である。

(i) $X^{'}$ は単調でないこと： $x_{i}^{'} = i + 1 > i = x_{i + 1}^{'}$ なので $X^{'}$ は増加列ではない。また減少列でないことを示すため、 $x_{k}^{'} < x_{k + 1}^{'}$ となる $k$ を見つける。 $i \geq 2$ のときは $x_{i - 1}^{'} = i - 1 < i + 1 = x_{i}^{'}$ である。 $i = 1$ のときは $n \geq 3$ より $x_{3}^{'} = 3$ が存在し、 $x_{2}^{'} = 1 < 3 = x_{3}^{'}$ である。いずれの場合も $X^{'}$ は減少列ではない。よって $X^{'}$ は単調でなく、正しい出力は「いいえ」である。

(ii) 対 ${i, i + 1}$ 以外の比較の結果は $X$ と $X^{'}$ で同じであること： $k, l$ がどちらも $i, i + 1$ と異なるときは $x_{k} = x_{k}^{'}$ , $x_{l} = x_{l}^{'}$ なので結果は同じである。一方だけが $i$ または $i + 1$ のとき、もう一方の添字 $k$ $(k \neq = i, i + 1)$ の値 $k$ は $i, i + 1$ のどちらとも異なる整数なので、 $k \leq i - 1$ または $k \geq i + 2$ である。 $k \leq i - 1$ なら $X, X^{'}$ のどちらでも $x_{k}$ は $i$ 番目・ $i + 1$ 番目の値（ $i$ と $i + 1$ ）より小さく、 $k \geq i + 2$ ならどちらでも大きい。よって比較結果は変わらない。

(iii) 実行が同じになること：比較の回数についての帰納法で、 $X$ と $X^{'}$ での実行が一致することを示す。 $X$ と $X^{'}$ で最初の $m$ 回の比較が同じ対で同じ結果であるとする（ $m = 0$ のときは何も比較していないので成り立つ）。アルゴリズムは決定的で、次の動作はそれまでの比較結果だけで決まるので、 $m + 1$ 回目の動作（次に比較する対、または停止して出力する内容）は $X$ と $X^{'}$ で同じである。それが比較であれば、 $X$ での実行では対 ${i, i + 1}$ は比較されないのでこの対は ${i, i + 1}$ ではなく、(ii) より結果も同じである。よって $X$ と $X^{'}$ での実行は、比較の列とその結果、および最後の出力まで完全に一致する。

したがってアルゴリズムは $X$ と $X^{'}$ に同じ答えを出力する。ところが正しい出力は $X$ では「はい」、 $X^{'}$ では「いいえ」であるから、どちらか一方で誤った答えを出力する。これはアルゴリズムが常に正しく判定することに反する。よって主張が示された。

結論. 1 回の比較で調べられる添字の対は 1 組だけなので、入力 $X$ に対して相異なる $n - 1$ 組の対 ${1, 2}, {2, 3}, \dots, {n - 1, n}$ をすべて比較するには、少なくとも $n - 1$ 回の比較が必要である。アルゴリズムは任意だったので、比較だけで単調性を正しく判定する任意のアルゴリズムは、最悪の場合 $n - 1$ 回以上の比較を行う。 $■$

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる