ぺるせんたげの学習帳

手作り数学のブログです

トップ > 手作り数学 > 抽象化〇×クイズの最小手数

抽象化〇×クイズの最小手数

手作り数学
全n問の○×クイズを、満点がとれるまでやり直す。ただし、各問題の正誤は不明だが、過去に行った各回の点数は分かるとする。
このとき、どんな場合にも満点をとるには何回繰り返せば良いか？

問題の作成者：SOx @SOx_S_R_M



今回は論理パズルのお話です。


※上の目次のうち、重要な(そして面白い)のは 4. 論理的に考えてみる 以降です。数学的な話以外に興味がなければそこから読んでください。



1. 抽象化○×クイズ

問題の意味を確認します。

○×クイズとは、正解が○か×である問題に対し、○か×かで回答する二択形式のクイズのことです。

例：
　Q . 太陽は地球の周りを回っている。○か×か？
　A . ×

このように、正解が×であるときは、×と答えると正しい回答になります。正しい回答をしたら○とか、間違った回答をしたら×、とかいうことではないので注意しましょう。

さて、今回はn問の○×クイズがあり、何度か挑戦してそれら全てに正解することを目指し、最悪の場合での最小手数を考えます。ただし正解/不正解のフィードバックは、個々の問題についてはされず、総合得点のみ分かるという状況です。例えば正解が"○×○"である場合に"×××"と回答すれば1問正解となります。
また、満点と書かれていましたが、1問正解すると何点得られるのかは不明です。とりあえず1点として一般性は失われませんが、この点については後で議論します。

それでは早速やっていきましょう。

2. 愚直な方法

当たり前ですが、個々の問題の正解を知ることができれば全問正解です。なので個々の問題について一つ一つ正解を確認していけば良いです。

前述のとおり、○×クイズは二択です。よって特定の1問以外の回答を統一して、その1問について○と×の場合の得点を比較することで正解がわかるはずです。
1問目について○と×の場合を比較し、1問目の回答を判明した正解に固定して2問目について○と×の場合を比較し、2問目の回答を判明した正解に固定して3問目について○と×の場合を比較し……というのをn問目まで繰り返せばすべての正解がわかり、満点が得られます。
この方法では2n回の試行が必要……そうですが、実は正解を知るだけなら2n-1回でも十分です。n問目の正解については一度確認すればn-1点かn点かがわかるので、2回確認する必要がないのです。2n-1回目の試行で全ての正解がわかり、その時点で全問正解を達成するか、2n回目の試行で全問正解するかのどちらかです。

ということで、この方法での最小手数は最悪の場合で2n です。

3. もう少し賢い方法

得点しか情報がないので、基本的には各試行の得点の差を使って考えていくしかありません。上の方法も得点差を利用したものですが、もっと効率的な方法があります。一つの共通の基準と個々の問題を比較するのです。

1回目は(キャリブレーションとして)全て○で回答を出し、その得点を確認します。2回目は1問目だけを×にして回答し、その得点を確認します。1問だけ回答を変えているので得点は1増えるか1減るかのどちらかです。増えれば×が正解だったことになり、減れば○が正解だったということです。どちらであれ1問目の正解がわかります。
以降も同様に得点の増減を確認することで、各問題の正解を決定できます。

この方法は最初のキャリブレーションの1回と後の正解決定のn回の合計n+1回が必要……そうですが、全ての正解を決定するだけであれば、やはりn回で十分です。
n回目の試行が終わった時点での状況をよく見てみると、1問目~n-1問目までの正解が判明していて、n回目の試行は1問目~n-2問目までが正しい解答を選んでいて、n-1問目が正解か不正解のどちらか(どちらかは判明している)で、n問目はどちらかわからない状態です。このとき、n回目の試行の得点によって場合分けすることができます。
1. n点の場合：運良く全問正解だった場合です。この時点で全問正解が達成されました。
2. n-1点の場合：更に場合分けします。
　2-1. n-1問目が正解の場合：n問目が不正解であるとわかるので、n+1回目の試行で全問正解が可能です。
　2-2. n-1問目が不正解の場合：n問目が正解であるとわかるので、n+1回目の試行で全問正解が可能です。
3. n-2点の場合：n-2問目までは全て正しい解答を選んでいるので、残り2問はどちらも不正解であったということです。それらの回答を変えることで、n+1回目の試行で全問正解が可能です。

以上から、どの場合でもn+1回目の試行までには全問正解できることがわかります。

※一応書いておくと、○と×は入れ替えても問題ありません。シンボル自体に意味はないからです。

4. 論理的に考えてみる

