４×４の反転パズルは常に解けるか？【問題編】

Рет қаралды 2,794

Күн бұрын

=== そのパズルゲー↓ Rokuluro(Lynn)さんが作成 ===
okimath.com/pu...
=== サブch ===
/ @goyahideki
=== Twitter ===
/ g_sen_sei
=== すうがくブログ ===
www.okimath.com
=== 統計ch ===
/ @hsugaku
=== 連絡先([あっと]は@に変える)===
goyaic[あっと]me.com

Пікірлер: 36

@Natsume_jp 2 жыл бұрын

色の違う箇所を記憶してその箇所を押す、これを1回か2回行うと常にクリアできるようです。 3*3だとこのやり方でクリアできることもあればできないこともあります。理屈はわかりません。

@Natsume_jp 2 жыл бұрын

(他の書き込みは見ずに)納得いく答えが出ました。 n*nのマス目でnが偶数の場合、ある特定のマスだけ色を反転させたいなら、そこを中心に十字に全てのマスを押せばよい。反転させたいマスについて: 反転させたいマスは1回押す。それ以外の縦のマスの数は奇数個、横のマスの数は奇数個。反転する回数は、それらを加算するので1+奇数+奇数=奇数で反転する。反転させたいマスの縦及び横方向のマスについて: これらのマスは1直線に偶数個あるので偶数回反転し、元のままとなる。それ以外のマスについて: 縦方向のどこかから1回押されて反転し、横方向からも同様に1回反転するので元のままとなる。上記により、任意の1マスだけを反転させられることが分かったので、すべてのマスは任意に反転させられることになり、必ずすべてのマスを一色にできるとわかる。

@sugakunosu 2 жыл бұрын

4x4マスを 01,02,03,04 05,06,07,08 09,10,11,12 13,14,15,16 と番号付けする。 01のみ色変したいならば、 01と同じ行か同じ列のボタン計7コ(01,02,03,04,05,09,13)を押せばよい。同様に、xのみ色変したいならば、 xと同じ行か同じ列のボタン計7コ(xも含む)を押せばよい。よって任意の模様からスタートしてすべて同色にできる。有限体F_2上の線形代数学として理論的に分析するためには 16次行列A=[a_{ij}]を次で定める。上記のi番(1≦i≦16)を押したとき j番が色変するならばa_{ij}=1, j番が色変しないならばa_{ij}=0. このときA^2はF_2上で16次単位行列であるのでAは正則行列。以下略。

@tokinegi 2 жыл бұрын

考察と呼べるか分からないですが… パズルの配置を点対称または線対称に一度してから、対称性を崩さないよう、対称の中心または軸について対になっている2つのボタンを押していくと解きやすくなりました！

@ikkame 2 жыл бұрын

1つのマスについて考えると偶数回押したときは1回も押さなかったときと変わらず、奇数回押したときは1回押したときと変わらないため、各マス押すか押さないかの2通りの操作を考えればよい。全体としては、nマス×mマスの場合、nmマスあるので2^(nm)通りの操作がある。一方、マスの色も2通りのため、パズル盤面のパターンも同じ2^(nm)通りある。この操作と盤面パターンが1対1に対応していれば、ある操作によって任意のマスを反転できるので常に解くことができる。反対に、異なる操作によって同じ盤面になった場合は解けないパターンが存在することになる。偶数×奇数の反転パズルの場合、「何も押さない」という操作と「すべてのマスを押す」という操作の結果が同じであるため、解けないパターンが存在する。奇数×奇数の反転パズルの場合、あるマスAについて「Aを押す」という操作と「Aと同じ行or同じ列のマスをすべて押す」という操作の結果が同じであるため、解けないパターンが存在する。偶数×偶数の反転パズルの場合、2色を0,1に対応させると、とあるマスAと同じ行or同じ列のマスの和の偶奇について、その偶奇を反転させられるのはＡを押したときだけであるため、Ａを押したときと押さなかったときで同じパターンになることはない。各マスについて同じことが言えるので、各操作と反転パターンは1対1対応している。よって4×4の反転パズルは常に解ける。

@karaagee00 2 жыл бұрын

