クリスマスライトホラーストーリー!

パズルリングの不思議な挙動をしたクリスマスライトのストーリーに触発されて、私は今自分自身のクリスマスライトホラーストーリーを共有するのが快適だと感じています。

それはすべて、私がeBayでスターライトのグリッドを注文したときに始まりました。 「inifinitely
bright!」と宣伝されて、私はそれらを箱から外したときに何を期待するか分からなかった。驚いたことに、星の格子は無限に大きかった!驚いたことに、星の数は限られていました。

明らかに、私はそのような厄介な細部に対処できませんでした。私はそれらをすべてオンにしようとしましたが、それらの一部だけがオンになりました。混乱して、私は指示を読んだ:

‘点灯しているライトの数(ゼロを含む)に隣接している場合にのみ、ライトのオン/オフを切り替えることができます。

なんて騒がしい!私はついに、すべてのライトをオンにすることができました。しかし、私は、無限大のライトの壁にフィットする場所がないことを知ったので、ボックスに戻して、eBayの売り手から払い戻しを求めました。これに代わって、フェズはクールです。

これに銀色の裏地があるなら、それは私が奇妙なパズルを考え始めることです。

無限のグリッドがあり、有限数がオフであり、残りがオンであると仮定し、偶数の直交するONライトがある場合にのみ、ライトを切り替えることができます。
あなたは完全に点灯することができるすべての光のパターンを特徴付けることができますか?

(例:次のパターンで、4つのライトだけが消灯しているとします。

  1  
 2  
34  

ライト2または3を切り替えることはできませんが、1と4をオンにして2と3をオンにすることができます。
これは簡単な例ですが、いくつかのパターンのライトでは、他のライトをオフにする必要があります。

編集:これは、オリンピックのマタマティクスで
‘コンビナトリアル’の問題として知られています。コミネーターの問題は、多くの「偽の解決策」、あるいは固体のように見えるが、問題の重要な部分について実際にスケートする解決策を持つことで有名です。これまでの両方の答えは間違いなく正しい道ですが、残念ながら完全な解決策ではありません。それは、常に保持していない仮定やステートメントを作るのは超簡単です…注意してください!

ベストアンサー

オフ/オンの代わりに間違った/正しいを使用します。なぜなら、そうでなければ間違っていることを知っているからです。したがって、無限に多くの間違ったライトを持つ無限のグリッドがあり、4つの隣接する偶数のライトを切り替えることしかできません。

まず、間違ったライトのどれかを切り替えることができる場合は、そうしてください。これは、残りのすべての間違ったライトが奇数であることを意味します(奇数の間違ったネイバーを持ちます)。

今グリッドの左上に最も遠い間違った光を見てください。したがって状況は次のようになります。

.....?
....??
...x??
..????
.?????

ここで、xは間違った光であり、ドットは正しいライトであり、そして?不明なステータスのライトをマークします。
xの右上のライトが正しいと仮定することができます(そうでない場合は、最後の間違ったライトの対角線に沿って移動します)。

.....?
.....?
...x??
..????
.?????

私たちは間違った光が奇数の間違った隣人を持たなければならないことを知っています。したがって、次のいずれかがあります。

.....?    .....?
.....?    .....?
...xy?    ...x.?
..?.??    ..?y??
.?????    .?????

yは間違った隣人です。

1から4までの移動がここに表示されます:

.....?    .....?
..12.?    ..12.?
...34?    ...3.?
..?.??    ..?4??
.?????    .?????

これは、2つの間違ったライトをxとyからシフトして、位置1と2にドミノを形成します。

このようにして、ドミノを分離することができます。同様の動きで、そのドミノを左上にさらに遠ざけることができます。このプロセスを繰り返すことで、大規模なクラスタをドミノに分割することができます。間違ったライトがいくつか残っているシェイプを残していることがあります。このライトは、次のドミノを分割する前に切り替えることができます。

したがって、間違ったライトの開始位置は、広く離れたドミノだけからなる位置に変換することができます。これらのドミノを簡単に動かすことができます。そして、2つのドミノを互いに近づけてペアにして、それらを全滅させることができます:

.......
.xx.xx.
.......

.......
.xxxxx.
.......

.......
.x.x.x.
.......

.......
.......
.......

彼らはそんなに並んでいる必要はありません –
彼らはそれらの間に1つのスペースでお互いの隣にいる限り、任意の方向にすることができます。

私が説明した手順は、あなたが偶数のドミノを生産する限り、すべてのライトをオンにすることができます。 Gareth
McCaughanが与えたパリティの議論は、どの出発ポジションが奇数のドミノを生産するかを予測することができます。誤ったライトの隣接するペアの数を数えます。すべての移動でこれが均等に変更されるため、この数は全体にわたって均等または奇数のままです。それが奇数の場合、完全に解決されたグリッドは均一であるため、位置は解決できません。解決手順を使用する場合は、奇数のドミノを生成しなければなりません。その場合、残りのドミノは1つだけ減らすことができますが、これ以上はドミノを減らすことはできません。隣り合った数の間違ったライトのペアが偶数の場合、偶数のドミノを取得しなければならないので、それを解決することができます。

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です