Το παιγνίδι μαντέματος ψευτών (lίar's guessίng game) είναι ένα παιγνίδι που παίζεται μεταξύ δύο παικτών $Α$ και $Β$. Οι κανόνες του παιγνιδιού εξαρτώνται από δύο θετικούς ακέραιους $k$ και $n$ που είναι γνωστοί και στους δύο παίκτες.
Κατά την έναρξη του παιγνιδιού ο παίκτης $Α$ επιλέγει ακέραιους $χ$ και $Ν$ με $1\leq{χ}\leq{Ν}$. Ο παίκτης $Α$ κρατάει τον ακέραιο $χ$ μυστικό και λέει με ειλικρίνεια τον ακέραιο $Ν$ στον παίκτη $Β$.
Ο παίκτης $Β$ τώρα προσπαθεί να πάρει πληροφορίες για τον ακέραιο $χ$ με ερωτήσεις προς τον παίκτη $Α$ ως εξής: κάθε ερώτηση συνίσταται στον καθορισμό από τον παίκτη $Β$ ενός τυχαίου συνόλου $S$ (ενδεχομένως να είναι ένα που έχει ήδη καθοριστεί σε κάποια προηγούμενη ερώτηση) θετικών ακέραιων και στο να ζητήσει από τον $Α$ να του πει, αν ο $χ$ ανήκει στο σύνολο $S$. Ο παίκτης $Β $ μπορεί να κάνει τέτοιες ερωτήσεις όσες επιθυμεί.
Μετά από κάθε ερώτηση ο παίκτης $Α$ πρέπει αμέσως να την απαντήσει με ένα ναι ή με ένα όχι, αλλά του επιτρέπεται να πει ψέματα όσες φορές θέλει.
Ο μόνος περιορισμός του είναι ότι: μεταξύ οποιωνδήποτε $k + 1$ διαδοχικών απαντήσεων, σε μία τουλάχιστον απάντηση πρέπει να πει την αλήθεια. Αφού ο $Β$ έχει κάνει όσες ερωτήσεις επιθυμεί, πρέπει να καθορίσει ένα σύνολο $Χ$ το οποίο πρέπει να περιέχει το πολύ n θετικούς ακέραιους.
Αν ο $χ$ ανήκει στο σύνολο $Χ$, τότε ο $Β$ κερδίζει, διαφορετικά, χάνει. Να αποδείξετε ότι:
1. Αν $n\geq {2^k}$, τότε ο $Β$ έχει στρατηγική νίκης.
2. Για κάθε αρκετά μεγάλο $k$, υπάρχει ακέραιος $n\geq {1, 99^k}$, τέτοιος ώστε ο $Β$ δεν μπορεί να έχει στρατηγική νίκης.
53η Διεθνής Μαθηματική Ολυμπιάδα 2012, Αργεντινή
(Πρόβλημα 3ο, προτάθηκε από τον Καναδά)
Δεν υπάρχουν σχόλια:
Δημοσίευση σχολίου