Σημεία και ευθείες. Για φοιτητές με ταπεραμέντο!

[Μάκης Χατζόπουλος]

Ομοίως και αυτή η άσκηση περιέχεται στην ίδια πηγή με την προηγούμενη άσκηση που έθεσα...

Άσκηση 2η
Δίδεται ένα πεπερασμένο σύνολο σημείων στο επίπεδο που δεν είναι όλα συνευθειακά. Δείξτε ότι υπάρχει μια ευθεία που περιέχει ακριβώς δύο από τα σημεία αυτά.

[dxdy]

To πρόβλημα αυτό είχε τεθεί απο τον Sylvester οπως διαβαζουμε στο σημείωμα που ακολουθεί.Δεν γνωρίζω εαν είχε δώσει και λύση ο ιδιος.

[Μάκης Χατζόπουλος]

Υπόδειξη:

Από όλα τα δυνατά ζεύγη (Ε, Α), όπου

* Ε ευθεία που ορίζεται από το δεδομένο σύνολο σημείων και
* Α ένα από τα σημεία μας που δεν ανήκει στην ευθεία Ε,

επιλέξτε να δουλέψετε με εκείνο το ζευγάρι που ελαχιστοποιεί την απόσταση του Α από την Ε.

[Σεραφείμ]

Πολύ χρήσιμη υπόδειξη !!!

[Μάκης Χατζόπουλος]

Καταπληκτικός, όπως πάντα !

Σεραφείμ δεν σε πέτυχα Γιάννενα που ήμουν την προηγούμενη εβδομάδα, αλλά τα είπαμε με τον Γρηγόρη που δεν είχαμε γνωριστεί από κοντά!

[Demetres]

Στο συνημμένο του dxdy μιλάει για μια απόδειξη του Kelly η οποία «ίσως να είναι η καλύτερη». Αυτή είναι ακριβώς η απόδειξη του Σεραφείμ μετά την υπόδειξη του Μάκη.

[dimitris pap]

Πολύ ωραίο πρόβλημα με εξίσου όμορφη λύση!
Θέλω να κάνω μια εικασία πάνω στο πρόβλημα:

Οταν έχουμε σημεία μπορούμε πάντα να βρούμε τουλάχιστον ευθείες που να διέρχονται ακριβώς από 2 σημεία έκαστη.
(κάτι δηλαδή πολύ ισχυρότερο απ' το πρόβλημα που τέθηκε)

Ελπίζω να βρούμε κάποια απόδειξη ή αντιπαράδειγμα

[Dreamkiller]

Πολύ όμορφο Δημήτρη!
Η απόδειξή μου είναι επαγωγική. Ονομάζουμε μια ευθεία που διέρχεται από ακριβώς δύο σημεία καλή.
Παρατηρούμε ότι για ισχύει τετριμμένα.
Υποθέτοντας ότι ισχύει για θα αποδείξω ότι ισχύει και για , ότι δηλαδή μη συνευθειακά σημεία ορίζουν τουλάχιστον καλές ευθείες. Έστω, λοιπόν, ότι έχουμε τα σημεία . Aν από αυτά είναι συνευθειακά, έστω τα με τότε οι ευθείες είναι οι ζητούμενες. Διαφορετικά, από το αρχικό πρόβλημα (το θεώρημα Sylvester - Gallai) υπάρχει μέσα στα σημεία μία καλή ευθεία, έστω η ενώ από την επαγωγική υπόθεση τα σημεία σχηματίζουν τουλάχιστον καλές ευθείες. Συνολικά, έχουμε καλές ευθείες και η απόδειξη τέλειωσε.

EDIT: Τελικά έλυσα άλλο πρόβλημα αλλά τουλάχιστον το έλυσα όπως ο Erdős.
Το άρθρο που αναφέρει ο Δημήτρης βρίσκεται εδώ.

[Demetres]

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

Υπάρχει πρόβλημα σε αυτό το σημείο. Οι «καλές ευθείες» για τα σημεία μπορεί να μην είναι καλές για τα σημεία αφού ίσως το σημείο να ανήκει σε αυτές τις ευθείες.

Ήμουν σίγουρος ότι η απάντηση ήταν θετική και ότι κάπου το είχα ξαναδεί. Έψαξα στο άρθρο

N. G. de Bruijn and P. Erdös, On a combinatorial problem, Nederl. Akad. Wetensch., Proc. 51, (1948) 1277--1279.

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

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

Αφού έψαξα στην βιβλιογραφία ακόμη λίγο βρήκα τα εξής:

O Motzkin (Th. Motzkin, The lines and planes connecting the points of afinite set, Trans. Amer. Math. Soc, 70 (1951), 451-464.) έδειξε ότι .

Οι Kelly και Moser (L. M. Kelly and W. O. J. Moser, On the number of ordinary lines determined by points, Canad. J. Math. 1 (1958), 210--219.) έδειξαν ότι . Επίσης έδειξαν ότι για αυτό είναι το καλύτερο δυνατόν. (Δηλαδή η εικασία δεν ισχύει. Το αντιπαράδειγμα είναι τρία σημεία που ορίζουν ένα ισόπλευρο τρίγωνο μαζί με το βαρύκεντρο και τα μέσα των τριών πλευρών. Εικάζουν όμως ότι για αρκετά μεγάλα . Έκαναν επίσης και την πιο ασθενή εικασία ότι για αρκετά μεγάλα . Νομίζω ότι μέχρι στιγμής το καλύτερο φράγμα που έχει βρεθεί είναι για αλλά δεν το έχω ψάξει αρκετά.

[dimitris pap]

Ευχαριστώ πολύ για την ενασχόληση με την εικασία που έθεσα και κυρίως με την αναφορά σε διάφορες βιβλιογραφικές πηγές!
(έχει πλάκα γιατί είχα ψάξει να δω αν η εικασία ισχύει για μέχρι 6 σημεία και το αντιπαράδειγμα βρίσκεται απ' τα 7 )

[Demetres]

Έκανα σήμερα λίγο περισσότερο ψάξιμο. Το καλύτερο κάτω φράγμα μέχρι στιγμής είναι το για :

J. Csima and E. T. Sawyer, There exist ordinary points, Discrete Comput. Geom. 9 (1993), 187-202.

Για , έχει αποδειχθεί από τον Boroczky ότι . Η κατασκευή του εμφανίστηκε για πρώτη φορά στο

D. W. Crowe and T. A. McKee, Sylvester's problem on collinear points, Math. Mag. 41 (1968), 30--34.

Έχει επίσης δώσει κατασκευές που δείχνουν ότι και (για .

(Η εικασία για μεγάλα είναι λοιπόν λανθασμένη, ενώ η εικασία για από ότι αντιλαμβάνομαι παραμένει ανοικτή.)

Τέλος να προσθέσω την παρακάτω γενική επισκόπηση του προβλήματος η οποία έχει και αρκετές παραπομπές σε σχετικά άρθρα.

P. Borwein and W. O. J. Moser, A survey of Sylvester's problem and its generalizations, Aequationes Math. 40 (1990), 111-135.