mathematica.gr

Δημοσιεύτηκε: **Πέμ Δεκ 01, 2016 9:05 pm**

Δύο μαθητές, ο Θάνος και ο Χρίστος, γράφουν στον πίνακα από έναν αριθμό.
πχ Θ: 13
Χ: 24
Στη συνέχεια, ο Θάνος γράφει τη θετική διαφορά τους,
δηλαδή Θ: 24-13 = 11
Συνεχίζουν εναλλάξ, γράφοντας κάθε φορά μία θετική διαφορά αριθμών που υπάρχουν στον πίνακα και η οποία δεν είναι ήδη γραμμένη στον πίνακα.
πχ Χ: 13-11 = 2
Χάνει ο μαθητής, ο οποίος δεν μπορεί να γράψει στον πίνακα έναν νέο αριθμό με αυτήν τη διαδικασία.

Τελειώνει πάντα το παιχνίδι; Υπάρχει στρατηγική νίκης για κάποιον από τους δύο;

Δημοσιεύτηκε: **Παρ Δεκ 02, 2016 4:42 pm**

polysot έγραψε:Δύο μαθητές, ο Θάνος και ο Χρίστος, γράφουν στον πίνακα από έναν αριθμό.
πχ Θ: 13
Χ: 24
Στη συνέχεια, ο Θάνος γράφει τη θετική διαφορά τους,
δηλαδή Θ: 24-13 = 11
Συνεχίζουν εναλλάξ, γράφοντας κάθε φορά μία θετική διαφορά αριθμών που υπάρχουν στον πίνακα και η οποία δεν είναι ήδη γραμμένη στον πίνακα.
πχ Χ: 13-11 = 2
Χάνει ο μαθητής, ο οποίος δεν μπορεί να γράψει στον πίνακα έναν νέο αριθμό με αυτήν τη διαδικασία.

Τελειώνει πάντα το παιχνίδι; Υπάρχει στρατηγική νίκης για κάποιον από τους δύο;

Έστω

ο μεγαλύτερος από τους δύο αριθμούς που γράφουν ο Θάνος και ο Χρήστος. Τότε όλοι αριθμοί που θα γραφτούν στον πίνακα (πάντα διαφορετικοί μεταξύ τους) θα είναι από το διάστημα [a,0)

, οι οποίοι όμως έχουν πεπερασμένο πλήθος και άρα το παιχνίδι κάποτε θα τελειώσει.

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

Αρχικά, θα αποδείξουμε πως πρέπει αναγκαστικά ένας από τους δύο αρχικούς αριθμούς να είναι άρτιος. Αρκεί να απορρίψουμε μία μόνο περίπτωση, την οποία ο Χρήστος δεν θα μπορεί να ανατρέψει. Έστω a_1

,

, ...

οι αριθμοί με την σειρά με την οποία γράφονται στον πίνακα. Αν a_1=1

, τότε

(λόγω παραμέτρων η πρώτη αφαίρεση πρέπει να δίνει διαφορά διάφορη από ήδη υπάρχοντα αριθμό στον πίνακα) και αφού a_2 = 2m+1

(αφού υποθέσαμε ότι θα είναι περιττός), θα είναι a_3=2m

,

. Εύκολα βλέπουμε πως αν ένας

αριθμός είναι γραμμένος τότε θα γραφτεί και ο f-1

. Συνεπώς, θα γραφτούν όλοι οι αριθμοί από το διάστημα [2m+1,1]

.Το πλήθος όμως

θα είναι περιττός, αφού το αποτελουν όλοι αριθμοί του διαστήματος [2m+1,1]

που είναι

σε αριθμό, άτοπο (αφού εμείς θέλουμε να είναι άρτιος). Επομένως, πρέπει ένας τουλάχιστον από τους δύο αρχικούς αριθμούς να είναι άρτιος.
Τώρα σε περίπτωση που a_1=2g

, αν ο Χρηστος επιλέξει a_2=1

, τότε θα κερδίσει αφού το πλήθος των αριθμών του πίνακα θα είναι άρτιο για τον λόγο που εξήγησαμε πιο πάνω. Υποθέτουμε λοιπόν ότι ο Θάνος έχει επίγνωση του παραπάνω και επομένως θα είναι a_1=2h+1

. Άρα πρέπει a_2=2l

. Παρατηρούμε ότι αν ισχύει a_2=(4+2n)a_1

. Τότε

,

,

. Εύκολα, βλέπουμε ότι αν ο

είναι γραμμένος στον πίνακα τότε θα είναι γραμμένος και ο (z-1)c

και επομένως όλοι οι αριθμοί

