Προβλήματα Μαθηματικών

Σεπτεμβρίου 14, 2009

Σημεία και ευθείες

Filed under: Λυμένα Προβλήματα,Με υπόδειξη — Mihalis Kolountzakis @ 10:58 πμ

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

Advertisements

14 Σχόλια »

  1. Μία σκέψη για αυτό το πρόβλημα είναι η εξής:

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

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

    Η διαδικασία απαρίθμησης (έχοντας για υποθέσεις ότι: 1) δεν υπάρχει ευθεία που περνά από ακριβώς 2 σημεία, 2) δεν είναι όλα τα σημεία συνευθειακά, και ότι 3) το σύνολο των σημείων πεπερασμένο στο πλήθος) είναι η εξής:

    Παίρνουμε τυχαίο σημείο (έστω το α) και το καταγράφουμε σαν πρώτο στη λίστα. Παίρνουμε ένα άλλο σημείο (έστω το β) και το καταγράφουμε σαν δεύτερο. Φέρνουμε ευθεία Εαβ. Η ευθεία Εαβ περιέχει και άλλο σημείο εκτός των α, β , έστω το γ και ενδεχομένως και άλλα σημεία. Τα καταγράφω όλα αυτά στη λίστα. Αφού δεν είναι από υπόθεση όλα συνευθειακά, θα πρέπει να υπάρχει άλλο σημείο εκτός της Εαβ, έστω το δ, το καταγράφω. Φέρνω ευθεία Εαδ, σε αυτήν υπάρχει τουλάχιστον ένα επιπλέον σημείο, μαζί ενδεχομένως με άλλα, τα οποία καταγράφω. Υπάρχουν τώρα αρκετά σημεία για να φέρω και άλλες ευθείες, φέρνω π.χ. την Εδβ, κ.ο.κ. Η πιο πάνω διαδικασία απαρίθμησης των σημείων δεν τελειώνει ποτέ διότι η υπόθεση 1 πάντα με οδηγεί στο να υπάρχει ένα επιπλέον σημείο που δεν το έχω απαριθμήσει.

    Νομίζω ότι με αυτό τον τρόπο παράγεται όλο το επίπεδο των σημείων. Εάν αρχίσει κάποιος και ακολουθήσει την πιο πάνω διαδικασία θα γεμίσει όλο το χαρτί με σημεία, όταν επαναλάβει άπειρες φορές τη διαδικασία.

    Θα ήθελα να βρώ μια πιο ικανοποιητική εξήγηση για την ύπαρξη του επόμενου σημείου στην καταγραφή της λίστας.

    Μου αρέσει!

    Σχόλιο από pebox — Οκτώβριος 1, 2009 @ 9:19 πμ

  2. Η διαδικασία που περιγράφεις μπορεί να περνάει άπειρες φορές από κάποια σημεία, άρα δε λέει τίποτα το ότι δουλεύει επ’ άπειρον.

    Δε νομίζω ότι είσαι στο σωστό δρόμο.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Οκτώβριος 1, 2009 @ 1:16 μμ

  3. Το ότι δουλεύει επ’ άπειρον νομίζω σημαίνει ότι πάντα προσθέτω μία καινούργια ευθεία στο επίπεδο. Από την άλλη όμως τα σημεία του συνόλου που μου έδωσαν πεπερασμένα, άρα δεν μπορούν να ανήκουν σε άπειρες ευθείες (από ένα συγκεκριμένο αριθμό σημείων περνάει νομίζω πεπερασμένος αριθμός ευθειών), άρα αφού θα προσθέτω αναγκαστικά άπειρες ευθείες θα πρέπει πάντα να υπάρχει ένα νέο σημείο που δεν το έχω υπολογίσει, πράγμα που μου μεγαλώνει στο άπειρο το μέγεθος του συνόλου των σημείων, πράγμα άτοπο. Έτσι το σκέφτηκα.

    Μου αρέσει!

    Σχόλιο από pebox — Οκτώβριος 1, 2009 @ 2:19 μμ

  4. Όχι δεν προσθέτεις πάντα μια καινούργια ευθεία. Δοκίμασε τη μέθοδό σου, π.χ., σε τρία σημεία και άλλα τρία στα μέσα των πλευρών του τριγώνου που ορίζουν τα τρία πρώτα.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Οκτώβριος 1, 2009 @ 3:28 μμ

  5. Έστω τρία σημεία α,β,γ. φέρνω Εαβ, σε αυτήν ανήκει το σημείο Μαβ (σημείο στο μέσον του τμήματος αβ), μετά φέρνω Εαγ, σε αυτήν ανήκει το σημείο Μαγ (το μέσον τους), φέρνω Εβγ, σε αυτήν πρέπει να ανήκει το Μβγ. Φέρνω ευθεία που περνά από Μαβ και Μαγ ποιό σημείο ανήκει σε αυτήν? ένα άλλο εκτός από τα α,β,γ,Μαγ , έστω το κ. φέρνω μετά από το κ ευθεία. δεν υπάρχει πάντα μία επιπλέον ευθεία?

    Μου αρέσει!

    Σχόλιο από pebox — Οκτώβριος 1, 2009 @ 3:45 μμ

  6. Διόρθωση του Post 5: από «ένα άλλο εκτός από τα α,β,γ,Μαγ» διορθώνω στο «ένα άλλο εκτός από τα α,β,γ,Μβγ»

    Μου αρέσει!

    Σχόλιο από pebox — Οκτώβριος 1, 2009 @ 4:01 μμ

  7. Pebox, η απόδειξη σου δεν δουλεύει. Τι συμβαίνει π.χ. αν έχουμε τα σημεία α,β,γ,δ,ε,ζ,η και τις ευθείες αβδ,αγε,βγζ,γδη,βεη,δεζ; (Εδώ εννοώ ότι η ευθεία αβδ περιέχει τα σημεία α,β,δ και μόνο αυτά.) Φυσικά η άσκηση είναι σωστή και δεν μπορεί στο επίπεδο να υπάρξει τέτοιος σχηματισμός σημείων/ευθειών αλλά κοιτάζοντας μόνο τις ευθείες και ποια σημεία βρίσκονται πάνω στις ευθείες δεν είναι καθόλου προφανές ότι δεν υπάρχει τέτοιος σχηματισμός.

    Μου αρέσει!

    Σχόλιο από Δημήτρης — Οκτώβριος 1, 2009 @ 4:45 μμ

  8. Ξέχασα να προσθέσω την αζη στις ευθείες.

    Μου αρέσει!

    Σχόλιο από Δημήτρης — Οκτώβριος 1, 2009 @ 5:00 μμ

  9. Η κατασκευή που περιγράφεις (εάν υπάρχει) αποδεικνύει νομίζω ότι το πρόβλημα είναι λάθος. Όμως επειδή όπως λες το πρόβλημα σωστό, έχω την εντύπωση ότι η κατασκευή που περιγράφεις δεν υπάρχει. Εάν υπήρχε θα είχαμε βρει ένα πεπερασμένο σύνολο από 7 σημεία στα οποία καμία ευθεία δεν περνάει ακριβώς από 2 σημεία του συνόλου.

    Νομίζω η ιδέα που πρότεινα είναι ότι αν υποθέσει κανείς ότι υπάρχει μία τέτοια κατασκευή σημείων (που δηλαδή σε κάθε ευθεία ανάμεσα σε οποιαδήποτε σημεία της κατασκευής να ανήκουν τουλάχιστον 3 σημεία της κατασκευής), τότε αυτή η κατασκευή έχει άπειρα στο πλήθος σημεία, πράγμα που εδώ μας λένε ότι έχουμε πεπερασμένο στο πλήθος σημεία. Αυτό ουσιαστικά πάω να αναδείξω με την άπειρη διαδικασία αυτή. Μία τέτοια κατασκευή είναι αυτή που προτεινε ο Mihalis (με μια τροποποιηση, ότι δηλαδη ενα τρίγωνο μέσα στο άλλο με κορυφές στις διαμέσους του εξωτερικού και αυτό να επαναλαμβάνεται στο άπειρο), αλλά όμως αυτή είναι άπειρη κατασκευή και όχι πεπερασμένη κάτι που δεν το θέλουμε εδώ.

    Μου αρέσει!

    Σχόλιο από pebox — Οκτώβριος 1, 2009 @ 5:23 μμ

  10. Δημήτρης, Να προσπαθήσω να εκφρασθώ και αλλιώς: δώσε μου στο χαρτί ένα πεπερασμένο σύνολο σημείων και η πιο πάνω διαδικασία (με τις 3 υποθέσεις) στην προσπάθειά της να απαριθμήσει τα σημεία του συνόλου που μου έδωσες, είτε θα φθάσει σε άτοπο θερώντας ότι υπάρχει ευθεία που έχει μόνο 2 σημεία, είτε σε άλλο άτοπο (για να αποφύγω το πρώτο) ότι θα έχω άπειρα στο πλήθος σημεία. Άρα η υπόθεση που έκανα (ότι δεν υπάρχει ευθεία στο σύνολο με ακριβώς 2 σημεία) δεν ισχύει, άρα υπάρχει ευθεία με ακριβώς 2 σημεία.

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

    Μου αρέσει!

    Σχόλιο από pebox — Οκτώβριος 1, 2009 @ 5:47 μμ

  11. Πάντως το πρόβλημα φαίνεται ζόρικο, σε αντίθεση με την απλή διατύπωσή του… Και ζόρικο πρόβλημα με απλη διατύπωση μπορεί να γίνει έμμονη ιδέα: είτε αυτό λέγεται εικασία του Goldbach είτε «Σημεία και ευθείες»!! Προσωπικά ακόμη και τώρα πότε-πότε ξαναπιάνω αυτό το πρόβλημα με τα ομοιμορφικά «Υ», που αν θυμάμαι ήταν από τα πρώτα που δημοσιεύσατε στο blog… Λέτε να την πατήσω και μ’ αυτό? :S

    Μου αρέσει!

    Σχόλιο από nefelh — Οκτώβριος 1, 2009 @ 8:01 μμ

  12. Υπόδειξη:

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

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

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

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Οκτώβριος 1, 2009 @ 11:08 μμ

  13. Έστω δεν υπάρχει ευθεία που να περνά από ακριβώς 2 σημεία. Παίρνω ζευγάρι (Ε,α) σύμφωνα με υπόδειξη, φέρνω κάθετη από σημείο α στην Ε. Έστω m το σημείο τομής. Στην Ε ανήκουν τουλάχιστον 3 σημεία του συνόλου, έστω b, c, d . Αυτά τα σημεία b,c,d έστω ότι εμφανίζονται επάνω στην ευθεία με την ίδια σειρά που τα έχουμε γράψει. Σε κάθε περίπτωση δύο από αυτά τα σημεία θα βρίσκονται στο ίδιο ημιεπίπεδο που ορίζει η ευθεία στην οποία ανήκει το ύψος αm. Μπορεί και τα τρία να είναι στο ίδιο ημιεπίπεδο, πάντως 2 τουλάχιστον θα είναι. Έστω b,c τα δύο αυτά σημεία και τμήμα mb < mc. Φέρνω ευθεία ac. Φέρνω ευθεία που περνά από a,c και φέρνω κάθετη από b σε αυτή την ευθεία, έστω k το σημείο τομής. Όμως τώρα δημιουργείται άτοπο διότι στο ορθογώνιο τρίγωνο bkc, το ύψος από την κορυφή b, το bk δηλαδή, είναι μικρότερο από το ύψος am. Το άτοπο εμφανίζεται διότι ενώ εγώ υπέθεσα ότι το ζευγάρι (Ε,α) είναι μικρότερης απόστασης, βρήκα άλλο ένα ζευγάρι, την ευθεία akc (που ανήκει στο σύνολο, διότι τα a,c σημεία του συνόλου) και το σημείο b.

    Άρα ισχύει η ίδια απόδειξη και για το ζευγάρι (Ε,α) που μεγιστοποιεί την απόσταση α από Ε, αν τώρα δουλεύαμε με το σημείο που είναι μόνο του σε ημιεπίπεδο; νομίζω όχι διότι μπορεί και τα τρία να είναι από την ίδια μεριά του m, οπότε η απόσταση θα βγαίνει πάντα μικρότερη της μέγιστης.

    Μου αρέσει!

    Σχόλιο από pebox — Οκτώβριος 9, 2009 @ 9:34 μμ

  14. Σωστά, αυτή είναι η λύση.

    Μου αρέσει!

    Σχόλιο από Mihalis Kolountzakis — Οκτώβριος 10, 2009 @ 12:24 πμ


RSS feed for comments on this post. TrackBack URI

Σχολιάστε

Συνδεθείτε για να δημοσιεύσετε το σχόλιο σας:

Λογότυπο WordPress.com

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό WordPress.com. Αποσύνδεση / Αλλαγή )

Φωτογραφία Twitter

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Twitter. Αποσύνδεση / Αλλαγή )

Φωτογραφία Facebook

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Facebook. Αποσύνδεση / Αλλαγή )

Φωτογραφία Google+

Σχολιάζετε χρησιμοποιώντας τον λογαριασμό Google+. Αποσύνδεση / Αλλαγή )

Σύνδεση με %s

Δημιουργήστε ένα δωρεάν ιστότοπο ή ιστολόγιο στο WordPress.com.

Αρέσει σε %d bloggers: