Γίνε μέλος στο grifoi.org

Στους γρίφους με τη σήμανση ".Άλυτοι 1-100" μπορούν να στέλνουν τις λύσεις τους μόνο τα Μέλη του site grifoi.org. Πληροφορίες για το πως θα γίνετε μέλος μπορείτε να διαβάσετε εδώ.

Σάββατο, 4 Ιανουαρίου 2014

Λογικής - Αντιστοίχιση κλειδιών (***)

Ένα καινούργιο ξενοδοχείο διαθέτει 10 δωμάτια. Ο ξενοδόχος μπέρδεψε τα 10 κλειδιά τους πριν προλάβει να τους περάσει τους αριθμούς των δωματίων και έτσι τώρα δεν έχει κανένα τρόπο να τα αντιστοιχίσει στις πόρτες που ανοίγουν, παρά μόνο δοκιμάζοντάς τα πάνω τους.
Ποιος είναι ο μέγιστος αριθμός δοκιμών που μπορεί να χρειαστούν προκειμένου να αντιστοιχίσει το κάθε κλειδί στη σωστή πόρτα;

4 σχόλια:

pantsik είπε...

Λύση:

Το 1ο κλειδί δοκιμάζεται με τη σειρά σε κάθε πόρτα. Αν δεν μπορεί να ανοίξει τις 9 πρώτες πόρτες τότε αυτό το κλειδί αντιστοιχεί αναγκαστικά στη 10η πόρτα.
Το 2ο κλειδί δοκιμάζεται με τη σειρά σε κάθε μία από τις υπόλοιπες πόρτες. Αν δεν μπορεί να ανοίξει τις 8 πρώτες πόρτες τότε αυτό το κλειδί αντιστοιχεί αναγκαστικά στην 9η πόρτα.
Ακολουθώντας την ίδια λογική γίνεται φανερό ότι ο μέγιστος αριθμός δοκιμών που μπορεί να χρειαστούν είναι 9+8+7+6+5+4+3+2+1 = 45 δοκιμές.

Pericles Petrides είπε...

Αυτη θα ηταν η πρωτη σκεψη καποιου, αλλα πιστευω πως δεν ισχυει αν θελουμε αποκλειστικα και μονο τον ΜΕΓΙΣΤΟ αριθμο δοκιμων, στον οποιο βεβαια μπορουμε να φτασουμε αν σκεφτομε με τον πιο αντι-παραγωγικο τροπο.
Εστω πορτες 1-10 και αντιστοιχα κλειδια 1-10. Δοκιμαζουμε ολα τα κλειδια εκτος του 1 και του 2 στην πορτα 1, ετσι δεν ξερουμε ποιο απτα δυο κλειδια λειτουργει στην πορτα 1. Προχωραμε, χρησιμοποιωντας ολα τα κλειδια εκτος του 1 και του 2 παλι στην πορτα 2. Παλι δεν ξερουμε ποιο παει που σιγουρα. Ετσι συνεχιζουμε μεχρι το τελος, οποτε εχουμε 8*10= 80 μεχρι τωρα. Αλλα ακομα δεν εχουμε αντιστοιχισει κανενα κλειδι με την πορτα του. Παιρνουμε λοιπον με την σειρα και δοκιμαζουμε το λαθος απτα δυο πιθανα κλειδια που μενουν μεχρι να μην μεινει κανενα αδεσποτο, οπου αναλογα με το πως δοκιμασαμε τα κλειδια προηγουμενως, και ποια δυο κλειδια εχουν μεινει για καθε πορτα, θα μπορουσε να φτασει μεχρι και περιπου 5-6 δοκιμες ακομα, αρα μπορουμε να εχουμε μεχρι 85 περιπου δοκιμες στην χειροτερη περιπτωση που αποφασισουμε πως δεν εχουμε αλλες δουλειες απτο να δοκιμαζουμε κλειδια σε πορτες.
Ισως τα νουμερα δεν ειναι ακριβως τοσα, δεν εκατσα να τα υπολογισω ακριβως, αλλα ακομα και αν ειναι αισθητα λιγοτερα απο 85, πιθανοτατα να ειναι πανω απο 45.

pantsik είπε...

@Pericles Petrides: Στη λύση που προτείνω εννοείται πως εφαρμόζεται η καλύτερη δυνατή στρατηγική, η οποία θα οδηγήσει στο επιθυμητό αποτέλεσμα σε έναν αριθμό δοκιμών από 9 (αν είμαστε σούπερ τυχεροί) μέχρι 45 (αν είμαστε σούπερ άτυχοι).

swt είπε...

Με την προϋπόθεση να μην δοκιμάσω κάποιο κλειδί πάνω από μια φορά στην ίδια πόρτα και να μην ελέγξω κάποια πόρτα/κλειδί για την οποία ήδη ξέρω τη σωστή αντιστοίχιση, ο αριθμός των δοκιμών δεν μπορεί να ξεπεράσει τις 45, εκτός κι αν δεν ήμασταν σίγουροι ότι τα κλειδιά ανοίγουν όντως τις πόρτες, οπότε θα χρειαζόμασταν 10 ακόμη, το πολύ, προσπάθειες.
Οι προϋποθέσεις αυτές είναι εντελώς λογικές.