上2つの方法はどちらも直観によって得られたものです。特に2つ目の方法は非常に効率が良さそうですが、今回知りたいのは"最小"手数です。直感的な方法ではなかなか最小性を保証できません。
そこでほしくなるのが数学による保証です。公理に従っていれば数学は公理の範囲で常に正しさを保証してくれるいいヤツなので、どうにか今回の問題を数学の言葉で表現したいところです。
そこで、2つ目の方法を数学の言葉に置き換えてみましょう。

i回目の試行での回答セットを行ベクトルA_i、n個の正解を順番に並べた列ベクトルをc、各試行での得点をp_iとします。
ところで、回答セットと正解はすべて○か×ですが、普通これらは計算できないので、このままでは扱いにくいです。そこで、○と×を対応する計算可能なものと置き換えます。具体的には○を1に、×を-1に対応付けます。
こうすると、○×クイズの挙動と計算が以下のようにXOR(排他的論理和)っぽく上手く対応します。

回答が○、正解が○の場合：1×1=1 (正解)
回答が○、正解が×の場合：1×(-1)=-1 (不正解)
回答が×、正解が○の場合：-1×1=-1 (不正解)
回答が×、正解が×の場合：-1×(-1)=1 (正解)

つまり、○と×に1と-1を、正解/不正解と積を対応付けることができるのです。
具体的に見てみましょう。

正解が"○×○"である場合にi回目の試行として"×××"と回答する状況では、c=(1,-1,1){}^T、A_i=(-1,-1,-1)なので、A_i\cdot c=p_i=(-1×1)+(-1×(-1))+(-1×1)=-1となります(右上のTは転置記号です)。
上で見たようにこの場合の得点は1点ですが、p_i=-1です。このズレは不正解のときの点数の違いが原因で、内積を利用した対応付けにより最小値は-nとなります。

これをn回の試行に関して考えると、A_iを積み重ねた回答行列Aと得点ベクトルpにより、Ac=pと表せます。
知りたいのは正解、つまりcです。Aが正則であればc=A^{-1}pとしてn回の試行と得点から計算できるので、n回の試行を一次独立になるように気をつけて行えば良いです。
ここで本題である最小性について考えます。Aとcの内積を計算するためにはAはn行である必要があり、正解の完全な情報を含むcを得るには正則な回答行列Aを得る必要があります。よってcを得るにはn次正則行列Aが必要になるのです。これは最低でもn回は試行が必要であることと同値なので、n回の試行の最小性が保証されます。

これで正解がわかることを2つ目の方法で確認してみましょう。
n=3、1回目の回答を"○○○"、2回目の回答を"×○○"、3回目の回答を"○×○"とすると、

 \begin{pmatrix}
1&1&1\\
-1&1&1\\
1&-1&1
\end{pmatrix}
c=
\begin{pmatrix}
1\\
-1\\
3
\end{pmatrix}

となり、Aは正則になっています。よってこの3回の試行でcが計算でき、

c=\frac{1}{2}
\begin{pmatrix}
1&-1&0\\
1&0&-1\\
0&1&1
\end{pmatrix}
\begin{pmatrix}
1\\
-1\\
3
\end{pmatrix}
=
\begin{pmatrix}
1\\
-1\\
1
\end{pmatrix}

全ての正解が"○×○"であることがわかります(今回は更に運良く3回目で全問正解もできていますが、常にこうなる訳ではありません)。

以上のことから、n問の○×クイズで全問正解するために必要な最小回数は最悪でn+1です。

5. 得点の変換

ここまで○×クイズの得点を1点と0点、○と×を1点と-1点に対応させてきました。この変換の正当性を確認しておきます。

変換前の得点の組を(T, F)、m問正解したときの変換前の合計得点をS(m)、変換後の得点の組を(T', F')、m問正解したときの変換後の合計得点をS'(m)とする。このとき
S(m)=mT+(n-m)F, S'(m)=mT'+(n-m)F'となる。
S(m)からS'(m)への変換は変換関数\phi: S'(m)=\phi(S(m))=\frac{T'-F'}{T-F}S(m)+\frac{TF'-T'F}{T-F}nを定義することで可能になる。
T, F, T', F'は任意なので、T=1, F=0, T'=1, F'=-1とすることで、上の議論で行った変換が可能であることが保証される。

6. 感想

自然言語で書かれた論理パズルを数学の言葉で書き直すことで厳密で見通しの良い議論ができました。
数学の効力は数学の提供する公理系が実際の問題と同一視できる場合に発揮されますが、その場合には非自明な結論を行うのに非常に強力です。このことを簡潔に評した言葉を引用して今回は終わりにしたいと思います。


"数学は着想や概念をフォーマリズム（形式化された理論的手続き）に翻訳し, そのフォーマリズムを適用して, あまり形式的でない分析が通常なら施せないような洞察を導き出す."

―― J. ヨスト, 現代数学の基本概念 上, 丸善出版, 2019