Από Αναδρομική σε Αναδρομική!

Συντονιστές: Demetres, socrates, silouan

JimNt.
Δημοσιεύσεις: 507
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Από Αναδρομική σε Αναδρομική!

#1

Μη αναγνωσμένη δημοσίευση από JimNt. » Τρί Απρ 18, 2017 2:21 pm

Παίρνουμε n σημεία πάνω σε έναν κύκλο, τα οποία ενώνουμε ανα 2 με ένα ευθύγραμμο τμήμα. (Έχουμε συνολικά \binom{n}{2} τέτοια τμήματα). Αν δίνεται ότι τα τμήματα αυτά ανα τρία δεν συντρέχουν στο εσωτερικό του κύκλου, να βρείτε το πλήθος των περιοχών στις οποίες χωρίζεται ο κύκλος από τα τμήματα αυτά. Για μαθητές.


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.

Λέξεις Κλειδιά:
ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ
Δημοσιεύσεις: 501
Εγγραφή: Σάβ Μαρ 28, 2015 8:49 pm

Re: Από Αναδρομική σε Αναδρομική!

#2

Μη αναγνωσμένη δημοσίευση από ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ » Τρί Απρ 18, 2017 3:38 pm

Είχα γράψει 2^{n-1} ως απάντηση αλλα για 6 σημεία είναι λάθος!!!

Δείτε το !

Το πρόβλημα αποκτά τεράστιο ενδιαφέρον!


ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ
Δημοσιεύσεις: 501
Εγγραφή: Σάβ Μαρ 28, 2015 8:49 pm

Re: Από Αναδρομική σε Αναδρομική!

#3

Μη αναγνωσμένη δημοσίευση από ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ » Τρί Απρ 18, 2017 3:51 pm

Εχω βρει μια απάντηση που περιέχει τον τύπο του Euler αλλα δεν ειναι για τον φάκελο και ψάχνω και αλλη!


min##
Δημοσιεύσεις: 52
Εγγραφή: Τρί Απρ 18, 2017 3:40 pm

Re: Από Αναδρομική σε Αναδρομική!

#4

Μη αναγνωσμένη δημοσίευση από min## » Τρί Απρ 18, 2017 3:52 pm

Το λεγόμενο ''Moser's circle problem''
hint: v-e+f=2,handshake lemma


JimNt.
Δημοσιεύσεις: 507
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

Re: Από Αναδρομική σε Αναδρομική!

#5

Μη αναγνωσμένη δημοσίευση από JimNt. » Τρί Απρ 18, 2017 4:03 pm

Δεν είχα το παραπάνω υπόψη μου... Λύνεται με πολύ πιο στοιχειώδη μέσα...


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7751
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Από Αναδρομική σε Αναδρομική!

#6

Μη αναγνωσμένη δημοσίευση από Demetres » Τρί Απρ 18, 2017 9:20 pm

ΧΑΡΗΣ ΤΙΟΥΡΙΝΓΚ έγραψε:Είχα γράψει 2^{n-1} ως απάντηση αλλα για 6 σημεία είναι λάθος!!!

Δείτε το !

Το πρόβλημα αποκτά τεράστιο ενδιαφέρον!
Από τα αγαπημένα μου προβλήματα ακριβώς για αυτόν τον λόγο. Η ακολουθία ξεκινάει ως εξής: 1,2,4,8,16,31.


Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 666
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Από Αναδρομική σε Αναδρομική!

#7

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Τετ Απρ 19, 2017 12:07 am

Ο κύκλος ακόμα και χωρίς ευθύγραμμα τμήματα αποτελεί από μόνος του 1 περιοχή.

