Διακεκριμένα σύνολα μετά από αφαίρεση στοιχείου

#1

Δίνονται

διακεκριμένα υποσύνολα $A_1,\ldots,A_n$ του $\{1,2,\ldots,n\}$ . Να δειχθεί ότι υπάρχει στοιχείο $x \in \{1,2,\ldots,n\}$ ώστε $A_i \setminus \{x\} \neq A_j \setminus \{x\}$ για κάθε $i \neq j$ .

Nick1990 · #2

Θα κανω μια προσπαθεια:

Εστω A_1, A_2, ... A_n

τα διακεκριμενα συνολα. Κατασκευαζουμε στο $SL_{n}(Z_{2})$ τον χαρακτηριστικο nxn

πινακα

αν το $i \in A_j$ και

αλλιως. Οι στιλες του πινακα αυτου ειναι διαφορετικες ανα 2. Το ζητουμενο ισοδυναμει με το να μπορουμε να διαγραψουμε μια γραμμη και ο πινακας που θα απομεινει να μην εχει 2 ιδιες στιλες. Αν προσθετοντας οποιεσδηποτε στιλες του χαρακτηριστικου πινακα δεν προκειπτει ποτε το διανυσμα (0,0,...0,1,0,...0) (mod2)

οπου το

βρησκεται στην

θεση, τοτε διαγραφοντας την k-γραμμη εχουμε προφανως το ζητουμενο. Σε αλλη περιπτωση μπορουμε να βρουμε διανυσματα v_1, u_1, v_2, u_2, ... v_n, u_n

τα οποια ανηκουν στο συνολο των στιλων του χαρακτηριστικου πινακα, τετοια ωστε για καθε $1 \leq k \leq n$ να ειναι v_k + u_k = (0,0,...0,1,0,...0) (mod2)

, οπου στην

θεση εμφανιζεται η μοναδα. Τοτε τα διανυσματα s_k = u_k + v_k

ειναι βαση του χωρου ${Z_2}^n$ στο σωμα ${Z_2}$ , και επηδη απο τα διανυσματα αυτα μπορουμε να φτιαξουμε μονο διανυσματα που προκειπτουν προσθετοντας καποιες απο τις

στιλες του πινακα (οποτε το πολυ 2^n

διανυσματα), επεται οτι καθε στοιχειο του χωρου θα γραφεται κατα μοναδικο τροπο σαν αθροισμα στιλων του πινακα. Απο εδω προκειπτει και οτι προσθετοντας καποιες απο τις στιλες του πινακα, θα παρουμε το μηδενικο διανυσμα μονο οταν καθε στιλη θα εμφανιστει στο αθροισμα αρτιου πληθους φορες. Αν λοιπον ισχυουν τα προηγουμενα, τοτε προσθετοντας καποια απο αυτα μπορουμε να κατασκευασουμε το στοιχειο u_1

, ομως αυτο δεν μπορει να γινει για τον εξης λογο: προσθετοντας τα στοιχεια s_k

των οποιων το αθροισμα ειναι u_1

, προσθετονται αρτιου πληθους διανυσματα v_k, u_k

, στο αθροισμα αυτο ομως θα εμφανιστει περιττου πληθους φορες το διανυσμα u_1

και (οπως προκειπτει απο τα παραπανω) αρτιου πληθους διανυσματα v_k, u_k

διαφορα του u_1

, οποτε περιττου πληθους διανυσματα v_k, u_k

, πραγμα που (λογο της μοναδικοτητας της γραφης ενος διανυσματος σαν αθροισμα διανυσματων u_k, v_k

) μας οδηγει σε αντιφαση. Αρα ισχυει το ζητουμενο.

#3

Νίκο σωστά. Μόνο που δεν δουλεύουμε στο $SL_n(\mathbb{F}_2)$ αλλά σε όλους τους $n \times n$ πίνακες με στοιχεία από το $\mathbb{F}_2$ .

