mathematica.gr

Δημοσιεύτηκε: **Παρ Νοέμ 27, 2009 4:27 pm**

Για να μην πεθάνει το θέμα, δίνω τις λύσεις κάποιων ασκήσεων και βάζω καινούργιες.

Λύση Άσκησης 6: Χρωματίζουμε μια ακμή μπλε αν είναι η μεγαλύτερη ακμή κάποιο από τα τετράεδρα και κόκκινη αλλιώς. Αφού $R(4,4) \leqslant 18$ , είτε θα υπάρχει ένα τετράεδρο με όλες τις ακμές κόκκινες είτε θα υπάρχει ένα τετράεδτο με όλες τις ακμές μπλε. Το πρώτο είναι αδύνατο αφού κάθε τετράεδρο έχει τουλάχιστον μία μπλε ακμή. Άρα υπάρχει ένα τετράεδρο με όλες τις ακμές μπλε, δηλαδή κάθε ακμή του είναι η ακμή με το μεγαλύτερο μήκος ενός από τα τετράεδρα.

Δημοσιεύτηκε: **Παρ Νοέμ 27, 2009 5:00 pm**

Λύση Άσκησης 8α: Δίνεται ένας χρωματισμός των ακμών πλήρους γραφήματος σε $R(n_1-1,\ldots,n_k) + R(n_1,n_2-1,\ldots,n_k) + \cdots + R(n_1,\ldots,n_k-1) - k + 2$ κορυφές με

χρώματα. Πρέπει να δείξουμε ότι είτε υπάρχει ένα $K_{n_1}$ με όλες τις ακμές να έχουν χρώμα 1, είτε ... είτε υπάρχει ένα $K_{n_k}$ με όλες τις ακμές να έχουν χρώμα

. Κοιτάζουμε τις $\displaystyle{R(n_1-1,\ldots,n_k) + R(n_1,n_2-1,\ldots,n_k) + \cdots + R(n_1,\ldots,n_k-1) - k + 2 = }$ $\displaystyle{1 + \left(R(n_1-1,n_2,\ldots,n_k) - 1 \right) + \left(R(n_1,n_2-1,\ldots,n_k) - 1 \right) + \cdots + \left(R(n_1,n_2,\ldots,n_k-1) - 1 \right) }$ ακμές που προσπίπτουν σε μία κορυφή. Από την αρχή του περιστερώνα, είτε $R(n_1-1,n_2,\ldots,n_k)$ εξ' αυτών θα έχουν το χρώμα 1, είτε $R(n_1,n_2-1,\ldots,n_k)$ εξ' αυτών θα έχουν το χρώμα 2, είτε ... είτε $R(n_1,n_2,\ldots,n_k-1)$ εξ' αυτών θα έχουν το χρώμα

. Χωρίς βλάβη της γενικότητας $R(n_1-1,n_2,\ldots,n_k)$ εξ' αυτών έχουν το χρώμα 1. Αλλά το $K_{R(n_1-1,n_2,\ldots,n_k)}$ που σχηματίζεται είτε έχει ένα $K_{n_1-1}$ στο χρώμα 1 (που μαζί με την αρχική κορυφή δίνει ένα $K_{n_1}$ στο χρώμα 1), είτε ένα $K_{n_2}$ στο χρώμα 2 είτε ... είτε ένα $K_{n_k}$ στο χρώμα

.

(Αυτή η απόδειξη είναι η γενίκευση της απόδειξης του Ηλία ότι $R(3,3,3) \leqslant 17$ .)

Λύση Άσκησης 8β: Αν χρωματίσουμε με

χρώματα τις ακμές ενός πλήρους γραφήματος με $R(n_1,\ldots,n_{k-2},R(n_{k-1},n_k))$ , τότε (σκεφτόμαστε τα χρώματα k-1

και

σαν ένα χρώμα) είτε θα υπάρχει ένα μονοχρωματικό $Κ_{n_1}$ στο χρώμα 1, είτε ... είτε ένα μονοχρωματικό $Κ_{n_{k-2}}$ στο χρώμα k-2

