Πρόβλημα Φυλακισμένων
Πρόβλημα Φυλακισμένων
Έστω ότι υπάρχουν 100 φυλακισμένοι σε 100 κελιά που κάθε κελί περιέχει ακριβώς έναν κρατούμενο και οι πόρτες των κελιών είναι όλες κλειδωμένες.
Λέμε ότι ένας φύλακας αλλάζει την κατάσταση του κελιού αν όταν είναι κλειδωμένο το ξεκλειδώνει και αν είναι ξεκλείδωτο το κλειδώνει.
Μετά ο φύλακας ξεκλειδώνει όλα τα κελιά και στη συνέχεια κλειδώνει τα κελιά που είναι πολλαπλάσια του 2. Συνεχίζει και αλλάζει την κατάσταση των κελιών που είναι πολλαπλάσια του 3 και μετά αλλάζει την κατάσταση των κελιών που είναι πολλαπλάσια του 4 και συνεχίζει μέχρι τα πολλαπλάσια του 100.
Πόσες πόρτες θα μείνουν ξεκλείδωτες στο τέλος;
Λέμε ότι ένας φύλακας αλλάζει την κατάσταση του κελιού αν όταν είναι κλειδωμένο το ξεκλειδώνει και αν είναι ξεκλείδωτο το κλειδώνει.
Μετά ο φύλακας ξεκλειδώνει όλα τα κελιά και στη συνέχεια κλειδώνει τα κελιά που είναι πολλαπλάσια του 2. Συνεχίζει και αλλάζει την κατάσταση των κελιών που είναι πολλαπλάσια του 3 και μετά αλλάζει την κατάσταση των κελιών που είναι πολλαπλάσια του 4 και συνεχίζει μέχρι τα πολλαπλάσια του 100.
Πόσες πόρτες θα μείνουν ξεκλείδωτες στο τέλος;
Κωνσταντίνος Σμπώκος
Λέξεις Κλειδιά:
-
- Επιμελητής
- Δημοσιεύσεις: 15778
- Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am
Re: Πρόβλημα Φυλακισμένων
Καλό.stranger έγραψε: ↑Δευ Σεπ 07, 2020 12:27 amΈστω ότι υπάρχουν 100 φυλακισμένοι σε 100 κελιά που κάθε κελί περιέχει ακριβώς έναν κρατούμενο και οι πόρτες των κελιών είναι όλες κλειδωμένες.
Λέμε ότι ένας φύλακας αλλάζει την κατάσταση του κελιού αν όταν είναι κλειδωμένο το ξεκλειδώνει και αν είναι ξεκλείδωτο το κλειδώνει.
Μετά ο φύλακας ξεκλειδώνει όλα τα κελιά και στη συνέχεια κλειδώνει τα κελιά που είναι πολλαπλάσια του 2. Συνεχίζει και αλλάζει την κατάσταση των κελιών που είναι πολλαπλάσια του 3 και μετά αλλάζει την κατάσταση των κελιών που είναι πολλαπλάσια του 4 και συνεχίζει μέχρι τα πολλαπλάσια του 100.
Πόσες πόρτες θα μείνουν ξεκλείδωτες στο τέλος;
Για κάθε διαιρέτη του κελιού υπ' αριθμόν , παρατηρούμε ότι ο (υποχρεωτικά ακέραιος) είναι επίσης διαιρέτης του . Αν είναι διαφορετικός, , σημαίνει ότι ο φύλακας άλλαξε την κατάσταση της πόρτας δύο φορές, δηλαδή ουσιαστικά καμία αλλαγή. Αντιθέτως, αν , ισοδύμναμα τέλειο τετράγωνο, η αλλαγή κατάστασης έγινε μία φορά.
Θέλω να πω: Για έναν αριθμό μη τέλειο τετράγωνο, οι διαιρέτες ζευγαρώνουν. Π.χ. του 12 είναι τα ζεύγη και και . Αντίθετα για τέλεια τετράγωνα κάποιος μένει χωρίς ζευγάρι. Π.χ. του έχουμε τα ζεύγη και αλλά ο μένει χωρίς ταίρι.
Συμπέρασμα: Τα κελιά που δεν είναι τέλεια τετράγωνα θα μείνουν στο τέλος κλειστά, ενώ τα τέλεια τετράγωνα θα μείνουν ανοικτά. Με άλλα λόγια τα ανοικτά θα είναι τα και μόνον αυτά τα δέκα.
Re: Πρόβλημα Φυλακισμένων
ΜαMihalis_Lambrou έγραψε: ↑Δευ Σεπ 07, 2020 2:14 amΜε άλλα λόγια τα ανοικτά θα είναι τα και μόνον αυτά τα δέκα.
στην πρώτη φάση ξεκλειδώνει τα πάντα και μετά
κλειδώνει τα κελιά
στην δεύτερη φάση άλλαζει την κατάσταση των κελιών
Δηλαδή ξεκλείδωσε το κελί που ήταν κλειδωμένο στην 1η φάση
Μετά αλλάζει την κατάσταση στα κελιά
που δεν επηρεάζει το κελί
Άρα το κελί πιστεύω πως θεωρείται ανοιχτό.
-
- Επιμελητής
- Δημοσιεύσεις: 15778
- Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am
Re: Πρόβλημα Φυλακισμένων
Το λάθος σου είναι εκεί που σημείωσα.
Μετά από τα κλειδώματα και ξεκλειδώματα που ανέφερες έχει τα
που δεν επηρεάζουν το κελί και μετά έχει τα
που το επηρεάζουν και ξέχασες να το προσμετρήσεις.
- george visvikis
- Επιμελητής
- Δημοσιεύσεις: 13334
- Εγγραφή: Παρ Νοέμ 01, 2013 9:35 am
Re: Πρόβλημα Φυλακισμένων
Όταν πάει στα πολλαπλάσια του θα κλειδωθεί ξανά!nikhtas30 έγραψε: ↑Δευ Σεπ 07, 2020 3:18 amΜαMihalis_Lambrou έγραψε: ↑Δευ Σεπ 07, 2020 2:14 amΜε άλλα λόγια τα ανοικτά θα είναι τα και μόνον αυτά τα δέκα.
στην πρώτη φάση ξεκλειδώνει τα πάντα και μετά
κλειδώνει τα κελιά
στην δεύτερη φάση άλλαζει την κατάσταση των κελιών
Δηλαδή ξεκλείδωσε το κελί που ήταν κλειδωμένο στην 1η φάση
Μετά αλλάζει την κατάσταση στα κελιά
που δεν επηρεάζει το κελί
Άρα το κελί πιστεύω πως θεωρείται ανοιχτό.
Βλέπω ότι πληκτρολογούσαμε ταυτόχρονα με τον Μιχάλη.
Re: Πρόβλημα Φυλακισμένων
Μια κάπως διαφορετική λύση είναι η εξής:
Παρατηρούμε ότι το κελί μένει ξεκλείδωτο αν και μόνο αν ο είναι περιττός.
Όμως αν όπου πρώτοι τότε .
Άρα ο είναι περιττός αν και μόνο αν όλοι οι είναι περιττοί αν και μόνο αν όλοι οι είναι άρτιοι αν και μόνο αν ο είναι τέλειο τετράγωνο.
Παρατηρούμε ότι το κελί μένει ξεκλείδωτο αν και μόνο αν ο είναι περιττός.
Όμως αν όπου πρώτοι τότε .
Άρα ο είναι περιττός αν και μόνο αν όλοι οι είναι περιττοί αν και μόνο αν όλοι οι είναι άρτιοι αν και μόνο αν ο είναι τέλειο τετράγωνο.
Κωνσταντίνος Σμπώκος
Re: Πρόβλημα Φυλακισμένων
Κύριε Λάμπου, νομίζω ότι υπάρχει ένα λάθος εδώ πέρα.Mihalis_Lambrou έγραψε: ↑Δευ Σεπ 07, 2020 2:14 amΓια κάθε διαιρέτη του κελιού υπ' αριθμόν , παρατηρούμε ότι ο (υποχρεωτικά ακέραιος) είναι επίσης διαιρέτης του . Αν είναι διαφορετικός, , σημαίνει ότι ο φύλακας άλλαξε την κατάσταση της πόρτας δύο φορές, δηλαδή ουσιαστικά καμία αλλαγή.
Αν για κάθε διαιρέτες του (κάτι που δεν συμβαίνει ποτέ) τότε άλλαξε την κατάσταση της πόρτας άρτιες φορές.
Η σωστή λύση είναι στα παρακάτω.
stranger έγραψε: ↑Δευ Σεπ 07, 2020 10:40 am.
Μια κάπως διαφορετική λύση είναι η εξής:
Παρατηρούμε ότι το κελί μένει ξεκλείδωτο αν και μόνο αν ο είναι περιττός.
Όμως αν όπου πρώτοι τότε .
Άρα ο είναι περιττός αν και μόνο αν όλοι οι είναι περιττοί αν και μόνο αν όλοι οι είναι άρτιοι αν και μόνο αν ο είναι τέλειο τετράγωνο.
Κωνσταντίνος Σμπώκος
-
- Επιμελητής
- Δημοσιεύσεις: 15778
- Εγγραφή: Κυρ Δεκ 21, 2008 2:04 am
Re: Πρόβλημα Φυλακισμένων
Ίσως δεν βλέπω κάτι αλλά δεν ισχυρίστηκα το παραπάνω. Έχω δύο διαφορές: Η μία είναι ότι δεν έχω και , αλλά μόνο , άσε που δεν έχω καθολικό ποσοδείκτη. Η δεύτερη είναι ότι για κάποια (σταθερά) μπορεί να υπάρχει κάποιος διαιρέτης τους με . Για παράδειγμα αυτό συμβαίνει για τον διαιρέτη του , εδώ , ενώ για άλλους αριθμούς (τα μη τέλεια τετράγωνα) είναι πάντα . Π.χ. για , o διαιρέτης του δίνει άλλον διαιρέτη, τον , και βέβαια .
Re: Πρόβλημα Φυλακισμένων
Έχετε δίκιο κύριε Λάμπρου. Δικό μου λάθος.
Ας το δούμε φορμαλιστικά.Αν ορίσουμε τα σύνολα και τότε η συνάρτηση με είναι ένα προς ένα και επί.
Άρα .
Αν δεν υπάρχει διαιρέτης του ώστε τότε εύκολα βλέπουμε ότι .
Άρα ο είνα άρτιος.
Αν υπάρχει διαιρέτης του ώστε τότε , οπότε ο είναι περιττός.
Άρα ο είναι περιττός αν και μόνο αν ο είναι τετράγωνο.
Ουσιαστικά, είναι η φορμαλιστική δικαιολόγιση της ιδέας του κυρίου Λάμπρου.
Ας το δούμε φορμαλιστικά.Αν ορίσουμε τα σύνολα και τότε η συνάρτηση με είναι ένα προς ένα και επί.
Άρα .
Αν δεν υπάρχει διαιρέτης του ώστε τότε εύκολα βλέπουμε ότι .
Άρα ο είνα άρτιος.
Αν υπάρχει διαιρέτης του ώστε τότε , οπότε ο είναι περιττός.
Άρα ο είναι περιττός αν και μόνο αν ο είναι τετράγωνο.
Ουσιαστικά, είναι η φορμαλιστική δικαιολόγιση της ιδέας του κυρίου Λάμπρου.
Κωνσταντίνος Σμπώκος
-
- Δημοσιεύσεις: 3601
- Εγγραφή: Πέμ Φεβ 27, 2014 9:05 am
- Τοποθεσία: ΧΑΛΚΙΔΑ- ΑΘΗΝΑ-ΚΡΗΤΗ
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 2 επισκέπτες