行列の足し算で状態変化を表すのかな？？初期状態の盤面をxとする。 B_{i, j} = [b_{i, j}] = [行i, 列j は 1 で残りは 0]として、mod 2のもと、xにどんどん足していく。つまり x の状態からボタンi, jを押した状態変化を x + B_{i, j}と表す。このとき 2B_{i,j} = O(ゼロ行列)で、 (x + B_{i,j}) + B_{k, l} = (x + B{k, l}) + B_{i, j} = x + (B_{k, l} + B_{i, j}) のように交換法則と結合法則が使えることに注意する。 (つまり同じボタンを2度以上押す必要がなく、ボタンを押す順番も関係ない) いくつかのボタンを押して、最終的に x + B = y(すべて同じ色) の形になったとすると、解の存在は B = x - y (mod 2) となる Bが B_{i, j} の和で作れるかで決まる。係数 c_{i, j} を 0か1を取る数として、 c_{1, 1} * B_{1, 1} + ... c_{4, 4} * B_{4, 4} = y - x (mod 2) 両辺 4 * 4 の行列で、各要素に対して方程式を作る。これを満たす c_{i, j} が定まれば c_{i, j} = 1 に対応するボタンを任意の順で押せばok。定まらなければ、どのボタンをどんな順序で押しても、盤面を同じ色にできない。

@karaagee00 2 жыл бұрын

なるほど、x, y, B_{i, j} を 4 * 4 でなく 16 * 1 の行列にしておけば、最後の方程式が行列[B_{1, 1} ... B_{4, 4}]] * 縦ベクトル[c_{1, 1} ... c_{4, 4}] = y - x (mod 2) になるから、16 * 16 の行列 [B_{1, 1} ... B_{4, 4}]]が正則か否かを調べればいいのか！ ...それでも計算量が多いな笑何かしらのヒューリスティックで次元削減できるのかな？追記：と思ったけど、この16*16の行列の条件、Bのみで決まっていてxに依存していないので間違ってますね笑頭がパンクしてきた

@karaagee00 2 жыл бұрын

2 * 2 で実験。 B_{1, 1} = [1 1; 1 0] のようにボタン操作に対応する2 * 2 行列を4つ作る。初期配置を x = [0, 0; 1, 1]とする。完成形を y = [1, 1; 1 1] c_{1, 1}B_{1, 1} + ... c_{2, 2}B_{2, 2} = = y - x ⇔ B * c = y - x .... (A) ただし B = [1, 1, 1, 0 1, 1, 0, 1 1, 0, 1, 1 0, 1, 1, 1] (考察: これはB_{i, j}の各行を横につなげたベクトルを縦に並べたものになってる) c = [c_{1, 1} c_{1, 2} c_{2, 1} c_{2, 2}] y - x = [1 1 0 0] det(B) ≠ 0 なので、(A)は解ける。 Bの逆行列を左からかけて(A)を解くと c = [2/3 2/3 -1/3 -1/3 ] 2/3 ≡ 0 (mod 2) -1/3 ≡ (-1 + 4)/3 ≡ 1 (mod2) なので mod2 のもと c ≡ [0 0 1 1] よって {2, 1}と{2, 2}のボタンを押せばxは yになるはず。 {2, 1}->{2, 2}の順で押すと x = [0 0 1 1] -> [1 0 0 0] -> [1 1 1 1] = y 確かにyになった！ ({2, 2}->{2, 1}も同様) 2 * 2 ならできそう。ということは 4 * 4 も結局Bが正則か否かで、xによらず常に解があるかも？？追記: すごい誤解をしていた。 Bc= x - yの形のとき Bが正則 ⇔ 唯一解だった。ということは B が正則でない場合、解なし or 複数解。代わりに、rank(B) = rank([B x-y])が成立すれば解が存在すると言えそう。

@karaagee00 2 жыл бұрын

