Πρόβλημα με το αίσιο τέλος

Το αρχικό πρόβλημα, το οποίο θα μπορούσε να μεταφραστεί ως το πρόβλημα με το αίσιο τέλος (αγγλικά: Happy ending problem), ονομάστηκε έτσι από τον Πολ Έρντος επειδή οδήγησε τελικά σε γάμο τους δύο εμπλεκόμενους ερευνητές, τον Τζορτζ Σέκερες και την Έστερ Κλάιν A world of teaching and numbers - times two, Michael Cowling, The Sydney Morning Herald, 2005-11-07, cited 2014-09-04. Η δήλωση έχει ως εξής: 

 Θεώρημα - κάθε σύνολο πέντε σημείων στο επίπεδο σε γενική θέσηIn this context, general position means that no two points coincide and no three points are collinear. έχει ένα υποσύνολο τεσσάρων σημείων που σχηματίζουν τις κορυφές ενός κυρτού τετραπλεύρου.

Αυτό ήταν ένα από τα αρχικά αποτελέσματα που οδήγησαν στην ανάπτυξη της θεωρίας Ράμσεϊ.

Το θεώρημα πρόβλημα με το αίσιο τέλος μπορεί να αποδειχθεί με μια απλή ανάλυση περιπτώσεων: αν τέσσερα ή περισσότερα σημεία είναι κορυφές του κυρτού περιβλήματος, μπορούν να επιλεγούν οποιαδήποτε τέσσερα τέτοια σημεία. Αν, από την άλλη πλευρά, το κυρτό περίβλημα έχει τη μορφή τριγώνου με δύο σημεία στο εσωτερικό του, μπορούν να επιλεγούν τα δύο εσωτερικά σημεία και μία από τις πλευρές του τριγώνου. Βλ. Πέτερσον () για μια εικονογραφημένη εξήγηση αυτής της απόδειξης και Μόρις & Σόλταν () για μια λεπτομερέστερη επισκόπηση του προβλήματος.

Η εικασία Ερντος-Σζεκέρες δηλώνει ακριβώς μια πιο γενική σχέση μεταξύ του αριθμού των σημείων σε ένα σύνολο σημείων γενικής θέσης και του μεγαλύτερου υποσυνόλου του που σχηματίζει ένα κυρτό πολύγωνο, δηλαδή ότι ο μικρότερος αριθμός σημείων για τον οποίο οποιαδήποτε διάταξη γενικής θέσης περιέχει ένα κυρτό υποσύνολο  σημείων είναι . Παραμένει αναπόδεικτο, αλλά είναι γνωστά λιγότερο ακριβή όρια.

Με βάση τις γνωστές τιμές του  για N = 3, 4 και 5, οι Ερντος και Σζεκέρες υπέθεσαν στην αρχική τους εργασία ότι 

alt=Σύνολο δεκαέξι σημείων σε γενική θέση χωρίς κυρτό εξάγωνο|thumb|Σύνολο δεκαέξι σημείων σε γενική θέση χωρίς κυρτό εξάγωνο

Μεγαλύτερα πολύγωνα

Οι Έρντος & Σέκερες () απέδειξαν την ακόλουθη γενίκευση:  
 Θεώρημα - για κάθε θετικό ακέραιο , κάθε αρκετά μεγάλο πεπερασμένο σύνολο σημείων στο επίπεδο σε γενική θέση έχει ένα υποσύνολο  σημείων που σχηματίζουν τις κορυφές ενός κυρτού πολυγώνου.

Η απόδειξη εμφανίστηκε στην ίδια εργασία που αποδεικνύει το θεώρημα Ερντος και Ζέκερες για τις μονοτονικές υποακολουθίες σε ακολουθίες αριθμών.

