Θέμα Εισαγωγικών Scuola Normale Superiore 2014-15 (4)

[dement]

Η Κλάρα και ο Γκουέλφο παίζουν το ακόλουθο παιχνίδι. Ξεκινούν από έναν ακέραιο μεγαλύτερο του και εναλλάξ εκτελούν μία από τις ακόλουθες πράξεις: Είτε διαιρούν τον αριθμό με έναν πρώτο διαιρέτη του είτε, εναλλακτικά, αν ο αριθμός είναι τέλειο τετράγωνο, υπολογίζουν την τετραγωνική του ρίζα. Έτσι, για παράδειγμα, αν ο τρέχων αριθμός είναι , ο παίκτης μπορεί να τον διαιρέσει με , παίρνοντας , ή να υπολογίσει την τετραγωνική του ρίζα, παίρνοντας . Κερδίζει ο πρώτος παίκτης η πράξη του οποίου δίνει αποτέλεσμα . Η Κλάρα ξεκινάει πάντα πρώτη.

Αποδείξτε ότι:

1. Αν ο αρχικός αριθμός είναι , η Κλάρα έχει στρατηγική νίκης.
2. Αν ο αρχικός αριθμός είναι , ο Γκουέλφο έχει στρατηγική νίκης.

[Διονύσιος Αδαμόπουλος]

1. Καταρχάς παρατηρούμε πως αν ο αρχικός αριθμός είναι , τότε η Κλάρα έχει στρατηγική νίκης.

Πράγματι, η Κλάρα θα υπολογίσει τη τετραγωνική ρίζα του , που είναι . Είτε τώρα ο Γκουέλφο υπολογίσει την τετραγωνική ρίζα του είτε διαιρέσει το με το , το αποτέλεσμα θα είναι . Συνεπώς, Η Κλάρα θα διαιρέσει το με το , που δίνει αποτέλεσμα , άρα νικάει.

Θα αποδείξουμε πως αν , με , η Κλάρα έχει στρατηγική νίκης.

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

Επειδή ο είναι άρτιος, έχουμε πως όταν , η Κλάρα νικάει.

[dement]

Σωστά. Φυσικά αντί για θα μπορούσε να είναι οποιοσδήποτε άλλος πρώτος.

Καλή τύχη με το δεύτερο σκέλος...

[Διονύσιος Αδαμόπουλος]

2. Γράφουμε τον αριθμό στην μορφή .

Έστω πως η Κλάρα διαιρεί με το ή με το .

Τότε ο ένας από τους δύο εκθέτες θα γίνει περιττός.

Ο Γκουέλφο θα διαιρέσει με τον άλλο αριθμό για να κάνει και τον άλλο εκθέτη περιττό.

Έπειτα η Κλάρα δεν θα μπορεί να υπολογίσει την τετραγωνική ρίζα του αριθμού, καθώς δεν θα είναι τέλειο τετράγωνο. Έπεται λοιπόν πως θα διαιρέσει πάλι με το ή με το , άρα θα κάνει έναν από τους δύο εκθέτες άρτιους.

Ο Γκούλφο θα διαιρέσει με τον ίδιο αριθμό για να κάνει και τους δύο εκθέτες πάλι περιττούς.

Αυτή η διαδικασία επαναλαμβάνεται, καθώς η Κλάρα δεν μπορεί να ξεφύγει.

Παρατηρούμε ακόμα πως κάθε φορά που πρέπει να παίξει ο Γκουέλφο, το άθροισμα των δύο εκθετών θα είναι περιττό και κατά δυο μικρότερο από την τελευταία φορά που είχε σειρά.

Σε κάποια φάση λοιπόν που θα πρέπει να παίξει ο Γκουέλφο, ο αριθμός που θα μένει θα είναι ή , άρα θα διαιρέσει με ή το αντίστοιχα και θα νικήσει.

Έστω πως η Κλάρα υπολογίσει την τετραγωνική ρίζα του . Ο αριθμός τότε θα γίνει .

Ο Γκουέλφο θα υπολογίσει και αυτός την τετραγωνική ρίζα του και ο αριθμός θα γίνει .

Ο αριθμός αυτός δεν είναι τέλειο τετράγωνο, άρα η Κλάρα θα διαιρέσει με ή με το , άρα θα κάνει έναν από τους δύο εκθέτες άρτιους.

