Ακολουθίες ακεραίων

#1

Δίνονται τρεις (άπειρες) ακολουθίες θετικών ακεραίων $(a_n)_{n=1}^{\infty}, (b_n)_{n=1}^{\infty}$ και $(c_n)_{n=1}^{\infty}$ .

Να δειχθεί ότι υπάρχουν ακέραιοι p,q

με $p \neq q$ ώστε $a_p \geqslant a_q, b_p \geqslant b_q$ και $c_p \geqslant c_q$

Πηγή: Σοβιετική Ένωση 1961

AlexandrosG · #2

Γειά σου Δημήτρη.

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

Υπάρχει τρόπος χωρίς το Θεώρημα Ramsey?

#3

AlexandrosG έγραψε:Γειά σου Δημήτρη.

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

Υπάρχει τρόπος χωρίς το Θεώρημα Ramsey?

Ναι υπάρχει. Την ακόλουθη λύση την γνώριζα από παλιά γι 'αυτό δεν την έγραψα, ώστε να την χαρούν άλλοι:

Επειδή η ακολουθία (a_n)

παίρνει τιμές φυσικούς αριθμούς, υπάρχει κάποιος όρος ο οποίος είναι ο μικρότερος δυνατός (πρόκειται για την Αρχή του Ελαχίστου των Φυσικών, που ισοδυναμεί με την Αρχή της Επαγωγής). ΄Εστω ο n_1

ο μικρότερος δείκτης με αυτή την ιδιότητα. Εξετάζοντας τους n> n_1

, υπάρχει για τον ίδιο λόγο κάποιος μικρότερος όρος $a_{n_2}$ της ακολουθίας με n_2> n_1

. Φυσικά ισχύει $a_{n_1} \le a_{n_2}$ . Όμοια ορίζουμε επαγωγικά n_1<n_2< n_3< ...

τέτοιους ώστε $a_{n_1} \le a_{n_2} \le a_{n_3}\le ...$ .

Κοιτάμε τώρα τους $b_{n_1}, b_{n_2}, b_{n_3}, ...$ στην θέση των a_n

, από όπου βρίσκουμε υπακολουθία $n_{k_m}$ της ακολουθίας με $b_{n_m}$ αύξουσα. Έτσι τώρα έχουμε άπειρους όρους για κάθε μία από τις a_n, b_n

που ικανοποιούν το ζητούμενο. Επαναλαμβάνουμε για την c_n

(με υπακολουθία της υπακολουθίας) και ούτω καθ' εξής.

Η διαδικασία αυτή δίνει και τις δύο γενικεύσεις του Αλέξανδρου: Άπειροι όροι σε μονοτονία και οσοδήποτε πεπερασμένο πλήθος ακολουθιών.

Φιλικά,

Μιχάλης

Υ.Γ. Το παραπάνω επιχείρημα είναι πανομοιότυπο με το επιχείρημα στην απόδειξη ότι ο $\mathbb R ^N$ έχει την ιδιότητα Bolzano-Weierstrass, όπου βρίσκουμε συγκλίνουσα υπακολουθία δοσμένης ακολουθίας N-άδων.

#4

AlexandrosG έγραψε:Γειά σου Δημήτρη.

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

Υπάρχει τρόπος χωρίς το Θεώρημα Ramsey?

Η πρώτη απόδειξη που έκανα ήταν ακριβώς αυτή. Καλά έκανες και το αναφέρεις μιας και το θεώρημα Ramsey είναι αρκετά ισχυρό σε τέτοιες περιπτώσεις.

Mihalis_Lambrou έγραψε: Υ.Γ. Το παραπάνω επιχείρημα είναι πανομοιότυπο με το επιχείρημα στην απόδειξη ότι ο $\mathbb R ^N$ έχει την ιδιότητα Bolzano-Weierstrass, όπου βρίσκουμε συγκλίνουσα υπακολουθία δοσμένης ακολουθίας N-άδων.

Και πανομοιότυπο με μια από τις αποδείξεις του άπειρου θεωρήματος Ramsey. Μάλιστα το θεώρημα Ramsey αποδεικνύει σχεδόν άμεσα το Bolzano-Weiertrass. (Καθόλου παράξενο αφού οι δυο αποδείξεις είναι αρκετά παρόμοιες.)

Π.χ. για N=1

, δεδομένης της άπειρης ακολουθίας (a_n)

, για

φυσικούς συνδέουμε τους i,j

με μια μπλε ακμή αν i < j

και με μια κόκκινη ακμή αν $i \geqslant j$ . Το θεώρημα Ramsey μας δίνει ένα άπειρο υποσύνολο

το $\mathbb{N}$ του οποίου όλες οι ακμές είναι του ιδίου χρώματος. Αυτό αντιστοιχεί σε μια άπειρη μονότονη υπακολουθία. Τα υπόλοιπα είναι γνωστά. Με παρόμοιο τρόπο δουλεύει η απόδειξη και για N > 1

μόνο που χρησιμοποιούμε 2^N

χρώματα.

Ακολουθίες ακεραίων

Ακολουθίες ακεραίων

Re: Ακολουθίες ακεραίων

Re: Ακολουθίες ακεραίων

Re: Ακολουθίες ακεραίων

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