ライトを2つ置く


こちら
に精通していただければ幸いです。

基本的に

20本のライトの各ストランドは5×4グリッドのように配線され、各バルブは青、赤、紫、または緑のいずれかになります。しかし、1つの電球の色を変えると、グリッド内の隣接するものも次の色に変わります。

例えば

第1のライトの色を変更し、2番目と6番目のライトも赤に変わります。あなたはもう一度それを変更し、同じ3つは紫色になります。サイクルが再びグリーンになり、最後の1回がブルーに戻ります。ちょうど確かめるために、7番目のライトの色を順番に調べて、2番目、6番目、8番目、12番目のライトがスーツに従っていることに注目してください。

今すぐあなたは本当にクールなランダムパターンを描きました! (例えば、赤青緑赤緑青紫など)

私の質問は:

あなたのパターンに合わせてライトを変更することはいつも可能ですか?不可能ないくつかの設定が存在しますか?

ベストアンサー

Short answer:

はい、いつでも可能です。


スポイラータグなしの多少の短い答え:

あなたのパズルは次のように見えます:

ライトの2つの構成があれば、常に一方から他方に到達することは可能ですか? (シナリオ1)

これは、次の質問に相当します。これは、私が対処するものです。

ライトの設定がある場合、すべてのライトが青色になっている設定にいつでも到達できますか? (シナリオ2)

この同値性の証拠は私の答えの終わりです。

シナリオ2への答えがこちらのアイデアを展開します>はい]をクリックします。私はこの特定のスタックに慣れていないので、ここでは
“典型的な”ユーザーの数学的背景が何であるかわからないので、できるだけ多くの基本的な詳細を説明します。

For any single given light bulb starting on blue, the sequence
of colors is: $$ text{blue $to$ red $to$ purple $to$ green
$to$ blue} $$ I will assign numeric values to the colors as
follows: begin{array}{c|c} text{color} & text{value}\ hline
text{blue} & 0\ text{red} & 1\ text{purple} & 2\ text{green}
& 3 end{array} Note that starting with $text{blue} = 0$ is
completely arbitrary. All that matters for the math that follows is
that one of these colors is assigned $0$, and each of the following
colors gets assigned $1, 2, 3$ in the order in which the colors
appear in the sequence (so, for example, purple = 0, green = 1,
blue = 2, red = 3 is also perfectly acceptable).

Anyway, an example of a 5×4 grid with these values is as
follows. (The mathematician in me is obligated to point out that I
interpret “5×4 grid” as 5 rows and 4 columns, but based on your
further description you clearly meant 5 columns and 4 rows, so I
will proceed like that for consistency.) begin{matrix} 0 & 0 & 0 &
0 & 0\ 1 & 1 & 1 & 1 & 2\ 3 & 1 & 2 & 3 & 2\ 2 & 2 & 3 & 3 & 3
end{matrix} Just for clarity, in this example configuration the
entire first row is blue, the light in the lower-left corner is
purple, the light in the lower-right corner is green, and the light
in the first column of row two is red.

ここで、なぜこの番号付けが有用であるかを見ていきます。言い換えれば、ここで私たちは数学を得る。ライトの1つを変更すると、そのライトとその2つ、3つ、または4つのネイバー(上、下、左、右の隣り合ったものがグリッドに実際に存在するもの)も変更されます。
「変更する」とは、ライトの数値にモジュロ4を1加算することを意味します。「モジュロ4」とは、3 + 1 = 4
$がある場合は4 $を置き換えます(4を法とする4は0であり、すなわち、4を4で割ったときの余りは0であるため)0
$である。ここでは、単一のライトがどのように変化する可能性があるかの完全なリストを示します。

  • 青色のライト(値$ 0 $)が変更されると、赤色(値$ 1 $、$ 0 + 1
    $)になります。
  • 赤いライト(値$ 1 $)が変更された場合、紫色になります(値$ 2 $、$ 1 + 1
    $)。
  • 紫色のライト(値$ 2 $)が変更されると緑色に変わります(値$ 3 $、$ 2 + 1
    $)。
  • 緑色のライト(値$ 3 $)が変更されると青色になります(値$ 0 $、$ 3 + 1 $モジュロ$ 4
    $)。