Έστω  το ελάχιστο  για το οποίο κάθε σύνολο  σημείων σε γενική θέση πρέπει να περιέχει ένα κυρτό N-gon. Είναι γνωστό ότι 
 , τετριμμένα.
 .This was the original problem, proved by Esther Klein.
 .According to , this was first proved by E. Makai; the first published proof appeared in . Ένα σύνολο οκτώ σημείων χωρίς κυρτό πεντάγωνο φαίνεται στην εικόνα, αποδεικνύοντας ότι - το πιο δύσκολο μέρος της απόδειξης είναι να δείξουμε ότι κάθε σύνολο εννέα σημείων σε γενική θέση περιέχει τις κορυφές ενός κυρτού πενταγώνου.
 .This has been proved by . They carried out a computer search which eliminated all possible configurations of 17 points without convex hexagons while examining only a tiny fraction of all configurations.
 Η τιμή της  είναι άγνωστη για όλα τα . Σύμφωνα με το αποτέλεσμα των Ερντος και Ζέκερες  , η  είναι γνωστό ότι είναι πεπερασμένη για όλα τα πεπερασμένα .

Με βάση τις γνωστές τιμές του  για N = 3, 4 και 5, οι Ερντος και Σέκερης υπέθεσαν στην αρχική τους εργασία ότι 
alt=Σύνολο δεκαέξι σημείων σε γενική θέση χωρίς κυρτό εξάγωνο|thumb|Σύνολο δεκαέξι σημείων σε γενική θέση χωρίς κυρτό εξάγωνο

Αργότερα απέδειξαν, κατασκευάζοντας ρητά παραδείγματα, ότι 

Το 2016 ο Άντριου Σουκ. See binomial coefficient and big O notation for notation used here and Catalan numbers or Stirling's approximation for the asymptotic expansion. έδειξε ότι για 

Ο Σουκ αποδεικνύει στην πραγματικότητα, για N αρκετά μεγάλο,  

Αυτό βελτιώθηκε στη συνέχεια σε:

Κενά κυρτά πολύγωνα

Υπάρχει επίσης το ερώτημα αν οποιοδήποτε αρκετά μεγάλο σύνολο σημείων σε γενική θέση έχει ένα "κενό" κυρτό τετράπλευρο, πεντάγωνο κ.λπ., δηλαδή ένα που δεν περιέχει κανένα άλλο σημείο εισόδου. Η αρχική λύση του προβλήματος με το αίσιο τέλος μπορεί να προσαρμοστεί για να δείξει ότι οποιαδήποτε πέντε σημεία σε γενική θέση έχουν ένα κενό κυρτό τετράπλευρο, όπως φαίνεται στην εικόνα, και οποιαδήποτε δέκα σημεία σε γενική θέση έχουν ένα κενό κυρτό πεντάγωνο.. Ωστόσο, υπάρχουν αυθαίρετα μεγάλα σύνολα σημείων σε γενική θέση που δεν περιέχουν κανένα κενό κυρτό επτάγωνο.

Για μεγάλο χρονικό διάστημα το ερώτημα της ύπαρξης κενών εξαγώνων παρέμενε ανοιχτό, αλλά οι Νικολάς () και Γκέρκεν () απέδειξαν ότι κάθε επαρκώς μεγάλο σύνολο σημείων σε γενική θέση περιέχει ένα κυρτό κενό εξάγωνο. Πιο συγκεκριμένα, ο Γκέρκεν έδειξε ότι ο αριθμός των σημείων που απαιτούνται δεν υπερβαίνει το f(9)  για την ίδια συνάρτηση f που ορίστηκε παραπάνω, ενώ ο Νικολάς έδειξε ότι ο αριθμός των σημείων που απαιτούνται δεν υπερβαίνει το f(25). Ο Βαλτρ () παρέχει μια απλοποίηση της απόδειξης του Γκέρκεν που απαιτεί ωστόσο περισσότερα σημεία, f(15). αντί για f(9). Απαιτούνται τουλάχιστον 30 σημεία- υπάρχει ένα σύνολο 29 σημείων σε γενική θέση χωρίς κενό κυρτό εξάγωνο.. Το ερώτημα απαντήθηκε τελικά από τους Χόιουλ & Σέουχερ (), οι οποίοι έδειξαν, χρησιμοποιώντας μια προσέγγιση επίλυσης SAT, ότι πράγματι κάθε σύνολο 30 σημείων σε γενική θέση περιέχει κενό εξάγων.

Σχετικά προβλήματα

