1. Τρεις εργάτες μοιράζονται μεταξύ τους πέντε δουλειές.
Κάθε δουλειά γίνεται από έναν εργάτη και κάθε εργάτης κάνει τουλάχιστον μία δουλειά.
Με πόσους διαφορετικούς τρόπους μπορεί να γίνει η μοιρασιά;
(οι εργάτες είναι διαφορετικοί, οι δουλειές είναι διαφορετικές και δύο τρόποι είναι διαφορετικοί αν διαφέρουν σε μία τουλάχιστον δουλειά ενός τουλάχιστον εργάτη)
2. Με πόσους τρόπους μπορούμε να μοιράσουμε 12 καραμέλες σε 6 παιδιά ώστε ένα το πολύ παιδί να μείνει χωρίς καραμέλα;
(οι καραμέλες είναι ίδιες, τα παιδιά διαφορετικά και δύο τρόποι είναι διαφορετικοί αν διαφέρουν στον αριθμό καραμελών ενός τουλάχιστον παιδιού)
1.O Α εργάτης μπορεί να επιλέξει 2 δουλειές με τους C 5 ανά 2=10 τρόπους. Τότε ο Β μπορεί να επιλέξει 2 δουλειές με 3 τρόπους. Άρα 2 δουλειές του Α και 2 του Β μπορούν να επιλεγούν με 30 τρόπους. Αν αυτό γίνει εναλλακτικά για όλους θα έχουμε 90 τρόπους.
Ο Α μπορεί να επιλέξει 3 δουλειές με τους C 5 ανά 3=10 τρόπους. Οι άλλοι 2 θα επιλέξουν τις 2 δουλειές με 2 τρόπους. Άρα υπάρχουν 20 τρόποι να κάνει 3 δουλειές ο Α. Άρα και για τους 3 60 τρόποι.
Άρα συνολικά 150 τρόποι.
2. Ένα το πολύ παιδί χωρίς καραμέλα σημαίνει: 0 παιδιά χωρίς καραμέλα δηλαδή κάθε παιδί μία τουλάχιστον καραμέλα ή 1 παιδί χωρίς καραμέλα.
Το 1ο συμβαίνει με τους C 12 ανά 6=924 τρόπους και το 2ο με 6*C 12 ανά 5=4752 τρόπους, δηλαδή συνολικά 5676 τρόπους.
1. Ο καταμερισμός των εργασιών στα τρία μπορεί να γίνει είτε ως 3-1-1 με C(5,3)=10 τρόπους, είτε ως 2-2-1 με C(5,2)*C(3,2)/2 = 15 τρόπους. Οι εργάτες μπορούν να αναλάβουν αυτές τις καταμερισμένες στα τρία εργασίες με (10+15)*3! = 150 τρόπους.
2. Υπάρχουν 24 τρόποι να μοιραστούν οι καραμέλες στα παιδιά, από τον 8-1-1-1-1-0 έως τον 2-2-2-2-2-2. Υπολογίζω τις δυνατές διατάξεις για κάθε τρόπο και τις αθροίζω. Το σύνολό τους είναι 2442 τρόποι.
1. Οι πέντε δουλειές μπορούν να μοιραστούν στους 3 εργατες είτε 3-1-1, είτε 2-2-1.
Στη πρώτη περίπτωση, οι 3 δουλειές μπορούν να επιλεγούν από τις 5, με C(5,3)=10 τρόπους, ενώ υπάρχουν δύο τρόποι να μοιραστούν οι υπόλοιπες 2 δουλειές στους άλλους δύο. Παράλληλα υπάρχουν τρείς δυνατότητες ως προς το ποιος εργάτης θα κάνει τις 3 δουλειές, σύνολο 10Χ2Χ3=60 τρόποι
Στη δεύτερη περίπτωση οι δύο εργασίες μπορούν να επιλεγούν με C(5,2)=10 τρόπους, ενώ οι επόμενες δύο με C(3,2)=3 τρόπους. Παράλληλα υπάρχουν τρείς δυνατότητες ως προς το ποιος θα είναι ο εργάτης που θα κάνει 1 δουλειά, σύνολο 10Χ3Χ3=90 τρόποι
Σύνολο 60+90=150 τρόποι
2. Διακρίνουμε δύο περιπτώσεις:
Α. Δεν έμεινε κάποιο παιδί χωρίς καραμέλα, δηλαδή και τα 6 παιδιά πήραν από τουλάχιστον μία. Οι δυνατοί τρόποι είναι C(11,5)=462
B. Ακριβώς ένα παιδί έμεινε χωρίς καραμέλα. Αυτό ισοδυναμεί με το ότι οι 12 καραμέλες μοιράστηκαν σε 5 παιδιά και καθένα πήρε τουλάχιστον μία. Οι δυνατοί τρόποι είναι C(11,4)=330. Υπάρχουν 6 δυνατότητες ως προς το ποιο παιδί θα μείνει χωρίς καραμέλα, άρα εχουμε συνολικά 330Χ6=1980 τρόπους
Σύνολο 462+1980=2.442 τρόποι
Πρόβλημα 1
Οι πέντε εργασίες μπορούν να γίνουν από τους τρεις εργάτες κ ένας εξ αυτών να κάνει συνολικά τρεις εργασίες. Αυτή η περίπτωση μας δίνει 120/6*3=60. Επιπλέον μπορούν οι πέντε εργασίες να γίνουν από τους τρεις κ δυο εξ αυτών να κάνουν από δυο εργασίες. Αυτή η περίπτωση δίνει 120/4*3=90. Σύνολο 150 τρόποι.
Πρόβλημα 2
Υπαρχουν οι εξης περιπτωσεις:
Α. περίπτωση που όλα τα παιδιά παίρνουν από μια καραμέλα τουλάχιστον 11!/(5!*6!)=462
Περίπτωση που ένα παιδί δεν παίρνει καραμέλες και τα υπόλοιπα παίρνουν τις 12.
11!/(4!*7!)=330. Επειδή υπάρχουν έξι παιδιά άρα συνολικά 6*330=1980.
1980+462=2442
Άψογες όλες οι λύσεις στο 1, θερμά συγχαρητήρια!
Θα ήθελε κάποιος φίλος να εξηγήσει στο 2 γιατί C(11,5)+6(11,4) και όχι C(12,6)+6C(12,5) ή το ανάποδο;
Οι δυνατοί τρόποι που κ πανομοιότυπα αντικείμενα μπορούν να διαμοιραστούν σε λ διακριτά άτομα και όλα τα άτομα να πάρουν τουλάχιστον από 1, είναι C(κ-1,λ-1).
Αυτό φαίνεται καθαρά, αν στο συγκεκριμένο πρόβλημα, οι 12 καραμέλες έπρεπε να μοιραστούν σε 2 παιδιά, και να πάρουν και τα δύο από τουλάχιστον μία, οπότε οι δυνατοί τρόποι θα ήταν 11: (11,1), (10,2)…., (2,10), (1,11), δηλαδή θα ήταν C(11,1) και όχι C(12,2)=66
Ενας εποπτικός τρόπος για να γίνει αυτό κατανοητό, είναι ο ακόλουθος:
Θεωρούμε τις 12 καραμέλες σαν μία διαδοχή από 12 τελείες σε μία ευθεία
. . . . . . . . . . . .
Στη συνέχεια θεωρούμε ότι βάζουμε ανάμεσα στις τελείες 6 διαχωριστικά, με το πρώτο να βρίσκεται αριστερά, αμέσως πριν τη πρώτη τελεία και τα υπόλοιπα 5 ενδιάμεσα. Πχ.
|. . .| .| . . .| . . |.| . .
Με το τρόπο αυτό οι τελείες (καραμέλες) διαχωρίζονται σε 6 ομάδες (παιδιά), οπου κάθε ομάδα περιεχει τουλάχιστον μία τελεία. Για να συμβεί αυτό (η κάθε ομάδα να περιέχει τουλάχιστον μία τελεία), το τελευταίο διαχωριστικό πρέπει να βρίσκεται πρίν την τελευταία (12η) τελεία.
Κάθε συνδυασμός τοποθέτησης των 5 διαχωριστικών, μας δίνει και μία διαφορετική κατανομή των 12 καραμελων στα 6 παιδιά. Εχουμε δηλαδή 5 διαχωριστικά που μπορούν να τοποθετηθούν σε μία σειρά 11 τελειών οπότε οι δυνατοί συνδυασμοί είναι C(11,5)
Εξαιρετικά Στράτο, υποκλίνομαι!
Γενικότερα, όταν έχουμε να μοιράσουμε ν στοιχεία σε κ άτομα χωρίς περιορισμό πλήθους στοιχείων ανά άτομο, τοποθετούμε τα ν στοιχεία σε μιά σειρά και στην ίδια σειρά τοποθετούμε κ-1 διαχωριστικά, με τα οποία διαχωρίζονται τα στοιχεία κάθε ατόμου από τα στοιχεία των άλλων. Έχουμε επομένως να επιλέξουμε τις θέσεις που μπορεί να πάρουν τα κ-1 διαχωριστικά σε μια σειρά ν+(κ-1) στοιχείων + διαχωριστικών, πράγμα που γίνεται με C(ν+κ-1,κ-1) τρόπους.
Στο πρόβλημά μας ειδικότερα:
Αν κανένα παιδί δεν μείνει χωρίς καραμέλα, τότε 6 καραμέλες θα δοθούν από μία σε κάθε παιδί και οι υπόλοιπες 6 θα μοιραστούν χωρίς περιορισμό στα 6 παιδιά, πράγμα που γίνεται με C(6+6-1,6-1)=C(11,5) τρόπους.
Αν ένα ακριβώς παιδί μείνει χωρίς καραμέλα, υπάρχουν 6 τρόποι να διαλέξουμε αυτό το παιδί και αφού δώσουμε από μία καραμέλα στα άλλα 5 παιδιά, μοιράζουμε τις υπόλοιπες 7 καραμέλες στα ίδια 5 παιδιά χωρίς περιορισμό, πράγμα που γίνεται με C(7+5-1,5-1)=C(11,4) τρόπους.
Επομένως οι ζητούμενοι τρόποι είναι τελικά:
C(11,5)+6*C(11,4) = 462+6*330 = 2442
Ευχαριστώ και πάλι μπράβο στους φίλους!