Υπάρχει και λύση χωρίς γραμμική άλγεβρα.

Nick1990 · #4

Demetres έγραψε:Νίκο σωστά. Μόνο που δεν δουλεύουμε στο $SL_n(\mathbb{F}_2)$ αλλά σε όλους τους $n \times n$ πίνακες με στοιχεία από το $\mathbb{F}_2$ .

Υπάρχει και λύση χωρίς γραμμική άλγεβρα.

Ναι, αυτο ακριβως εννοουσα, απλα νομισα οτι το συγκεκριμενο συνολο το συμβολιζουμε με $SL_n(\mathbb{F}_2)$ . Τωρα ομως θυμιθηκα οτι στο $SL_n(\mathbb{F}_2)$ εχουμε επι πλεον οτι οι οριζουσες ειναι 1.

Ilias_Zad · #5

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

Παιρνω τον χαρακτηριστικο πίνακα και εγω.
Εστω οτι δεν ισχυει το ζητουμενο τοτε για καθε

μεταξυ

και

υπάρχουν δυο ακριβως στηλες που δινουν αθροισμα το e_i

.
Ομως αυτο σημαινει οτι Α αντιστρεφεται και ο αντιστροφος του εχει σε καθε στηλη ακριβως

ασσους αρα οταν πολ/σουμε τον $A^{-1}$ αναστροφο με το ολο μοναδες διανυσμα παιρνουμε το μηδενικο, κατι αδυνατο!
Ελπιζω να ειναι οκ.

Nick1990 · #6

Ilias_Zad έγραψε:Να δωσω και εγώ την λύση μου στο θέμα αν και παραμένει με γραμμική άλγεβρα ( επιδεχεται όμως σιγουρα συνδιαστική ερμηνεια.)
Παιρνω τον χαρακτηριστικο πίνακα και εγω.
Εστω οτι δεν ισχυει το ζητουμενο τοτε για καθε μεταξυ και υπάρχουν δυο ακριβως στηλες που δινουν αθροισμα το .
Ομως αυτο σημαινει οτι Α αντιστρεφεται και ο αντιστροφος του εχει σε καθε στηλη ακριβως ασσους αρα οταν πολ/σουμε τον $A^{-1}$ αναστροφο με το ολο μοναδες διανυσμα παιρνουμε το μηδενικο, κατι αδυνατο!
Ελπιζω να ειναι οκ.

Πολυ ωραια Ηλια, αν θελουν λιγη περισσοτερη αναλυση αυτα που γραφεις για να ειναι απολυτως κατανοητα.
Οσο για τη συνδιαστικη λυση, δεν ξερω αν εχει καποια σχεση με αυτο που ζηταει ο Δημητρης, αλλα οι γραμμοπραξεις στο F_2

που δινουν το ατοπο, νομιζω πως μπορουν ευκολα να μεταφραστουν σε πραξεις μεταξυ πολυσυνολων

Ilias_Zad · #7

Οκ τοτε.
Δίνω ,πιστευω πολυ αυτη την φορα,αναλυτικά την λύση μου. (οι ισοτητες modulo2)

Θεωρω τον χαρακτηριστικο πινακα με

και

οπου κάθε στηλη

εχει

στο

αν και μονο αν το A_j

περιέχει το στοιχειο

.

Τώρα υποθέτουμε οτι δεν ισχύει το ζητούμενο.

Toτε για καθε

απο

μεχρι

υπαρχει ζευγος δεικτων i_1,i_2

,που ειναι διαφορετικοί μεταξυ τους, ωστε να ισχύει $A_{i_1}-\{i\}=A_{i_2}-\{i \}$

Τωρα είναι άμεσο(γιατι;) οτι το

περιέχεται σε ενα ακριβως απο τα $A_{i_1},A_{i_2}$ .

Ετσι μεταφραζομενο το δεδομένο αυτό στις στηλες του πινακα μας δινει οτι Au=e_i

οπου

