IMC 2001/1/1

#1

Έστω

θετικός ακέραιος. Συμπληρώνουμε τα κελιά ενός $n \times n$ πίνακα με τις τιμές $1,2,\ldots,n^2$ με την σειρά ξεκινώντας από πάνω αριστερά και συνεχίζουμε συμπληρώνοντας κάθε γραμμή από τα αριστερά προς τα δεξιά. (Οι γραμμές συμπληρώνονται και αυτές με την σειρά από πάνω προς τα κάτω.)

Επιλέγουμε

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

#2

Αναδιατυπώνουμε το πρόβλημα ως εξής:

Έστω ο $\displaystyle{n \times n}$ πίνακας

$\displaystyle{A = \left( {\begin{array}{*{20}{c}} 1&2& \ldots &n\\ {n + 1}&{n + 2}& \ldots &{2n}\\ \vdots & \vdots & \ddots & \vdots \\ {{n^2} - n + 1}&{{n^2} - n + 2}& \ldots &{{n^2}} \end{array}} \right)}$

και $\displaystyle{P,Q}$ τυχαίοι $\displaystyle{n \times n}$ πίνακες μεταθέσεων. Ζητείται να υπολογιστεί το ίχνος του πίνακα $\displaystyle{PAQ}$ .

[ Ένας $\displaystyle{n \times n}$ πίνακας μεταθέσεων $\displaystyle{P}$ είναι της μορφής

$\displaystyle{P = {P_\sigma } = \left( {\begin{array}{*{20}{c}} {{e_{\sigma \left( 1 \right)}}}\\ {{e_{\sigma \left( 2 \right)}}}\\ \vdots \\ {{e_{\sigma \left( n \right)}}} \end{array}} \right)}$

όπου $\displaystyle{\sigma \in {S_n}}$ και

$\displaystyle{{e_j} = \left( {\begin{array}{*{20}{c}} 0&0& \ldots &0&{\mathop 1\limits_{\mathop \uparrow \limits_j } }&0& \ldots &0 \end{array}} \right)}$

για $\displaystyle{j \in \left\{ {1,2, \ldots ,n} \right\}}$ . Παρατηρούμε ότι για οποιονδήποτε $\displaystyle{n \times n}$ πίνακα $\displaystyle{M}$ , ο πίνακας $\displaystyle{{P_\sigma }M}$ προκύπτει από τον $\displaystyle{M}$ εφαρμόζοντας τη μετάθεση $\displaystyle{\sigma }$ στις γραμμές του $\displaystyle{M}$ , ενώ ο πίνακας $\displaystyle{M{P_\sigma }}$ προκύπτει από τον $\displaystyle{M}$ εφαρμόζοντας τη μετάθεση $\displaystyle{\sigma }$ στις στήλες του $\displaystyle{M}$ ].

Η λύση του αναδιατυπωμένου προβλήματος έχει ως εξής:

Γράφουμε $\displaystyle{A = B + C}$ , όπου

$\displaystyle{B = \left( {\begin{array}{*{20}{c}} 0&0& \ldots &0\\ n&n& \ldots &n\\ \vdots & \vdots & \ddots & \vdots \\ {{n^2} - n}&{{n^2} - n}& \ldots &{{n^2} - n} \end{array}} \right)}$ , $\displaystyle{C = \left( {\begin{array}{*{20}{c}} 1&2& \ldots &n\\ 1&2& \ldots &n\\ \vdots & \vdots & \ddots & \vdots \\ 1&2& \ldots &n \end{array}} \right)}$ .

Παρατηρούμε ότι ο $\displaystyle{B}$ είναι αναλλοίωτος από τις μεταθέσεις στηλών του, ενώ ο $\displaystyle{C}$ είναι αναλλοίωτος από τις μεταθέσεις γραμμών του. Άρα, είναι:

$\displaystyle{tr\left( {PAQ} \right) = tr\left( {PBQ} \right) + tr\left( {PCQ} \right) = tr\left( {BQP} \right) + tr\left( {QPC} \right) = }$

$\displaystyle{ = tr\left( B \right) + tr\left( C \right) = tr\left( A \right) = 1 + \left( {n + 2} \right) + \left( {2n + 3} \right) + \cdots + {n^2} = }$

$\displaystyle{ = \boxed{\frac{{n\left( {{n^2} + 1} \right)}}{2}}}$ .

#3

Demetres έγραψε:Έστω θετικός ακέραιος. Συμπληρώνουμε τα κελιά ενός $n \times n$ πίνακα με τις τιμές $1,2,\ldots,n^2$ με την σειρά ξεκινώντας από πάνω αριστερά και συνεχίζουμε συμπληρώνοντας κάθε γραμμή από τα αριστερά προς τα δεξιά. (Οι γραμμές συμπληρώνονται και αυτές με την σειρά από πάνω προς τα κάτω.)

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

Για την ιστορία: Το πρόβλημα είναι "ουσιαστικά το ίδιο" με το εξής θέμα 4 από τον ΑΡΧΙΜΉΔΗ του 1996.

Το θέμα αυτό (και αν θυμάμαι καλά, επίσης τα θέματα 2 και 3 του ίδιου διαγωνισμού) τα είχα βάλει εγώ, ως μέλος τότε της επιτροπής διαγωνισμών της ΕΜΕ. Η λύση που είχα κατά νου είναι αυτή που γράφει ο Δημήτρης στη παραπάνω παραπομπή.

Μ.

Γ.-Σ. Σμυρλής · #4

Γενίκευση: (τετριμμένη)

'Εστω πίνακας με $n\times n$ τετράγωνα, και στο τετράγωνο (i,j)

γράφουμε την τιμή $f_{i,j}=a_i+b_j$ , όπου $a_1,\ldots,a_n$ και $b_1,\ldots,b_n$ πραγματικοί αριθμοί. Έστω επίσης ότι ο φυσικός

διαιρεί τον

και βάφομε

τετράγωνα κόκκινα, ώστε κάθε γραμμή και κάθε στήλη να έχει ακριβώς

κόκκινα τετράγωνα. Τότε

$\displaystyle{ \sum_{(i,j)\,\text{\greektext κόκκινο}} f_{i,j} \,=\, \frac{k}{n} \sum_{i,j=1}^n f_{i,j}. }$

IMC 2001/1/1

IMC 2001/1/1

Re: IMC 2001/1/1

Re: IMC 2001/1/1

Re: IMC 2001/1/1

Μέλη σε σύνδεση