Πρόβλημα Φυλακισμένων

[stranger]

Έστω ότι υπάρχουν 100 φυλακισμένοι σε 100 κελιά που κάθε κελί περιέχει ακριβώς έναν κρατούμενο και οι πόρτες των κελιών είναι όλες κλειδωμένες.
Λέμε ότι ένας φύλακας αλλάζει την κατάσταση του κελιού αν όταν είναι κλειδωμένο το ξεκλειδώνει και αν είναι ξεκλείδωτο το κλειδώνει.
Μετά ο φύλακας ξεκλειδώνει όλα τα κελιά και στη συνέχεια κλειδώνει τα κελιά που είναι πολλαπλάσια του 2. Συνεχίζει και αλλάζει την κατάσταση των κελιών που είναι πολλαπλάσια του 3 και μετά αλλάζει την κατάσταση των κελιών που είναι πολλαπλάσια του 4 και συνεχίζει μέχρι τα πολλαπλάσια του 100.
Πόσες πόρτες θα μείνουν ξεκλείδωτες στο τέλος;

[Mihalis_Lambrou]

Έστω ότι υπάρχουν 100 φυλακισμένοι σε 100 κελιά που κάθε κελί περιέχει ακριβώς έναν κρατούμενο και οι πόρτες των κελιών είναι όλες κλειδωμένες.
Λέμε ότι ένας φύλακας αλλάζει την κατάσταση του κελιού αν όταν είναι κλειδωμένο το ξεκλειδώνει και αν είναι ξεκλείδωτο το κλειδώνει.
Μετά ο φύλακας ξεκλειδώνει όλα τα κελιά και στη συνέχεια κλειδώνει τα κελιά που είναι πολλαπλάσια του 2. Συνεχίζει και αλλάζει την κατάσταση των κελιών που είναι πολλαπλάσια του 3 και μετά αλλάζει την κατάσταση των κελιών που είναι πολλαπλάσια του 4 και συνεχίζει μέχρι τα πολλαπλάσια του 100.
Πόσες πόρτες θα μείνουν ξεκλείδωτες στο τέλος;

Καλό.

Για κάθε διαιρέτη του κελιού υπ' αριθμόν , παρατηρούμε ότι ο (υποχρεωτικά ακέραιος) είναι επίσης διαιρέτης του . Αν είναι διαφορετικός, , σημαίνει ότι ο φύλακας άλλαξε την κατάσταση της πόρτας δύο φορές, δηλαδή ουσιαστικά καμία αλλαγή. Αντιθέτως, αν , ισοδύμναμα τέλειο τετράγωνο, η αλλαγή κατάστασης έγινε μία φορά.

Θέλω να πω: Για έναν αριθμό μη τέλειο τετράγωνο, οι διαιρέτες ζευγαρώνουν. Π.χ. του 12 είναι τα ζεύγη και και . Αντίθετα για τέλεια τετράγωνα κάποιος μένει χωρίς ζευγάρι. Π.χ. του έχουμε τα ζεύγη και αλλά ο μένει χωρίς ταίρι.

Συμπέρασμα: Τα κελιά που δεν είναι τέλεια τετράγωνα θα μείνουν στο τέλος κλειστά, ενώ τα τέλεια τετράγωνα θα μείνουν ανοικτά. Με άλλα λόγια τα ανοικτά θα είναι τα και μόνον αυτά τα δέκα.

[User#0000]

Με άλλα λόγια τα ανοικτά θα είναι τα και μόνον αυτά τα δέκα.

Μα
στην πρώτη φάση ξεκλειδώνει τα πάντα και μετά
κλειδώνει τα κελιά

στην δεύτερη φάση άλλαζει την κατάσταση των κελιών
Δηλαδή ξεκλείδωσε το κελί που ήταν κλειδωμένο στην 1η φάση

Μετά αλλάζει την κατάσταση στα κελιά
που δεν επηρεάζει το κελί

Άρα το κελί πιστεύω πως θεωρείται ανοιχτό.

[User#0000]

ΕΜΦΑΝΙΣΗ ΚΕΙΜΕΝΟΥ

Ίσως πιο μετά βάλω την λύση ολοκληρωμένη για την ώρα θεωρώ πως είναι ανοιχτές πόρτες

[Mihalis_Lambrou]

Μετά αλλάζει την κατάσταση στα κελιά
που δεν επηρεάζει το κελί

Άρα το κελί πιστεύω πως θεωρείται ανοιχτό.

Το λάθος σου είναι εκεί που σημείωσα.

Μετά από τα κλειδώματα και ξεκλειδώματα που ανέφερες έχει τα

που δεν επηρεάζουν το κελί και μετά έχει τα

που το επηρεάζουν και ξέχασες να το προσμετρήσεις.

[george visvikis]

Με άλλα λόγια τα ανοικτά θα είναι τα και μόνον αυτά τα δέκα.

Μα
στην πρώτη φάση ξεκλειδώνει τα πάντα και μετά
κλειδώνει τα κελιά

στην δεύτερη φάση άλλαζει την κατάσταση των κελιών
Δηλαδή ξεκλείδωσε το κελί που ήταν κλειδωμένο στην 1η φάση

Μετά αλλάζει την κατάσταση στα κελιά
που δεν επηρεάζει το κελί

Άρα το κελί πιστεύω πως θεωρείται ανοιχτό.

Όταν πάει στα πολλαπλάσια του θα κλειδωθεί ξανά!

Βλέπω ότι πληκτρολογούσαμε ταυτόχρονα με τον Μιχάλη.

[stranger]

Μια κάπως διαφορετική λύση είναι η εξής:
Παρατηρούμε ότι το κελί μένει ξεκλείδωτο αν και μόνο αν ο είναι περιττός.
Όμως αν όπου πρώτοι τότε .
Άρα ο είναι περιττός αν και μόνο αν όλοι οι είναι περιττοί αν και μόνο αν όλοι οι είναι άρτιοι αν και μόνο αν ο είναι τέλειο τετράγωνο.

[stranger]

Για κάθε διαιρέτη του κελιού υπ' αριθμόν , παρατηρούμε ότι ο (υποχρεωτικά ακέραιος) είναι επίσης διαιρέτης του . Αν είναι διαφορετικός, , σημαίνει ότι ο φύλακας άλλαξε την κατάσταση της πόρτας δύο φορές, δηλαδή ουσιαστικά καμία αλλαγή.

Κύριε Λάμπου, νομίζω ότι υπάρχει ένα λάθος εδώ πέρα.
Αν για κάθε διαιρέτες του (κάτι που δεν συμβαίνει ποτέ) τότε άλλαξε την κατάσταση της πόρτας άρτιες φορές.
Η σωστή λύση είναι στα παρακάτω.

.
Μια κάπως διαφορετική λύση είναι η εξής:
Παρατηρούμε ότι το κελί μένει ξεκλείδωτο αν και μόνο αν ο είναι περιττός.
Όμως αν όπου πρώτοι τότε .
Άρα ο είναι περιττός αν και μόνο αν όλοι οι είναι περιττοί αν και μόνο αν όλοι οι είναι άρτιοι αν και μόνο αν ο είναι τέλειο τετράγωνο.

[Mihalis_Lambrou]

Αν για κάθε διαιρέτες του (κάτι που δεν συμβαίνει ποτέ)

Ίσως δεν βλέπω κάτι αλλά δεν ισχυρίστηκα το παραπάνω. Έχω δύο διαφορές: Η μία είναι ότι δεν έχω και , αλλά μόνο , άσε που δεν έχω καθολικό ποσοδείκτη. Η δεύτερη είναι ότι για κάποια (σταθερά) μπορεί να υπάρχει κάποιος διαιρέτης τους με . Για παράδειγμα αυτό συμβαίνει για τον διαιρέτη του , εδώ , ενώ για άλλους αριθμούς (τα μη τέλεια τετράγωνα) είναι πάντα . Π.χ. για , o διαιρέτης του δίνει άλλον διαιρέτη, τον , και βέβαια .

[stranger]

Έχετε δίκιο κύριε Λάμπρου. Δικό μου λάθος.
Ας το δούμε φορμαλιστικά.Αν ορίσουμε τα σύνολα και τότε η συνάρτηση με είναι ένα προς ένα και επί.
Άρα .
Αν δεν υπάρχει διαιρέτης του ώστε τότε εύκολα βλέπουμε ότι .
Άρα ο είνα άρτιος.
Αν υπάρχει διαιρέτης του ώστε τότε , οπότε ο είναι περιττός.
Άρα ο είναι περιττός αν και μόνο αν ο είναι τετράγωνο.
Ουσιαστικά, είναι η φορμαλιστική δικαιολόγιση της ιδέας του κυρίου Λάμπρου.

[ΠΑΠΑΔΟΠΟΥΛΟΣ ΣΤΑΥΡΟΣ]

Εχω μια απορία.
Τι σχέση έχει το θέμα με ΣΤΑΤΙΣΤΙΚΗ-ΠΙΘΑΝΟΤΗΤΕΣ;