質問: 古典的なコンビナトリアルパズル Edsger Dijkstra による古典的なパズルです。 元の問題を引用せず、*バッグとボール*に変更すると、パズルは次のようになります。 > バッグには黒と白のボールが入っています。次のプロセスは、可能な限り繰り返されなければなりません(黒と白の球が無限に供給されていると仮定して)。 > > > > * バッグから2つのボールをランダムに選択します。彼らが同じ色なら、それらを投げ捨てるが、余分な黒いボールを入れる。 > * 色が異なる場合は、白いものを袋に戻し、黒いものを捨てます。 > プロセスの各繰り返しがバッグ内のボールの数を1つ減らすことがわかります。また、プロセスの反復は、バッグ内のちょうど1つのボールで終了しなければならない。質問は: **白いボールの数と最初にバッグに入った黒いボールの数に基づいて、最終的なボールの色については何かが言えます。**
回答: 言われることは、 > 白いボールの数のパリティは決して変化しません。したがって、奇数の白いボールが最初にある場合、バッグの最後のボールは白くなければなりません。偶数の場合、最後のボールは黒でなければなりません。 > > パズルが述べられている方法は、私が意図的には不明であると思います。あなたは同等に(そしてもっと透明に)、次のように言うことができます:*各ステップで、黒いボールを1つ取り除くか、2つの白を取り除き、黒を1つ追加する*。これはまた、 > 各ステップで、黒いボールの数のパリティが変更されます。ただし、毎回1つのボールが削除され、白いパリティは不変であるため、変更する必要があります。 > > (元のバージョンでは2つのボールをランダムに削除して2つのもののどちらを行うかを決定するので、2つのステートメントは全く同じではありませんが、パズル自体は興味があります最悪の場合。)