to διάνυσμα με μηδεν παντου εκτός απο τις θέσεις i_1,i_2

και

το

-στοιχειο της κανονικής βάσης.

Τωρα απο εδώ έχουμε ,οτι αφου το

ηταν τυχαιο ότι ο

είναι αντιστεψιμος και ότι ο $A^{-1}$ έχει στην

στηλη του ακριβως το διανυσμα

.

Aυτο όμως σημαίνει ότι ο αντίστροφος του Α εχει ακριβως

μοναδες ανα στήλη αρα αν παρουμε τον αναστροφο του που παραμενει αντιστρέψιμος πολλαπλασιασμενο με το ολο μονάδες διάνυσμα δινει ως αποτελεσμα το μηδενικό διανυσμα, πραγμα που μας οδηγει στην ζητουμενη αντιφαση.

#8

Σωστή και η λύση του Ηλία. Δίνω μια από τις λύσεις που έχω υπόψη μου. Θα δώσω και άλλες λύσεις από αύριο:

Θέτουμε $B_i = A_i \setminus \{n\}$ . Αν τα $B_1,\ldots,B_n$ είναι όλα διαφορετικά τότε τελειώσαμε. Υποθέτουμε λοιπόν πως το πολύ n-1

από αυτά είναι διαφορετικά. Εφ' όσων αυτά είναι υποσύνολα του $\{1,\ldots,n-1\}$ επαγωγικά υπάρχει $x \in \{1,\ldots,n-1\}$ ώστε $B_i \neq B_j \Rightarrow B_i \setminus \{x\} \neq B_j \setminus \{x\}$ . Ισχυρίζομαι ότι $A_i \setminus \{x\} \neq A_j \setminus\{x\}$ για κάθε $i \neq j$ . Πράγματι αν το

ανήκει σε ακριβώς ένα από τα A_i,A_j

τότε σίγουρα $A_i \setminus \{x\} \neq A_j \setminus\{x\}$ ενώ αν τα

ανήκει και στα δύο ή αν δεν ανήκει σε κανένα τότε $B_i \neq B_j$ άρα $B_i \setminus \{x\} \neq B_j \setminus \{x\}$ και άρα πάλι έχουμε $A_i \setminus \{x\} \neq A_j \setminus\{x\}$ .

#9

Ακόμη μια λύση (με χρήση θεωρίας γραφημάτων)

Υποθέτουμε πως για κάθε $i \in \{1,\ldots,n\}$ υπάρχουν δυο διαφορετικά σύνολα από τα $A_1,\ldots,A_n$ , έστω τα B_i

και

ώστε $B_i = C_i \cup \{i\}$ .

Κατασκευάζω ένα γράφημα με κορυφές τα $A_1,\ldots,A_n$ . Το γράφημα θα έχει ακριβώς

ακμές. Ακριβώς μία για κάθε ζεύγος B_i,C_i

. Στην ακμή μεταξύ των B_i

και

τοποθετούμε μια "ετικέτα" που λέει ότι αυτή η ακμή προήλθε από το στοιχείο

.

Από την θεωρία γραφημάτων τώρα, αυτό το γράφημα πρέπει να περιέχει ένα κύκλο.(*) Δηλαδή υπάρχει

ώστε χωρίς βλάβη της γενικότητας υπάρχουν οι ακμές $A_1A_2,A_2A_3,\ldots,A_{k-1}A_k,A_kA_1$ . Ισχυρίζομαι ότι αυτό δεν μπορεί να συμβεί. Πράγματι έστω ότι η πρώτη ακμή έχει την ετικέτα "

". Χωρίς βλάβη της γενικότητας το σύνολο A_1

δεν περιέχει το

ενώ το σύνολο A_2

περιέχει το

. Αλλά η ετικέτα "

" δεν ξαναεμφανίζεται. Αυτό σημαίνει πως όλα τα σύνολα $A_3,\ldots,A_k$ περιέχουν το

. Αλλά η ετικέτα "

