IMC 2001/1/1

Συντονιστής: Demetres

Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8587
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

IMC 2001/1/1

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Σεπ 25, 2012 7:07 pm

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

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


Άβαταρ μέλους
emouroukos
Συντονιστής
Δημοσιεύσεις: 1417
Εγγραφή: Δευ Δεκ 22, 2008 1:27 pm
Τοποθεσία: Αγρίνιο

Re: IMC 2001/1/1

#2

Μη αναγνωσμένη δημοσίευση από emouroukos » Σάβ Σεπ 29, 2012 6:30 pm

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

Έστω ο \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}}}.


Βαγγέλης Μουρούκος

Erro ergo sum.
Mihalis_Lambrou
Επιμελητής
Δημοσιεύσεις: 13165
Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am

Re: IMC 2001/1/1

#3

Μη αναγνωσμένη δημοσίευση από Mihalis_Lambrou » Σάβ Σεπ 29, 2012 10:25 pm

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

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

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

Μ.


Άβαταρ μέλους
Γ.-Σ. Σμυρλής
Δημοσιεύσεις: 557
Εγγραφή: Κυρ Οκτ 14, 2012 9:47 am
Τοποθεσία: Λευκωσία, Κύπρος

Re: IMC 2001/1/1

#4

Μη αναγνωσμένη δημοσίευση από Γ.-Σ. Σμυρλής » Πέμ Οκτ 18, 2012 9:54 pm

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

'Εστω πίνακας με n\times n τετράγωνα, και στο τετράγωνο (i,j) γράφουμε την τιμή f_{i,j}=a_i+b_j, όπου a_1,\ldots,a_n και b_1,\ldots,b_n πραγματικοί αριθμοί. Έστω επίσης ότι ο φυσικός k διαιρεί τον n και βάφομε kn τετράγωνα κόκκινα, ώστε κάθε γραμμή και κάθε στήλη να έχει ακριβώς k κόκκινα τετράγωνα. Τότε

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


Απάντηση

Επιστροφή σε “Διαγωνισμοί για φοιτητές”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης