uniolympiads English

IMC 2001, Ημέρα 1, Θέμα 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?

Πρωτότυπο από το επίσημο 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?

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

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.

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 1. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;