" δεν εμφανίζεται ούτε στην ακμή A_kA_1

. Άρα και το A_1

περιέχει το

, άτοπο.

(*) Απόδειξη: Έστω ένα γράφημα με

κορυφές και

ακμές. Έστω $x_1x_2 \cdots x_k$ ένα μέγιστο μονοπάτι (όλα τα x_i

διαφορετικα). Αν υπάρχει ακμή μεταξύ του x_k

και του

για κάποιο $1 \leqslant i \leqslant k-2$ τότε το γράφημα περιέχει τον κύκλο $x_ix_{i+1} \cdots x_kx_i$ . Αν όχι τότε το x_k

είναι γειτονικό μόνο με την κορυφή $x_{k-1}$ (αφού το μονοπάτι είναι μέγιστο). Αφαιρώντας λοιπόν το x_k

παίρνουμε ένα γράφημα με n-1

κορυφές και n-1

ακμές. Από την επαγωγική υπόθεση αυτό το γράφημα περιέχει ένα κύκλο. Άρα και το αρχικό γράφημα περιέχει ένα κύκλο.

#10

Θέλω να βάλω ακόμη μια λύση. Είναι μεν στοιχειώδης αλλά αρκετά πιο δύσκολη. Η ιδέα όμως μπορεί να χρησιμοποιηθεί και σε παρόμοια προβλήματα.

Έστω $\mathcal{A} = \{A_1,\ldots,A_n\}$ . Αν κάποιος μας έλεγε ότι αν $A \in \mathcal{A}$ και $B \subseteq A$ τότε $B \in \mathcal{A}$ τότε τα πράγματα θα ήταν εύκολα. Θα είχαμε $\emptyset \in \mathcal{A}$ και αφού $|\mathcal{A}| = n$ τουλάχιστον ένα από τα σύνολα $\{1\},\ldots,\{n\}$ , έστω το $\{i\}$ δεν θα ανήκε στην $\mathcal{A}$ . Αλλά πάλι από την πιο πάνω ιδιότητα κανένα σύνολο της $\mathcal{A}$ δεν θα περιείχε το

. Άρα όλα τα $A_1 \setminus \{i\},\ldots,A_n \setminus\{i\}$ θα ήταν διαφορετικά.

Θα προσπαθήσουμε λοιπόν να «συμπιέσουμε» την $\mathcal{A}$ ώστε να αποκτήσει αυτήν την ιδιότητα. (Σε αυτήν την περίπτωση η $\mathcal{A}$ ονομάζεται ideal ή downset. Προτιμώ το δεύτερο μιας και είναι πιο περιγραφικό.)

Η πρώτη προσπάθεια θα ήταν από την οικογένεια $\mathcal{A}$ να δημιουργήσουμε την οικογένεια $\mathcal{A}_n = \{A_1 \setminus\{n\},\ldots,A_n \setminus \{n\}\}$ . Το πρόβλημα εδώ είναι ότι $\mathcal{A}_n$ μπορεί να έχει λιγότερα από

σύνολα. Άλλωστε αν γνωρίζαμε ότι είχε

σύνολα θα είχαμε τελειώσει.

Πρέπει λοιπόν να κάνουμε κάτι πιο έξυπνο. Για $A \in \mathcal{A}$ ορίζουμε το σύνολο D_n(A)

ως εξής. Αν υπάρχει $B \in \mathcal{A}$ ώστε $A \setminus \{n\} = B$ τότε ορίζουμε D_n(A) = A

. Αλλιώς ορίζουμε $D_n(A) = A \setminus \{n\}$ . Ο βασικός λόγος που το ορίσαμε έτσι είναι ότι τώρα για $A,B \in \mathcal{A}$ με $A \neq B$ έχουμε $D_n(A) \neq D_n(B)$ . Πράγματι αν D_n(A) = D_n(B)

τότε είτε το

ανήκει και στα δύο οπότε A = D_n(A) = D_n(B) = B

