Author |
Topic: locks and switches (Read 2288 times) |
|
Aryabhatta
Guest
|
There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too. Give an algorithm which, given N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles.
Note 1: Can be done in O(N^2) time and O(1) space.
Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence)
|
|
 IP Logged |
|
|
|
John_Gaughan
Uberpuzzler
Behold, the power of cheese!
    
Gender: 
Posts: 767
|
 |
Re: locks and switches
« Reply #1 on: Mar 8th, 2004, 10:04pm » |
 Quote  Modify
|
I believe that most combinations are possible to unlock. This reminds me of a Rubik's cube, in fact, I've seen puzzles similar to this before. I think the solution has to do with if there is an odd or even number of switches turned on and whether n2 is even or odd, or maybe it is 2n-1... I don't remember...
|
|
IP Logged |
x = (0x2B | ~0x2B)
x == the_question
|
|
|
Aryabhatta
Guest
|
John_gaughan wrote:
>I believe that most combinations are possible to unlock. This
>reminds me of a Rubik's cube, in fact, I've seen puzzles
>similar to this before. I think the solution has to do with if
>there is an odd or even number of switches turned on and
>whether n2 is even or odd, or maybe it is 2n-1... I don't
>remember...
For odd N, a lot less than half the combinations are unlockable. This is similar (atleast in problem statement) to the lights out puzzle..
|
|
IP Logged |
|
|
|
kellys
Junior Member
Gender:
Posts: 78
|
|
Re: locks and switches
« Reply #3 on: Mar 9th, 2004, 8:14pm » |
Quote Modify
|
Some observations:
Thinking of the question as adding matrices in the field with two elements:
1) It doesn't matter what order you toggle the switches in. So,
2) You might as well assume that you toggle a switch no more than once, since two toggles gets you right back to where you started.
3) You also should work backwards: start with all of the switches on, and see which configurations you can get to.
|
|
IP Logged |
|
|
|
NotMe
Guest
|
It seems to me that if all switches in one row/column are unlocked, then there are two possibilities:
1. The rest are unlocked as well.
2. The rest is a mix of locked/unlocked.
Proposition 1: it's impossible in the case #2 to unlock the lock.
I think I have a proof of it in my head, but I may be wrong; OTOH, I'm too lazy to write it here.
Now, if you agree with the Proposition1, you have a solution to the problem right there.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: locks and switches
« Reply #5 on: Mar 15th, 2004, 11:41am » |
Quote Modify
|
Hint: For N even we can always unlock the lock
|
|
IP Logged |
|
|
|
NotMe
Guest
|
I'm probably missing something here, but how do you unlock this one:
1 1
1 0
1=ON 0=OFF
?
|
|
IP Logged |
|
|
|
NotMe
Guest
|
Thank you, towr. You know what it means? - It means that my little theory falls apart!
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: locks and switches
« Reply #9 on: Mar 18th, 2004, 10:53am » |
Quote Modify
|
You're welcome 
I'm still not quite sure how to handle this problem..
Obviously if you can (using a certain sequence) switch off/on any square without affecting the rest of the grid, then you can switch off the whole grid (on square at a time if you want to do it the slow way). So based on Aryabhatta's hint this should hold for even N, the question is whether that's any easier to prove..
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
kraj
Guest
|
Code://
// There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too. Give an algorithm which, given N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles.
//
//Note 1: Can be done in O(N^2) time and O(1) space.
//Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence)
using System;
public class ToggleSwitch
{
public static void PrintSwitches( int[][] switches, int x, int y)
{
for(int i=0 ; i <x ; i++ )
{
for(int j=0; j < y; j++ )
{
Console.Write( switches[i][j] + " " );
}
Console.WriteLine();
}
}
public void Toggle(int[][] switches, int x, int y , int size )
{
int state = switches[x][y];
for( int i=0; i< size; i++ )
switches[i][y] = ( switches[i][y] == 1 ? 0 : 1 );
for( int j=0; j< size; j++ )
switches[x][j] = ( switches[x][j] == 1 ? 0 : 1 );
switches[x][y] = ( state == 1 ? 0 : 1 );
}
public static void Main(string[] args)
{
int max = 5;
int[][] switches = new int[max][];
int i,j;
ToggleSwitch ts = new ToggleSwitch();
for(i=0;i<max;i++) switches[i] = new int[max];
for(i=0;i<max;i++)
for (j=0;j<max;j++) switches[i][j] = 0;
PrintSwitches( switches, max, max );
Console.WriteLine();
for ( i=0 ; i <max ; i++ )
for ( j=0; j <max; j++ )
ts.Toggle( switches, i , j, max );
PrintSwitches( switches, max, max );
}
}
|
|
|
|
IP Logged |
|
|
|
kraj
Guest
|
It starts with a N x N array assigned with 0. The algorithm just toggles each cell once. The end result is every cell as 1.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: locks and switches
« Reply #13 on: Mar 19th, 2004, 2:17am » |
Quote Modify
|
ah..
Well, at least that means that it doesn't matter wether we get to all unlocked or all locked state. So if a certain state is solvable, the inverse is as well.
To solve the grid when N is even, you can switch off any single square by toggling every square in the same column and row.
This means the square itself gets flipped 2N-1 times, each other square in the same row or column N times (which is even, so they are in their original state), and every other square twice.
That still leaves the case for odd N
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: locks and switches
« Reply #14 on: Mar 19th, 2004, 4:11pm » |
Quote Modify
|
Right towr. So for even N, we have an O(1) algorithm
Hint for odd n: X = n-1 can be cOnsideRed.
|
|
IP Logged |
|
|
|
kraj
Guest
|
For N being odd, we can just flip any row or column
|
|
IP Logged |
|
|
|
hsp246
Guest
|
Answer:
For n odd, say n=2k+1, first ignore the first row and first column. That leaves us a 2k by 2k square which we know we can always unlock.
Also, note that when we toggle any of the switch in the 2k by 2k square by the aforementioned operation (toggling all the switches in its row and column in the 2k by 2k square), the state of the switch on the first row and column remains unchanged, since they are either toggled 2k times or not toggled at all.
So the question is whether we can turn off all the switches on the frist row and first column. If we can do that, we can take care of the remaining 2k times 2k switches without affecting the state of those in the first row and column.
We can assume the corner element is off, since otherwise we just toggle it.
Now count the number of switches that are "on" at the first row and column. The claim is that if their (odd/even) parity matches,
it can be unlocked, otherwise, it cannot.
Therefore, the algorithm is the check the parity of the "on" switches on the first row and column. Repeat that for all the four corners of the matrix. If the check passes for one of the cases, output "YES". Otherwise, output "NO"
The claim is true because the odd/even parity relationship is preserved no matter which switch you toggle. Since to unlock you need to reach a state where the parity is the same, you have to start with the same relationship.
If their parity is the same, we can always find a sequence. Consider two cases:
i) If the number of "on" swithces is the same on both row and column, we can simultaneously turn a row-switch and column-switch off by toggling their "common affecting" switch.
ii) If the number on the row is greater than column, then we can turn the one light on the row off and turn on one light on the column simultaneously. Since the row-column parity is the same, eventually they will have the same number of "on" switches.
Therefore the algorithm is simply parity checking
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: locks and switches
« Reply #17 on: Apr 2nd, 2004, 11:53am » |
Quote Modify
|
hsp246 wrote:
>For n odd, say n=2k+1, first ignore the first row and first
>column. That leaves us a 2k by 2k square which we know
>we can always unlock.
>
>Also, note that when we toggle any of the switch in the 2k
>by 2k square by the aforementioned operation (toggling all
>the switches in its row and column in the 2k by 2k square),
>the state of the switch on the first row and column remains
>unchanged, since they are either toggled 2k times or not
>toggled at all.
Not true.
For instance, n = 3.
0 0 0
0 0 0
0 0 1
Flipping the middle switch changes it to
0 1 0
1 1 1
0 1 1
Note that the bottom right 2x2 is unlocked now. While the first row and column have changed. (It does not matter how you switch the 2x2 on, you will always end up with the above matrix)
In fact the above cannot be unlocked, while your algorithm returns YES for this.
You are on the right lines though...
|
|
IP Logged |
|
|
|
hsp246
Guest
|
oops you caught me.  Let me give it another try:
For odd case, do the following:
For each entry (i,j), sum up all the entries in row i and column j (not counting the entry (i,j) itself), check its parity.
If the parity is even for all (i,j) return YES, otherwise return NO
It works because such parity is always preserved for each (i,j) no matter which switch you toggle every time.
The naive algorithm will do that in O(n^3) time. To do it in O(n^2), we compute the total sum for each row and each column, which takes O(n^2) time. To compute the parity info for each (i,j), just add up total sum of row i and column j and it will give the parity info, since the entry is added twice and will be toggled to 0
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: locks and switches
« Reply #19 on: May 21st, 2004, 8:14pm » |
Quote Modify
|
If you need to sum rows for every (i,j), the method is O(N3).
In fact, you only need to check that every row and every column has an even number of switches on.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: locks and switches
« Reply #20 on: May 22nd, 2004, 12:53am » |
Quote Modify
|
on Apr 3rd, 2004, 10:24am, hsp246 wrote:oops you caught me. Let me give it another try:
For odd case, do the following:
For each entry (i,j), sum up all the entries in row i and column j (not counting the entry (i,j) itself), check its parity.
If the parity is even for all (i,j) return YES, otherwise return NO
It works because such parity is always preserved for each (i,j) no matter which switch you toggle every time.
The naive algorithm will do that in O(n^3) time. To do it in O(n^2), we compute the total sum for each row and each column, which takes O(n^2) time. To compute the parity info for each (i,j), just add up total sum of row i and column j and it will give the parity info, since the entry is added twice and will be toggled to 0 |
|
Sorry hsp246, I had completely forgotten that I had posted this one. Your solution seems right.
You need to prove the sufficiency of the condition you state. i.e if the value for each (i,j) is even, the lock is unlockable. What you have shown is that if the lock is unlockable then the value for each (i,j) must be even.
Also, the algorithm you gave uses O(N^2) space.
Again, sorry for not responding earlier.
|
| « Last Edit: May 22nd, 2004, 5:17pm by Aryabhatta » |
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: locks and switches
« Reply #21 on: May 22nd, 2004, 12:56am » |
Quote Modify
|
on May 21st, 2004, 8:14pm, grimbal wrote:If you need to sum rows for every (i,j), the method is O(N3).
In fact, you only need to check that every row and every column has an even number of switches on. |
|
For N odd:
Consider the case when all are on. Every row and every column has an odd number of switches on..
And consider the case when all are off. Every row and every column has an even number of switches on..
Either case, the lock is unlockable..
Also, hsp246's solution can be done in O(N^2) time, the way he/she described it.
The space usage is more though.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: locks and switches
« Reply #22 on: May 22nd, 2004, 9:41am » |
Quote Modify
|
Hm... that happens when you post at 5:41. Just a small correction, for N odd:
Either all rows and columns must be even or all rows and columns must be odd. [1]
The condition is necessary because every action will toggle an odd number of switches in each row and each column.
Is the condition sufficient? If the condition [1] is met, we can assume every row and column is odd. If they are all even, just press any switch, and they all become odd.
Then consider what happens when you switch 4 switches at the corners of a rectangle. The result is that only these 4 switches change state. Note also that it does not change the parity of any row or column.
So, from a state where every row is odd (and therefore where the number of OFF switches is always even), you can turn a pair of switches ON if you toggle the same switches in the last row. Working by pairs, you can turn on all switches in the top row. Then, doing the same for all other row, you can turn ON each switch in every row, except the last row. But when you have done all but the last row, the condition of the columns being odd implies that the switch on the last row are all ON.
So, if the condition [1] is met, you can turn all switches ON and unlock the lock.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: locks and switches
« Reply #23 on: May 22nd, 2004, 11:27am » |
Quote Modify
|
on May 22nd, 2004, 9:41am, grimbal wrote:Hm... that happens when you post at 5:41. Just a small correction, for N odd:
Either all rows and columns must be even or all rows and columns must be odd. [1]
The condition is necessary because every action will toggle an odd number of switches in each row and each column.
Is the condition sufficient? If the condition [1] is met, we can assume every row and column is odd. If they are all even, just press any switch, and they all become odd.
Then consider what happens when you switch 4 switches at the corners of a rectangle. The result is that only these 4 switches change state. Note also that it does not change the parity of any row or column.
So, from a state where every row is odd (and therefore where the number of OFF switches is always even), you can turn a pair of switches ON if you toggle the same switches in the last row. Working by pairs, you can turn on all switches in the top row. Then, doing the same for all other row, you can turn ON each switch in every row, except the last row. But when you have done all but the last row, the condition of the columns being odd implies that the switch on the last row are all ON.
So, if the condition [1] is met, you can turn all switches ON and unlock the lock.
|
|
N is odd.
The condition [1] you described is necessary and sufficient.
Let me rephrase the condition:
[1] If R_i is the parity of row i and C_j is the parity of row j, the condition is R_i = C_j for any i,j.
That the condition is necessary, you noted.
It is also sufficient. This can be seen from hsp246's post.
Here is another proof that the condition is sufficient.
Toggling any switch causes all the R_i's and C_j's to flip simultaneously. This means that condition [1] is invariant under switch toggles. (i.e if it was true before a toggle, it remains true after a toggle)
Now consider the (N-1)x(N-1) sub-grid. All the switches in this grid can be turned on since N-1 is even. We are left with the bottom row and the rightmost column. The value of R_i is the state of the ith switch in the last row. The value of C_j is the state of the jth switch in the righmost column (except possibly R_N and C_N). Now if condition [1] was satisfied for the original grid it must be satisfied for this grid too. It implies that either the switches of the last row and column are all on or the switches of the last row and column are all off. In the former case, the lock is unlocked. In the latter case you can unlock the lock by flipping the bottom right switch.
This proves that the condition is sufficient too.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: locks and switches
« Reply #24 on: May 22nd, 2004, 5:11pm » |
Quote Modify
|
on May 22nd, 2004, 11:27am, Aryabhatta wrote:
It is also sufficient. This can be seen from hsp246's post.
|
|
I just reread hsp246's post.. I don't think the sufficiency of the condition is proved.
Sorry for the confusion. It's been a long time since i thought about this problem.
hsp246, you have only proved the necessity of the the condition that you state. Not the sufficiency, which is required. (otherwise you may be saying YES to inputs for which the answer is actually no).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print
Remove