Σύνολο, μέγιστη τιμή

Συντονιστές: cretanman, Demetres, polysot, socrates, silouan

socrates
Επιμελητής
Δημοσιεύσεις: 6098
Εγγραφή: Δευ Μαρ 09, 2009 1:47 pm
Τοποθεσία: Θεσσαλονίκη
Επικοινωνία:

Σύνολο, μέγιστη τιμή

#1

Μη αναγνωσμένη δημοσίευση από socrates » Δευ Φεβ 21, 2011 7:52 pm

Δίνεται το σύνολο M=\{1,2,3,...,n\}.
Αν υπάρχουν σύνολα X,Y τέτοια ώστε X\cup Y=M, και κανένα από αυτά δεν περιέχει την μέση τιμή δύο οποιονδήποτε στοιχείων του,
να βρεθεί η μέγιστη τιμή του n.


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

Re: Σύνολο, μέγιστη τιμή

#2

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Φεβ 25, 2011 12:06 pm

Θα δείξουμε ότι η μέγιστη δυνατή τιμή είναι το 8.

Αν n = 8 μπορούμε να πάρουμε X = \{1,3,6,8\} και Y = \{2,4,5,7\}. Παρατηρούμε ότι πράγματι αυτά τα σύνολα ικανοποιούν τις συνθήκες.

Ας υποθέσουμε τώρα ότι n \geqslant 9. Χωρίς βλάβη της γενικότητας μπορούμε να υποθέσουμε ότι 5 \in X. Αν 3 \in X, τότε 1,4,7 \in Y (αφού το 3 είναι η μέση τιμή των 1,5, το 4 είναι η μέση τιμή των 3,5 και το 5 είναι η μέση τιμή των 3,7). Αυτό όμως είναι άτοπο αφού το 4 είναι η μέση τιμή των 1,7. Άρα 3 \in Y και με παρόμοιο τρόπο δείχνουμε ότι 7 \in Y.

Αν 2 \in Y, τότε επειδή 3 \in Y πρέπει 1,4 \in X. Επειδή όμως 5 \in X πρέπει 6,9 \in Y, άτοπο αφού το 6 είναι η μέση τιμή των 3,9. Άρα 2 \in X. Με παρόμοιο τρόπο δείχνουμε ότι 8 \in X, άτοπο αφού το 5 είναι η μέση τιμή των 2,8.

---------------------

Το πρόβλημα αυτό γενικεύεται. Παρατηρούμε αρχικά ότι αν το z είναι η μέση τιμή των x,y, τότε τα x,z,y είναι διαδοχικοί όροι αριθμητικής προόδου.

Δείξαμε ότι για κάθε n \geqslant 9 αν χρωματίσουμε τους ακεραίους του συνόλου \{1,2,\ldots,n\} με δύο χρώματα τότε θα υπάρχει τουλάχιστον ένα χρώμα το οποίο να περιέχει μια αριθμητική πρόοδο με τρία στοιχεία.

Η γενίκευση αυτού ονομάζεται θεώρημα van der Waerden και λέει ότι για κάθε k και κάθε r υπάρχει N ώστε για κάθε n \geqslant N, αν χρωματίσουμε τους ακεραίους 1,2,\ldots,n με r χρώματα, θα υπάρχει τουλάχιστον ένα χρώμα το οποίο θα περιέχει μια αριθμητική πρόοδο με k στοιχεία.

Ο μικρότερος αριθμός N για τον οποίο ισχύει το πιο πάνω θεώρημα ονομάζεται αριθμός van der Waerden και συμβολίζεται με W(r,k). Για παράδειγμα δείξαμε ότι W(2,3) = 9. Είναι επίσης τετριμμένο να υπολογιστούν τα W(r,k) για r=1 και k =1,2. Εκτός αυτών, ελάχιστους άλλους αριθμούς van der Waerden γνωρίζουμε. Δείτε π.χ. εδώ.

Τα άνω και κάτω φράγματα που γνωρίζουμε για αυτούς τους αριθμούς έχουν τερααααααστια διαφορά μεταξύ τους.


socrates
Επιμελητής
Δημοσιεύσεις: 6098
Εγγραφή: Δευ Μαρ 09, 2009 1:47 pm
Τοποθεσία: Θεσσαλονίκη
Επικοινωνία:

Re: Σύνολο, μέγιστη τιμή

#3

Μη αναγνωσμένη δημοσίευση από socrates » Σάβ Απρ 11, 2020 11:44 pm

Για n=8 πόσα τέτοια σύνολα X,Y τέτοια ώστε X\cup Y=M, \ X\cap Y=\emptyset υπάρχουν;


Θανάσης Κοντογεώργης
Απάντηση

Επιστροφή σε “Άλγεβρα - Θεωρία Αριθμών - Συνδυαστική (Juniors) - Παλαιότερες Συζητήσεις”

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

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