Ο Γκουέλφο ακολουθώντας την στρατηγική που αναφέραμε παραπάνω, θα νικήσει.

[dement]

Αν κατάλαβα καλά, η στρατηγική σου βασίζεται στο να αφήνει ο Γκουέλφο δύο περιττούς εκθέτες.

Έτσι όμως υπάρχει πρόβλημα. Αν η Κλάρα π.χ. μείνει με το κάνει , ο Γκουέλφο , η Κλάρα και ο Γκουέλφο την πάτησε από το προηγούμενο σκέλος.

[Διονύσιος Αδαμόπουλος]

Αν κατάλαβα καλά, η στρατηγική σου βασίζεται στο να αφήνει ο Γκουέλφο δύο περιττούς εκθέτες.

Έτσι όμως υπάρχει πρόβλημα. Αν η Κλάρα π.χ. μείνει με το κάνει , ο Γκουέλφο , η Κλάρα και ο Γκουέλφο την πάτησε από το προηγούμενο σκέλος.

Σκέφτηκα μια αντιμετώπιση στο σχολείο, ελπίζω να είναι σωστή:

Θα αποδείξουμε πως αν ο αριθμός είναι ή , τότε νικάει αυτός που έχει σειρά να παίξει (αυτός που πρόκειται να παίξει):

Πράγματι, ο παίχτης (παίχτης ) που παίζει θα διαιρέσει με το ή με το αντίστοιχα και έτσι η διαφορά των δυο συντελεστών θα γίνει .

Τώρα αν ο άλλος παίχτης (παίχτης ) διαιρέσει με το ή με το , ο παίχτης θα διαιρέσει με το ή με το αντίστοιχα. Έτσι η διαφορά θα παραμείνει .

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

Οι εκθέτες θα μειώνονται συνεχώς μέχρι να φτάσουμε στον αριθμό:

ή και θα παίζει ο παίχτης .

Αν τώρα διαιρέσει με το ή με το αντίστοιχα, θα φτάσουμε στον αριθμό ή αντίστοιχα. Ο παίχτης θα διαιρέσει μετά με το ή με το αντίστοιχα και θα φτάσουμε στον αριθμό ή , με τον παίχτη να παίζει, όπου ότι και να κάνει θα χάσει.

Αν διαιρούσε με το ή με το αντίστοιχα, ο παίχτης θα διαιρέσει με το ή με το αντίστοιχα και θα φτάσουμε στον αριθμό ή , με τον παίχτη να παίζει, όπου ότι και να κάνει θα χάσει πάλι.

Επιστρέφουμε στο πρόβλημά μας:

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

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

[dement]

Πολύ ωραία, αυτή είναι νικηφόρα στρατηγική!

Αν και δεν το ζητάει το θέμα, είναι ενδιαφέρον ερώτημα (και στην ουσία έχεις προχωρήσει αρκετά):

Αν ο αρχικός αριθμός είναι , για ποια έχει νικηφόρα στρατηγική η Κλάρα και για ποια ο Γκουέλφο;

[dement]

Δίνω εδώ τη γενική περίπτωση:

- Αν η διαφορά των εκθετών είναι , άρτιος μεγαλύτερος του ή με τους εκθέτες στη μορφή , η Κλάρα έχει στρατηγική νίκης.

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

Κάνουμε επαγωγή ως προς το άθροισμα των εκθετών.

Αν το άθροισμα είναι , η διαφορά δεν μπορεί παρά να είναι και φυσικά η Κλάρα κερδίζει.

Έστω το άθροισμα των εκθετών και έστω ότι το αποδεικτέο ισχύει για άθροισμα μέχρι και .

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

Αντίστροφα: Αν η διαφορά είναι , ό,τι και να κάνει θα την μετατρέψει σε ή , χάνοντας. Αν η διαφορά είναι περιττός μεγαλύτερος του , δεν μπορεί να πάρει τετραγωνική ρίζα και θα την μετατρέψει σε άρτιο μεγαλύτερο του , χάνοντας. Αν, τέλος, οι εκθέτες είναι ίσοι της μορφής τότε ή θα μετατρέψει τη διαφορά σε ή θα πάρει τη ρίζα, μετατρέποντας τους εκθέτες στη μορφή και χάνοντας.