Διαφορετικές σειρές μετά από διαγραφή στήλης

#1

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

Mathletic · #2

Ορίζουμε μια αύξουσα ακολουθία $s_0,...,s_n\in \{1,...,n\}$ ως εξής:

s_0 = 1

και

ισούται με τον αριθμό των διακριτών γραμμών του $n\times k$ πίνακα,που αποτελείται από τις

πρώτες στήλες του αρχικού πίνακα.

Είναι προφανές ότι είναι μια αύξουσα ακολουθία και αν $s_{k-1} = s_k$ , τότε μπορούμε να διαγράψουμε την

-οστή στήλη , χωρίς κάποιες από τις γραμμές να γίνουν ίσες.

Όμως $s_k \leq n \forall k$ και s_0 = 1

,οπότε συνεπάγεται ότι πρέπει να υπάρχει ένα $k\in \{1,...,n\}$ τέτοιο ώστε $s_{k-1} = s_k$ .

#3

Πολύ ωραία! Δίνω και μια απόδειξη με θεωρία γραφημάτων:

Ας υποθέσουμε ότι αυτό δεν ισχύει. Σχηματίζουμε ένα γράφημα με κορυφές τις σειρές του πίνακα. Για κάθε $1 \leqslant i \leqslant n$ επιλέγουμε ακριβώς ένα ζεύγος σειρών οι οποίες είναι ίδιες μεταξύ τους όταν αφαιρεθεί αυτή η στήλη και τοποθετούμε μία ακμή μεταξύ τους.

Έχουμε

κορυφές και

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

. (Πιθανώς k=2

.) Οπότε υπάρχουν σειρές $r_1,r_2,\ldots,r_k$ ώστε χωρίς βλάβη της γενικότητας, για κάθε $1 \leqslant i \leqslant k$ οι στήλες r_i

και $r_{i+1}$ (όπου $r_{k+1} = r_1$ ) έχουν ακριβώς τα ίδια στοιχεία εκτός ίσως από το στοιχείο στην στήλη

. Τότε όμως η r_1

έχει το ίδιο στοιχείο με την r_2

στην στήλη

, άρα το ίδιο και με την r_3

και επαγωγικά η r_1

και

έχουν το ίδιο στοιχείο στην στήλη

. Οπότε έχουν ακριβώς τα ίδια στοιχεία, άτοπο.

Mathletic · #4

Demetres έγραψε:Πολύ ωραία! Δίνω και μια απόδειξη με θεωρία γραφημάτων:

Ας υποθέσουμε ότι αυτό δεν ισχύει. Σχηματίζουμε ένα γράφημα με κορυφές τις σειρές του πίνακα. Για κάθε $1 \leqslant i \leqslant n$ επιλέγουμε ακριβώς ένα ζεύγος σειρών οι οποίες είναι ίδιες μεταξύ τους όταν αφαιρεθεί αυτή η στήλη και τοποθετούμε μία ακμή μεταξύ τους.

Έχουμε κορυφές και ακμές οπότε υπάρχει ένα κύκλος στο γράφημα, έστω μήκους . (Πιθανώς .) Οπότε υπάρχουν σειρές $r_1,r_2,\ldots,r_k$ ώστε χωρίς βλάβη της γενικότητας, για κάθε $1 \leqslant i \leqslant k$ οι στήλες και $r_{i+1}$ (όπου $r_{k+1} = r_1$ ) έχουν ακριβώς τα ίδια στοιχεία εκτός ίσως από το στοιχείο στην στήλη . Τότε όμως η έχει το ίδιο στοιχείο με την στην στήλη , άρα το ίδιο και με την και επαγωγικά η και έχουν το ίδιο στοιχείο στην στήλη . Οπότε έχουν ακριβώς τα ίδια στοιχεία, άτοπο.

Ενδιαφέρον!

Διαφορετικές σειρές μετά από διαγραφή στήλης

Διαφορετικές σειρές μετά από διαγραφή στήλης

Re: Διαφορετικές σειρές μετά από διαγραφή στήλης

Re: Διαφορετικές σειρές μετά από διαγραφή στήλης

Re: Διαφορετικές σειρές μετά από διαγραφή στήλης

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