【合ってるかわからないけど考察まとめ】 n * n の反転ゲームに解があるか調べる。 [各種定義] n * n の初期状態の盤面を表す行列を作る。 (色がついている箇所を1, そうでなければ0に対応させる) 上から順にこの行列の各行を横(右)へ結合し(以降flattenと呼ぶ)、さらにそれを転置させた縦ベクトルをxとする。 i = 1, 2, ... n, j = 1, 2, ..., n について B_{i, j} = [行i, 列jは1, それ以外は0] の n * nの行列を作る。 B_{i, j}をflattenし、B_{1, 1}に対応する横ベクトルから順に縦方向に結合して、(n*n) * (n*n) の行列 B を作る。 y を(n*n) * 1 のすべての要素が1の縦ベクトルとする。 B と y - xを横方向で結合した (n*n) * (n*n + 1) の行列をB'とする。 [解の存在判定 + 解の導出] rank B ≠ rank B' ならば、反転ゲームの解は存在しない。 (どのボタンをどの順序で押してもyにたどり着けない) rank B = rank B' = n*n ならば反転ゲームは唯一解を持つ可能性あり。 (ボタンの押下順、同じボタンの2度以上の押下は考えない) このときB^(-1)が存在するので、B^(-1) * (y - x) を計算する。得た(n*n) * 1の縦ベクトルを上から n個ずつに分割、さらにそれらを転置して縦方向に結合し、n * n の行列をつくる(以降unflattenと呼ぶ)。各成分を mod 2 で 0 または 1に変換させる。仮に 1/2 のように mod 2 が適用できない成分があれば解なし。 (例えばmod 2で 1/2 ≡ x とすると 1 ≡ 2x すなわち 1≡ 0 となってしまうため x が存在しない) そうでなければ、成分が1となっている位置に対応するボタンを任意の順で押下することで反転ゲームが解ける。 rank B = rank B' ≠ n*n の場合、反転ゲームの解が複数ある可能性がある。 c = [c_{1, 1}, c_{1, 2}, ..., c_{2, 1}, ..., c_{n, n}]^T とする(縦ベクトル)。 Bc = y - x について c_{i, j}を未知数とする連立方程式を作り、これを解く。 c_{i, j} = 任意の値となる箇所は任意の数(整数)を代入し、cを一つ得る。 cをunflattenして、各成分をmod2 で0 か 1に変換する。この場合も 1/2 のように mod 2 が適用できない成分があればこのようなcは不適。そうでなければ成分が1となっている位置に対応するボタンを任意の順で押下することで反転ゲームが解ける。

@karaagee00 2 жыл бұрын

