Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This puzzle is the continuation of "Professor Halfbrain and the 99x99 chessboard (Part 1)". The difference is that "four corners of a rectangle" has now become "$2\times2$ subsquare".


Professor Halfbrain has spent the last weekend with filling the squares of a $99\times99$ chessboard with real numbers from the interval $[-1,+1]$. Whenever four squares form a $2\times2$ subsquare of the chessboard, then the four numbers in these squares had to add up to zero.

Professor Halfbrain has proved two extremely deep theorems on this.

Professor Halfbrain's first theorem: It is possible to fill the chessboard subject to the above rules, so that the sum of all numbers in all the squares is $0$.

Professor Halfbrain's second theorem: If we fill the chessboard subject to the above rules, then the sum of all numbers in all the squares is at most $9801$.

This puzzle asks you to improve the two theorems of professor Halfbrain and to make them even deeper. Find an integer $y$, so that "the sum in all the squares is $0$" in the first theorem may be replaced by "the sum in all the squares is $y$", and so that "the sum is at most $9801$" in the second theorem may be replaced by "the sum is at most $y$" (again yielding true statements, of course).

share|improve this question
1  
The first is trivial to prove - simply fill the entire board with nothing but 0's... – Darrel Hoffman Mar 1 at 19:07
3  
The second is, too; he is Professor "Halfbrain" – Richard Rast Mar 1 at 20:20
    
@Gamow if my answer is acceptable, could you please mark it as the accepted answer? :) Or elaborate if it's not acceptable? Thanks. – Piotr Pytlik Mar 3 at 16:28
up vote 13 down vote accepted

Part 1
Since we know that all $2\times2$ squares will have a sum of all values equal to $0$, then we can say that the sum of the chessboard is equal to the sum of elements in the last row and column, because we can group all the other squares into $2\times2$ squares of sum $0$.

I can achieve a sum of $99$ by filling the board with:

enter image description here

The sum of the last column and last row $= 99 \times 1 + 1-1 + 1-1 +... +1-1 = 99$.

Proving the upper, lower bound

I've shown a method to get the value $99$. We can get $-99$ by multiplying each square by $-1$.
I can further show that we definitely can't achieve more than $99$; this will be proof for the upper bound (also for lower bound).

We will fill the chessboard with $2\times2$ tiles, where each tile covers a $2\times2$ square of which the sum is equal to $0$. Thanks to Paul Sinclair for noticing that the below tiling shows that you can place $49^2$ tiles and that we don't need to prove you can't place more.

A valid tiling would be to leave a zig-zag across a diagonal, as shown in smaller scale:

tiling

I would like to now state that for every red L shape, the sum of all 3 squares is between $[-1, +1]$. This is obvious because the red L shape, along with the neighboring green square must have a sum of $0$, and the value of the green square is between $[-1, +1]$.

With this property we can now say that there are 50 blue squares on our board, and 49 red L shapes, and the sum of all these squares is the sum of our board. However the blue squares are each between $[-1, +1]$, and each red L shape is between $[-1, +1]$, so our board sum must be between $[-99, +99]$.

Part 2
My first tiling allows us to get the sum of all numbers in all the squares is $= x$ as long as $-99 \le x \le 99$.
Say $x = 99y$. Now lets change all my $1$'s to $y$'s, and all my $-1$'s to $-y$'s.
Similarly, adding the squares gives the sum equal to $99y = x$, again $-1 \le y < 1$, so for this solution, $-99 \le x \le 99$.

share|improve this answer
    
Do you mean $49^2$ tiles? You can get that many by covering a 98x98 subgrid. – Paul Sinclair Mar 1 at 20:01
1  
But I don't see why you need a proof that $49^2$ is the maximum number of tiles that can be placed. It isn't needed for your bound - just the one tiling you showed. – Paul Sinclair Mar 1 at 20:06
    
@PaulSinclair yes, I meant the amount you said, I'll change it. I guess if I showed that 99 is possible and it can't be more as per the tiling, then it pulls that you can't place more tiles. I just wasn't sure, at the moment of posting, if adding another tile would change anything :) Thanks for the comment. – Piotr Pytlik Mar 1 at 21:05

Another way of getting 99: If we give each square an $x$ and $y$ coordinate, starting with (1,1) in the top left corner, we give each square with even $x$ and even $y$ a value of $-1$, each square with odd $x$ and $y$ a value of $1$, and each other square a value of $0$, then we have $50^2 \times 1 + 49^2 \times -1 = 99$.

Old Answer: Not sure if it's optimal, but I can get 866 65.6:

If we give each square an $x$ and $y$ coordinate, starting with (1,1) in the top left corner, we give each square with even $x$ and even $y$ a value of $-1$, and each other square a value of $\frac13$. Each $2\times2$ square will contain exactly one square with value $-1$, and $3$ with value $\frac13$, for a total sum of $0$. We have $49^2$ -1's, and $99^2 - 49^2$ with value $\frac13$, for a total value of $65.6$.

share|improve this answer
    
I'm not sure enough of my answer, so i'm not posting anything yet, but i'd like to say that we know that any 2x2 square has a sum of 0, so we can group squares so that we know the sum of the board equals the sum of all the elements in the last row and column of the board. Also, your solution gives 65.(6), not 866. – Piotr Pytlik Mar 1 at 15:55
    
@PiotrPytlik Must have messed up the calculation somehow. Will revise answer – StephenTG Mar 1 at 16:07
    
Your first version is interesting, because you will get 99 even if you change a single 0 to some value p, because it will automatically fill the board so that for all odd x and even y, the value is -p, and for all even x and odd y, the value is +p. In the last column and row, the amount of such squares is the same, so the sum stays 99 :) (in my suggestion, i set p to -1) – Piotr Pytlik Mar 1 at 16:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.