So, continuing with our example configuration above, if
we were to change the light in row 3, column 4, boxed here for
emphasis: begin{matrix} 0 & 0 & 0 & 0 & 0\ 1 & 1 & 1 & 1 & 2\ 3
& 1 & 2 & boxed 3 & 2\ 2 & 2 & 3 & 3 & 3 end{matrix} Then it
would change (i.e., increase by $1$, modulo $4$) the values of each
of its four neighbors, also boxed below: begin{matrix} 0 & 0 & 0 &
0 & 0\ 1 & 1 & 1 & boxed 1 & 2\ 3 & 1 & boxed 2 & boxed 3 &
boxed 2\ 2 & 2 & 3 & boxed 3 & 3 end{matrix} So our result
would be this configuration: begin{matrix} 0 & 0 & 0 & 0 & 0\ 1 &
1 & 1 & 2 & 2\ 3 & 1 & 3 & 0 & 3\ 2 & 2 & 3 & 0 & 3 end{matrix}
For one more example, if we were to take this new configuration and
then change the light in row 1, column 2, boxed here for emphasis:
begin{matrix} 0 & boxed 0 & 0 & 0 & 0\ 1 & 1 & 1 & 2 & 2\ 3 & 1
& 3 & 0 & 3\ 2 & 2 & 3 & 0 & 3 end{matrix} Then it would change
that light and its three neighbors, boxed here: begin{matrix}
boxed 0 & boxed 0 & boxed 0 & 0 & 0\ 1 & boxed 1 & 1 & 2 & 2\
3 & 1 & 3 & 0 & 3\ 2 & 2 & 3 & 0 & 3 end{matrix} So our
configuration would be: begin{matrix} 1 & 1 & 1 & 0 & 0\ 1 & 2 &
1 & 2 & 2\ 3 & 1 & 3 & 0 & 3\ 2 & 2 & 3 & 0 & 3 end{matrix} So
the question now is, what exactly are we doing? We’re just
doing matrix addition!
If we view our original example
configuration as a $4times5$ matrix (4 rows and 5 columns), then
our first light change was just this matrix addition (don’t
forget the modulo 4
) here: $$ begin{bmatrix} 0 & 0 & 0 &
0 & 0\ 1 & 1 & 1 & 1 & 2\ 3 & 1 & 2 & 3 & 2\ 2 & 2 & 3 & 3 & 3
end{bmatrix} + begin{bmatrix} 0 & 0 & 0 & 0 & 0\ 0 & 0 & 0 & 1 &
0\ 0 & 0 & 1 & 1 & 1\ 0 & 0 & 0 & 1 & 0 end{bmatrix} =
begin{bmatrix} 0 & 0 & 0 & 0 & 0\ 1 & 1 & 1 & 2 & 2\ 3 & 1 & 3 &
0 & 3\ 2 & 2 & 3 & 0 & 3 end{bmatrix} $$ And our second light
change example was just this matrix addition here: $$
begin{bmatrix} 0 & 0 & 0 & 0 & 0\ 1 & 1 & 1 & 2 & 2\ 3 & 1 & 3 &
0 & 3\ 2 & 2 & 3 & 0 & 3 end{bmatrix} + begin{bmatrix} 1 & 1 & 1
& 0 & 0\ 0 & 1 & 0 & 0 & 0\ 0 & 0 & 0 & 0 & 0\ 0 & 0 & 0 & 0 & 0
end{bmatrix} = begin{bmatrix} 1 & 1 & 1 & 0 & 0\ 1 & 2 & 1 & 2 &
2\ 3 & 1 & 3 & 0 & 3\ 2 & 2 & 3 & 0 & 3 end{bmatrix} $$ Now,
every time we change the light in row 3, column 4, we are simply
adding this matrix (modulo 4!!!), which I’ll call $A_{34}$ (because
row 3, column 4), to our existing configuration: $$ A_{34} =
begin{bmatrix} 0 & 0 & 0 & 0 & 0\ 0 & 0 & 0 & 1 & 0\ 0 & 0 & 1 &
1 & 1\ 0 & 0 & 0 & 1 & 0 end{bmatrix} $$ Similarly, every time we
change the light in row 1, column 2, we are simply adding this
matrix (modulo 4!!!), which I’ll call $A_{12}$ (because row 1,
column 2), to our existing configuration: $$ A_{12} =
begin{bmatrix} 1 & 1 & 1 & 0 & 0\ 0 & 1 & 0 & 0 & 0\ 0 & 0 & 0 &
0 & 0\ 0 & 0 & 0 & 0 & 0 end{bmatrix} $$ And here’s a very
important note: Each light in the grid has its own
corresponding matrix!
For example, the light in row 4,
column 5 has this matrix: $$ A_{45} = begin{bmatrix} 0 & 0 & 0 & 0
& 0\ 0 & 0 & 0 & 0 & 0\ 0 & 0 & 0 & 0 & 1\ 0 & 0 & 0 & 1 & 1
end{bmatrix} $$ And so on.

したがって、これまでの主なポイントを要約すると、

  1. 青= 0、赤= 1、紫= 2、緑= 3
  2. ライトを変更するとは、その数値と既存のネイバーの数値に1(モジュロ4)を加算することです。
  3. グリッド内の各ライトには、$ A_ {ij} $という特別な行列があります。$ i $はライトの行、$ j
    $はライトの列です。
  4. 構成の行$ i $と列$ j $のライトを変更することは、構成の数値表現に$ A_ {ij}
    $(モジュロ4)を追加することによって数学的に表されます。

