# A question from Regional Maths Olympiad, Maharashtra, IndiaWatch

Announcements
#1
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
5 years ago
#2
(Original post by 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.
good grief.

I hope somebody does it so I can see the solution too.
1
5 years ago
#3
(Original post by 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.
Start with a grid 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:
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
#4
(Original post by 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:
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.

man, you rock!
0
5 years ago
#5
(Original post by Spandy)
man, you rock!
Only on the odd occasion.
0
5 years ago
#6
(Original post by 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.
ETA: this is unfinished, and ghostwalker's solution is much more elegant :P this is just me demonstrating how I thought about it, and presenting an approach which could yield some more general results.

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.)

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
5 years ago
#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
0
X

new posts Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### University open days

• University of East Anglia
Tue, 3 Mar '20
Tue, 3 Mar '20
• Queen's University Belfast
Wed, 4 Mar '20

### Poll

Join the discussion

#### Do you get study leave?

Yes- I like it (523)
60.05%
Yes- I don't like it (44)
5.05%
No- I want it (245)
28.13%
No- I don't want it (59)
6.77%