I hope you are familiar with this.
Basically
Each strand of 20 lights is wired like a 5x4 grid, and each bulb can be either blue, red, purple, or green. However, when you change the color of 1 bulb, the adjacent ones in the grid will cycle to the next color as well.
e.g
You change the color of the 1st light and the 2nd and 6th lights also change to red. You change it again, and the same three become purple. Cycle again makes them green, and one last time brought them back to blue. Just to make sure, you cycle through the colors of the 7th light and notice the 2nd, 6th, 8th, and 12th lights follow suit.
Now you've just drawn out some really cool random patterns! (for example, red blue green red green blue purple etc. etc.)
My question is:
Is it always possible to change the lights to match your pattern or does there exist some configurations for which it is impossible?
Answer
Short answer:
Yes, it's always possible.
Somewhat less short answer with no spoiler tags:
Your puzzle appears to be:
Given any two configurations of lights, is it always possible to reach one from the other? (Scenario 1)
This is equivalent to the following question, which is the one I will address:
Given any configuration of lights, is it always possible to reach the configuration where all lights are blue? (Scenario 2)
A proof of this equivalency is at the end of my answer.
I'll expand on the ideas presented here to show that the answer to scenario 2 is yes. I'm new to this particular stack and as such I don't know what the mathematical background of the "typical" user here is, so I'll explain in as much basic detail as I can.
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 5x4 grid with these values is as follows. (The mathematician in me is obligated to point out that I interpret "5x4 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.
Now, here's where we see why this numbering is useful. In other words, here's where we get mathy. If we change one of the lights, then that light and its two, three, or four neighbors (whichever of the top, bottom, left, and right neighbors actually exist in the grid) also get changed. And here's the important part: "Getting changed" means we add 1 to the light's numeric value, modulo 4. "Modulo 4" means if we have $3+1 = 4$, then we replace $4$ with $0$ (because 4 modulo 4 is 0, i.e., the remainder is 0 when 4 is divided by 4). Here is a complete list of how a single light can change:
- If a blue light (value $0$) gets changed, it becomes red (value $1$, which is $0 + 1$).
- If a red light (value $1$) gets changed, it becomes purple (value $2$, which is $1 + 1$).
- If a purple light (value $2$) gets changed, it becomes green (value $3$, which is $2 + 1$).
- If a green light (value $3$) gets changed, it becomes blue (value $0$, which is $3 + 1$ modulo $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 $4\times5$ 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.
So, to summarize the main points so far:
- Blue = 0, red = 1, purple = 2, green = 3.
- Changing a light means adding 1 (modulo 4) to its numeric value and to the numeric values of its existing neighbors.
- Each light in our grid has its own special matrix $A_{ij}$, where $i$ is the row of the light and $j$ is the column of the light.
- Changing a light in row $i$ and column $j$ in the configuration is represented mathematically by adding $A_{ij}$ (modulo 4) to the numeric representation of the configuration.
Recall the question we're addressing:
Given any configuration of lights, is it always possible to reach the configuration where all lights are blue? (Scenario 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:
Given any matrix with $4$ rows and $5$ columns where each entry is one of the numbers $0$, $1$, $2$, or $3$, is it possible to add some combination of the $A_{ij}$ matrices (as defined above) modulo 4, so that we end up with the matrix $B$ (also defined above)? (Scenario 3a)
Using more sophisticated mathematical notation, we can rephrase Scenario 3a as follows:
Fix $S \in \Bbb{Z}_4^{4 \times 5}$. Can we always find $x_{ij} \in \Bbb{Z}_4$ that satisfy the following equation, where $A_{ij}$ and $B$ are as defined above? $$ S + \sum_{i=1}^4 \sum_{j=1}^5 x_{ij} A_{ij} = B $$ (Scenario 3b)
Note that since $B$ has only zeros in it, then this equation is equivalent to: $$ \sum_{i=1}^4 \sum_{j=1}^5 x_{ij} A_{ij} = -S $$ (Since we're working modulo 4 then the $-S$ can be simplified in practice, but this is irrelevant for what we're trying to show.) Let's break down what all of this means.
First, the big $\sum$ ("sigma") is just a shorthand way of writing a sum of a bunch of numbers.
Second, $S \in \Bbb{Z}_4^{4 \times 5}$ is just a mathy (and perhaps non-standard) way of saying what we said in Scenario 3a: $S$ is a matrix with 4 rows and 5 columns, and each entry of $S$ is one of $0$, $1$, $2$, or $3$.
Next, what are the $x_{ij} \in \Bbb{Z}_4$? The notation just means each $x_{ij}$ can only be $0$, $1$, $2$, or $3$. And what do these $x_{ij}$ actually represent? Well, $x_{ij}$ represents the number of times that we add $A_{ij}$ to our configuration. In other words, $x_{ij}$ represents the number of times we change the light in row $i$ and column $j$. Note that this is why each $x_{ij}$ can only be one of $0$, $1$, $2$, or $3$: Because if we change a light, say, 4 times, that's the same as doing absolutely nothing, because after 4 changes it's back to its original color (mathematically, it's because 4 modulo 4 is 0). And if we change a light, say, 6 times, that's the same as changing it 4 times and then 2 more times, and since those first 4 times are the equivalent of doing nothing, then we really only changed the light twice, with those last two changes (mathematically, it's because 6 modulo 4 is 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.
So, after all this, we end up with the standard linear algebra equation $$ Ax = M,$$ where $A$ is the $20 \times 20$ matrix we just wrote above, $x$ is the vector we also just wrote above, and $M$ is the vector that consists of the columns of $-S$ stacked on top of one another (so $M$ is a $20 \times 1$ vector, just like $x$ is).
Recall that our goal was to determine whether or not we can always find values $x_{ij}$ that solve the equation in Scenario 3b. Well, this is equivalent to solving the equation $Ax = M$ for $x$. And since $A$ is a square matrix, then we know that $x = A^{-1}M$, provided $A^{-1}$ exists. If $A^{-1}$ does exist, then the answer to OP's original question is "Yes, it's always possible." If $A^{-1}$ does not exist, then the answer to OP's original question is "No, it's not always possible." So how do we know whether or not $A^{-1}$ exists? Since $A$ is a square matrix then we can just calculate its determinant. This is hilariously nontrivial (to do by hand) for a $20 \times 20$ matrix. Computers to the rescue! Using Maple, we see that the determinant of this matrix is $55$, and $55$ modulo $4$ is $3$, which means $A$ is invertible. Therefore $A^{-1}$ exists, so we can always write $x = A^{-1}M$. (Side note: Some care needs to be taken when dealing with the determinant modulo $4$. It's not enough to just have the determinant be nonzero. A discussion is beyond the scope of this post, but see the comment thread on this answer for some details.)
Proof of equivalency between scenario 1 and scenario 2:
We'll show that each scenario implies the other. Let's first suppose scenario 1 is true, i.e., if we have any two given configuration of lights, then each can reach the other. Since this is possible for any two configurations, then we can simply fix one of the configurations to have all blue lights (ABL). Since the other configuration can be any configuration we want, then we see that any configuration we want can reach ABL. This shows that scenario 1 implies scenario 2.
Now suppose scenario 2 holds. Then for any two light configurations we have, we know that each can reach ABL. Therefore for one configuration $C_1$ to reach any other configuration $C_2$, all we need to do is get $C_1$ to ABL, and then follow the $C_2$'s path to ABL "backwards" so that we go from ABL to $C_2$. Therefore scenario 2 implies scenario 1.
No comments:
Post a Comment