私たちが取り組んでいる質問を思い出してください。

ライトの設定がある場合、すべてのライトが青色になっている設定にいつでも到達できますか? (シナリオ2)

Note that “all lights are blue” corresponds to the following
matrix: $$ B = begin{bmatrix} 0 & 0 & 0 & 0 & 0\ 0 & 0 & 0 & 0 &
0\ 0 & 0 & 0 & 0 & 0\ 0 & 0 & 0 & 0 & 0 end{bmatrix} $$ Based on
the discussion so far, hopefully everyone is convinced that
scenario 2 is equivalent to the following more mathematical
question:

各エントリが$ 0 $、$ 1 $、$ 2 $、または$ 3 $のいずれかである$ 4 $行と$ 5 $列を持つ行列があれば、$
A_ {ij} $ (上で定義した)行列を4にすることで、$ B $(これも上で定義した)の行列になるでしょうか?
(シナリオ3a)

より洗練された数学的記法を使用して、シナリオ3aを次のように言い換えることができます。

Bbb {Z} _4 ^ {4 times 5} $で$ S を修正してください。 $ A_ {ij} $と$ B
$は上で定義した通りですが、次の式を満たす$ B_ {B} {B}   $$   S_ {1}
^ 4 sum_ {j = 1} ^ 5 x_ {ij} A_ {ij} = B $$
  (シナリオ3b)

$ B $にはゼロしか含まれていないので、この方程式は次のようになります。 $$    sum_ {i =
1} ^ 4 sum_ {j = 1} ^ 5 x_ {ij} A_ {ij} = -S $$
(私たちはモジューロ4で作業しているので、実際には$ -S
$を単純化することができますが、これは私たちが表示しようとしているものとは関係ありません)。

まず、大きな$ sum $( “sigma”)は数多くの数の和を書く簡単な方法です。

2番目に、$ S in Bbb {Z} _4 ^ {4 times 5}
$は、シナリオ3aで述べたことを言うための数学的(おそらく非標準的)の方法です:$ S $は4行$ S $の各エントリは、$ 0
$、$ 1 $、$ 2 $、または$ 3 $のいずれかです。

次に、$ x_ {ij} in Bbb {Z} _4 $とは何ですか?表記は、各$ x_ {ij} $は$ 0 $、$
1 $、$ 2 $、または$ 3 $のみであることを意味します。そして、これらの$ x_ {ij} $は実際に何を表していますか? $
x_ {ij} $は、私たちの設定に$ A_ {ij} $を追加した回数を表します。つまり、$ x_ {ij} $は、行$ i
$と列$ j $でライトを変更した回数を表します。これが、$ x_ {ij} $が$ 0 $、$ 1 $、$ 2 $、$ 3
$のいずれかにしかならない理由であることに注意してください。光を4倍に変更すると、
4つの変更の後、元の色に戻ります(数学的には、4の法4が0なので)。
6倍、4倍、4倍に変更するのと同じです。最初の4回は何もしないのと同じですから、実際には2回だけ変更しました。最後の2つの変更(数学的には、6の法4は2なので)です。

So now that we’ve got this down to a linear algebra problem, how
do we actually answer it? Luckily, we actually know what all of the
$A_{ij}$ are. We explicitly wrote down a few of them earlier in
this post. Here is one more, just as another example: $$ A_{24} =
begin{bmatrix} 0 & 0 & 0 & 1 & 0\ 0 & 0 & 1 & 1 & 1\ 0 & 0 & 0 &
1 & 0\ 0 & 0 & 0 & 0 & 0 end{bmatrix} $$ Here’s where I need to
be a little bit hand-wavy, for a few reasons. One, this post is
long enough already. Two, I don’t want to scare off too many more
non-mathy people by giving too many more mathy details. Three, most
of the details I’m not showing next are just routine yet tedious
linear algebra calculations.

