Author |
Topic: binary matrix transformation (Read 3298 times) |
|
ic10503
Junior Member
Gender: 
Posts: 57
|
 |
binary matrix transformation
« on: Sep 22nd, 2009, 10:39am » |
 Quote  Modify
|
How do i convert a binary matrix(containing only 0s and 1s) to a complete zero matrix? Only operations allowed are u can toggle a whole row or a whole column. The conversion has to be done in minimum number of steps(a step is defined as toggling a whole row or whole column).
|
|
 IP Logged |
|
|
|
ic10503
Junior Member
Gender:
Posts: 57
|
|
Re: binary matrix transformation
« Reply #1 on: Sep 23rd, 2009, 1:59am » |
Quote Modify
|
any replies ??/
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: binary matrix transformation
« Reply #2 on: Sep 23rd, 2009, 2:31am » |
Quote Modify
|
If both dimensions of the matrix are even, and the number of 1s is odd, then it's impossible. Because every step conserves parity.
In general, you don't need to toggle the same row or column more than once. So you can pick a column (or row), and split into the cases where you toggle it and one where you don't. And then toggle all the rows (or columns) that have a 1 in that column (row). After that you can only toggle rows (columns), because otherwise you mess up the first row (column). Pick any column (row) to decide which remaining rows (columns) need to be toggled, and you're done.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: binary matrix transformation
« Reply #3 on: Sep 23rd, 2009, 3:51am » |
Quote Modify
|
As towr points out, there are at most 2 solutions for any configuration. But given any solution, toggling every row and every column gives another solution. Therefore any configuration has either no solutions, or exactly two solutions, which are complements of each other. So one can simply assume, WLOG, that the first column is not flipped and then deduce all the moves; if this gives a solution with more than n moves, take the complement. But only 22n-1 out of 2n^2 configuration will have solutions at all.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: binary matrix transformation
« Reply #4 on: Sep 24th, 2009, 7:15am » |
Quote Modify
|
on Sep 23rd, 2009, 2:31am, towr wrote:| ... (working solution) ... |
|
And if that doesn't solve it, nothing does. I.e. if that doesn't work, then there is no solution.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print