Έστω ότι υπάρχουν ήδη κάποια ευθύγραμμα τμήματα. Για κάθε επιπλέον ευθύγραμμο τμήμα που δημιουργείται μεταξύ 2 σημείων του κύκλου έχουμε τις εξής περιπτώσεις:
α) Αν το νέο τμήμα δεν τέμνεται από κανένα άλλο τμήμα τότε δημιουργεί μια επιπλέον περιοχή (χωρίζει μια προϋπάρχουσα περιοχή σε δύο περιοχές).
β) Αν το νέο τμήμα τέμνεται από k άλλα τμήματα, τότε αυτό χωρίζεται σε k+1 μικρότερα τμήματα, δημιουργώντας k+1 επιπλέον περιοχές.
Συγχωνεύοντας τις δύο περιπτώσεις σε μία, μπορούμε να πούμε ότι κάθε νέο τμήμα που τέμνεται σε k (με k \geq 0) σημεία από άλλα τμήματα δημιουργεί k+1 νέες περιοχές.

Δηλαδή έχουμε:

Πλήθος περιοχών = 1 + πλήθος ευθυγράμμων τμημάτων + πλήθος σημείων τομής = \boxed{1 + \dbinom{n}{2} + \dbinom{n}{4} }

Βέβαια ο παραπάνω τύπος ισχύει αν n \geq 4. Διαφορετικά:

Αν n=0 ή n=1 τότε έχουμε \boxed{1} περιοχή.

Αν n=2 ή n=3 τότε έχουμε \boxed{1 + \dbinom{n}{2} } περιοχές.

Υ.Γ.
Σε αυτό το σημείο αναρωτιέμαι αν τα παραπάνω αρκούν ή χρειάζεται κάποια "κανονική απόδειξη" π.χ. επαγωγή.


Houston, we have a problem!
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 666
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Από Αναδρομική σε Αναδρομική!

#8

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Παρ Απρ 21, 2017 5:09 pm