上記方法を、Juliaでプログラムを組んで調べたところ興味深い結果に。 3 * 3 は解けないパターンがある。例：初期状態 = [0 1 1 1 0 0 0 1 0] c = [-0.5, 0, 0.5, 1, -0.5, 0, 0 0.5, 0]^T となり、0.5 = 1/2 はmod 2が使えないので不適。 brute-forceで全通り試してもやはり見つからない。なんなら動画で紹介されたcolor-switcherの3*3はもしかして常に解けない問題を出してる？笑 3 * 3 で解けるパターンがあるものは複数解あるっぽい。しかも毎回16通り。 (ここで「rank(B)と rank(B')がn*nより小さければ複数解」という仮定が破綻することに気づく。確かに考えてみればrank(B)は常にn * n だった。今回は合同連立方程式なので、普通の連立方程式の解の個数判定は使えなさそう。さらにBが正則だからといって、そこから得られるcは唯一解とは限らない) 2 * 2 と 4 * 4 は常に正しい解を出力してくれる(しかも唯一解！！)。 5 * 5 の解けるパターンを試すと, 256通り存在した。以上より新たな仮説↓↓ ① 偶数 * 偶数の盤面は必ず唯一解がある ② 奇数 * 奇数(3以上) の盤面は解けないパターンと解けるパターンがある。 ③ 奇数 * 奇数(3以上)の解けるパターンは2^(2*(奇数-1)) 通りの解法がある。解けるパターンの法則と2^(2*(奇数-1)) というマジックナンバーがどこからきているのか気になりますね〜

@YoshioHasegawa421 2 жыл бұрын

与えられた図形をF2上の4次正方行列とみなす。 1マスを選んで押す操作をF(i,j)とおく。全ての行列がクリア可能であること： (i,j)成分のみ1で他が0である行列に対し、i行全て＋j列全ての合計7回操作すればゼロ行列になることから、値が1である成分全てに対してこの操作を施せば良い。クリア可能までのステップ数： ①任意の(i,j)に対して、F(i,j)^2=id ②任意の(i,j),(k,l)に対してF(i,j)とF(k,l)は可換。 ③全ての(i,j)に対して、F(i,j)を1回ずつ行うと元の図形を全て反転させた形になる。（与えられた図形において各成分を反転させるような(i,j)はちょうど7個だから) したがってクリア可能のためのステップを操作F(i,j)の積で表現した場合、 ①②から多くても16個の異なるF(i,j)の積となる。よってクリアまでの最大ステップ数は16。

@YoshioHasegawa421 2 жыл бұрын

なお、③より、与えられた問題のクリアまでのステップ数をnとすると、16-nステップで成分がすべて1の正方行列にすることができるので、単純に全てを同色(要は全て1か全て0)のどちらかにすれば良いのであれば、最大8回でクリア可能。

@YoshioHasegawa421 2 жыл бұрын

パズルを楽しめるように解法を返信に書きますが、初期配置に対して、各(i,j)成分に対して、i行目とj列目の7マスの中で1であるマス目の数を数えて、奇数なら押す、偶数なら押さないとすれば必ず解けます（初期配置をメモしとく必要がありますが）

@KoheiMomose 2 жыл бұрын

@@YoshioHasegawa421 ほんとだ！！

@watabe7969 2 жыл бұрын

不変量の定義考えるの難しすぎる…

@チョッパリパーク 2 жыл бұрын

ゴリラです。初期配置の白マスor青マスを全て叩いた後、その配置の白マスor青マスを叩き続けるとどんな初期配置でも10秒ほどでクリアできました。 2つ目の配置は中心対象or線対象で出てくるので、うまいこと重複を避ければどんな配置でも8手でクリアできそうです。条件は全くわかりません。

@たらこたらこ-w8n 2 жыл бұрын

各成分に2色と対応するように0or1を当て嵌めた4×4行列を初期値として用意してやる。あるマスをタッチし、そのマスと同じ列と行が色が変わる。という操作を、初期値の行列に、色が変わるマス目に対応する成分に1が入った行列を足してやることを対応させる。そして、そのふたつの行列の和の成分を2を法として呼んでやれば、やはり色と0と1が一致して見える。というアイディアで線形代数に落とし込んで、連立方程式でガリガリやってみようとしてますけど、なかなか一般的な話をするのは厳しそう……。というところで手が止まってしまいました。解説楽しみにしてます！

@この顔にピンときたら-g8l 2 жыл бұрын

プログラムで全探索したから分かったけど、どう証明するんだろ

@この顔にピンときたら-g8l 2 жыл бұрын

どんな盤面でも8手以内にいけるそう

@31歳男ニート 2 жыл бұрын

簡単な考察で順番によらないこと同じマスを2回以上操作しても意味ないことがわかるので2^16通り全部試せばいいこのぐらいなら指数時間でも数秒で終わる実装はbit演算とxor使えば楽

@koko-chan8764 2 жыл бұрын

微妙に法則が違うんだけど、昔タカラから発売されていたライツアウトというゲームを思い出しました！

@masa_aa 2 жыл бұрын

真っ白から任意の盤面ができるかどうかという問題を考える真っ白な盤面から真っ白な盤面へいくような操作があるとき単射でなくなるので偽となる(単射でないなら|操作列の集合| = |盤面の集合|より全射でない) 実際に真っ白な盤面から(0, 0), (0, 1), (1, 0), (1, 1)と操作すると真っ白な盤面に戻る同様に任意の盤面でも同じことが言える

@ラルトス-g8h 2 жыл бұрын

はぇ～すっごい

@Hisako8101 2 жыл бұрын

左上、右上、左下、右下で2×2のブロックに分けて考察すると上手くいきました。ネタ潰したくないので次の動画とやり方が違ったらその時また書きます。

@ikarigendou 2 жыл бұрын

DSマリオのミニゲームを思い出しました

@ikarigendou 2 жыл бұрын

逆に「全て同じ色の状態から、2の16乗通りの盤面を作り出せる」ことが証明できれば良いのではないでしょうか。その際に、ルービックキューブやスライドパズルの要領で何か工夫できないかなぁ。と、数学とは全く縁のない社会科教員は考えてみました。

@エンジェル-y6i 2 жыл бұрын

見た感じ難しそう

@tetratan4804 2 жыл бұрын

マスが属する行と列に存在する色のついたマスの個数が奇数の場所のみ反転させれば常に最短手数。色が2色の場合、偶数サイズの正方形で常にこの解法で解ける。色がn色でm×mの正方形なら、nと(m-1)(2m-1)が互いに素のときは1マスを1色だけ進める方法が存在するから、どんな盤面でも解ける。互いに素でないときは解けないパターンが存在するが、1回色を進めたときの各行と列の色の変化に着目して不変量を作る事で、解ける盤面を判別できる。具体的には、色に1,2,…,nと番号を振ったときに、2m個ある行(列)の番号の和が全てgcd(n,m-1)と合同であれば解ける。例えば2色で 101 100 100 ならgcd(n,m-1)=2だが、1行目と2行目の時点で番号の和がmod2で合同でないので解けないというところまで考えました。