A question from Regional Maths Olympiad, Maharashtra, India Watch

Spandy
Badges: 3
Rep:
?
#1
Report Thread starter 5 years ago
#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
reply
TeeEm
Badges: 19
Rep:
?
#2
Report 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
reply
ghostwalker
  • Study Helper
Badges: 17
#3
Report 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
reply
Spandy
Badges: 3
Rep:
?
#4
Report Thread starter 5 years ago
#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
reply
ghostwalker
  • Study Helper
Badges: 17
#5
Report 5 years ago
#5
(Original post by Spandy)
man, you rock!
Only on the odd occasion.
0
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#6
Report 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: f, g are unchanged on reordering rows and columns, and f+g on taking the transpose. f(-A) = -f(A) because n is odd, and more generally if we negate an m \times m submatrix where m is even, then f, g are unchanged. (Proof in spoiler.)
Spoiler:
Show
Proof: f, g are unchanged on reordering rows and columns, so reorder such that the elements we negated are the top mxm square. Then if the row products were f_1, f_2, \dots, f_m, f_{m+1}, \dots, f_n before, they are now f_1 (-1)^{m \pmod{2}}, f_2 (-1)^{m \pmod{2}}, \dots, f_m (-1)^{m \pmod{2}}, f_{m+1}, \dots, f_n, but that's just the same as f_1, \dots, f_n. Same analysis on g.


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 -1, because if there are, flip them to 1 without changing f, g. (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 f, g 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 f+g? 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 (x_1, \dots, x_r) = (m_1, \dots, m_k, 0, n_1, \dots, n_l), then, we have \displaystyle f+g = - \sum_{i=1}^k m_i + \sum_{i=1}^l (-1)^{n_i} + \sum_{j=1}^k (-1)^{m_j} - \sum_{j=1}^l n_j.

That is \displaystyle (\sum_{i=1}^r -x_i + (-1)^{x_i})-1 (the -1 is to account for the (-1)^0 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.
Attached files
1
reply
Smaug123
  • Study Helper
Badges: 13
Rep:
?
#7
Report 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
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

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

Personalise

University open days

  • University of East Anglia
    PGCE Open day Postgraduate
    Tue, 3 Mar '20
  • University of Bradford
    Postgraduate Open day/Evening Postgraduate
    Tue, 3 Mar '20
  • Queen's University Belfast
    Postgraduate LIVE Masters & PhD Study Fair Postgraduate
    Wed, 4 Mar '20

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%

Watched Threads

View All