με

(το πλήθος των οποίων είναι 4+2n

άρτιος) και άρα όλες οι δυνατές διαφορές αφού η διαφορά δύο πολλαπλάσιων του ίδιου αριθμού θα είναι πολλαπλάσιο του αριθμού αυτόυ μικρότερο του αφαιρετέου. Επομένως, η στρατηγική νίκης του Χρήστου είναι η εξής:
Γράφει στον πίνακα τον αριθμό (4+2n)a_1

με

φυσικό.
(Πιστεύω ότι είναι σωστό. Αν και νομίζω ότι υπάρχει μια λιγότερο χρονοβόρα λύση.)

Δημοσιεύτηκε: **Παρ Δεκ 02, 2016 8:05 pm**

Παρατήρηση: Αν αρχικά στον πίνακα είναι γραμμένοι οι αριθμοί n,n+1

τότε στο τέλος στον πίνακα είναι γραμμένοι όλοι οι αριθμοί από το

ως το

.

Απόδειξη: Σίγουρα στο επόμενο βήμα θα γραφτεί το

. Ας υποθέσουμε προς άτοπο ότι στο τέλος, κάποιος αριθμός από τους $1,2,\ldots,n+1$ δεν έχει γραφτεί στον πίνακα. Έστω

ο μεγαλύτερος από αυτούς που δεν έχουν γραφτεί. Τότε ο m+1

είναι γραμμένος στον πίνακα. Αφού όμως οι

και

είναι γραμμένοι στον πίνακα, τότε σε κάποια φάση θα έπρεπε να γραφτεί και ο m = (m+1)-1

.

Πάμε τώρα στην άσκηση:

Αν ο Θάνος γράψει έναν άρτιο, έστω τον

, τότε ο Χρήστος γράφει τον 2n-1

. Στο τέλος θα είναι γραμμένοι οι $1,2,\ldots,2n$ . Τον τελευταίο αριθμό τον έγραψε ο Χρήστος ο οποίος και κερδίζει. Αν ο Θάνος γράψει έναν περιττό, έστω τον 2n-1

, τότε ο Χρήστος γράφει τον

και πάλι κερδίζει.

Άσκηση: Ποιος κερδίζει αν αρχικά στον πίνακα είναι γραμμένοι οι αριθμοί

και

;

Δημοσιεύτηκε: **Σάβ Δεκ 03, 2016 11:14 am**

Demetres έγραψε: Άσκηση: Ποιος κερδίζει αν αρχικά στον πίνακα είναι γραμμένοι οι αριθμοί και ;

Ονομάζουμε $m=\gcd (a,b)$ και χωρίς βλάβη της άσκησης υποθέτουμε ότι a>b>1

.

α) Αν m=1

, τότε η διοφαντική εξίσωση $(1): ax+by=c (c \in Z )$ έχει πάντα ακέραιες λύσεις,
οπότε μπορούμε να γράψουμε όλους τους θετικούς ακεραίους που είναι μικρότεροι από τον

με θετικές διαφορές των a,b

.
Έτσι για m=1

, αν το

είναι άρτιος κερδίζει ο Χάρης ενώ αν το

είναι περιττός κερδίζει ο Θάνος.

β) Αν m>1

και $a=m \cdot k$ τότε μπορούμε να γράψουμε στον πίνακα άλλους (k-2)

θετικούς ακεραίους, τους a-m, a-2m,. . .,a-(k-1)m

( εκτός βέβαια τον

που είναι ήδη γραμμένος στον πίνακα ). (Τώρα η (1)

έχει λύσεις μόνο για

πολλαπλάσιο του

).
Σ'αυτή την περίπτωση, αν ο

είναι άρτιος κερδίζει ο Θάνος ενώ αν ο

είναι περιττός κερδίζει ο Χάρης.

Δημοσιεύτηκε: **Σάβ Δεκ 03, 2016 8:32 pm**

Να συμπληρώσω στην λύση του nikkru ότι η ιδέα του παιχνιδιού προέρχεται από τον ΕΥκλείδιο αλγόριθμο εύρεσης του ΜΚΔ και την αναδρομική χρηση του για την επίλυση της αντίστοιχης διοφαντικής γραμμικής εξίσωσης.

mathematica.gr

Γράφοντας αριθμούς στον πίνακα

Γράφοντας αριθμούς στον πίνακα

Re: Γράφοντας αριθμούς στον πίνακα

Re: Γράφοντας αριθμούς στον πίνακα

Re: Γράφοντας αριθμούς στον πίνακα

Re: Γράφοντας αριθμούς στον πίνακα