Putnam 2011/A4

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

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

Putnam 2011/A4

#1

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Οκτ 26, 2016 8:48 pm

Για ποιους φυσικούς n υπάρχει ακέραιος πίνακας ώστε το εσωτερικό γινόμενο κάθε σειράς του πίνακα με τον εαυτό της να είναι άρτιος, ενώ το εσωτερικό γινόμενο κάθε δύο διαφορετικών σειρών να είναι περιττός;



Λέξεις Κλειδιά:
dement
Διευθύνον Μέλος
Δημοσιεύσεις: 1405
Εγγραφή: Τρί Δεκ 23, 2008 10:11 am

Re: Putnam 2011/A4

#2

Μη αναγνωσμένη δημοσίευση από dement » Πέμ Οκτ 27, 2016 12:20 am

Υπάρχει κατάλληλος πίνακας αν και μόνο αν ο n είναι περιττός.

Για κάθε n \in \mathbb{Z}_+ ορίζουμε τον πίνακα n \times n S_n με (S_n)_{ij} \equiv 1 - \delta_{ij}. Εύκολα διαπιστώνουμε ότι, αν ο n είναι περιττός, ο S_n είναι κατάλληλος πίνακας.

Αντίστροφα, έστω A κατάλληλος πίνακας για n άρτιο. Προσθέτοντας όλες τις στήλες του στην πρώτη διαπιστώνουμε ότι ο \det(A) είναι άρτιος (αφού κάθε γραμμή του έχει άρτιο αριθμό περιττών στοιχείων). Επειδή κάθε στοιχείο του AA^T είναι ισότιμο \mod 2 με το αντίστοιχο του S_n συμπεραίνουμε ότι και ο \det(S_n) είναι άρτιος. Όμως, προσθέτοντας (\mod 2) όλες τις στήλες του S_n στην πρώτη και στη συνέχεια αφαιρώντας την πρώτη στήλη από όλες τις άλλες καταλήγουμε σε πίνακα τριγωνικό κάτω με όλα τα στοιχεία της διαγωνίου 1. Άρα ο \det(S_n) είναι περιττός και έχουμε άτοπο.


Δημήτρης Σκουτέρης

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

Re: Putnam 2011/A4

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Οκτ 27, 2016 12:47 am

Ωραία Δημήτρη!

Διαφορετικά αν γράψουμε J_n για τον n \times n πίνακα που έχει παντού άσσους, τότε είναι \mathrm{rank}(J_n)=1 και άρα ο J_n έχει ιδιοτιμή 0 με πολλαπλότητα n-1. Επειδή \mathrm{tr}(J_n) = n η άλλη ιδιοτιμή του J_n ισούται με n.

Άρα ο AA^T = J_n - I_n έχει ιδιοτιμές -1,-1,\ldots,-1,n-1 και άρα \det(AA^T) = (-1)^{n-1}(n-1) \equiv 1 \bmod 2.

\rule{500pt}{1pt}

Στην λύση που είδα δείχνει ότι (J_n-I_n)^2 = \cdots = (n-2)J_n + I_n \equiv I_n \bmod 2


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

Re: Putnam 2011/A4

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Οκτ 27, 2016 2:36 pm

Ας δούμε ακόμη μια απόδειξη:

Έστω x_1,\ldots,x_n οι γραμμές του πίνακα τις οποίες θεωρούμε ως διανύσματα πάνω από το \mathbb{F}_2. Έστω επίσης x = (1,1,\ldots,1).

Στην περίπτωση όπου ο n είναι άρτιος, θα δείξω ότι τα x,x_1,\ldots,x_n είναι γραμμικώς ανεξάρτητα. Αυτό ασφαλώς είναι άτοπο αφού αυτά είναι n+1 διανύσματα στο \mathbb{F}_2^n.

Οι συνθήκες δίνει x_i \cdot x_j = 1 - \delta_{ij}. Επίσης x \cdot x_i = x_i \cdot x_i = 0.