είτε είτε ένα $K_{R(n_{k-1},n_k)}$ που οι ακμές του έχουν μόνο τα χρώματα k-1

και

. Στην τελευταία περίπτωση όμως, είτε υπάρχει ένα μονοχρωματικό $K_{n_{k-1}}$ στο χρώμα k-1

είτε μονοχρωματικό $K_{n_{k}}$ στο χρώμα

.

Η μέθοδος απόδειξης εδώ όπου αρχικά συγχέουμε δύο (ή περισσότερα) χρώματα εμφανίζεται αρκετά συχνά σε αποδείξεις στην θεωρία Ramsey.

Δημοσιεύτηκε: **Παρ Νοέμ 27, 2009 5:12 pm**

Μέχρι στιγμής νομίζω έχουν μείνει άλυτες οι 3α,3β και 7.

Άσκηση 9 (Θεώρημα Schur): Χρωματίζουμε τους θετικούς ακεραίους με

χρώματα. Να δειχθεί ότι υπάρχουν τρεις θετικοί ακέραιοι x,y,z

(όχι απαραίτητα διακεκριμένοι) οι οποίοι έχουν το ίδιο χρώμα και ικανοποιούν x+y=z

.

Δημοσιεύτηκε: **Σάβ Δεκ 05, 2009 12:58 pm**

Kαλημερα σε ολους.

3α)
Χωριζουμε το γραφημα σε ολες τις πιθανες εξαδες κορυφων οπου σε καθε μια θα περιεχεται τουλαχιστον ενα μονοχρωματικο τριγωνο και διαρουμε με το πληθος των πολλαπλομετρησεων καθενος.

3β)
τα διχρωματικα θα ειναι το πολυ $\frac{n}{2}\frac{(n-1)^2}{4}$

9)
Βαζουμε τους πρωτους

φυσικους οπου n=R(3,3,..,3)

σε ενα συνολο Μ. Τα

-αρια εχουν πληθος

.
Τωρα φτιαχνουμε ενα γραφημα

κορυφων οπου σε καθε μια αντιστοιχει μονοσημαντα ενας φυσικος απο το συνολο M.
Χρωματιζουμε καθε ακμη με χρωμα ιδιο με αυτο που εχει η κορυφη με τιμη την απολυτη διαφορα των αριθμων που αντιστοιχουν στις δυο ακμες.
Απο ramsey υπαρχει μονοχρωματικο τριγωνο απο οπου οι αριθμοι εστω |x-y|,|y-z|,|z-x|

εχουν το ιδιο χρωμα.
Tο ζητουμενο επεται.

Δημοσιεύτηκε: **Σάβ Δεκ 05, 2009 1:17 pm**

Μάκης Χατζόπουλος έγραψε:Βρήκα κάποιες σημειώσεις πάνω στην θεωρία του Ramsey, επειδή το αγνοούσα το θεώρημα και τις μοιράζομαι μαζί σας!! Αν έχετε σημειώσεις πάνω στο θέμα (κατατοπιστικές με θεωρία και λυμένες ασκήσεις) θα ήταν ευπρόσδεκτες!

To σχημα στο R(4,4) ειναι εκπληκτικο!

Δημοσιεύτηκε: **Σάβ Δεκ 05, 2009 7:57 pm**

Ilias_Zad έγραψε:Kαλημερα σε ολους.

3α)
Χωριζουμε το γραφημα σε ολες τις πιθανες εξαδες κορυφων οπου σε καθε μια θα περιεχεται τουλαχιστον ενα μονοχρωματικο τριγωνο και διαρουμε με το πληθος των πολλαπλομετρησεων καθενος.

3β)
τα διχρωματικα θα ειναι το πολυ $\frac{n}{2}\frac{(n-1)^2}{4}$