Διονύσιος Αδαμόπουλος έγραψε: Βέβαια ο παραπάνω τύπος ισχύει αν n \geq 4.
Κάπου είδα ότι θα μπορούσαμε να ορίσουμε ότι \dbinom{x}{y}=0 αν x<y. Αν ισχύει αυτό, τότε ο αρχικός τύπος θα ισχύει για όλα τα n.
Διονύσιος Αδαμόπουλος έγραψε: Υ.Γ.
Σε αυτό το σημείο αναρωτιέμαι αν τα παραπάνω αρκούν ή χρειάζεται κάποια "κανονική απόδειξη" π.χ. επαγωγή.
Σε αυτό δεν απάντησε κανείς... :(


Houston, we have a problem!
Άβαταρ μέλους
cretanman
Διαχειριστής
Δημοσιεύσεις: 3798
Εγγραφή: Πέμ Δεκ 18, 2008 12:35 pm
Τοποθεσία: Ηράκλειο Κρήτης
Επικοινωνία:

Re: Από Αναδρομική σε Αναδρομική!

#9

Μη αναγνωσμένη δημοσίευση από cretanman » Παρ Απρ 21, 2017 5:22 pm

Για τον ίδιο λόγο που αναφέρει ο Δημήτρης είναι και για μένα ένα από τα αγαπημένα προβλήματα. Φαίνεται να ακολουθείται ένα μοτίβο το οποίο κάποια στιγμή (με 6 σημεία) χαλάει...

Είχε συζητηθεί εδώ και ήταν θέμα στον Αρχιμήδη το 1999 στο οποίο είχα συμμετάσχει ως μαθητής (τα θέματα εδώ).

Αλέξανδρος


Αλέξανδρος Συγκελάκης
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 666
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Από Αναδρομική σε Αναδρομική!

#10

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Παρ Απρ 21, 2017 9:48 pm

Διονύσιος Αδαμόπουλος έγραψε: Βέβαια ο παραπάνω τύπος ισχύει αν n \geq 4.
Κάπου είδα ότι θα μπορούσαμε να ορίσουμε ότι \dbinom{x}{y}=0 αν x<y. Ισχύει πράγματι;

Αν ισχύει αυτό, τότε ο αρχικός τύπος θα ισχύει για όλα τα n.
Διονύσιος Αδαμόπουλος έγραψε: Υ.Γ.
Σε αυτό το σημείο αναρωτιέμαι αν τα παραπάνω αρκούν ή χρειάζεται κάποια "κανονική απόδειξη" π.χ. επαγωγή.
Σε αυτό δεν απάντησε κανείς... :(

Ας βάλουμε και ένα πρόσθετο ερώτημα:
β) Ποιο είναι το πλήθος των ευθυγράμμων τμημάτων στα οποία χωρίζονται αυτές οι \dbinom{n}{2} χορδές μέσω των σημείων τομής τους.


Houston, we have a problem!
min##
Δημοσιεύσεις: 52
Εγγραφή: Τρί Απρ 18, 2017 3:40 pm

Re: Από Αναδρομική σε Αναδρομική!

#11

Μη αναγνωσμένη δημοσίευση από min## » Παρ Απρ 21, 2017 11:08 pm

Από τον τύπο V-E+F=2 όπου στο V προσμετρούνται τα σημεία τομής των χορδών (\binom{n}{4}) και τα n σημεία, στο F προσμετράται η περιοχή εκτός του κύκλου και στο e τα καμπυλόγραμμα τμήματα μεταξύ δύο διαδοχικών σημείων(n στο πλήθος),παίρνουμε \binom{n}{4}+n-(πλήθοςζητούμενωντμημάτων +n)+\binom{n}{4}+\binom{n}{2}=0.Λύνοντας ως προς το πλήθος των ζητούμενων τμημάτων(έστω e') παίρνουμε e'=2\binom{n}{4}+\binom{n}{2}.Τέλος αφαιρούμε τα n μη τεμνόμενα τμήματα και παίρνουμε: e'=2\binom{n}{4}+\binom{n}{2}-n..


Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 666
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Από Αναδρομική σε Αναδρομική!

#12

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Κυρ Απρ 30, 2017 10:52 pm

Διονύσιος Αδαμόπουλος έγραψε: Ας βάλουμε και ένα πρόσθετο ερώτημα:
β) Ποιο είναι το πλήθος των ευθυγράμμων τμημάτων στα οποία χωρίζονται αυτές οι \dbinom{n}{2} χορδές μέσω των σημείων τομής τους.
min## έγραψε:Από τον τύπο V-E+F=2 όπου στο V προσμετρούνται τα σημεία τομής των χορδών (\binom{n}{4}) και τα n σημεία, στο F προσμετράται η περιοχή εκτός του κύκλου και στο e τα καμπυλόγραμμα τμήματα μεταξύ δύο διαδοχικών σημείων(n στο πλήθος),παίρνουμε \binom{n}{4}+n-(πλήθοςζητούμενωντμημάτων +n)+\binom{n}{4}+\binom{n}{2}=0.Λύνοντας ως προς το πλήθος των ζητούμενων τμημάτων(έστω e') παίρνουμε e'=2\binom{n}{4}+\binom{n}{2}.Τέλος αφαιρούμε τα n μη τεμνόμενα τμήματα και παίρνουμε: e'=2\binom{n}{4}+\binom{n}{2}-n..
Νομίζω πως δεν υπάρχει λόγος να αφαιρέσουμε τα n μη τεμνόμενα τμήματα, όπως λες στο τέλος της λύσης σου.

Εναλλακτικά:

Κάθε χορδή από μόνη της αποτελεί ένα ευθύγραμμο τμήμα. Κάθε σημείο τομής που βρίσκεται πάνω σε μια χορδή δημιουργεί ένα επιπλέον τμήμα σε αυτή τη χορδή (π.χ. αν μια χορδή περιέχει k σημεία τομής τότε χωρίζεται σε k+1 τμήματα).

Όμως κάθε σημείο τομής βρίσκεται σε 2 χορδές. Επομένως έχουμε:

Πλήθος τμημάτων = πλήθος χορδών + 2 \cdot ( πλήθος σημείων τομής )= \boxed{\dbinom{n}{2} + 2 \dbinom{n}{4} }


Houston, we have a problem!
Απάντηση

Επιστροφή σε “Συνδυαστική - Προχωρημένο Επίπεδο (Juniors)”

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

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