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

Συντονιστές: grigkost, Κοτρώνης Αναστάσιος

Άβαταρ μέλους
Μάκης Χατζόπουλος
Δημοσιεύσεις: 2456
Εγγραφή: Δευ Δεκ 22, 2008 4:13 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

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

#1

Μη αναγνωσμένη δημοσίευση από Μάκης Χατζόπουλος » Σάβ Αύγ 21, 2010 11:35 pm

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

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


(1) verba volant, scripta manent = τα λόγια πετούν, τα γραπτά μένουν
Εικόνα

Λέξεις Κλειδιά:
dxdy
Δημοσιεύσεις: 53
Εγγραφή: Κυρ Ιουν 13, 2010 10:20 am
Τοποθεσία: Θεσσαλονίκη

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

#2

Μη αναγνωσμένη δημοσίευση από dxdy » Κυρ Αύγ 22, 2010 10:53 am

To πρόβλημα αυτό είχε τεθεί απο τον Sylvester οπως διαβαζουμε στο σημείωμα που ακολουθεί.Δεν γνωρίζω εαν είχε δώσει και λύση ο ιδιος.
Συνημμένα
sylvester.png
sylvester.png (100.98 KiB) Προβλήθηκε 773 φορές


Άβαταρ μέλους
Μάκης Χατζόπουλος
Δημοσιεύσεις: 2456
Εγγραφή: Δευ Δεκ 22, 2008 4:13 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

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

#3

Μη αναγνωσμένη δημοσίευση από Μάκης Χατζόπουλος » Κυρ Αύγ 22, 2010 6:13 pm

Υπόδειξη:

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

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

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


(1) verba volant, scripta manent = τα λόγια πετούν, τα γραπτά μένουν
Εικόνα
Άβαταρ μέλους
Σεραφείμ
Επιμελητής
Δημοσιεύσεις: 1872
Εγγραφή: Τετ Μάιος 20, 2009 9:14 am
Τοποθεσία: Θεσσαλονίκη - Γιάννενα

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

#4

Μη αναγνωσμένη δημοσίευση από Σεραφείμ » Κυρ Αύγ 22, 2010 7:12 pm

:clap2: :clap2: Πολύ χρήσιμη υπόδειξη !!!
Συνημμένα
Line2Points.jpg
Line2Points.jpg (125.88 KiB) Προβλήθηκε 713 φορές


Σεραφείμ Τσιπέλης
Άβαταρ μέλους
Μάκης Χατζόπουλος
Δημοσιεύσεις: 2456
Εγγραφή: Δευ Δεκ 22, 2008 4:13 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

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

#5

Μη αναγνωσμένη δημοσίευση από Μάκης Χατζόπουλος » Κυρ Αύγ 22, 2010 7:36 pm

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

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


(1) verba volant, scripta manent = τα λόγια πετούν, τα γραπτά μένουν
Εικόνα
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8444
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#6

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Αύγ 23, 2010 10:27 am

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


dimitris pap
Δημοσιεύσεις: 287
Εγγραφή: Παρ Ιαν 23, 2009 3:42 pm

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

#7

Μη αναγνωσμένη δημοσίευση από dimitris pap » Τετ Αύγ 25, 2010 12:48 pm

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

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

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


Dreamkiller
Δημοσιεύσεις: 263
Εγγραφή: Τρί Δεκ 23, 2008 12:52 pm

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

#8

Μη αναγνωσμένη δημοσίευση από Dreamkiller » Τετ Αύγ 25, 2010 4:47 pm