9)
Βαζουμε τους πρωτους φυσικους οπου σε ενα συνολο Μ. Τα -αρια εχουν πληθος .
Τωρα φτιαχνουμε ενα γραφημα κορυφων οπου σε καθε μια αντιστοιχει μονοσημαντα ενας φυσικος απο το συνολο M.
Χρωματιζουμε καθε ακμη με χρωμα ιδιο με αυτο που εχει η κορυφη με τιμη την απολυτη διαφορα των αριθμων που αντιστοιχουν στις δυο ακμες.
Απο ramsey υπαρχει μονοχρωματικο τριγωνο απο οπου οι αριθμοι εστω εχουν το ιδιο χρωμα.
Tο ζητουμενο επεται.

Σωστά. Βάζω λίγες περισσότερες λεπτομέρειες για τους υπόλοιπους μαθητές που μπορεί να παρακαλουθούν την συζήτηση.

Στο (3α) υπάρχουν ακριβώς $\binom{n}{6}$ πιθανες εξαδες κορυφων. Επειδή R(3,3) = 6

, κάθε τέτοια εξάδα περιέχει ένα μονοχρωματικό τρίγωνο. Κάθε τρίγωνο περιέχεται σε ακριβώς $\binom{n-3}{3}$ εξάδες άρα υπάρχουν τουλάχιστον $\binom{n}{6}/\binom{n-3}{3}$ μονοχρωματικά τρίγωνα.

Στο (3β) μετράμε τον αριθμό των διχρωματικών γωνιών. Κάθε διχρωματικό τρίγωνο έχει ακριβώς δύο τέτοιες γωνίες. Μια κορυφή με

μπλε και

κόκκινες ακμές έχει ακριβώς $ab \leqslant (a+b)^2/4 = (n-1)^2/4$ . Άρα υπάρχουν το πολύ n(n-1)^2/8

διχρωματικά τρίγωνα και άρα τουλάχιστον $\binom{n}{3} - n(n-1)^2/8 = n(n-1)(n-5)/24$ μονοχρωματικά τρίγωνα.

Δημοσιεύτηκε: **Σάβ Δεκ 05, 2009 9:05 pm**

Άσκηση 9β: Δείξτε ότι στο συμπέρασμα της άσκησης 9 μπορούμε να ζητήσουμε τα x,y,z

να είναι διακεκριμένοι

Άσκηση 10α: Δείξτε (χρησιμοποιώντας το θεώρημα Ramsey) ότι για κάθε θετικό ακέραιο

υπάρχει

ώστε κάθε ακολουθία

πραγματικών αριθμών περιέχει μια μονότονη υπακολουθία

αριθμών.

Άσκηση 10β Δείξτε (χωρίς την χρήση του θεωρήματος Ramsey) ότι στην άσκηση 10α μπορούμε να πάρουμε N = (n-1)^2+1

αλλά όχι

Δημοσιεύτηκε: **Δευ Δεκ 07, 2009 12:04 pm**

10α)
Παιρνουμε σαν N=R(n,n,n)

και αφου τοποθετησουμε σε αντιστοιχια κορυφες- ορους της ακολουθιας και χρωματισουμε καθε ακμη που συνδεει δυο κορυφες x_i,x_j

(

) ,με μπλε αν x_i>x_j

,με κοκκινο αν x_i<x_j

, και με πρασινο εαν x_i=x_j

εχουμε το ζητουμενο.

To 10β τo αφηνω επειδη το εχω ξαναδει.

Δημοσιεύτηκε: **Τρί Δεκ 08, 2009 12:58 pm**

Ilias_Zad έγραψε:10α)
Παιρνουμε σαν και αφου τοποθετησουμε σε αντιστοιχια κορυφες- ορους της ακολουθιας και χρωματισουμε καθε ακμη που συνδεει δυο κορυφες () ,με μπλε αν ,με κοκκινο αν , και με πρασινο εαν εχουμε το ζητουμενο.

Σωστά. Αυτή η απόδειξη δείχνει ακόμη περισσότερα από ότι ζήτησα. Δείχνει επίσης ότι θα υπάρχει υπακολουθία

αριθμών η οποία είτε θα είναι γνησίως μονότονη είτε σταθερή.

Δημοσιεύτηκε: **Τρί Δεκ 08, 2009 1:53 pm**

Χρωματίζοντας τριάδες (και βάλε)

Μέχρι στιγμής χρωματίζαμε τις ακμές ενος (πλήρους) γραφήματος. Με άλλα λόγια είχαμε ένα (πεπερασμένο) σύνολο

και χρωματίζαμε όλα τα ζευγη $\{x,y\}$ με $x \neq y$ και $x,y \in X$ .

Το θεώρημα Ramsey που αποδείξαμε μέχρι στιγμής λέει ότι για οποιοδήποτε σύνολο

με $|X| \geqslant R_k(n)$ , όπως και να χρωματίσουμε τα ζεύγη του

με

χρώματα, θα υπάρχει ένα μονοχρωματικό υποσύνολο

με

. (Εννοώντας ότι όλα τα ζεύγη του

έχουν το ίδιο χρώμα.)

Χρησιμοποιώντας την ίδια ορολογία, η αρχή του περιστερώνα λέει ότι για οποιοδήποτε σύνολο

με $|X| \geqslant k(n-1)+1$ , όπως και να χρωματίσουμε τα στοιχεία του

με

χρώματα, θα υπάρχει ένα μονοχρωματικό υποσύνολο

με

. (Εννοώντας ότι όλα τα στοιχεία του

έχουν το ίδιο χρώμα.)

Ας δούμε τώρα τι λέει το θεώρημα Ramsey για τις τριάδες:

Για κάθε k,n

υπάρχει ένας πεπερασμένος αριθμός $R_k^{(3)}(n)$ ώστε για οποιοδήποτε σύνολο

με $|X| \geqslant R_k^{(3)}(n)$ , όπως και να χρωματίσουμε τις τριάδες του

με

χρώματα, θα υπάρχει ένα μονοχρωματικό υποσύνολο

με

. (Εννοώντας ότι όλες οι τριάδες του

έχουν το ίδιο χρώμα.)

Στην απόδειξη του θεωρήματος Ramsey (για ζεύγη), χρησιμοποιήσαμε την αρχή του περιστερώνα. Στην απόδειξη του θεωρήματος Ramsey για τριάδες θα χρησιμοποιήσουμε το θεώρημα Ramsey για ζεύγη.

Υπόδειξη: Πάρτε ένα στοιχείο $x \in X$ και χρωματίστε τα ζεύγη του $X \setminus \{x\}$ ως εξής: Το ζέυγος $\{y,z\}$ θα πάρει το ίδιο χρώμα με το χρώμα που εχει η τριάδα $\{x,y,z\}$ .

Άσκηση 11 Για κάθε

υπάρχει

ώστε για κάθε σύνολο

σημείων στο επίπεδο που είναι ανα τρία μη συνευθειακά, υπάρχει είτε μια κυρτή είτε μια κοίλη καμπύλη που περνάει από τουλάχιστον

από αυτά.

Δημοσιεύτηκε: **Τρί Δεκ 29, 2009 9:03 pm**

Demetres έγραψε: Άσκηση 11 Για κάθε υπάρχει ώστε για κάθε σύνολο σημείων στο επίπεδο που είναι ανα τρία μη συνευθειακά, υπάρχει είτε μια κυρτή είτε μια κοίλη καμπύλη που περνάει από τουλάχιστον από αυτά.

Υπόδειξη: Χρωματίστε την τριάδα (x,y,z)

ως εξής: Μπορούμε να υποθέσουμε ότι x_1 < y_1 < z_1

. Αν $\frac{y_2-x_2}{y_1 - x_1} < \frac{z_2 - y_2}{z_1 - x_1}$ τότε χρωματίζουμε την τριάδα μπλε. Αλλιώς την χρωματίζουμε κόκκινη. Τι παρατηρείτε;

Δημοσιεύτηκε: **Τρί Δεκ 29, 2009 9:16 pm**

Μέχρι στιγμής έχουν μείνει αναπάντητα τα 7,9β,10β και 11. Βάζω κάποιες καινούργιες ασκήσεις με χρωματισμούς στο επίπεδο.

Άσκηση 12α: Να δειχθεί ότι όπως και να χρωματιστεί το επίπεδο με τρία χρώματα, υπάρχουν δυο σημεία με το ίδιο χρώμα που έχουν απόσταση 1.

Άσκηση 12β: Δείξτε ότι υπάρχει θετικός ακέραιος

και χρωματισμός του επιπέδου με

χρώματα ώστε κάθε δυο σημεία σε απόσταση 1 να έχουν διαφορετικό χρώμα.

Άσκηση 13α: Δείξτε ότι υπάρχει χρωματισμός του επιπέδου με δύο χρώματα ώστε κανένα ισόπλευρο τρίγωνο μήκους 1 να μην είναι μονοχρωματικό.

Άσκησε 13β: Δείξτε ότι όπως και να χρωματιστεί το επίπεδο με δύο χρώματα, είτε υπάρχει μονοχρωματικό ισόπλευρο τρίγωνο μήκους 1, είτε υπάρχει μονοχρωματικό ισόπλευρο τρίγωνο μήκους $\sqrt{3}$ .

Δημοσιεύτηκε: **Πέμ Δεκ 31, 2009 1:12 pm**

Θα απαντήσω για το 12α (που μάλλον είναι το πιο εύκολο-γνωστό) και θα επανέλθω για τα επόμενα!
Υποθέτουμε ότι δεν ισχύει το ζητούμενο. Εστω τα ισόπλευρα τρίγωνα ΑΒΓ, ΑΒΔ πλευράς ένα. Τότε τα Γ, Δ έχουν απόσταση $\sqrt{3}$ και απαραίτητα το ίδιο χρώμα (γιατί;)! Με τον τρόπο αυτό μπορούμε να δούμε ότι ο κύκλος με κέντρο το Γ και ακτίνα ρίζα 3 θα έχει (όλα τα σημεία του) το ίδιο χρώμα με το Γ. Συνεπώς θα υπάρχει μια χορδή μήκους 1, της οποίας τα άκρα θα έχουν το ίδιο χρώμα!

Δημοσιεύτηκε: **Τρί Ιαν 19, 2010 5:45 pm**

Λύση Άσκησης 11

Μπορούμε αρχικά να υποθέσουμε ότι κάθε ευθεία παράλληλη με τον άξονα των ψ περιέχει το πολύ ένα από τα σημεία. Αν όχι, επειδή ξέρουμε πως περιέχει το πολύ δύο από τα σημεία απλώς πετάμε έξω το ένα από αυτά και μένουμε με τουλάχιστον N/2

σημεία. Τώρα χρωματίζουμε τις τριάδες των σημείων ως εξής:

Για κάθε τριάδα (x,y,z) = ((x_1,x_2),(y_1,y_2),(z_1,z_2))

με

χρωματίζουμε την τριάδα μπλε αν $\displaystyle{\frac{y_2-x_2}{y_1 - x_1} < \frac{z_2 - y_2}{z_1 - y_1} }$ και κόκκινη αν $\displaystyle{\frac{y_2-x_2}{y_1 - x_1} > \frac{z_2 - y_2}{z_1 - y_1} }$ . Με άλλα λόγια την χρωματίζουμε κόκκινη αν και μόνο αν η κλίση της ευθείας που ενώνει τα

και

είναι μικρότερη από την κλίση της ευθείας που ενώνει τα

και

(Οι δυο ευθείες δεν έχουν την ίδια κλίση αφού τα σημεία είναι ανά τρία μη συνευθειακά.)

Από τα θεώρημα Ramsey για τριάδες, αν

αρκετά μεγάλο θα υπάρχουν

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