Ας υποθέσουμε λοιπόν ότι \lambda x + \lambda_1 x_1 + \cdots + \lambda_nx_n = 0. (*)

Παίρνοντας εσωτερικό γινόμενο στην (*) με το x_1 λαμβάνουμε \lambda_2 + \cdots + \lambda_n = 0 ή ισοδύναμα \lambda_1 + \cdots + \lambda_n = \lambda_1.

Ομοίως λαμβάνουμε \displaystyle{ \lambda_1 + \cdots + \lambda_n = \lambda_1 = \cdots = \lambda_n}

Αν λοιπόν \lambda_1 = \cdots = \lambda_n = k, τότε k = \lambda_1 + \cdots + \lambda_n = nk = 0 αφού ο n είναι άρτιος. Άρα \lambda_1 = \cdots = \lambda_n = 0 και από την (*) παίρνουμε και \lambda = 0.

Οπότε όντως τα διανύσματα είναι γραμμικώς ανεξάρτητα και το ζητούμενο αποδείχθηκε.


Άβαταρ μέλους
gbaloglou
Επιμελητής
Δημοσιεύσεις: 2745
Εγγραφή: Παρ Φεβ 27, 2009 10:24 pm
Τοποθεσία: Θεσσαλονικη
Επικοινωνία:

Re: Putnam 2011/A4

#5

Μη αναγνωσμένη δημοσίευση από gbaloglou » Πέμ Οκτ 27, 2016 7:11 pm

Demetres έγραψε:Ας δούμε ακόμη μια απόδειξη:

Έστω x_1,\ldots,x_n οι γραμμές του πίνακα τις οποίες θεωρούμε ως διανύσματα πάνω από το \mathbb{F}_2. Έστω επίσης x = (1,1,\ldots,1).

Στην περίπτωση όπου ο n είναι άρτιος, θα δείξω ότι τα x,x_1,\ldots,x_n είναι γραμμικώς ανεξάρτητα. Αυτό ασφαλώς είναι άτοπο αφού αυτά είναι n+1 διανύσματα στο \mathbb{F}_2^n.

Οι συνθήκες δίνει x_i \cdot x_j = 1 - \delta_{ij}. Επίσης x \cdot x_i = x_i \cdot x_i = 0.

Ας υποθέσουμε λοιπόν ότι \lambda x + \lambda_1 x_1 + \cdots + \lambda_nx_n = 0. (*)

Παίρνοντας εσωτερικό γινόμενο στην (*) με το x_1 λαμβάνουμε \lambda_2 + \cdots + \lambda_n = 0 ή ισοδύναμα \lambda_1 + \cdots + \lambda_n = \lambda_1.

Ομοίως λαμβάνουμε \displaystyle{ \lambda_1 + \cdots + \lambda_n = \lambda_1 = \cdots = \lambda_n}

Αν λοιπόν \lambda_1 = \cdots = \lambda_n = k, τότε k = \lambda_1 + \cdots + \lambda_n = nk = 0 αφού ο n είναι άρτιος. Άρα \lambda_1 = \cdots = \lambda_n = 0 και από την (*) παίρνουμε και \lambda = 0.

Οπότε όντως τα διανύσματα είναι γραμμικώς ανεξάρτητα και το ζητούμενο αποδείχθηκε.
Πεπερασμένα σώματα, άπειρες εφαρμογές! :clap2:


Γιώργος Μπαλόγλου -- κρυσταλλογράφω άρα υπάρχω

Ὁρᾷς, τὸ κάλλος ὅσσον ἐστὶ τῆς λίθου, ἐν ταῖς ἀτάκτοις τῶν φλεβῶν εὐταξίαις. -- Παλατινή Ανθολογία 9.695 -- Ιδού του πετραδιού η άμετρη ομορφιά, μεσ' των φλεβών τις άναρχες πειθαρχίες.
Απάντηση

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

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

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