Οι περιορισμοί αίρονται σιγά σιγά και η μπάρα του Mathbar είναι πλέον σε θέση να εξυπηρετεί πελάτες (με περιορισμούς).
Υπάρχουν $10$ σκαμπό σε ένα μπαρ. Οι περιορισμοί ορίζουν ότι κανένας πελάτης δεν μπορεί να κάθεται σε σκαμπό ακριβώς δίπλα σε άλλο πελάτη, κατά τα άλλα μπορεί να καθίσει σε όποιο άλλο σκαμπό θέλει.
Με αυτόν τον περιορισμό, πόσες πιθανές ασφαλείς διαμορφώσεις καθισμάτων υπάρχουν;
Είχα κάνει μία ερώτηση, αλλά για κάποιο λόγο διαγράφηκε, οπότε απαντώ όπως αντιλαμβάνομαι ο ίδιος το πρόβλημα:
ΑπάντησηΔιαγραφήΜπορούν να καθίσουν 1 έως 5 πελάτες (με περισσότερους δημιουργείται συνωστισμός). Με χρήση τεχνικής stars & bars, έχουμε:
1 πελάτης κάθεται με C(10,1)=10 τρόπους,
2 πελάτες κάθονται με C(9,2)=36 τρόπους,
3 πελάτες κάθονται με C(8,3)=56 τρόπους,
4 πελάτες κάθονται με C (7,4)=35 τρόπους,
5 πελάτες κάθονται με C(6,5)=6 τρόπους.
Συνολικά, 1 έως 5 πελάτες κάθονται με 143 διαφορετικούς τρόπους.
Εξήγηση:
ΔιαγραφήΥποθέτουμε ότι έχουμε 10 σκαμπό σε σειρά (βλ.εικόνα), από τα οποία τα χ πράσινα και τα 10-χ κόκκινα, και τα αριθμούμε από 1 έως 10, από τα αριστερά προς τα δεξιά. Στα χ πράσινα σκαμπό θα καθίσουν χ πελάτες, με χ=1 έως 5, και τα 10-χ κόκκινα θα μείνουν άδεια.
Για να μην κάθονται στα πράσινα σκαμπό κανένα ζευγάρι γειτόνων, πρέπει ανάμεσα σε οποιαδήποτε δύο πράσινα να υπάρχει ένα τουλάχιστον κόκκινο. Τοποθετούμε λοιπόν αρχικά τα χ πράσινα στις θέσεις 1,3,..,2χ-1 και βάζουμε από ένα κόκκινο στις ενδιάμεσες θέσεις 2,4,.,2(χ-1). Αν τώρα ξεκινώντας από αυτή τη διάταξη τοποθετήσουμε με κάθε δυνατό τρόπο τα υπόλοιπα 11-2χ κόκκινα μπροστά ή ανάμεσα ή πίσω από τα πράσινα, μετατοπίζοντας όσο χρειάζεται κάθε φορά τα ήδη τοποθετημένα προς τα δεξιά, θα πάρουμε όλες τις διατάξεις με τα 10 σκαμπό που δεν έχουν κολλητές πράσινες θέσεις, άρα όλες τις διατάξεις που δεν περιέχουν γειτονικούς πελάτες . Επομένως το πλήθος των επιτρεπόμενων διατάξεων είναι:
C(11-2χ+χ,χ)=C(11-χ,χ) για χ=1 έως 5
Γιατί όμως διαγράφτηκε; 😀😀
ΑπάντησηΔιαγραφή