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

Συντονιστές: Φωτεινή, silouan

Άβαταρ μέλους
polysot
Επιμελητής
Δημοσιεύσεις: 2491
Εγγραφή: Δευ Οκτ 19, 2009 11:43 pm
Τοποθεσία: Όπου βρω ενδιαφέρουσες προσωπικότητες...
Επικοινωνία:

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

#1

Μη αναγνωσμένη δημοσίευση από polysot » Πέμ Δεκ 01, 2016 9:05 pm

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

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


Σωτήρης Δ. Χασάπης

Ζήσε τα μαθηματικά σου!
-----------------------------
"There is a scientific taste just as there is a literary or artistic one", Renan
"The journey of a thousand miles begins with one step.", Lao Tzu

Λέξεις Κλειδιά:
JimNt.
Δημοσιεύσεις: 516
Εγγραφή: Παρ Μάιος 20, 2016 3:00 pm

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

#2

Μη αναγνωσμένη δημοσίευση από JimNt. » Παρ Δεκ 02, 2016 4:42 pm

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

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

Αρχικά, θα αποδείξουμε πως πρέπει αναγκαστικά ένας από τους δύο αρχικούς αριθμούς να είναι άρτιος. Αρκεί να απορρίψουμε μία μόνο περίπτωση, την οποία ο Χρήστος δεν θα μπορεί να ανατρέψει. Έστω a_1, a_2, ... a_n οι αριθμοί με την σειρά με την οποία γράφονται στον πίνακα. Αν a_1=1, τότε a_2 > 2 (λόγω παραμέτρων η πρώτη αφαίρεση πρέπει να δίνει διαφορά διάφορη από ήδη υπάρχοντα αριθμό στον πίνακα) και αφού a_2 = 2m+1 (αφού υποθέσαμε ότι θα είναι περιττός), θα είναι a_3=2m, a_4=2m-1. Εύκολα βλέπουμε πως αν ένας f αριθμός είναι γραμμένος τότε θα γραφτεί και ο f-1. Συνεπώς, θα γραφτούν όλοι οι αριθμοί από το διάστημα [2m+1,1].Το πλήθος όμως n θα είναι περιττός, αφού το αποτελουν όλοι αριθμοί του διαστήματος [2m+1,1] που είναι 2m+1 σε αριθμό, άτοπο (αφού εμείς θέλουμε να είναι άρτιος). Επομένως, πρέπει ένας τουλάχιστον από τους δύο αρχικούς αριθμούς να είναι άρτιος.
Τώρα σε περίπτωση που a_1=2g , αν ο Χρηστος επιλέξει a_2=1 , τότε θα κερδίσει αφού το πλήθος των αριθμών του πίνακα θα είναι άρτιο για τον λόγο που εξήγησαμε πιο πάνω. Υποθέτουμε λοιπόν ότι ο Θάνος έχει επίγνωση του παραπάνω και επομένως θα είναι a_1=2h+1. Άρα πρέπει a_2=2l. Παρατηρούμε ότι αν ισχύει a_2=(4+2n)a_1. Τότε a_1=c, a_2=(4+2n)c, a_3=(3+2n)c. Εύκολα, βλέπουμε ότι αν ο zc είναι γραμμένος στον πίνακα τότε θα είναι γραμμένος και ο (z-1)c και επομένως όλοι οι αριθμοί jc με j ∈ [4+2n,1] (το πλήθος των οποίων είναι 4+2n άρτιος) και άρα όλες οι δυνατές διαφορές αφού η διαφορά δύο πολλαπλάσιων του ίδιου αριθμού θα είναι πολλαπλάσιο του αριθμού αυτόυ μικρότερο του αφαιρετέου. Επομένως, η στρατηγική νίκης του Χρήστου είναι η εξής:
Γράφει στον πίνακα τον αριθμό (4+2n)a_1 με n φυσικό.
(Πιστεύω ότι είναι σωστό. Αν και νομίζω ότι υπάρχει μια λιγότερο χρονοβόρα λύση.)


It's the questions we can't answer that teach us the most. They teach us how to think. If you give a man an answer, all he gains is a little fact. But give him a question and he'll look for his own answers.
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 7953
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

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

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Παρ Δεκ 02, 2016 8:05 pm

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

Απόδειξη: Σίγουρα στο επόμενο βήμα θα γραφτεί το 1. Ας υποθέσουμε προς άτοπο ότι στο τέλος, κάποιος αριθμός από τους 1,2,\ldots,n+1 δεν έχει γραφτεί στον πίνακα. Έστω m ο μεγαλύτερος από αυτούς που δεν έχουν γραφτεί. Τότε ο m+1 είναι γραμμένος στον πίνακα. Αφού όμως οι 1 και m+1 είναι γραμμένοι στον πίνακα, τότε σε κάποια φάση θα έπρεπε να γραφτεί και ο m = (m+1)-1.

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

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

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


nikkru
Δημοσιεύσεις: 333
Εγγραφή: Σάβ Δεκ 26, 2009 6:42 pm

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

#4

Μη αναγνωσμένη δημοσίευση από nikkru » Σάβ Δεκ 03, 2016 11:14 am

Demetres έγραψε: Άσκηση: Ποιος κερδίζει αν αρχικά στον πίνακα είναι γραμμένοι οι αριθμοί a και b;
Ονομάζουμε m=\gcd (a,b) και χωρίς βλάβη της άσκησης υποθέτουμε ότι a>b>1 .

α) Αν m=1, τότε η διοφαντική εξίσωση (1):  ax+by=c (c  \in Z ) έχει πάντα ακέραιες λύσεις,
οπότε μπορούμε να γράψουμε όλους τους θετικούς ακεραίους που είναι μικρότεροι από τον a με θετικές διαφορές των a,b.
Έτσι για m=1, αν το a είναι άρτιος κερδίζει ο Χάρης ενώ αν το a είναι περιττός κερδίζει ο Θάνος.

β) Αν m>1 και a=m \cdot k τότε μπορούμε να γράψουμε στον πίνακα άλλους (k-2) θετικούς ακεραίους, τους a-m, a-2m,. . .,a-(k-1)m
( εκτός βέβαια τον b που είναι ήδη γραμμένος στον πίνακα ). (Τώρα η (1) έχει λύσεις μόνο για c πολλαπλάσιο του m ).
Σ'αυτή την περίπτωση, αν ο k είναι άρτιος κερδίζει ο Θάνος ενώ αν ο k είναι περιττός κερδίζει ο Χάρης.


Άβαταρ μέλους
polysot
Επιμελητής
Δημοσιεύσεις: 2491
Εγγραφή: Δευ Οκτ 19, 2009 11:43 pm
Τοποθεσία: Όπου βρω ενδιαφέρουσες προσωπικότητες...
Επικοινωνία:

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

#5

Μη αναγνωσμένη δημοσίευση από polysot » Σάβ Δεκ 03, 2016 8:32 pm

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


Σωτήρης Δ. Χασάπης

Ζήσε τα μαθηματικά σου!
-----------------------------
"There is a scientific taste just as there is a literary or artistic one", Renan
"The journey of a thousand miles begins with one step.", Lao Tzu
Απάντηση

Επιστροφή σε “Άλγεβρα - Επίπεδο Θαλή/Ευκλείδη (Juniors)”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης