Μαντέψτε ποιος λέει ψέμματα

Το παιγνίδι μαντέματος ψευτών (lίar's guessίng game) είναι ένα παιγνίδι που παίζεται μεταξύ δύο παικτών ${\rm A}$ και ${\rm B}$. Οι κανόνες του παιγνιδιού εξαρτώνται από δύο θετικούς ακέραιους $k$ και $n$ που είναι γνωστοί και στους δύο παίκτες.

Κατά την έναρξη του παιγνιδιού ο παίκτης ${\rm A}$ επιλέγει ακέραιους $\chi$ και ${\rm N}$ με $1\le \chi \le {\rm N}$. Ο παίκτης ${\rm A}$ κρατάει τον ακέραιο $\chi$ μυστικό και λέει με ειλικρίνεια τον ακέραιο ${\rm N}$ στον παίκτη ${\rm B}$.

Ο παίκτης ${\rm B}$ τώρα προσπαθεί να πάρει πληροφορίες για τον ακέραιο $\chi$ με ερωτήσεις προς τον παίκτη ${\rm A}$ ως εξής: κάθε ερώτηση συνίσταται στον καθορισμό από τον παίκτη ${\rm B}$ ενός τυχαίου συνόλου $S$ (ενδεχομένως να είναι ένα που έχει ήδη καθοριστεί σε κάποια προηγούμενη ερώτηση) θετικών ακέραιων και στο να ζητήσει από τον ${\rm A}$ να του πει, αν ο $\chi$ ανήκει στο σύνολο $S$. Ο παίκτης ${\rm B}$ μπορεί να κάνει τέτοιες ερωτήσεις όσες επιθυμεί. 

Μετά από κάθε ερώτηση ο παίκτης ${\rm A}$ πρέπει αμέσως να την απαντήσει με ένα ναι ή με ένα όχι, αλλά του επιτρέπεται να πει ψέματα όσες φορές θέλει.

Ο μόνος περιορισμός του είναι ότι: μεταξύ οποιωνδήποτε $k+1$ διαδοχικών απαντήσεων, σε μία τουλάχιστον απάντηση πρέπει να πει την αλήθεια. Αφού ο ${\rm B}$ έχει κάνει όσες ερωτήσεις επιθυμεί, πρέπει να καθορίσει ένα σύνολο ${\rm X}$ το οποίο πρέπει να περιέχει το πολύ n θετικούς ακέραιους. 

Αν ο $\chi$ ανήκει στο σύνολο ${\rm X}$, τότε ο ${\rm B}$ κερδίζει, διαφορετικά, χάνει. Να αποδείξετε ότι:

1. Αν $n\ge 2^k$, τότε ο ${\rm B}$ έχει στρατηγική νίκης.

2. Για κάθε αρκετά μεγάλο $k$, υπάρχει ακέραιος $n\ge 1,{99}^k$, τέτοιος ώστε ο ${\rm B}$ δεν μπορεί να έχει στρατηγική νίκης.

53η Διεθνής Μαθηματική Ολυμπιάδα 2012, Αργεντινή

(Πρόβλημα 3ο, προτάθηκε από τον Καναδά)