Ο Αντώνης κι ο Βρασίδας είναι φοιτητές και συγκάτοικοι. Ψάχνοντας ένα βράδυ στο ψυγείο τους (πολλά μαθηματικώς αξιοπερίεργα πράγματα μπορεί να βρεθούν ξεχασμένα σε ένα
φοιτητικό ψυγείο, ακόμη και το κενό σύνολο ενίοτε...) ανακάλυψαν $3$ κομμάτια πίτσα. Κρύα και ελαφρώς μπαγιάτικη, η πίτσα θα μπορούσε να μοιραστεί με διάφορους τρόπους.
Αν ας πούμε ο Αντώνης πεινούσε πάρα πολύ κι ο Βρασίδας όχι και τόσο, θα μπορούσε να φάει δύο κομμάτια ο Α και ένα ο Β. Θα μπορούσε όμως να μην φαίνεται σε κανέναν ελκυστική η προοπτική ,και να μη φάνε κανένα κομμάτι.
Ποιες θα ήταν όλες οι δυνατότητες μοιράσματος των ακεραίων ίδιων κομματιών πίτσας ; Ας κάνουμε ένα πινακάκι με Α(ντώνη), Β(ρασίδα) και έναν εικονικό φίλο-φάντασμα, ας τον πούμε Γ(ιάννη), που "τρώει" τα κομμάτια που δεν τρώει κανείς από τους δύο φίλους:
A B Γ3 0 0
2 1 0
2 0 1
1 1 1
1 2 0
1 0 2
0 3 0
0 2 1
0 1 2
0 0 3
Αυτοί οι $10$ τρόποι υπάρχουν συνολικά, για να μοιραστούν ο Α και ο Β τα τρία κομμάτια,με τη δυνατότητα να μένουν κομμάτια (ή κομμάτι) που δεν τρώει κανείς.
Τι λέτε να ισχύει λοιπόν για τέσσερις ($4$) φίλους που κάθονται να μοιραστούν μια πίτσα κομμένη σε $12$ όμοια κομμάτια ; Με πόσους διαφορετικούς τρόπους μπορεί να μοιραστεί αυτή η πίτσα ,με την παραδοχή πως κάποιο, κάποια ή και όλα τα κομμάτια μπορεί και να μη φαγωθούν;
Καλημέρα φίλτατε Γιώργο, καλημέρα και σε όλη την καλή παρέα. Χαθήκαμε λιγάκι.. Ελπίζω να μη χάσαμε εντελώς τη φόρμα μας :-)
ΑπάντησηΔιαγραφήΈνας απλός / παραστατικός τρόπος για να απαντηθεί το ερώτημα είναι ο εξής:
Ας φανταστούμε τα 12 κομμάτια πίτσας σε μια γραμμή. Αν βάλουμε 4 διαχωριστικά, σε τυχαίες θέσεις το καθένα, στην αρχή ή στο τέλος ή ανάμεσά τους, τα 12 κομμάτια χωρίζονται σε 5 ομάδες / μερίδια, καθένα από τα οποία περιλαμβάνει ένα μη αρνητικό ακέραιο αριθμό κομματιών.
Aρκεί λοιπόν να υπολογίσουμε με πόσους τρόπους από 12+4=16 στοιχεία (κομμάτια πίτσας και διαχωριστικά) επιλέγουμε τα 4 (τα διαχωριστικά).
C(16, 4) = 1820.
Γεια σου Θανάση! Eσύ πάντως δεν την έχασες τη φόρμα σου. :-)
ΑπάντησηΔιαγραφήEπίτρεψέ μου να παραστήσω τη λύση σου γραφικά:
* * | * * * | * | * * | * * * *
Tα αστεράκια και οι μπάρες τι δείχνουν; Δείχνουν αυτό που περιέγραψε ακριβέστατα ο papadim ή εναλλακτικά και απολύτως ισοδύναμα τον τρόπο να επιλέξουμε $12$ αντικείμενα από $16$. Η συμμετρία των διωνυμικών συντελεστών άλλωστε, όπως δείχνει πολύ εποπτικά το τρίγωνο του Πασκάλ, υπαγορεύει πως το C(12,4)=C(16,12)= 1820.
Aυτός ο ωραίος συνδυαστικός τρόπος ,που οι αγγλοσάξωνες αποκαλούν "Stars and Bars method" (Aστέρια και Κάθετες) πρωτοεισήχθη από τον Feller στο διάσημο και κλασικό βιβλίο του για τις Πιθανότητες. http://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
και μας βεβαιώνει όντως πως είναι μάλλον ο καλύτερος και εποπτικότερος τρόπος δουλειάς όταν έχουμε να βρούμε με πόσους τρόπους $m$ ίδια αντικείμενα μπορούν να μοιραστούν μεταξύ $n$ διαφορετικών (διακριτών) ανθρώπων ή θέσεων.
Όπως είπε κι ο Θανάσης, μια γραμμή/λίστα m συμβόλων (άστρα) για τα αντικείμενα και n-1 συμβόλων διαίρεσης (μπάρες/κάθετες) κάνει εύκολη τη δουλειά, αφού διαπιστώνουμε εύκολα πως οι τρόποι που ψάχνουμε είναι:
$C(m+n-1 ,m)$
Στο εισαγωγικό μας πρόβλημα (2 φίλοι ,3 κομμάτια) το m και το n ήταν 3 και είχαμε: C(5,3)=10
Yγ. Aυτού του είδους η συνδυαστική μέθοδος απαντάται πολύ συχνά σε εφαρμογές της Στατιστικής και της Φυσικής. Π.χ οι φυσικοί συχνά πρέπει να βρούνε με πόσους διαφορετικούς τρόπους ένα σύνολο σωματιδίων μπορεί να κατηγοριοποιηθεί σε διάφορες διακριτές φυσικές καταστάσεις. Συνήθως ,ως παραδείγματα στις ασκήσεις, χρησιμοποιούνται μπάλες και βάζα ,αλλά και η πίτσα κάνει. :-)
Ένας εναλλακτικός ,αλλά δύσκολος, τρόπος αντιμετώπισης θα ήταν λογικά το να σκεφτεί κάποιος πως μάς ενδιαφέρει η διαμέριση (partition) του 12 με 5 όρους (προσθεταίους). Αυτό οπωσδήποτε θα δουλέψει, κι αν έχει όρεξη κάποιος φίλος ας το κάνει (με κανα μηχανάκι για ευκολία) λόγου χάρι στη διαμέριση (4+3+2+2+1) θα πρέπει να υπολογιστεί πόσες διαφορετικές αναδιατάξεις υπάρχουν (μια και οι 4 φίλοι είναι διακριτοί), πράγμα δύσκολο κι όχι και τόσο μαντζόβολο.
Ευχαριστώ πολύ Γιώργη! Να προσθέσω ότι σε (ξανα)βρίσκω πολύ ορεξάτο και χαίρομαι πολύ γι αυτό. Ωραίες αναλύσεις, επεξηγήσεις, γενικεύσεις, προεκτάσεις και όλα του κόσμου τα καλά. Νομίζω ότι η πολύμηνη απουσία σου από το ιστολόγιο ήταν παραπάνω από αισθητή.
ΑπάντησηΔιαγραφήΓια να μην ξεχνάω κι εγώ όμως τις παλιές ΄κακές΄ μου συνήθειες, επίτρεψέ μου να προσθέσω μια πιο δροσερή παραλλαγή του θέματος, όπου το πρότυπο 'stars & bars' δεν είναι ίσως άμεσα αναγνωρίσιμο:
Ένας παγωτατζής πουλάει παγωτό σε 10 διαφορετικές γεύσεις. Με πόσους διαφορετικούς τρόπους μπορεί να φτιαχτεί ένα κύπελλο παγωτού που περιέχει 4 μπαλίτσες, όχι αναγκαστικά διαφορετικής γεύσης για καθεμιά?
Μια και δε βλέπω ενδιαφέρον (είναι και καλοκαίρι και διακοπές για τους τυχερούς :-) ) θα απαντήσω στην δροσερή παραλλαγή που έθεσε ο papadim, γιατί είναι κρίμα να μείνει αφάγωτο κύπελλο με 4 μπάλες παγωτό! :-)
ΑπάντησηΔιαγραφήΥπάρχει δυνατότητα επανάληψης των στοιχείων, οπότε έχουμε συνδυασμούς με επανάληψη ή "επαναληπτικούς συνδυασμούς" (αφήνω την προσέγγιση Stars & Bars ως άσκηση... :-) )
CR(m,n)=C(m+n-1 ,n)=(m+n-1)!/(n!(m-1)!
Oπότε , μιας και δεν έχουμε χωνάκι, και το κύπελλο ας πούμε βανίλια- φραόυλα-φράουλα-σοκολάτα είναι το ίδιο με το φράουλα-σοκολάτα-βανίλια-φράουλα :-) ,θα έχουμε τα εξής διαφορετικά κύπελλα με 4 μπάλες (ίσως της ίδιας γεύσης):
CR(10,4)=C(13,4)=13!/(4!*9!)=715. Όχι και λίγα!