1. Η Επιτροπή ενός μαθηματικού διαγωνισμού αποτελείται από 11 μέλη και τα θέματα του διαγωνισμού φυλάσσονται κλειδωμένα σε ένα κιβώτιο με κάμποσα λουκέτα.
Στα μέλη της Επιτροπής έχουν μοιραστεί ένας αριθμός αντικλειδιών με τρόπο ώστε:
α) κάθε αντικλείδι να ανοίγει ένα λουκέτο,
β) οποιαδήποτε 6 μέλη να αρκούν για να ανοίξουν το κιβώτιο και
γ) οποιαδήποτε 5 μέλη να μην αρκούν για να ανοίξουν το κιβώτιο.
Ποιος είναι ο ελάχιστος αριθμός των αντικλειδιών που έχουν μοιραστεί στα μέλη της Επιτροπής;
2. Έχουμε 15 μπαταρίες, από τις οποίες οι 8 γεμάτες και οι 7 άδειες, αλλά δεν μπορούμε να ξεχωρίσουμε τις πρώτες από τις δεύτερες.
Αν χρειάζονται 2 γεμάτες μπαταρίες για να λειτουργήσει ένας φακός, πόσες δοκιμές θα χρειαστούν το πολύ μέχρι να το καταφέρουμε με βεβαιότητα;
Το ίδιο ερώτημα με 14 μπαταρίες, από τις οποίες 7 γεμάτες και 7 άδειες.
2. Mε τους συνδυασμούς των 9 μπαταριών (για να υπάρχουν 2 τουλάχιστον καλές) ανά 2, δηλαδή 90.720 δοκιμές. Για το επόμενο ερώτημα η απάντηση είναι η ίδια, αφού ο αριθμός των άδειων μπαταριών δεν αλλάζει.
Πρόβλημα Νο.2 (α, β)
Λόγω των τύπων για την λύση όρα εδώ:
https://imgur.com/a/u8R4QIg
Διευκρίνιση για το πρόβλημα 2:
Οι δοκιμές γίνονται με βάση κάποιο σχέδιο που έχει στόχο να λειτουργήσει ο φακός με τις ελάχιστες δυνατές προσπάθειες. Το ζητούμενο λοιπόν είναι να βρούμε πόσες το πολύ μπορεί να είναι αυτές οι προσπάθειες, χωρίς να μας ενδιαφέρει να διαπιστώσουμε ποιες μπαταρίες ακριβώς είναι γεμάτες και ποιες άδειες.
2. Αν τις χωρίσω σε τριάδες θα μπορούσαν να υπάρξουν το πολύ 3 τριάδες με 2 άδειες και 1 γεμάτη. Από τις 2 άλλες τριάδες η μία θα είχε 2 γεμάτες και 1 άδεια, άρα θα έκανα 12 το πολύ προσπάθειες μέχρι να λειτουργήσει ο φακός.
2
Με 15 μπαταρίες
Αριθμούμε τις μπαταρίες από 1 ως 15.
1-2, 3-4, 5-6, 7-8, 9-10,11-12, 13-14, 15-1, 15-2
9 δοκιμές
Με 14 μπαταρίες
Αριθμούμε τις μπαταρίες από 1 ως 14.
1-2, 2-3, 3-4, 4-5, 5-6, 6-7, 7-8, 8-9, 9-10, 10-11, 11-12, 12 -13, 13-14, 14-1, 1-3, 2-4
16 δοκιμές
1. Το αντικλείδι 1 θα λείπει από τα μέλη 1-5 και τα υπόλοιπα μέλη θα το έχουν, δηλαδή θα το έχουν 6 μέλη. Το αντικλείδι 2 θα λείπει από τα μέλη 1-4 και 6 και τα υπόλοιπα μέλη θα το έχουν, δηλαδή θα το έχουν επίσης 6 μέλη. Δημιουργούμε έτσι όλους τους συνδυασμούς ελλείψεων, καθένας από τους οποίους πρέπει να είναι διαφορετικός από όλους τους άλλους. Φτιάχνουμε δηλαδή συνολικά C(11,5)=462 συνδυασμούς ελλείψεων και αυτός είναι και ο ελάχιστος αριθμός λουκέτων που πρέπει να χρησιμοποιηθούν. Ο ελάχιστος αριθμός αντικλειδιών που θα μοιραστούν είναι 462*6= 2772 αντικλείδια.
2. Αν Γ είναι οι γεμάτες μπαταρίες και Μ το σύνολό τους τότε πρέπει να χωρίσουμε τις μπαταρίες σε Γ-1 ομάδες, ώστε σύμφωνα με την αρχή του περιστερώνα να υπάρχει τουλάχιστον μία ομάδα με τουλάχιστον 2 μπαταρίες εντός της. Μετά απλώς προσπαθούμε να βρούμε 2 γεμάτες μπαταρίες της ομάδας που ανάβουν το φακό. Οι Μ μπαταρίες πρέπει να χωριστούν στις ομάδες ισομερώς κατά το δυνατόν.
Έτσι στην περίπτωση όπου Γ=8 και Μ=15 χωρίζουμε τις μπαταρίες σε 7 ομάδες με 3-2-2-2-2-2-2 μπαταρίες η κάθε μία και θα χρειαστούμε το πολύ 3+1+1+1+1+1+1 = 9 προσπάθειες για να ανάψουμε τον φακό.
Στην περίπτωση όπου Γ=7 και Μ=14 χωρίζουμε τις μπαταρίες σε 6 ομάδες με 3-3-2-2-2-2 μπαταρίες η κάθε μία και θα χρειαστούμε το πολύ 3+3+1+1+1+1 = 10 προσπάθειες για να ανάψουμε τον φακό.
Πρόβλημα 1
Αντιστοιχουμε κάθε δυνατή πεντάδα με ένα κλειδί του κιβωτίου το οποίο δεν το δίνουμε στην εν λόγω πεντάδα. Συνολικά υπάρχουν 462 πεντάδες.
Με αυτό τον τρόπο εξασφαλίζουμε ότι οποιαδήποτε πέντε άτομα δεν μπορούν να ανοίξουν τα 462 λουκέτα. Συνολικά μοιράζονται 462*6=2772 αντικλείδια.
Πρόβλημα 2
Περίπτωση 8-7
Δημιουργούμε ανα δυο ομάδες μπαταριών κ δοκιμάζουμε. Αν έχουμε 6 συνεχόμενες αποτυχίες σημαίνει ότι οι τρεις τελευταίες αποτελούνται από δυο γεμάτες κ μια άδεια. Δοκιμάζουμε ακόμη τρεις μέγιστο για να τοποθετηθούν δυο γεμάτες μπαταρίες. Συνολικά 9 προσπάθειες.
Περίπτωση 7-7
Ακολουθούμε την ίδια τακτική κ μετά από έξι αποτυχημένες προσπάθειες σημαίνει ότι οι δυο τελευταίες είναι μια άδεια κ μια γεμάτη. Παίρνουμε κ τις μπαταρίες της έκτης ομάδας που απέτυχε να ανάψει το φακό κ με τέσσερις προσπαθείες έχουμε τοποθετήσει δυο γεμάτες. Συνολικά 10 προσπάθειες.
1. Οι συνδυασμοί των 11 ανά 6 είναι 462, επομένως τόσα θα πρέπει να είναι τα λουκέτα. Το κάθε λουκέτο θα πρέπει να έχει τουλάχιστον 6 αντικλείδια, άρα εχουμε συνολικά 462*6=2.772 αντικλείδια, μοιρασμένα σε 2.772/11=252 αντικλείδια ο καθένας
2.Στη περίπτωση με τις 8+7 μπαταρίες, τις χωρίζουμε σε 6 ομάδες των 2 και μία των 3. Δοκιμάζουμε διαδοχικά τις 6 ομάδες των 2 μπαταριών. Αν αποτύχουν όλες, συμπεραίνουμε ότι σε κάθε μία από τις 6 αυτές ομάδες δεν μπορούν να υπάρχουν περισσότερες από μία γεμάτη μπαταρία. Αρα στη τελευταία ομάδα των 3 μπαταριών υπάρχουν τουλάχιστον 2 γεμάτες που με τρείς το πολύ προσπάθειες, ο φακός θα ανάψει. Μέγιστο σύνολο προσπαθειών 6+3=9
Στη περίπτωση με τις 7+7 μπαταρίες, τις χωρίζουμε σε 4 ομάδες των 2 και δύο ομάδες των 3. Δοκιμάζουμε τις 4 ομάδες των δύο μπαταριών (4 προσπάθειες) και αν αποτύχουμε, συνεχίζουμε με τη πρώτη ομάδα των 3 μπαταριών (μέγιστο 3 προσπάθειες). Αν αποτύχουμε και πάλι, ειμαστε σίγουροι ότι στη τελευταία ομάδα των 3 μπαταριών υπάρχουν τουλάχιστον 2 γεμάτες και με μέγιστο άλλες τρεις προσπάθειες, ο φακός ανάβει. Μέγιστο σύνολο προσπαθειών 4+3+3=10
Ευχαριστώ τους φίλους, εύχομαι χρόνια πολλά σε όλους και ιδιαιτέρως στους εορτάζοντες!
2772, 9 και 10 οι σωστές απαντήσεις και τα θερμά συγχαρητήριά μου για τις πολύ όμορφες λύσεις!
Εξαιρετικές λύσεις!