σημεία . Αν όλες οι τριάδες είναι κόκκινες η καμπύλη θα είναι κυρτή ενώ αν όλες οι τριάδες είναι μπλε η καμπύλη θα είναι κοίλη.

Δημοσιεύτηκε: **Τετ Μάιος 26, 2010 2:05 pm**

Επαναφέρω την συζήτηση με μια λύση. Έχουν μείνει αναπάντητα τα 9β,10β,12β,13α,13β.

Λύση Άσκησης 7: Έχουμε ήδη δείξει ότι R(3,4) = 9

και άρα $R(4,4) \leqslant R(3,4) + R(4,3) = 18$ . Μένει να δείξουμε ότι $R(4,4) \geqslant 18$ . Να δείξουμε δηλαδή ότι υπάρχει χρωματισμός των ακμών του $K_{17}$ με δυο χρώματα ώστε να μην υπάρχει μονοχρωματικό K_4

.

Για τον χρωματισμό αριθμούμε τις κορυφές από το 0 ως το 16 και χρωματίζουμε την ακμή μεταξύ των

και

μπλε αν και μόνο αν $x-y \in \{\pm 1,\pm 2, \pm 4, \pm 8\} \bmod 17$ .

Έστω ότι υπάρχει μπλε K_4

με κορυφές τα x,y,z,w

. Τότε θα υπάρχει μπλε K_4

με κορυφές τα 0,y-x,z-x,w-x

. Μπορούμε λοιπόν να υποθέσουμε ότι x = 0

και

. Άρα υπάρχει μπλε K_3

με κορυφές τα y,z,w

όπου $y,z,w \in \{1,2,4,8,9,13,15,16\}$ .

Αν y=1

τότε $z,w \in \{2,9,16\}$ . Όμως τότε $w-z \in\{7,14\}$ άτοπο.
Αν y=2

τότε

, άτοπο.
Αν y=4

τότε

, άτοπο.
Αν y=8

τότε

, άτοπο.
Αν $y \in \{9,13,15,16\}$ τότε υπάρχει το πολύ ένα

με

και

μπλε, άτοπο.

Άρα δεν υπάρχει μπλε K_4

. Με παρόμοιο τρόπο δείχνουμε πως δεν υπάρχει κόκκινο K_4

. (Διαφορετικά: Αν υπήρχε κόκκινο K_4

στις κορυφές a,b,c,d

τότε μπορεί να ελεγχθεί ότι θα υπήρχε μπλε K_4

στις κορυφές $3a,3b,3c,3d \bmod 17$ , άτοπο.)

Άρα R(4,4) = 18

.

Ανοικτό πρόβλημα: Να υπολογιστεί το R(5,5)

. Μέχρι στιγμής γνωρίζουμε (με βοήθεια και από υπολογιστές) πως $43 \leqslant R(5,5) \leqslant 49$ .

Δημοσιεύτηκε: **Σάβ Μάιος 29, 2010 12:56 pm**

Λύση Άσκησης 9β: Χρησιμοποιούμε την μέθοδο που χρησιμοποίησε ο Ηλίας για την άσκηση 9 μόνο που τώρα το γράφημα θα έχει $R(4,\cdots,4)$ κορυφές. (Με

τεσσάρια.)

