Question

In how many ways can one fill a 4×4 grid with a 0 or 1 in each square such that the sum of the entries in each row, column, and long diagonal is even?

(copied question from a tournament test)

Answer 1

nah,,this is more complex than i assumed! hmm..

Answer 2

@Hero @lgbasallote @UnkleRhaukus @.Sam. @walne @ghass1978 @mukushla

Answer 3

( )( )( )( )
( )( )( )( )
( )( )( )( )
( )( )( )( )

Okay... this is just my thought. (So if there are other users who is looking at this, please tell me if this is right!)

There are 8 4-digit sequence you can make with 0 and 1 (that sums up to an even number)
0000
0011
0101
0110
1001
1010
1100
1111

So, just select to and put them in the diagonals.

for example,
(1)( )( )(0)
( )(0)(1)( )
( )(0)(0)( )
(1)( )( )(1)

like that.

Now, let's put a random number in one of the two blanks at the top.

(1)(1)( )(0)
( )(0)(1)( )
( )(0)(0)( )
(1)( )( )(1)

This automatically forces top and the bottom blanks.


(1)(1)(0)(0)
( )(0)(1)( )
( )(0)(0)( )
(1)(1)(1)(1)

Same thing happens with the left-and right.

(1)(1)(0)(0)
(0)(0)(1)(1)
(0)(0)(0)(0)
(1)(1)(1)(1)

Therefore, for each pair of diagonals, there can be 2x2=4 complete squares.

So, 8*8*4=256

(The hole of this proof
1. Does every pair of diagonal give 4 complete squares? There is no proof that all of them will actually work!

-I hope I can prove this, but it will take some time. So help, everyone!
)

Answer 4

I'm going to try to prove the hole.
(This is not the smartest way, but i think this works!)
First, I am going to define S pair and D pair.
S pair has to get the same number (either 0,0 or 1,1)
D pair has to get different numbers (either 0,1 or 1,0)

divide and conquer.

There are 6 different possibilities for 4 corners (the rest you can flip and rotate)
(0)( )( )(0)
( )( )( )( )
( )( )( )( )
(0)( )( )(0)

(0)( )( )(0)
( )( )( )( )
( )( )( )( )
(0)( )( )(1)

(0)( )( )(0)
( )( )( )( )
( )( )( )( )
(1)( )( )(1)

(0)( )( )(1)
( )( )( )( )
( )( )( )( )
(1)( )( )(0)

(0)( )( )(1)
( )( )( )( )
( )( )( )( )
(1)( )( )(1)

(1)( )( )(1)
( )( )( )( )
( )( )( )( )
(1)( )( )(1)

For the first one:
(0)(a)(b)(0)
(i)(c)(e)(k)
(j)(f)(d)(l)
(0)(g)(h)(0)

a and b is S pair.
c and d is S pair.
e and f is S pair.
g and h is S pair.
i and j is S pair.
k and l is S pair.

Unless there is an odd number of D pair, the square can always be completed.
(This is kind of obvious, so I'm not going to prove this)

For all other 5, we should do the same.

(0)(a)(b)(0)
(h)(i)(k)(c)
(g)(l)(j)(d)
(0)(f)(e)(1)
ab is S pair
cd is D pair
ef D
gh S
ij D
lk S

two D pair in the vertically long 2X4. (ef and ij)
two D pair in the horizontally long 4X2 (cd and ij)


--------------------------------------------------
I'm going to stop right here, since I have to go soon.

However, I think I wrote almost everything.

So please just double check this and ask if anything is unclear!

Thank you!

P.S. I will write the rest when I come back.

Answer 5

k, try to work it out next time.