Ένα καινούργιο ξενοδοχείο διαθέτει 10 δωμάτια. Ο ξενοδόχος μπέρδεψε τα 10 κλειδιά τους πριν προλάβει να τους περάσει τους αριθμούς των δωματίων και έτσι τώρα δεν έχει κανένα τρόπο να τα αντιστοιχίσει στις πόρτες που ανοίγουν, παρά μόνο δοκιμάζοντάς τα πάνω τους.
Ποιος είναι ο μέγιστος αριθμός δοκιμών που μπορεί να χρειαστούν προκειμένου να αντιστοιχίσει το κάθε κλειδί στη σωστή πόρτα;
Ποιος είναι ο μέγιστος αριθμός δοκιμών που μπορεί να χρειαστούν προκειμένου να αντιστοιχίσει το κάθε κλειδί στη σωστή πόρτα;
6 σχόλια:
Λύση:
Το 1ο κλειδί δοκιμάζεται με τη σειρά σε κάθε πόρτα. Αν δεν μπορεί να ανοίξει τις 9 πρώτες πόρτες τότε αυτό το κλειδί αντιστοιχεί αναγκαστικά στη 10η πόρτα.
Το 2ο κλειδί δοκιμάζεται με τη σειρά σε κάθε μία από τις υπόλοιπες πόρτες. Αν δεν μπορεί να ανοίξει τις 8 πρώτες πόρτες τότε αυτό το κλειδί αντιστοιχεί αναγκαστικά στην 9η πόρτα.
Ακολουθώντας την ίδια λογική γίνεται φανερό ότι ο μέγιστος αριθμός δοκιμών που μπορεί να χρειαστούν είναι 9+8+7+6+5+4+3+2+1 = 45 δοκιμές.
Αυτη θα ηταν η πρωτη σκεψη καποιου, αλλα πιστευω πως δεν ισχυει αν θελουμε αποκλειστικα και μονο τον ΜΕΓΙΣΤΟ αριθμο δοκιμων, στον οποιο βεβαια μπορουμε να φτασουμε αν σκεφτομε με τον πιο αντι-παραγωγικο τροπο.
Εστω πορτες 1-10 και αντιστοιχα κλειδια 1-10. Δοκιμαζουμε ολα τα κλειδια εκτος του 1 και του 2 στην πορτα 1, ετσι δεν ξερουμε ποιο απτα δυο κλειδια λειτουργει στην πορτα 1. Προχωραμε, χρησιμοποιωντας ολα τα κλειδια εκτος του 1 και του 2 παλι στην πορτα 2. Παλι δεν ξερουμε ποιο παει που σιγουρα. Ετσι συνεχιζουμε μεχρι το τελος, οποτε εχουμε 8*10= 80 μεχρι τωρα. Αλλα ακομα δεν εχουμε αντιστοιχισει κανενα κλειδι με την πορτα του. Παιρνουμε λοιπον με την σειρα και δοκιμαζουμε το λαθος απτα δυο πιθανα κλειδια που μενουν μεχρι να μην μεινει κανενα αδεσποτο, οπου αναλογα με το πως δοκιμασαμε τα κλειδια προηγουμενως, και ποια δυο κλειδια εχουν μεινει για καθε πορτα, θα μπορουσε να φτασει μεχρι και περιπου 5-6 δοκιμες ακομα, αρα μπορουμε να εχουμε μεχρι 85 περιπου δοκιμες στην χειροτερη περιπτωση που αποφασισουμε πως δεν εχουμε αλλες δουλειες απτο να δοκιμαζουμε κλειδια σε πορτες.
Ισως τα νουμερα δεν ειναι ακριβως τοσα, δεν εκατσα να τα υπολογισω ακριβως, αλλα ακομα και αν ειναι αισθητα λιγοτερα απο 85, πιθανοτατα να ειναι πανω απο 45.
@Pericles Petrides: Στη λύση που προτείνω εννοείται πως εφαρμόζεται η καλύτερη δυνατή στρατηγική, η οποία θα οδηγήσει στο επιθυμητό αποτέλεσμα σε έναν αριθμό δοκιμών από 9 (αν είμαστε σούπερ τυχεροί) μέχρι 45 (αν είμαστε σούπερ άτυχοι).
Με την προϋπόθεση να μην δοκιμάσω κάποιο κλειδί πάνω από μια φορά στην ίδια πόρτα και να μην ελέγξω κάποια πόρτα/κλειδί για την οποία ήδη ξέρω τη σωστή αντιστοίχιση, ο αριθμός των δοκιμών δεν μπορεί να ξεπεράσει τις 45, εκτός κι αν δεν ήμασταν σίγουροι ότι τα κλειδιά ανοίγουν όντως τις πόρτες, οπότε θα χρειαζόμασταν 10 ακόμη, το πολύ, προσπάθειες.
Οι προϋποθέσεις αυτές είναι εντελώς λογικές.
Ο πιο οικονομικός τρόπος είναι να δοκιμάζει κλειδιά πάνω στην πόρτα κι όχι κλειδί στις πόρτες. Τον ξεθεωσατε τον άνθρωπο... 9 κλειδιά στην πρώτη, 8 στη δεύτερη κλπ 1 στην ενατη και τέλος.
Οι περισσότερες δυνατές προσπάθειες είναι 100. Βάλτε κάθε κλειδί που ανοίγει μια πόρτα μπρος στην επόμενη πόρτα και αρχίστε δοκιμές σε μορφή ρεβολβερ. Θα δοκιμάσουμε όλα τα κλειδιά από μια φορά σε κάθε κλειδαριά μέχρι να καταλήξει στη δέκατη δοκιμή στη σωστή όπως όλα τα άλλα.
Έστω ότι πετυχαίνουμε το κατάλληλο κλειδί με την τελευταία προσπάθεια. Άρα πρώτη πόρτα 10 προσπάθειες. Μας μένουν 9 κλειδιά. Δεύτερη πόρτα με την τελευταία προσπάθεια (9 προσπάθειες). Άρα έχουμε 10+9+8+7+6+5+4+3+2=54 προσπάθειες. Το τελευταίο κλειδί εκ των πραγμάτων ταιριαζει στην τελευταία πόρτα άρα δεν θεωρείται δοκιμή και δεν προστίθεται στις συνολικές προσπάθειες.
Μόνο για μέλη: Γράψτε την απάντησή σας