Το πρόβλημα της εύρεσης συνόλων n σημείων που ελαχιστοποιούν τον αριθμό των κυρτών τετραπλεύρων είναι ισοδύναμο με την ελαχιστοποίηση του αριθμού των διασταυρώσεων σε μια ευθεία γραμμή ενός πλήρους γραφήματος. Ο αριθμός των τετραπλεύρων πρέπει να είναι ανάλογος της τέταρτης δύναμης του n, αλλά η ακριβής σταθερά δεν είναι γνωστή.

Είναι απλό να δείξουμε ότι, σε ευκλείδειους χώρους υψηλότερων διαστάσεων, αρκετά μεγάλα σύνολα σημείων θα έχουν ένα υποσύνολο k σημείων που θα σχηματίζει τις κορυφές ενός κυρτού πολυτόπου, για οποιοδήποτε k μεγαλύτερο από τη διάσταση: αυτό προκύπτει άμεσα από την ύπαρξη κυρτών  σε αρκετά μεγάλα επίπεδα σύνολα σημείων, προβάλλοντας το σύνολο σημείων υψηλότερων διαστάσεων σε έναν αυθαίρετο δισδιάστατο υποχώρο. Ωστόσο, ο αριθμός των σημείων που είναι απαραίτητος για να βρεθούν k σημεία σε κυρτή θέση μπορεί να είναι μικρότερος σε υψηλότερες διαστάσεις απ' ό,τι είναι στο επίπεδο, και είναι δυνατόν να βρεθούν υποσύνολα που είναι περισσότερο περιορισμένα. Συγκεκριμένα, σε d διαστάσεις, κάθε d + 3 σημεία σε γενική θέση έχουν ένα υποσύνολο d + 2 σημείων που αποτελούν τις κορυφές ενός κυκλικού πολυτόπου., Ex. 6.5.6, p.120. Grünbaum attributes this result to a private communication of Micha A. Perles. Γενικότερα, για κάθε d και k > d υπάρχει ένας αριθμός m(d, k) τέτοιος ώστε κάθε σύνολο m(d, k) σημείων σε γενική θέση να έχει ένα υποσύνολο k σημείων που σχηματίζουν τις κορυφές ενός γειτονικού πολυτόπου., Ex. 7.3.6, p. 126. This result follows by applying a Ramsey-theoretic argument similar to Szekeres's original proof together with Perles's result on the case k = d + 2.

 Εξωτερικοί σύνδεσμοι 
English - Greek Dictionary of Pure and Applied Mathematics Εθνικό Μετσόβιο Πολυτεχνείο
Αγγλοελληνικό Λεξικό Μαθηματικής Ορολογίας - Πανεπιστήμιο Κύπρου
 Ευκλείδεια Γεωμετρία - Πανελλήνιο Σχολικό Δίκτυο
 Θεωρία ομάδων και Λι αλγεβρών -Εθνικό Αρχείο Διδακτορικών Διατριβών
 Θεωρία Αριθμών και Εφαρμογές
 Υπολογιστική Θεωρία Αριθμών

 Δείτε επίσης 
 Θεωρία αριθμών
 Αλγεβρική θεωρία αριθμών
 Φυσικός λογάριθμος
 Δεύτερη Εικασία Χάρντι-Λίτλγουντ
 Κυκλοτομικό σώμα
 e (μαθηματική σταθερά)
 Πυθαγόρεια τετράδα
 Άρτιοι και περιττοί αριθμοί
 Δίδυμοι πρώτοι αριθμοί
 Γενικευμένη υπόθεση Ρίμαν
 Προβλήματα του Λαντάου
 Αριθμοί των Ταξί
 Εικασία του Γκόλντμπαχ
 Θεμελιώδες θεώρημα αριθμητικής
 Αλγεβρική γεωμετρία
 Υπόθεση H του Σίνζελ
 Συνάρτηση Όιλερ
 Ευκλείδειος χώρος

 Βιβλιογραφία












 Παραπομπές 

; reprinted in 

 Πηγές 








Κατηγορία:Διοφαντικές εξισώσεις
Κατηγορία:Περιοχές των μαθηματικών
Κατηγορία:Θεωρία αριθμών
Κατηγορία:Εικασίες
Κατηγορία:Άλυτα προβλήματα στα μαθηματικά