Χρωματίζουμε τις ακμές με τον ίδιο τρόπο (η ακμή μεταξύ των

και

χρωματίζεται με το χρώμα του |x-y|.

Βρίσκουμε λοιπόν τέσσερις κορυφές έστω x,y,z,w

με όλες τις ακμές το ίδιο χρώμα. Έστω x > y > z > w

. Τότε τα

έχουν το ίδιο χρώμα.

Έχουμε (x-z) = (x-y) + (y-z)

και

. Επειδή $y-z \neq y-w$ είτε $x-y \neq y-z$ είτε $x-y \neq y-w$ . Και στις δυο περιπτώσεις το ζητούμενο έπεται.

Δημοσιεύτηκε: **Τρί Ιουν 01, 2010 12:01 pm**

Άσκηση 14: Να δειχθεί ότι για κάθε $n \geqslant 3$ υπάρχει

ώστε για κάθε

σημεία στο επίπεδο με $m \geqslant N$ , υπάρχουν

από αυτά που είναι κορυφές κυρτού πολυγώνου.

Δημοσιεύτηκε: **Πέμ Ιουν 10, 2010 10:51 pm**

Demetres έγραψε:Άσκηση 14: Να δειχθεί ότι για κάθε $n \geqslant 3$ υπάρχει ώστε για κάθε σημεία στο επίπεδο με $m \geqslant N$ , υπάρχουν από αυτά που είναι κορυφές κυρτού πολυγώνου.

Υπόδειξη: Δείξτε πρώτα ότι για κάθε 5 σημεία στο επίπεδο υπάρχουν 4 που ορίζουν κυρτό τετράπλευρο.

Δημοσιεύτηκε: **Παρ Ιαν 28, 2011 5:38 pm**

Επαναφορά θέματος.

Από την Δευτέρα θα αρχίσω να βάζω τις λύσεις στα αναπάντητα ερωτήματα. Ίσως μετά να προσθέσω και κάποια άλλα ερωτήματα. Αν δεν κάνω λάθος δεν έχουν απαντηθεί τα 10β,12β,13α,13β,14.

Δημοσιεύτηκε: **Δευ Ιαν 31, 2011 4:42 pm**

Λύση Άσκησης 10β:

Έστω μια ακολουθία $a_1,a_2,\ldots,a_{(n-1)^2 + 1}$ πραγματικών αριθμών. Θέλουμε να δείξουμε ότι υπάρχει μονότονη υπακολουθία

αριθμών.

Ας υποθέσουμε πως δεν ισχύει. Ορίζουμε μια συνάρτηση $f: \{1,2,\ldots,(n-1)^2+1\} \to \{1,\ldots,n-1\} \times \{1,2,\ldots,n-1\}$ ως εξής: f(k) = (s_k,t_k)

, όπου

είναι το μεγαλύτερο μήκος φθίνουσας ακολουθίας που ξεκινάει από το a_k

και

το μεγαλύτερο μήκος αύξουσας ακολουθίας που ξεκινάει από το a_k

. Τότε η

δεν μπορεί να είναι 1-1. Έστω λοιπόν $k < \ell$ ώστε $f(k) = f(\ell)$ . Αυτό όμως είναι άτοπο αφού αν $a_k \leqslant a_{\ell}$ τότε $t_k > t_{\ell}$ ενώ αν $a_k > a_{\ell}$ τότε $s_k > s_{\ell}$ .

Περισσότερες αποδείξεις μπορείτε να δείτε στο άρθρο "Variations on the Monotone Subsequence Problem of Erdös and Szekeres" του M. J. Steele. (Μπορείτε να το κατεβάσετε από την σελίδα του συγγραφέα εδώ.)

Τέλος η άσκηση ζητάει να βρεθεί ακολουθία (n-1)^2

όρων η οποία να μην περιέχει μια μονότονη ακολουθία

όρων. Μια τέτοια ακολουθία είναι η εξής

$\displaystyle{ \begin{pmatrix} n-1 & n-2 & \cdots & 1 \\ 2(n-1) & 2(n-1) - 1 & \cdots & 2(n-1) - (n-2) \\ \vdots & \vdots & \vdots & \vdots \\ k(n-1) & k(n-1) - 1 & \cdots & k(n-1) - (n-2) \\ \vdots & \vdots & \vdots & \vdots \\ (n-1)^2 & (n-1)^2 - 1 & \cdots & \(n-1)^2 - (n-2)\end{pmatrix}}$

όπου η ακολουθία διαβάζεται από αριστερά προς τα δεξιά και μετά από πάνω προς τα κάτω.

mathematica.gr

Θεωρία Ramsey---------------->Bulletin(1/?)

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey

Re: Θεωρία Ramsey---------------->Bulletin(1/?)

Re: Θεωρία Ramsey---------------->Bulletin(1/?)