Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

Re: Re (tilly) 1: 5x5 Puzzle

by extremely (Priest)
on Jan 29, 2001 at 11:57 UTC ( #54958=note: print w/replies, xml ) Need Help??

in reply to Re (tilly) 1: 5x5 Puzzle
in thread 5x5 Puzzle

Thinking about the nature of the beast, I'd bet on powers of 4 having extra solutions and the squares that that have 4xN+1 sides (5, 9, 13, 17) having extra solutions as well. I think the 16x16 will have at least 2**16 solutions since it is actually a 2x2 of 4x4s and the 4x4 had 2**4 solutions. It also wouldn't suprise me that 13x13 had 8**8 solutions.

$you = new YOU;
honk() if $you->love(perl)

Replies are listed 'Best First'.
Re (tilly) 3 (smarter): 5x5 Puzzle
by tilly (Archbishop) on Jan 29, 2001 at 21:56 UTC
    OK, I figured I would tackle this problem smarter, not harder. With some success.

    First of all note that if you specify the first column, the next column is completely determined by the need to make the entries in the first column come out black. The following column is likewise determined by the need to make the entries in the second column come out black. And so on to the end. So it all comes down to choosing the first column correctly so that the n'th column comes out all black. (Or equivalently so that nothing would go into the n+1'th column.)

    But note, what happens if you compare what happens if you reverse a single choice in the first column. Well you get a pattern of switching what toggles you make through the rest of the puzzle! And the pattern of switches does not depend upon what other parameters you chose. (The final outcome of toggle/not toggle depends on other patterns, but the pattern of toggles you reverse for a single toggle does not.)

    To someone with a math background this looks suspiciously like a linear algebra problem over Z/2. (Z/2 is the set of integers mod 2 - ie 1's and 0's with addition and multiplication mod 2.) In fact it is. For each choice in the first column we have a pattern of switches it would make to toggles in the n+1'st column. If we start with a blank first column we have a pattern of switches we see in the n+1'st column. We want to find a linear combination (that is linear combination in Z/2) of choices in the first column that add up to that base pattern of switches and cancels it out.

    Basic linear algebra tells us that the answer set is either empty or a vector space of some dimension over Z/2. So this doesn't tell us why there are any solutions, but it does tell us that if we have a solution, the number of solutions will be a power of 2. Of course we have seen cases where we have 1 solution, 2**2 solutions, 2**2**2 solutions, 2**2**2**2 solutions, and I suspect that 19 has 2**2**2**2**2 solutions. Why that is seen I don't know. I don't even know why there are any solutions.

    However if I remain interested enough over the next couple of days, I know I can use linear algebra to find how many solutions to the n*n problem exist. That can be O(n**3) rather than the current exponential beast. If I do that I will probably want to do the general n*m problem. And I am not sure how easy my reasoning will be for others to figure out. So I may not do it.

    But if anyone is interested, tell me about it and I will be more likely to take the effort. :-)

Re (tilly) 3: 5x5 Puzzle
by tilly (Archbishop) on Jan 29, 2001 at 13:57 UTC
    Actually there is but one solution of size 13 but 16 again of size 14.

    Note that choosing the values for one side suffice to lay out the rest of the board. I think that has something to do with the pattern.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://54958]
GotToBTru thinks erix & MySql ... talk about a database trigger
[GotToBTru]: wow .. outta votes and it's not even lunchtime yet

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (17)
As of 2017-03-30 15:53 GMT
Find Nodes?
    Voting Booth?
    Should Pluto Get Its Planethood Back?

    Results (360 votes). Check out past polls.