• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Chessboard

 
Ranch Hand
Posts: 1907
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I tried this on Saturday evening!Almost got it but finally gave up to see the solution.
On every square of 8x8 chessboard there is an integer.You may choose any 4x4 square and increase the value of integer in every square by 1.In which situation you won't get every integer on board be divisible by 2 by repeating this process?
 
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
OK, to simplify, make the grid contain only '0's and '1's, and rather than incrementing each, just flip it. So 0 is analogous to even etc.
Now, if there are an odd number of 1s (and hence odd number of 0s), then you can never resolve the problem.
Reason: each flip flips 16 bits, thus a series of flips always flips an even number of bits. However, if there are an odd number of 1s, then in order to make all 0s, the "net" number of flips must be odd. I know that's a bit "back of the envelope" but I'm pretty sure it holds. It wouldn't be too hard to formalise that though.
So a necessary condition is that the number of 1s is even. Whether or not this is also sufficient I wouldn't like to guess.
--Tim
 
Tim West
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
OK, you can generalise the above restriction, to the statement: for any row or column, the number of 1s (and so 0s) must be even. Same logic - each flip changes an even number of values (ie, 4), so if there was an odd number to start with, there's an odd number to finish with.
So this is another necessary condition. I still don't think it's sufficient (eg, consider case where you have all 0s, but four 1s in a square in one corner), but it's closer.

--Tim
 
Tim West
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ugh, I just realised I was working on the negation of the original problem. I'm trying to find when you will get all 1s (or all 0s, the two are equivalent).
Still, since the problems are equivalent, I haven't wasted my time (well, no more than I had already )
-Tim
 
Arjun Shastry
Ranch Hand
Posts: 1907
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
My thinking was when we add one to each square ,there is total addition of 16.Hence at any stage,if S is initial sum,(S mod 16) is invariant.
 
Tim West
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Oh yeah - good thinking....that's obviously a super-condition to my even-number one.
By the same generalisation, the number of 1s in any column or row must be exactly four.
That to me feels a lot more complete. A proof still sounds pretty hard though.

--Tim
[ May 11, 2004: Message edited by: Tim West ]
 
Tim West
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hmm, more thoughts.
Some notation. Let the board be B, B[m,n] be the mth row, nth column. Let F[m,n] be a flip of a 4x4 area whose top left hand corner is [m, n]. 1 <= m,n <= 8.
Now, if a given board has a solution, then there must exist a series of flips F1 .. Fn such that the board after this series is all 0s.
Also, note that the order in which the flips are applied is irrelevant: the end result is that each cell of the board has been flipped a certain number of times. So, we can order the flips. Say the lowest being top LH corner, then increasing across the row, then onto the next row. (I could define this formally but I won't). Now, that means the last flip, if it is used, has coordinates F[5,5].
Now, with this in mind, I think the following algorithm will find a solution if there is one, or demonstrate that there isn't one:

Now, as to what properties this algorithm implies in terms of the number of 1s/0s at the start and anything else, I don't know. But I think it sounds good It's also O(n) on the number of squares on the board.

--Tim
[ May 11, 2004: Message edited by: Tim West ]
 
Arjun Shastry
Ranch Hand
Posts: 1907
1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
also (S mod 2)is invariant.For every integer in squre to be even ,at final stage (S mod 2) must be 0.so if inital sum is even only theb its possible to get even integer in square as even.
 
Tim West
Ranch Hand
Posts: 539
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yup it's invariant, but moreover it must be equal to zero if a solution exists. Also, (S mod 2 = 0) is always true if (S mod 16) = 0, which must be true as you pointed out earlier.
I think if I sat down and tried it now I could prove that the following two are necessary and sufficient for it to be possible:
  • (number of 0 squares) mod 16 = 0
  • For every row and column, (number of 0 squares) mod 4 = 0


  • But I dunno whether I'll ever get round to it...or post it here, it might be a lil' tedious.
    Hmmm....still not 100% sure it's OK though.
    --Tim
    [ May 11, 2004: Message edited by: Tim West ]
    [ May 11, 2004: Message edited by: Tim West ]
     
    Did you miss me? Did you miss this tiny ad?
    a bit of art, as a gift, that will fit in a stocking
    https://gardener-gift.com
    reply
      Bookmark Topic Watch Topic
    • New Topic