Μπλεζ Πασκάλ (Στοχασμοί)
Ένα πιάτο περιέχει Ν μακαρόνια. (κατά προτίμηση χωρίς σάλτσα..) Πιάνουμε δύο τυχαίες άκρες από μακαρόνια και τις ενώνουμε. Συνεχίζουμε αυτή τη διαδικασία ενώνοντας στην τύχη ελεύθερα άκρα έως ότου, μετά από Ν ενώσεις, δεν υπάρχουν άλλα ελεύθερα άκρα. Κατά μέσο όρο,πόσες θηλιές/βρόχοι θα δημιουργηθούν από αυτή τη διαδικασία;
ΑΠΑΝΤΗΣΗ:
ΑΠΑΝΤΗΣΗ:
Όταν πιάσουμε το πρώτο τυχαίο άκρο, απομένουν 2Ν-1 ελεύθερα άκρα στο πιάτο.Άρα υπάρχει μια πιθανότητα 1/(2Ν-1) να πιάσουμε το άλλο άκρο του ίδιου μακαρονιού και να σχηματίσουμε έναν βρόχο. (παρεμπ. η θηλιά είναι «βρόχος». Βρόγχος είναι κάτι άλλο, στους πνεύμονες). Και υπάρχει επίσης μια πιθανότητα (2Ν-2)/(2Ν-1) να μην σχηματιστεί βρόχος.Στην πρώτη περίπτωση καταλήγουμε με 1 βρόχο και Ν-1 καλάμια (μακαρόνια. Για ευκολία, θεωρoύμε και το απλό μακαρόνι σαν «καλάμι» μήκους 1).Στη δεύτερη περίπτωση καταλήγουμε απλώς με Ν-1 καλάμια (γιατί απλώς φτιάξαμε ένα καλάμι μήκους 2 μακαρονιών, αλλά δεν διαφέρει σε κάτι από τα υπόλοιπα μοναδιαία καλάμια =μακαρόνια, σε σχέση με το πρόβλημά μας.)
Έτσι, βλέπουμε ότι μετά το πρώτο βήμα, ασχέτως τι έχουμε κάνει, καταλήγουμε με Ν-1 καλάμια και με 1/(2Ν-1) βρόχους (κατά μέσο όρο!)
Η ίδια επαγωγική λογική για Ν-1 καλάμια που απομένουν στο 2ο βήμα, μας οδηγεί στο συμπέρασμα ότι μετά από αυτό το βήμα θα έχουμε μείνει με Ν-2 καλάμια και κατά μέσο όρο με άλλους 1/(2Ν-3) βρόχους. Και πάει λέγοντας μέχρις ότου μείνουμε με μόνο ένα καλάμι ,οπότε στο επόμενο και τελευταίο (Ν-ιοστό) βήμα μένουμε με 0 καλάμια και άλλο έναν βρόχο οπωσδήποτε! (αφού θα ενώσουμε τα άκρα του τελευταίου καλαμιού μεταξύ τους!)
Οπότε προσθέτοντας τις αναμενόμενες τιμές που βρήκαμε για τους βρόχους ανά βήμα προκύπτει ένας γενικός μέσος όρος:
B= 1/(2N-1) + 1(2N-3) + …+1/3 +1 (α)
Η (α) μεγαλώνει πολύ αργά όσο μεγαλώνει το Ν. Για παράδειγμα θέλουμε 8 μακαρόνια (Ν=8) για να περιμένουμε τουλάχιστον 2 βρόχους. Χαρακτηριστικά ,διατεταγμένα ζεύγη (Ν,Β) που δείχνουν αυτή την αργή αύξηση : (1,1) (2,8) (3, 57) (4,419) (5, 3092) (μεγάαλη γαβάθα μακαρόνια θέλουμε για 5 βρόχους!) Για μεγάλα Ν μια καλή προσέγγιση για το Β είναι: B= (lnN)/2.
Mιά κάπως πιο «εξεζητημένη» και ακριβής προσέγγιση είναι:
B = (περίπου) (½)*(lnN+ln4+γ) (β)
Από την (β) βγαίνει Ν=e^(2B-γ)/4 (που συμφωνεί με τα χαρακτηριστικά αποτελέσματα πιο πάνω)
γ=0,5772 η σταθερά Όϋλερ-Μασκερόνι.
Ερώτηση: Η αλυσίδα των μακαρονιών είναι ανοιχτή ή κλειστή?
ΑπάντησηΔιαγραφήΔηλαδή αν είναι μόνο ένα μακαρόνι θα δέσουμε τις άκρες του?
και αν 2 μακαρόνια 2 θηλιές? κ.ο.κ
@ Ε.Αλεξίου: Mπορεί να είναι ό,τι θέλει. Για Ν=1 (ένα μακαρόνι) θα δέσουμε τις άκρες του και θα έχουμε έναν βρόχο (θηλειά). Για 2 μακαρόνια ,με το πρώτο δέσιμο έχουμε είτε 1 "καλάμι" (δύο μακαρόνια εν σειρά) και με το δεύτερο ,αφού αναγκαστικά θα δέσουμε τα άκρα του καλαμιού, θα έχουμε 1 βρόχο, ή (αν δέσουμε πρώτα το κάθε μακαρόνι με το άλλο άκρο του) 2 βρόχους...
ΑπάντησηΔιαγραφήΑυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.
ΑπάντησηΔιαγραφήΓια 1 μακαρόνι η πιθανότητα είναι Π=1(σίγουρα 1 βρόχος)
ΑπάντησηΔιαγραφήΓια 2 μακαρόνια
1o δέσιμο:
1 βρόχος -(1/3)
2ο δέσιμο
1 βρόχος-(2/3)*1
2 βρόχοι-(1/3)*1
Για 3 μακαρόνια
1ο δέσιμο:
1 βρόχος: πιθανότητα (1/5)
2ο δέσιμο:
1 βρόχος - (4/5)*(1/3)
2 βρόχοι -(1/5)*(1/3)
3ο δέσιμο
1 βρόχος - (4/5)*(2/3)*1
2 βρόχοι -(4/5)*(1/3)*1
3 βρόχοι -((1/5)*(1/3))*1
κ.ο.κ
Για ν μακαρόνια
1ο δέσιμο
1 βρόχος (1/(ν-1))
Άρα ο μέσος όρος είναι άθροισμα πιθανοτήτων
Π=1*(1+(1/3+2/3) +(1/5+(4/5)*(1/3+2/3)+ 1/7*(...)+ 1/9*(....)+ 1/(N-1)*(....))+
2*(1/3+(1/3)*(1/5 + 4/5)+ κλπ)
Άρα γενικεύοντας το άθροισμα
1*ν+2*(ν-1)/3 +3*(ν-2)/5 + 4*(ν-3)/7 +....+ ν*1/(2*ν-1)
Πρέπει να βρούμε που συγκλίνει η ακολουθία για μεγάλα ν για να βρούμε το μο.Δεν το γνωρίζω όμως
@ donaltios:H ακολουθία :1*ν+2*(ν-1)/3 +3*(ν-2)/5 + 4*(ν-3)/7 +....+ ν*1/(2*ν-1) συγκλίνει (για ν-άπειρο) στο 0. Αποτέλεσμα που προφανώς δεν μπορεί να είναι σωστό.. :-)
ΑπάντησηΔιαγραφήΠρέπει να συνυπολογίσεις (ποσοτικοποιήσεις) με κάποιον τρόπο και τα ενδεχόμενα "καλάμια"
Ok απλά η εκφώνηση ζητούσε βρόχους και υπέθεσα πως αναφερόμαστε σε κλειστά σχήματα..
ΑπάντησηΔιαγραφήΑυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.
ΑπάντησηΔιαγραφήΣ[1/(2Ν-1)]=1+1/3+...+1/(2Ν-1)
ΑπάντησηΔιαγραφήΌταν έχουμε Ν μακαρόνια, η πιθανότητα να πιάσουμε το άλλο άκρο από το άκρο που έχουμε πιάσει πρώτο είναι 1/(2N-1). Τότε το σύνολο των ελεύθερων (χωρίς βρόγχο) μακαρονιών μειώνεται κατά 1 σε Ν-1. Όμως, όποιο άλλο άκρο κι αν πιάσουμε, τότε πάλι το σύνολο των ελεύθερων μακαρονιών μειώνεται κατά 1 σε Ν-1, αφού θα σχηματιστεί ένα μακαρόνι με σχεδόν διπλάσιο μήκος. Με την ίδια ακριβώς λογική, υπολογίζεται στο δεύτερο βήμα η πιθανότητα 1 νέου βρόγχου σε 1/(2Ν-3) κοκ. μέχρι να καταλήξουμε σε ένα ελεύθερο μακαρόνι και πιθανότητα ενός ακόμα βρόγχου ίση με 1.
@ swt: Πολύ σωστά! Συγχαρητήρια!
ΑπάντησηΔιαγραφήΔείτε και μια επέκταση ,συγκεκριμενοποίηση με αριθμούς της λύσης, στην ανάρτηση.
Nα προσθέσω, ότι αυτό το πρόβλημα ήταν παλιότερα σε μια λίστα ενδιαφερόντων και δύσκολων προβλημάτων του Τμήματος Φυσικής του γνωστού Πανεπιστημίου Χάρβαρντ.
ΑπάντησηΔιαγραφή