IMC 2012/1/2

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

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

IMC 2012/1/2

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Ιούλ 28, 2012 4:16 pm

Έστω θετικός ακέραιος n. Να υπολογιστεί η μικρότερη δυνατή τάξη ενός n \times n πίνακα ο οποίος έχει μηδενικά στην κύρια διαγώνιο και θετικούς πραγματικούς στις υπόλοιπες θέσεις.


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

Re: IMC 2012/1/2

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Σάβ Ιούλ 28, 2012 5:36 pm

Για n=1,2 οι απαντήσεις είναι 0 και 2 αντίστοιχα.

Για n \geqslant 3 ισχυρίζομαι ότι ο πίνακας έχει τάξη μεγαλύτερη ή ίση του 3. Πράγματι έστω ότι δεν ισχύει και έστω c_{i_1},c_{i_2},c_{i_3} τρεις γραμμικώς εξαρτημένες στήλες του πίνακα. Έστω ότι a_1c_{i_1} + a_2c_{i_2} + a_3c_{i_3} = 0 για κάποια a_1,a_2,a_3. Πρέπει a_1a_2a_3 \neq 0 αφού οι στήλες είναι γραμμικώς ανεξάρτητες ανά δύο. Χωρίς βλάβη της γενικότητας έχουμε οι a_1,a_2 έχουν το ίδιο πρόσημο έστω θετικό. Αλλά τότε κοιτώντας την γραμμή i_3, βλέπουμε ότι σε αυτήν την θέση το στοιχείο του a_1c_{i_1} + a_2c_{i_2} + a_3c_{i_3} είναι θετικό, άτοπο.

Θα δείξουμε τώρα ότι για n \geqslant 3 υπάρχει πίνακας τάξης 3 που ικανοποιεί τις προϋποθέσεις. Παίρνουμε σαν πρώτη γραμμή το r_1 = (0,a,b,1,2,\ldots,1) σαν δεύτερη γραμμή το r_2 = (c,0,d,1,2,\ldots,n-3) και σαν τρίτη γραμμή το r_3 = (e,f,0,1,4,\ldots,(n-3)^2). Σαν k+3 γραμμή τώρα ορίζουμε το r_1 - 2r_2/k + r_3/k^2. Τα a,b,c,d,e,f θα επιλεχθούν αργότερα.

Παρατηρούμε ότι στην k+3 θέση αυτής της γραμμής το στοιχείο ισούται με 1 - 2k/k + k^2/k^2 = 0 ενώ στην m+3 θέση με m \neq k ισούται με 1 - 2m/k + m^2/k^2 = (1-m/k)^2 > 0. Μένει να ελέξγουμε ότι τα στοιχεία στις τρεις πρώτες θέσεις των υπόλοιπων γραμμών είναι θετικά.

Για τις πρώτες θέσεις αρκεί -2c/k + e/k^2 > 0 οπότε αρκεί e > 2kc για κάθε 1 \leqslant k \leqslant n-3.
Για τις δεύτερες θέσεις αρκεί a + f/k^2 > 0 για κάθε 1 \leqslant k \leqslant n-3.
Για τις τρίτες θέσεις αρκεί b - 2d/k > 0 οπότε αρκεί bk > 2d για κάθε 1 \leqslant k \leqslant n-3.

Μπορούμε έυκολα να κάνουμε επιλογές που να ικανοποιούν τις πιο πάνω συνθήκες. Π.χ. a=b=c=f=1,d=1/3,e=2n.

Άρα για n \geqslant 3 η ελάχιστη δυνατή τάξη ισούται με 3.


Απάντηση

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

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

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