# A question from Regional Maths Olympiad, Maharashtra, India Watch

Announcements

Page 1 of 1

Go to first unread

Skip to page:

There is a square arrangement made out of n elements on each side (n^2 elements total). You can put assign a value of +1 or -1 to any element. A function f(x) is defined as the sum of the products of the elements of each row, over all rows and g(x) is defined as the sum of the product of elements of each column, over all columns. Prove that, for n being an odd number, f(x)+g(x) can never be 0.

1

reply

Report

#2

(Original post by

There is a square arrangement made out of n elements on each side (n^2 elements total). You can put assign a value of +1 or -1 to any element. A function f(x) is defined as the sum of the products of the elements of each row, over all rows and g(x) is defined as the sum of the product of elements of each column, over all columns. Prove that, for n being an odd number, f(x)+g(x) can never be 0.

**Spandy**)There is a square arrangement made out of n elements on each side (n^2 elements total). You can put assign a value of +1 or -1 to any element. A function f(x) is defined as the sum of the products of the elements of each row, over all rows and g(x) is defined as the sum of the product of elements of each column, over all columns. Prove that, for n being an odd number, f(x)+g(x) can never be 0.

I hope somebody does it so I can see the solution too.

1

reply

Report

#3

**Spandy**)

There is a square arrangement made out of n elements on each side (n^2 elements total). You can put assign a value of +1 or -1 to any element. A function f(x) is defined as the sum of the products of the elements of each row, over all rows and g(x) is defined as the sum of the product of elements of each column, over all columns. Prove that, for n being an odd number, f(x)+g(x) can never be 0.

Any arrangement can be reached by flipping 1's to -1's.

Spoiler:

Everytime you flip a 1 to a -1, f(x) changes by 2, and g(x) changes by 2, up or down in each case..

So f(x)+g(x) changes by 0 or 4, up or down, on each flip.

So, f(x) + g(x) is still not divisible by 4, and so cannot equal 0.

Show

Everytime you flip a 1 to a -1, f(x) changes by 2, and g(x) changes by 2, up or down in each case..

So f(x)+g(x) changes by 0 or 4, up or down, on each flip.

So, f(x) + g(x) is still not divisible by 4, and so cannot equal 0.

2

reply

(Original post by

start with a gird of all 1's, then f(x)+g(x) = 2n which is not divisible by 4 when n is odd.

Any arrangement can be reached by flipping 1's to -1's.

**ghostwalker**)start with a gird of all 1's, then f(x)+g(x) = 2n which is not divisible by 4 when n is odd.

Any arrangement can be reached by flipping 1's to -1's.

Spoiler:

everytime you flip a 1 to a -1, f(x) changes by 2, and g(x) changes by 2, up or down in each case..

So f(x)+g(x) changes by 0 or 4, up or down, on each flip.

So, f(x) + g(x) is still not divisible by 4, and so cannot equal 0.

Show

everytime you flip a 1 to a -1, f(x) changes by 2, and g(x) changes by 2, up or down in each case..

So f(x)+g(x) changes by 0 or 4, up or down, on each flip.

So, f(x) + g(x) is still not divisible by 4, and so cannot equal 0.

0

reply

Report

#6

**Spandy**)

There is a square arrangement made out of n elements on each side (n^2 elements total). You can put assign a value of +1 or -1 to any element. A function f(x) is defined as the sum of the products of the elements of each row, over all rows and g(x) is defined as the sum of the product of elements of each column, over all columns. Prove that, for n being an odd number, f(x)+g(x) can never be 0.

Preliminary observations: are unchanged on reordering rows and columns, and on taking the transpose. because is odd, and more generally if we negate an submatrix where m is even, then f, g are unchanged. (Proof in spoiler.)

Spoiler:

Show

The idea then occurs: perhaps there's some kind of normal form we can put each matrix into.

Wlog we may assume that there are no rectangles with corners all , because if there are, flip them to without changing . (There is a unique way to do this for any given matrix: whichever order you do it in, you'll get the same result.) Moreover, we may assume that there are no rectangles which have three corners -1, because we could flip that rectangle so that it had only one corner -1. (This procedure does end, because the number of -1's decreases at each step; note that we haven't proved that it terminates at a unique matrix depending on the order we did the steps in.)

What we have done is to make sure that any -1's which occur, do so in a certain non-overlapping way. Mathematica function to perform this reduction is in the spoiler.

Spoiler:

Show

Code:

internalReduce[mat_] := Module[{m = mat}, Do[If[(i != k && j != l) && Count[Extract[m, {{i, j}, {k, j}, {i, l}, {k, l}}], -1] > 2, {m[[i, j]], m[[i, l]], m[[k, j]], m[[k, l]]} = -{m[[i, j]], m[[i, l]], m[[k, j]], m[[k, l]]}; ], {i, 1, Length[mat]}, {j, 1, Length[mat]}, {k, 1, Length[mat]}, {l, 1, Length[mat]}]; m] reduce[mat_] := FixedPoint[internalReduce, mat]

Therefore there is a (not necessarily unique) reduced form for each matrix. If the matrix is all 1's, it is already in reduced form; otherwise there is a -1 somewhere, in which case reorder rows and columns to make it so that the first column contains the most -1's and they all appear together in the top-left. Reorder columns so that going from left to right the number of -1's decreases (not necessarily strictly). We have that if a column contains more than one -1, then they all appear together and so there is no overlap with any other row: {{-1, 1}, {-1, -1}} is a pattern which cannot appear. Delete any rows/columns of 1's if we can (those rows/columns will all appear at the bottom-right), keeping the grid square.

What does this reduced form look like? Picture attached (sorry it's sideways): it starts off with disjoint columns of -1's, then eventually hits rows of -1's which are also disjoint. Finally in the bottom-right corner there may be a single row or column (but not both) of 1's. ETA: It's easy to see that we can't transform different reduced forms into each other by row-swaps; I believe but haven't proved that we also can't transform them into each other by negating 2x2 squares. (This would prove the uniqueness of reduced forms.) It is true that flipping {{-1,1},{1,-1}} squares won't change the reduced form, because we can then row/col-swap back to the way it originally was.

Recall this matrix has the same as the original.

We can express the matrix as a sequence of integers: {4, 3, 3, 1, 0, 7, 3} for instance represents the 15x15 matrix pictured. (It also represents larger matrices, with rows and columns of 1 at the end, but that doesn't matter for f and g's purposes.)

What is ? Well, for each of the initial rows up to where we start getting rows of -1's, the row-product is -1. For the subsequent rows, the row-product is -1 if the number of -1's in the row is odd, and 1 if it's even.

Hence f=-(4+3+3+1) + (-1)^7 + (-1)^3.

g=(-1)^4 + (-1)^3 + (-1)^3 + (-1)^1 - (7 + 3).

(This ignores the effect of extra 1-rows and columns.)

Supposing the matrix were , then, we have .

That is (the -1 is to account for the term). We've still ignored the effect of extra 1-rows and columns.

Todo: work out how "n odd" restricts the possible sequences (x_i), then calculate f+g properly for each of those sequences, and show that none of them is 0.

1

reply

Report

#7

I completed my answer. It's based heavily on the one I wrote above - just required one more little leap.

http://www.patrickstevens.co.uk/math...ix-puzzle.html

http://www.patrickstevens.co.uk/math...ix-puzzle.html

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top