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

Από testwiki
Μετάβαση στην πλοήγηση Πήδηση στην αναζήτηση
Το πρόβλημα με το αίσιο τέλος: κάθε σύνολο πέντε σημείων σε γενική θέση περιέχει τις κορυφές ενός κυρτού τετραπλεύρου

Το αρχικό πρόβλημα, το οποίο θα μπορούσε να μεταφραστεί ως το πρόβλημα με το αίσιο τέλος (αγγλικά: Happy ending problem), ονομάστηκε έτσι από τον Πολ Έρντος επειδή οδήγησε τελικά σε γάμο τους δύο εμπλεκόμενους ερευνητές, τον Τζορτζ Σέκερες και την Έστερ Κλάιν [1]. Η δήλωση έχει ως εξής: 

Θεώρημα - κάθε σύνολο πέντε σημείων στο επίπεδο σε γενική θέση[2] έχει ένα υποσύνολο τεσσάρων σημείων που σχηματίζουν τις κορυφές ενός κυρτού τετραπλεύρου.

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

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

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

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

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

f(N)=1+2N−2for all N≥3.

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

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

Οι Έρντος & Σέκερες (Πρότυπο:Harvtxt) απέδειξαν την ακόλουθη γενίκευση: 

Θεώρημα - για κάθε θετικό ακέραιο Πρότυπο:Mvar, κάθε αρκετά μεγάλο πεπερασμένο σύνολο σημείων στο επίπεδο σε γενική θέση έχει ένα υποσύνολο Πρότυπο:Mvar σημείων που σχηματίζουν τις κορυφές ενός κυρτού πολυγώνου.

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

Έστω Πρότυπο:Math το ελάχιστο Πρότυπο:Mvar για το οποίο κάθε σύνολο Πρότυπο:Mvar σημείων σε γενική θέση πρέπει να περιέχει ένα κυρτό N-gon. Είναι γνωστό ότι

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

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

f(N)=1+2N−2for all N≥3. Αργότερα απέδειξαν, κατασκευάζοντας ρητά παραδείγματα, ότι [6] f(N)≥1+2N−2.

Το 2016 ο Άντριου Σουκ[7] έδειξε ότι για Πρότυπο:Math f(N)≤2N+o(N).

Ο Σουκ αποδεικνύει στην πραγματικότητα, για N αρκετά μεγάλο, f(N)≤2N+6N2/3logN.

Αυτό βελτιώθηκε στη συνέχεια σε:Πρότυπο:Sfnp f(N)≤2N+O(NlogN).

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

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

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

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

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

Είναι απλό να δείξουμε ότι, σε ευκλείδειους χώρους υψηλότερων διαστάσεων, αρκετά μεγάλα σύνολα σημείων θα έχουν ένα υποσύνολο k σημείων που θα σχηματίζει τις κορυφές ενός κυρτού πολυτόπου, για οποιοδήποτε k μεγαλύτερο από τη διάσταση: αυτό προκύπτει άμεσα από την ύπαρξη κυρτών Πρότυπο:Nowrap σε αρκετά μεγάλα επίπεδα σύνολα σημείων, προβάλλοντας το σύνολο σημείων υψηλότερων διαστάσεων σε έναν αυθαίρετο δισδιάστατο υποχώρο. Ωστόσο, ο αριθμός των σημείων που είναι απαραίτητος για να βρεθούν k σημεία σε κυρτή θέση μπορεί να είναι μικρότερος σε υψηλότερες διαστάσεις απ' ό,τι είναι στο επίπεδο, και είναι δυνατόν να βρεθούν υποσύνολα που είναι περισσότερο περιορισμένα. Συγκεκριμένα, σε d διαστάσεις, κάθε d + 3 σημεία σε γενική θέση έχουν ένα υποσύνολο d + 2 σημείων που αποτελούν τις κορυφές ενός κυκλικού πολυτόπου.[12] Γενικότερα, για κάθε d και k > d υπάρχει ένας αριθμός m(d, k) τέτοιος ώστε κάθε σύνολο m(d, k) σημείων σε γενική θέση να έχει ένα υποσύνολο k σημείων που σχηματίζουν τις κορυφές ενός γειτονικού πολυτόπου.[13]

Εξωτερικοί σύνδεσμοι

Δείτε επίσης

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

Παραπομπές

Πρότυπο:Reflist Πρότυπο:Refbegin

Πρότυπο:Refend

Πηγές

Πρότυπο:Portal bar Πρότυπο:Authority control

  1. ↑ A world of teaching and numbers - times two, Michael Cowling, The Sydney Morning Herald, 2005-11-07, cited 2014-09-04
  2. ↑ In this context, general position means that no two points coincide and no three points are collinear.
  3. ↑ This was the original problem, proved by Esther Klein.
  4. ↑ According to Πρότυπο:Harvtxt, this was first proved by E. Makai; the first published proof appeared in Πρότυπο:Harvtxt.
  5. ↑ This has been proved by Πρότυπο:Harvtxt. 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.
  6. ↑ Πρότυπο:Harvtxt
  7. ↑ Πρότυπο:Harvtxt. See binomial coefficient and big O notation for notation used here and Catalan numbers or Stirling's approximation for the asymptotic expansion.
  8. ↑ Πρότυπο:Harvtxt.
  9. ↑ Πρότυπο:Harvtxt
  10. ↑ Πρότυπο:Harvtxt.
  11. ↑ Πρότυπο:Harvtxt
  12. ↑ Πρότυπο:Harvtxt, Ex. 6.5.6, p.120. Grünbaum attributes this result to a private communication of Micha A. Perles.
  13. ↑ Πρότυπο:Harvtxt, 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.
Ανακτήθηκε από «https://el.wiki.beta.math.wmflabs.org/w/index.php?title=Πρόβλημα_με_το_αίσιο_τέλος&oldid=3079»