1

与えられたのは、黒または白の最大 30 個の石の列です。ゲームの開始時に隙間は許されませんが、30 個未満の石が存在する可能性があります。目標は、すべての石を取り除くことです。黒い石のみを取り除くことができます。石を取り除くと、その隣の石の色が変わります。取り除かれた石が真ん中にあった場合、これ以上埋めることができないギャップが生じます。その石の隣人は、石が取り除かれた後、隣人とは見なされません。

今、このゲームを力ずくで解くプログラムを作成しました。私は、ゲームが解けるのは、(明らかに) 黒い石がまったくなく、黒い石の数が奇数である場合のみであると結論付けました。また、黒石の数が奇数の場合は、列の最初の黒石を再帰的に取り除くことでゲームを解決できます。

私の問題は、黒い石の数が奇数でなければならず、最初の石を取り除くとゲームが解決するというこの条件を証明できないことです。このアルゴリズムを正しく証明するにはどうすればよいですか?

私はすでに誘導を使用しようとしましたが、私は立ち往生しています:

行 (a,b) = a*黒 + b*白

RemoveFirstBlack(Row(1, b)) = RemoveFirstBlack(black + b*white) = 0 (a=1 または n = 0 の場合、a=2n+1 および n は整数)

RemoveFirstBlack(Row(k*a, b)) = RemoveFirstBlack(k*a*black + b*white) = 0、k = 2p + 1、p を整数と仮定します。

RemoveFirstBlack(Row((k+1)*a, b)) = RemoveFirstBlack((k+1)*a*black + b*white) = RemoveFirstBlack((2(p+1)(2n+1))*black + b*白) = RemoveFirstBlack(2(p+1)*a*黒 + b*白) = 0?

あらゆる指針を前もって感謝します！

4

2 に答える 2

2

グループを分割せずに解ける石のグループがあると仮定します（グループを分割する必要がある場合は、実際には分割する必要のない2つのグループがあります）。グループから削除する最後の石は、単一の黒である必要があります[B]。[B]に到達する唯一の方法は[WB]を経由することであり、他の方法はありません。[WB]にアクセスするには、[BBB]または[WWB]のいずれかが必要です。ここからパターンが現れます。[xxW]に到達する唯一の方法は[xxBB]を経由することであり、[xxB]に到達する方法は[xxWB]を経由することです。これらすべての遷移で、パリティは変更されず、黒い石の最終的な数は奇数（1）であるため、単一の分割不可能なグループのパリティは奇数である必要があります。

ソリューションでは、グループを2つの分割できないサブグループに分割する必要があるとします。これらの2つのサブグループは奇数パリティを持っている必要があるとすでに結論付けています。新しい状態に移行する黒石を除外すると、これら2つのグループには実際には偶数の黒があります。それらを追加し、遷移を行う黒い石を追加すると、分割できない2つのグループに分割して解決されるグループにも、奇数個の黒い石が必要であると結論付けることができます。

単一分割グループでの誘導を使用すると、どのグループにも奇数の黒が必要であると結論付けることができます。

元の問題の解決には、ブルートフォースは必要ありません。あなたが一緒に来る最初の黒い石を選ぶだけです。

于 2012-03-14T14:36:38.043 に答える
2

2 つの動きを 1 つとして扱うことをお勧めします。(つまり、30 個の石が 15 回の移動で取り除かれます。)

これにより、奇数または偶数の黒い石を持つ特性がゲーム全体で不変であることを示すことができます。証明スケッチは次のとおりです。

ベースケース: 石が 2 つ残っています。黒の数が奇数。両方の石を 1 回のダブル ムーブで取り除くことができます。

b w       -> _ b        ->  _ _
w b       -> b _        ->  _ _

4 つ以上の石の場合、さまざまな可能な接頭辞をリストします。ここでO、 とは、それぞれ奇数と偶数の黒Eを持つ石の接尾辞シーケンスを表します。

開始するための 2 つのケースを次に示します。

b b w b E  -> _ w b b E  ->  _ w _ w E
b b w w O  -> _ w b w O  ->  _ b _ b O
....

いずれの場合も、結果のシーケンス (_ w _ w Oたとえば) に奇数の黒が含まれていることに注意してください。

シーケンスが 1 つの石で構成され、石の数が奇数である場合、その 1 つの石は必然的に黒でなければならないため、最後の石も削除できることを意味します。

黒い石の数が偶数の場合は不可能であることも示したいことに気付きました。これは簡単です。基本ケース (b bおよびw w) を解決することは不可能であり、各ダブル ムーブは偶数のブラック ストーンを削除するため、偶数から開始すると運が悪くなります :-)

于 2012-03-14T13:07:08.967 に答える