Anyway, since we explicitly know all 20 of the $A_{ij}$ for $i =
1,2,3,4$ and $j=1,2,3,4,5$, then we can explicitly write down what
the following sum is: $$ sum_{i=1}^4 sum_{j=1}^5 x_{ij} A_{ij} $$
It’s going to be a very messy matrix with 4 rows and 5 columns and
a bunch of $x_{ij}$ (where $i=1,2,3,4$ and $j=1,2,3,4,5$) all over
the place. And we can rewrite that matrix in a “nicer” form as a
product of a $20 times 20$ matrix with a $20 times 1$ vector,
where the vector consists of the values $x_{ij}$. Note that this
sort of thing is exactly what they did in the link I provided near
the beginning of the post, where they ended up with a $9 times 9$
matrix when considering a $3 times 3$ grid. Anyway, when all is
said and done, we end up with this as our $20 times 20$ matrix: $$
A = begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 &
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\ 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 &
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\ 0 & 1 & 1 & 1 & 0 & 0 &
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\ 0 & 0 & 1 &
1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\
0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
0 & 0 & 0\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 &
0 & 0 & 0 & 0 & 0 & 0\ 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 &
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\ 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 &
1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\ 0 & 0 & 0 & 1 & 0 &
0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\ 0 & 0 &
0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 &
0\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 &
0 & 0 & 0 & 0\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 &
0 & 0 & 0 & 1 & 0 & 0 & 0\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 &
0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0\ 0 & 0 & 0 & 0 & 0 & 0 & 0 &
0 & 1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0\ 0 & 0 & 0 & 0 &
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 0 & 0 & 1\ 0 &
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 &
0 & 0\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 &
1 & 1 & 1 & 0 & 0\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
1 & 0 & 0 & 0 & 1 & 1 & 1 & 0\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 1\ 0 & 0 & 0 & 0 & 0 & 0 &
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 end{bmatrix}
$$ And similar to what’s in the link I provided above, we can
define a vector $x$ to be $$ x = begin{bmatrix} x_{11}\ x_{12}\
x_{13}\ x_{14}\ x_{25}\ x_{21}\ x_{22}\ x_{23}\ x_{24}\
x_{25}\ x_{31}\ x_{32}\ x_{33}\ x_{34}\ x_{35}\ x_{41}\
x_{42}\ x_{43}\ x_{44}\ x_{45} end{bmatrix} $$ Finally, also
similar to what they did in the link, let’s define the matrix $M$
by taking our $-S$ from way up above and rewriting it as a single
column. That is, we’ll take the second column of $-S$ and stick it
under the first. Then we’ll take the third column of $-S$ and stick
it under the second (so now we have the first 3 columns in one
stack). Repeat with the last two columns. If you’re unclear on this
stacking process, don’t worry because it’s actually completely
irrelevant since all that really matters at this point is our
matrix $A$. I’m just continuing in this manner to explain
why our matrix $A$ matters.

したがって、この後、標準線形代数方程式 $$ Ax = M、$$ ここで$ A $は上で書いた$ 20 times 20
$行列です。$ x $は上で書いたベクトルです。$ M $は$ -S $の列からなるベクトルです($ M $は$ x $と同じように$
20 times 1 $ベクトルです)。

私たちの目標は、シナリオ3bの方程式を解く$ x_ {ij}
$の値を常に見つけることができるかどうかを判断することでした。これは、$ Ax = M $を$ x $に代入することと等価です。 $
A $は正方行列なので、$ x = A ^ { – 1} M $、 $ A ^ { – 1}
$が存在する
ということがわかります。 $ A ^ { – 1} $が存在すれば、OPの元の質問に対する答えは
“はい、いつでも可能です”です。 $ A ^ { – 1} $が存在しない場合、OPの最初の質問に対する答えは
“いいえ、いつも可能ではありません”です。では、$ A ^ { – 1} $が存在するかどうかをどのように知ることができますか? $
A $は正方行列なので、その行列式を計算することができます。これは$ 20 times 20
$行列のために陽気ではない(手作業で行う)。救助するコンピュータ! Maple を使用すると、この行列の行列式は$ 55 $であり、 $ 55
$モジュロ$ 4 $は$ 3 $です。これは$ A $が可逆であることを意味します。したがって、$ A ^ { – 1}
$が存在するので、$ x = A ^ { – 1} M $と書くことができます。 (サイドノート:行列式を$ 4
$で扱うときには注意が必要ですが、行列式をゼロ以外にするだけでは不十分です。この議論の範囲を超えた議論はありますが、詳細。)


シナリオ1とシナリオ2の等価性の証明:

それぞれのシナリオが別のシナリオを示していることを示します。最初に、シナリオ1が真であると仮定しましょう。すなわち、2つの与えられたライト構成がある場合、それぞれが別の構成に到達することができます。これは任意のの2つの設定で可能ですので、すべての青いライト(ABL)を持つように設定のうちの1つを修正することができます。他の設定は任意の設定にすることができるので、必要な設定がABLに到達できることがわかります。これは、シナリオ1がシナリオ2を意味することを示している。

シナリオ2が成り立つと仮定します。次に、私たちが持っている2つの光の構成について、それぞれがABLに到達できることがわかります。したがって、ある設定$
C_1 $が他の設定$ C_2 $に到達するためには、ABLに$ C_1 $を取得し、ABLへの$ C_2 $の経路に従うことで
“ABL $ C_2 $になります。したがって、シナリオ2はシナリオ1を意味します。

返信を残す

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