1971 IMO Problems/Problem 6
Contents
[hide]Problem
Let be a square matrix whose elements are non-negative integers. Suppose that whenever an element
, the sum of the elements in the
th row and the
th column is
. Prove that the sum of all the elements of the matrix is
.
Solution 1
Take the the row or column (without loss of generality, a row) with the minimum possible sum of its elements. Let
be the number of zeros in this row. We will assume
once the other case is obvious. Clearly
. The total sum
of all elements of the matrix is at least the number of zeros in this row multiplicated by
(because the sum of the elements of a row and a column meeting in a zero is
) plus the number of nonzero elements times
(that is the minimum possible sum), it is,
Note that, being
and
, we can put
instead of
and
instead of
until we get
, what makes the sum become smaller. So we have
by AM - QM inequality.
The above solution was posted and copyrighted by Renan. The original thread for this problem can be found here: [1]
Solution 2
Denote the
th line and column and
the sum of the elements on that row. Let
. For each permutation
, assign to it the number
Now pick a permutation
such that it generates
and its assigned number is minimal. Suppose wlog that
. If
, we are done as twice the sum of all elements is
So suppose
and look at a
such that
. By the maximality of
,
can have
only on the columns
. Note that if
has a
on
with
, i.e.
, by the minimality of the assigned number of
, we have that
. However, if the column
has a
on
, i.e.
, by the same argument we have
, hence
.
Suppose that appears exactly
times on
. This means that
. Suppose that the
s of
appear on the columns
. We have seen earlier that if
has a
on
we have that
. So suppose that it doesn't have
on these lines. However,
has
s only on the lines
by the maximality of
, hence
has at most
zeroes, so
. We thus infer that
so
. By the hypothesis this is also true for
so summing over all values of
we get that the sum is at least
.
The above solution was posted and copyrighted by Aiscrim. The original thread for this problem can be found here: [2]
Solution 3
If the main diagonal contains all zeroes, we can immediately deduce from the condition that the sum of the elements is at least
. This motivates us to consider the largest possible subset of elements, all zero, which are pairwise in different rows of columns - let the size of this subset be
. (If there is no such subset,
.)
Since the condition is invariant under the operation of switching rows or columns, we may rearrange the matrix such that these entries are on the main diagonal of the matrix, i.e.
. Let
,
and
. Then applying the condition to
, we get
.
If , then if
, then we may toss
out of our set and replace it with
and
, to form a larger feasible set of elements, contradiction. Consequently,
for
, which upon summation yields
. Finally,
, trivially. Therefore,
The above solution was posted and copyrighted by randomusername. The original thread for this problem can be found here: [3]
Remarks (added by pf02, March 2025)
Solutions 1 and 2 above are incorrect, and there is room for better wording in solution 3.
Solution 1 is plainly wrong, but it can be salvaged.
Solution 2 is hopelessly incorrect. An attempt to salvage it would be along the lines of Solution 3, in the context of the unnecessarily complicated setup of Solution 2.
Solution 3 is based on a very good idea, and it is easy to make the necessary improvements to make it robust.
The discussion page https://artofproblemsolving.com/community/c6h60831s1_sum_of_all_the_elements_in_the_matrix_is_at_least_n22 contains a fourth solution, but it is incomplete. If completed, it would be just a version of the corrected version of solution 1 given below.
Below I will point out the issues in the three solutions given
above, and when I can, I will give the corrected or improved
solutions. Then I will give some examples. The examples will
show that the inequality
is optimal.
Notation: in all the discussions and proofs given below, I will
denote the
th row and
th column respectively,
and
the sums of
their entries.
Solution 1 analysis and correction
The error in Solution 1
I will use the notation of the solution. We chose a row or
column with minimal sum of its elements (we can assume it was
a row), was the sum of the elements in this row, and
was the number of zeros in it.
At some point in the solution the author writes:
"Note that, being and
, we can put
instead of
and
instead of
until
we get
"
This is wrong! If was chosen to represent a chosen quantity,
we can not change its value in the middle of the proof.
We could try to make sense of the proof by saying that we replace
the given matrix A by a matrix B, where the rows of B are equal
to the rows of A, except for the "minimal" row we chose, in which
we replace one of the zeros by a number (which would replace
by
). This does not work, because if we would show that
the sum of the elements of
is
, it would not
follow that the same is true for
.
Solution 1 corrected
As in the solution, choose a row or column such that the sum of its
elements is minimal. We can assume this is a row (either notice
that taking the transpose of changes neither the hypothesis,
nor the conclusion; or notice that if we do the proof in the case
of a row, the proof in the case of a column is analogous.) Let
be the sum of the elements of this row, and
be the number
of zeros in this row.
For an element of
, we denote
the row and
the column containing
. We denote
the sum of the entries of the matrix in row
and
respectively.
If , then each row
has its sum of elements
, so
.
So, let us assume . Let
be the row we chose (now
is
fixed). For each
consider the sum of the elements of the column
containing
. If
, we know that
(by hypothesis), so
,
so
. We have
such columns.
If , we know that
because
was
minimal. We have
such columns.
So, .
Let . Here we split
in two parts:
represents the number of non-zeroes in
, and
represents
the sum of the "excess" amounts over
of the non-zero entries.
More explicitly,
.
(To clarify: if all non-zero entries of
would
, we
would have
, and
.) In general,
.
Then,
.
The last term is since
and we assumed we
are in the case
. It follows that
.
Note: The strict inequality is not true in general. We obtained
it assuming that . When
we have
.
Note: We could have proven directly that
and note that the last term is the product of two non-negative
factors. However, introducing
gives better insight into the
inequality.
Solution 2 analysis
The error in Solution 2
This solution starts by considering all the permutations
of
. For each
consider the set
, and
denote
to be the number of elements in
.
Let
. Choose a
such that
.
We can assume that . (Note: this
would normally need some justification, but a diligent reader can
supply it.)
For given row and column
define
the
sum of the elements of
and
, respectively.
For any permutation "assign to it the number"
.
At this point, the author says:
"Now pick a permutation such that it generates
and its
assigned number [
] is minimal."
This is the first problem with this proof. It is not clear whether
the author wants to choose to minimize
from among
the permutations for which
, or choose a
to
minimize
over all the possible permutations, and at the
same time
. Since the latter may be impossible, we
should assume the author meant the former. (Note: it does not make
much difference, we could assume that a
in the sense of the
latter interpretation is found, since we will soon see that the proof
is flawed anyway.)
Under the assumption , take
. The author goes on
to say:
"if has a
on
with
, i.e.
, by the minimality of the assigned number
[
] of
, we have that
"
This is completely wrong! One flaw is that is the
sum of many terms, one of them being
. Just because
is in some way minimal, we can not conclude that
one of the terms is
than a term in some other sum.
The other flaw is that it is not clear how the minimality of
is used. The minimality would mean that
for other permutations
, but in
this solution there is no other permutation defined.
There is no point in continuing the analysis, since this is a crucial argument in the proof, and it is an unrecoverable error.
Idea for a fix to Solution 2
We could drop all the discussion about the assigned number
, and about trying to make it minimal.
The author wants to prove that for (for which
) we have
.
(This would yield the desired conclusion). I believe this is true,
and it can be done with a careful examination of the zeros on
and
. It would use ideas along the lines of the
ideas in solution 3. It is not worth the effort of doing this
(especially not in the formalism of permutations) since it would
use no new ideas. This solution would be just a repetition of
solution 3 with a much more complicated formalism.
Note: We know that every permutation is a combination of swaps,
so the permutation could be replaced by swapping rows and/or
columns. Instead of having for
, we could make
for
, and
be maximal with this property.
Solution 3 analysis and improvement
Bad choices of words in Solution 3
The author says:
"consider the largest possible subset of elements, all zero, which
are pairwise in different rows of columns - let the size of this
subset be
...
we may rearrange the matrix such that these entries are on the
main diagonal of the matrix, i.e.
"
This is unclear: the definition of does not make much sense, but
if we insist of giving it some meaning, I would interpret it as
counting the zeroes of
which are not on the diagonal. Note
that this
could be larger than
. Fortunately this flaw is
very easy to correct.
Since there are a few more unhappy choices of words in the proof, I will repeat the proof below, making the improvements to wording.
Solution 3 rewritten
Both the hypothesis and the conclusion of the problem stay true if
we swap rows, or swap columns, or take the transpose of the given
matrix A. If the matrix has no zeroes then the sum of its entries
is . So assume there are zeroes in the matrix.
Recursively, swap rows and swap columns to bring more and more zeroes
onto the diagonal. Let be the maximum number of zeroes we can
bring onto the diagonal. Swap more rows and columns if needed, so
that we will have
.
If then
(by hypothesis). On the other hand
, so the desired result follows.
Assuming , let
, and let
, and
let
.
Because of the hypothesis applied to , we
get
.
Assume we have and
. Now swap
columns
and
. Then
becomes the new entry at
and
becomes the new entry at
. It follows that we
have
zero entries on the diagonal, which contradicts the fact
that
was maximal. Consequently, at least one of
is non-zero, so
for
. It follows
that
.
If we had with
then again, we could swap
columns
and
. Then
becomes the new entry at
,
and again, we have a contradiction of the fact that
was maximal.
Consequently, all elements
with
are non-zero.
It follows that
.
Therefore, .
Note: Another way of finishing off the proof would be to look at
. We know that the terms
for
are
by hypothesis. For
,
we know that
for
, and that
for
. It follows that
.
This is the argument solution 2 would have made in its
complicated formalism, had it reached this point correctly.
Examples
We will say that a matrix is minimal if it satisfies the
hypothesis of the problem (i.e. implies
), and no entry of the matrix
could be replaced by a smaller number such that the new
matrix still satisfies the hypothesis of the problem.
For example, in the matrices below, the first, third and fifth are minimal, but the second is not, since one of its entries could be made smaller to yield the third matrix, and similarly the fourth is not, since one of its entries could be made smaller to yield the fifth matrix.
The examples I will give are all minimal.
Now consider the following matrices:
These examples show that for even, it is possible to have
matrices so that
.
Note that the first three are essentially the same, they can
be obtained from each other by swapping rows and/or columns.
Now let us look at some examples with odd.
The first two are essentially equivalent, since they can be
obtained from each other by swapping rows and/or columns.
These all show that the minimum sum can be reached. The
minimum sum is
, which in
this case (
) is
.
And finally, let us look at a few examples which are minimal,
but the sum of the entries is not the minimum (which for
means that the sum is
).
See Also
1971 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last Question |
All IMO Problems and Solutions |