Συνδυαστική Γεωμετρία---------------->Bulletin (Δ. 4)

#1

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

k-ser · #2

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

#3

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

σημεία της περιφέρειάς του."

Αρκεί να βρούμε τα χωρία στα οποία χωρίζεται το αντίστοιχο εγγεγραμμένο στον κύκλο

-γωνο και προσθέτουμε επιπλέον

χωρία που βρίσκονται μεταξύ των πλευρών του

-γώνου και των αντίστοιχων τόξων του κύκλου.

Επίσης παρατηρήστε ότι όταν ενώνουμε δύο σημεία του

-γώνου και τέμνουμε

τμήματα τότε δημιουργούνται k+1

χωρία.

Τελικά τα συνολικά χωρία (δεν βρήκα κλειστό τύπο με τον τρόπο που το υπολόγισα παρόλο που είμαι σίγουρος ότι υπάρχει καθώς το πρόβλημα μου θυμίζει έντονα κάποιο πρόβλημα διαγωνισμού που είχα λύσει παλαιότερα. Ίσως να χρειάζεται η μέθοδος "count in two ways" για να υπολογίσουμε γρήγορα το πλήθος των χωρίων με δύο διαφορετικούς τρόπους) είναι
$\displaystyle\binom{n-1}{2}+1\cdot\binom{n-2}{2} + 2\cdot \binom{n-3}{2} + 3\cdot\binom{n-4}{2}+\cdots+ (n-5)\cdot\binom{4}{2}+(n-4)\cdot\binom{3}{2}+(n-3)\cdot\binom{2}{2}+n$

Αλέξανδρος

#4

Σωστός Αλέξανδρε. Να γράψω λίγο διαφορετικά την απάντησή σου. Βρήκες $\displaystyle \binom{n-1}{2} + n + \sum_{k=2}^{n-2}\binom{k-1}{1}\binom{n-k}{2}$ .

Έχουμε $\displaystyle \sum_{k=2}^{n-2} \binom{k-1}{1}\binom{n-k}{2} = \binom{n}{4}$ . Ένας τρόπος να το δούμε αυτό, κάθε $\binom{k-1}{1}\binom{n-k}{2}$ μετρά τον αριθμό τον υποσυνόλων του $\{1,\ldots,n\}$ με τέσσαρα στοιχεία εκ των οποίων το δεύτερο στοιχείο εμφανίζεται στην θέση κ.

Άρα η απάντηση του Αλέξανδρου μπορεί να γραφτεί ως $\displaystyle 1 + \binom{n}{2} + \binom{n}{4}$ . Το έγραψα επίτηδες έτσι διότι εισηγείται μια άλλη λύση. (Ουσιαστικά την ίδια με του Αλέξανδρου αλλά ένα διαφορετικό τρόπο για να μετρήσουμε τα χωρία.)

ΥΓ 1. Συγνώμη αν σας μπέρδεψε η εκφώνηση.

ΥΓ 2. Κάτι που μου αρέσει σε αυτή την άσκηση είναι πως αν κοιτάξουμε τις περιπτώσεις μικρών ν, παίρνουμε 1,2,4,8,16,... και μπορεί εύκολα κάποιος να παραπλανηθεί κάποιος και να πιστέψει πως η απάντηση είναι $2^{n-1}$ . Αν κοιτάξουμε την περίπτωση ν=6, βρίσκουμε 31 χωρία αλλά από το σχήμα είναι ήδη αρκετά δύσκολο να μετρήσουμε τα χωρία και εύκολα μπορεί να πιστέψουμε πως ίσως κάναμε λάθος στο μέτρημα διότι η απάντηση "πρέπει" να είναι $2^{n-1}$ .

#5

Δημήτρη σε ευχαριστώ πολύ για την παρέμβασή σου έστω και ετεροχρονισμένα! Μια και ασχολήθηκα σήμερα με το εν λόγω πρόβλημα (το συζητούσαμε με το συνάδελφο Ανδρέα Βαρβεράκη στον καφέ πριν 2 μέρες) θα αναφέρω ακόμη 1 λύση που δείχνει τον όμορφο τύπο που έγραψε ο Δημήτρης:

Όπως είναι γνωστό για τα κυρτά πολύεδρα του χώρου ισχύει ο τύπος του Euler

K+E=A+2

. όπου

ο αριθμός των κορυφών, εδρών και ακμών αντίστοιχα. Στο επίπεδο ισχύει ο τύπος $K+E=A+1 \Longrightarrow E=A-E+1$ [Για να το δείτε αυτό διαλέξτε μία οποιαδήποτε κορυφή και προβάλετε πάνω στο επίπεδο κάποιας έδρας, το πολύεδρό σας. Τότε το μόνο που θα συμβεί είναι να έχουμε ελάττωση των εδρών κατά μία ενώ τα υπόλοιπα θα παραμείνουν αμετάβλητα (φυσικά λόγω του προβλήματος, δεν θα έχουμε συμπτώσεις εδρών, κορυφών ή ακμών- παίρνουμε το μέγιστο πλήθος τους)].

Τώρα είμαστε έτοιμοι να ξεκινήσουμε το μέτρημα:

Κορυφές (K) :

όλα τα σημεία + $\displaystyle\binom{n}{4}$ τα εσωτερικά σημεία [Παρατηρήστε ότι

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

Ακμές (A) :

τα τόξα του κύκλου + $\displaystyle\binom{n}{2}$ οι πλευρές μαζί με τις διαγώνιες + $2\cdot\displaystyle\binom{n}{4}$ τα εσωτερικά τμήματα.

Άρα από τον τύπο του Euler έχουμε $E=n+\displaystyle\binom{n}{2}+2\cdot\binom{n}{4}-n-\binom{n}{4}+1 \Longrightarrow \boxed{E=\binom{n}{2}+\binom{n}{4}+1}$ .

Αλέξανδρος

#6

Αλέξανδρε, εξαιρετικά απλή και όμορφη λύση. Δεν την είχα ξαναδεί.

ΥΓ: Στο επίπεδο συνήθως χρησιμοποιώ τον τύπο Κ+Ε=Α+2, επειδή μετράω και το εξωτερικό μη φραγμένο μέρος του επιπέδου σαν έδρα.

Συνδυαστική Γεωμετρία---------------->Bulletin (Δ. 4)

Συνδυαστική Γεωμετρία---------------->Bulletin (Δ. 4)

Re: Συνδυαστική Γεωμετρία

Re: Συνδυαστική Γεωμετρία

Re: Συνδυαστική Γεωμετρία

Re: Συνδυαστική Γεωμετρία

Re: Συνδυαστική Γεωμετρία

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