είτε το

δεν ανήκει σε κανένα οπότε είτε A=B

είτε $A = B \cup \{n\}$ είτε $B = A \cup \{n\}$ . Αλλά στην δεύτερη και τρίτη περίπτωση θα είχαμε $D_n(A) \neq D_n(B)$ .

Τώρα λοιπόν γνωρίζουμε ότι η οικογένεια $D_n(\mathcal{A}) = \{D_n(A_1),\ldots,D_n(A_n)\}$ αποτελείται από

σύνολα. Ισχυρίζομαι ότι αν υπάρχει

ώστε όλα τα $D_n(A_i) \setminus \{x\}$ να είναι διαφορετικά, τότε και όλα τα $A_i \setminus \{x\}$ θα είναι διαφορετικά. Θα μελετήσουμε δυο περιπτώσεις:

(α) x = n

: Αν $A_i \setminus \{n\} = A_j \setminus \{n\}$ τότε χωρίς βλάβη της γενικότητας $A_i = A_j \cup \{n\}$ και $n \notin A_j$ . Αλλά τότε $D_n(A_i) = A_i, D_n(A_i) \setminus \{n\} = A_j$ και $D_n(A_j) \setminus \{n\} = A_j$ , άτοπο.

(β) $x \neq n$ : Αν $A_i \setminus \{x\} = A_j \setminus \{x\}$ τότε χωρίς βλάβη της γενικότητας $A_i = A_j \cup \{x\}$ και $x \notin A_j$ . Αν το

δεν ανήκει σε κανένα από τα A_i,A_j

τότε $D_n(A_i) \setminus \{x\} = D_n(A_j) \setminus \{x\} = A_j$ . Μπορούμε να υποθέσουμε λοιπόν πως $n \in A_i,A_j$ . Τότε είτε $D_n(A_i) = A_i \setminus \{n\}$ , είτε $A_i \setminus \{n\} \in \mathcal{A}$ . Στην δεύτερη περίπτωση $D_n(A_i \setminus \{n\}) = A_i \setminus \{n\}$ . Άρα και στις δύο περιπτώσεις υπάρχει $A_i{'} \in \mathcal{A}$ ώστε $D_n(A_i{'}) = A_i \setminus \{n\}$ . Ομοίως υπάρχει $A_j{'} \in \mathcal{A}$ ώστε $D_n(A_j{'}) = A_j \setminus \{n\}$ . Αλλά $D_n(A_i{'}) \setminus \{x\} = D_n(A_j{'}) \setminus \{x\}$ , άτοπο.

Ουσιαστικά τώρα έχουμε τελειώσει. Ορίζουμε $\mathcal{B} = D_1(D_2(\cdots D_n(\mathcal{A}) \cdots))$ . Από τα πιο πάνω αρκεί να αποδείξουμε το ζητούμενο για την οικογένεια $\mathcal{B}$ . Όμως η $\mathcal{B}$ είναι downset και άρα το ζητούμενο ισχύει.

Διακεκριμένα σύνολα μετά από αφαίρεση στοιχείου

Διακεκριμένα σύνολα μετά από αφαίρεση στοιχείου

Re: Διακεκριμένα σύνολα μετά από αφαίρεση στοιχείου

Re: Διακεκριμένα σύνολα μετά από αφαίρεση στοιχείου

Re: Διακεκριμένα σύνολα μετά από αφαίρεση στοιχείου

Re: Διακεκριμένα σύνολα μετά από αφαίρεση στοιχείου

Re: Διακεκριμένα σύνολα μετά από αφαίρεση στοιχείου

Re: Διακεκριμένα σύνολα μετά από αφαίρεση στοιχείου

Re: Διακεκριμένα σύνολα μετά από αφαίρεση στοιχείου

Re: Διακεκριμένα σύνολα μετά από αφαίρεση στοιχείου

Re: Διακεκριμένα σύνολα μετά από αφαίρεση στοιχείου

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