Talk:Flipping bits game: Difference between revisions

: I'm trying to work out if it is even ''possible'' to finish the game starting from an arbitrary position. I suspect it isn't. Consider a <math>2\times 2</math> grid with an initial position with one cell set, and where the target position is where all cells are unset; all sequences of game operations either keep one cell set (equivalent by rotation) or transition the state to one with three cells set (equivalent to the one-cell-set case by a trivial negation and rotation). Now, it might be that I'm missing something and that larger grids are in fact always soluble, but I suspect not right now. (I can't work it out for the <nowiki>3\times 3</nowiki> case but my investigations do run into the sand in a telling way, and larger grids feel like more of the same.)

: If my intuition is right, surely we should only be posing ''solvable'' games? And if that's true, what is the safety condition? (If it's some sort of parity, I'm not seeing it, but then I'm perhaps just being obtuse.) Or should we just do the creation of the starting position by construction (i.e., by generating a random sequence of moves from the target position — target/start are swappable of course as all moves are self-inverses)? –[[User:Dkf|Donal Fellows]] ([[User talk:Dkf|talk]]) 08:28, 11 July 2013 (UTC)