uniolympiads Ελληνικά

IMC 2001, Day 1, Problem 1

Let nn be a positive integer. Consider an n×nn \times n matrix with entries 1,2,…,n21, 2, \dots, n^2 written in order starting top left and moving along each row in turn left–to–right. We choose nn entries of the matrix such that exactly one entry is chosen in each row and each column. What are the possible values of the sum of the selected entries?

Original from the official PDFLet n be a positive integer. Consider an n×n matrix with entries 1, 2, . . . , n 2 written in order starting top left and moving along each row in turn left–to– right. We choose n entries of the matrix such that exactly one entry is chosen in each row and each column. What are the possible values of the sum of the selected entries?

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

Solution. Since there are exactly nn rows and nn columns, the choice is of the form

{(j,σ(j)):j=1,…,n}\{(j,\sigma(j)):j=1,\dots,n\}
where σ∈Sn\sigma\in S_n is a permutation. Thus the corresponding sum is equal to
∑j=1nn(j−1)+σ(j)=∑j=1nnj−∑j=1nn+∑j=1nσ(j)\sum_{j=1}^n n(j-1)+\sigma(j)=\sum_{j=1}^n nj-\sum_{j=1}^n n+\sum_{j=1}^n\sigma(j)
=n∑j=1nj−∑j=1nn+∑j=1nj=(n+1)n(n+1)2−n2=n(n2+1)2,=n\sum_{j=1}^n j-\sum_{j=1}^n n+\sum_{j=1}^n j=(n+1)\frac{n(n+1)}{2}-n^2=\frac{n(n^2+1)}{2},
which shows that the sum is independent of σ\sigma.

Transcribed from the official solutions, page 1. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?