Πολύ όμορφο Δημήτρη!
Η απόδειξή μου είναι επαγωγική. Ονομάζουμε μια ευθεία που διέρχεται από ακριβώς δύο σημεία καλή.
Παρατηρούμε ότι για k=2 ισχύει τετριμμένα.
Υποθέτοντας ότι ισχύει για k=n θα αποδείξω ότι ισχύει και για k=n+1, ότι δηλαδή n+1 μη συνευθειακά σημεία ορίζουν τουλάχιστον n καλές ευθείες. Έστω, λοιπόν, ότι έχουμε τα σημεία A_1, A_2, ..., A_{n+1}. Aν n από αυτά είναι συνευθειακά, έστω τα A_i με 1 \leq i \leq n τότε οι ευθείες A_iA_{n+1} είναι οι ζητούμενες. Διαφορετικά, από το αρχικό πρόβλημα (το θεώρημα Sylvester - Gallai) υπάρχει μέσα στα n+1 σημεία μία καλή ευθεία, έστω η A_1A_{n+1} ενώ από την επαγωγική υπόθεση τα σημεία A_1, A_2, ..., A_n σχηματίζουν τουλάχιστον n-1 καλές ευθείες. Συνολικά, έχουμε n καλές ευθείες και η απόδειξη τέλειωσε.

EDIT: Τελικά έλυσα άλλο πρόβλημα αλλά τουλάχιστον το έλυσα όπως ο Erdős. :lol:
Το άρθρο που αναφέρει ο Δημήτρης βρίσκεται εδώ.
τελευταία επεξεργασία από Dreamkiller σε Τετ Αύγ 25, 2010 5:27 pm, έχει επεξεργασθεί 1 φορά συνολικά.


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8444
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#9

Μη αναγνωσμένη δημοσίευση από Demetres » Τετ Αύγ 25, 2010 5:14 pm

Dreamkiller έγραψε: ενώ από την επαγωγική υπόθεση τα σημεία A_1, A_2, ..., A_n σχηματίζουν τουλάχιστον n-1 καλές ευθείες. Συνολικά, έχουμε n καλές ευθείες και η απόδειξη τέλειωσε.
Υπάρχει πρόβλημα σε αυτό το σημείο. Οι «καλές ευθείες» για τα σημεία A_1,\ldots,A_n μπορεί να μην είναι καλές για τα σημεία A_1,\ldots,A_{n+1} αφού ίσως το σημείο A_{n+1} να ανήκει σε αυτές τις ευθείες.

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

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

που θυμόμουν ότι το είχα δει. Τελικά εκεί είχε την εξής ερώτηση που δείχνει την δυσκολία του προβλήματος
Γράφουμε f(n) για τον ελάχιστο αριθμό ευθειών οι οποίες διέρχονται από ακριβώς δύο σημείο. Είναι άγνωστο αν \lim f(n) = \infty. Το μόνο που μπορούμε να δείξουμε είναι ότι f(n) \geqslant 3.
Αφού έψαξα στην βιβλιογραφία ακόμη λίγο βρήκα τα εξής:

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

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


dimitris pap
Δημοσιεύσεις: 287
Εγγραφή: Παρ Ιαν 23, 2009 3:42 pm

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

#10

Μη αναγνωσμένη δημοσίευση από dimitris pap » Τετ Αύγ 25, 2010 8:55 pm

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


Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8444
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#11

Μη αναγνωσμένη δημοσίευση από Demetres » Πέμ Αύγ 26, 2010 4:07 pm

Έκανα σήμερα λίγο περισσότερο ψάξιμο. Το καλύτερο κάτω φράγμα μέχρι στιγμής είναι το f(n) \geqslant 6n/13 για n \neq 7,13:

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

Για n \geqslant 3, έχει αποδειχθεί από τον Boroczky ότι f(2n) \leqslant n. Η κατασκευή του εμφανίστηκε για πρώτη φορά στο

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

Έχει επίσης δώσει κατασκευές που δείχνουν ότι f(4n+1) \leqslant 3n/4 και f(4n+3) \leqslant 3n (για n \geqslant 3).

(Η εικασία f(n) = n-1 για μεγάλα n είναι λοιπόν λανθασμένη, ενώ η εικασία f(n) \geqslant n/2 για n > 13 από ότι αντιλαμβάνομαι παραμένει ανοικτή.)

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

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


Απάντηση

Επιστροφή σε “ΑΝΑΛΥΣΗ”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες