Anonymous user
Talk:Flipping bits game: Difference between revisions
→References?
(→References?: Not seen before that I can remember) |
|||
Line 10:
::: Added! P.S. have you seen the game before? --[[User:Paddy3118|Paddy3118]] ([[User talk:Paddy3118|talk]]) 16:04, 11 July 2013 (UTC)
:::: Don't think so. I feel I've seen something like it (enough to wonder about parity checking as a method of verification) but not the same. –[[User:Dkf|Donal Fellows]] ([[User talk:Dkf|talk]]) 14:17, 16 July 2013 (UTC)
:: You're right -- there are actually more start-end pairs that cannot be completed than start-end pairs that can. I'll give a proof that even-sized grids cannot change parity via the legal moves, and from there, I'll show what else that means.
:: Let's define the parity of a grid to be whether the number of ones in the grid is odd or even. With this definition, I can show that '''for grids of size MxN, where M and N are both even, an ending position cannot be reached if the starting position has a different parity.'''
::* Every row or column either contains an even number of ones, or an odd number of ones. Since the grid is even-sized, if the row or column contains an even number of ones, there must be an even number of zeros as well. Similar can be said if there is an odd number of ones.
::* A move consists of replacing all ones with zeros and all zeros with ones in a single row or column.
::* Make an move on an arbitrary row (or column). If there was an even number of ones in the row, then after the move, there is still an even number of ones in the row, and the board's parity is retained. If there was an odd number of ones in the row, then after the move, there is still an odd number of ones in the row, and the board's parity is retained.
::* Since no move can change the parity of the board, then the ending position cannot be reached if its parity is different than the starting position's.
:: With this argument, you can show that '''from a starting position on an NxN grid (N > 1), you cannot reach all ending positions of like parity''', because for some you would have to change the parity of an even-sized subgrid in order to do it. As an example, try the following transformation on a 4x4 grid:
::<code>1100 => 0000
::1100 => 0110
::0000 => 0110
::0000 => 0000</code>
:: You can't possibly do it with the legal moves set up in the description. This proof highly restricts the start-end pairs that are actually solvable. -- [[User:AnonymousJohn|AnonymousJohn]] ([[User talk:AnonymousJohn|talk]]) 20:04, 28 November 2013 (UTC)
| |||