IMC 2012/1/2

Έστω θετικός ακέραιος

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

Για

οι απαντήσεις είναι 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$ υπάρχει πίνακας τάξης

που ικανοποιεί τις προϋποθέσεις. Παίρνουμε σαν πρώτη γραμμή το $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

. Τα

θα επιλεχθούν αργότερα.

Παρατηρούμε ότι στην k+3

θέση αυτής της γραμμής το στοιχείο ισούται με 1 - 2k/k + k^2/k^2 = 0

ενώ στην

θέση με $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$ η ελάχιστη δυνατή τάξη ισούται με

.

IMC 2012/1/2

IMC 2012/1/2

Re: IMC 2012/1/2

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