Πάνω σε ένα τραπέζι βρίσκονται απλωμένα $2015$ νομίσματα. Κάποια είναι γυρισμένα ώστε να δείχνουν κεφάλι και κάποια δείχνουν γράμματα. $2015$ άνθρωποι δικαιούνται να κάνουν το εξής: O 1ος θα γυρίσει ένα οποιοδήποτε νόμισμα. Ο 2ος θα γυρίσει $2$ οποιαδήποτε νομίσματα, ... ο $ν$-ιοστός θα γυρίσει οποιαδήποτε $ν$ νομίσματα..., ο 2015ος θα γυρίσει όλα τα νομίσματα. Δείξτε ότι:
$α.$ Ανεξαρτήτως της αρχικής διάταξης κεφαλιών-γραμμάτων στα νομίσματα, οι $2015$ άνθρωποι μπορούν να ακολουθήσουν μια διαδικασία, η οποία στο τέλος της θα δώσει $2015$ νομίσματα που όλα θα δείχνουν είτε κεφάλι ,είτε γράμματα.
$β.$ Δείξτε πως σε αυτή τη διαδικασία ,το αν θα είναι στο τέλος όλα κεφάλια ή όλα γράμματα, εξαρτάται από την αρχική θέση των νομισμάτων.
$β.$ Δείξτε πως σε αυτή τη διαδικασία ,το αν θα είναι στο τέλος όλα κεφάλια ή όλα γράμματα, εξαρτάται από την αρχική θέση των νομισμάτων.
Σε τέτοιου είδους προβλήματα,είναι εύλογο και συνήθως χρήσιμο να σκεφτούμε τί γίνεται για μικρούς αριθμούς νομισμάτων.
ΑπάντησηΔιαγραφήΓια ν=1 (1 νόμισμα) και ν=3 (για 3 νομίσματα) το ζητούμενο είναι αληθές. Για ν=2 όμως δεν είναι. Στην περίπτωση ας πούμε 2 κεφαλιών ως αρχική διάταξη, δεν υπάρχει τρόπος να έχουμε 2 ίδια στο τέλος. Υποπτευόμαστε λοιπόν πως το ζητούμενο μπορεί να είναι αληθές για περιττό ν μόνο,άρα και για ν=2015.
Μια Επαγωγή λοιπόν ως προς μ ,με $ν=2μ-1$ ,φαίνεται εύλογη... μπορεί κάποιος να ξεχωρίσει τις διατάξεις με ίδια αρχική θέση για όλα τα νομίσματα, και με διαφορετικές.
Αντιστρέφοντας τη σειρά των ερωτημάτων, επιχειρώ μια απάντηση στο β, η οποία ίσως θα μπορούσε να είναι μια πιθανή κατεύθυνση και για την απάντηση στο α.
ΑπάντησηΔιαγραφήΣτην αρχική διάταξη όπως και σε κάθε φάση του παιχνιδιού, οι ισοτιμίες (mod2) των αριθμών κεφαλιών (Κ) και γραμμάτων (Γ) είναι διαφορετικές μεταξύ τους (μονές οι πρώτες – ζυγές οι δεύτερες ή το ανάποδο), αφού ο συνολικός αριθμός των νομισμάτων είναι μονός.
Επί πλέον, οι μονής σειράς παίκτες (1ος, 3ος, … , 2015ος), στην εκάστοτε σειρά τους, μεταβάλλουν τις ισοτιμίες αυτές, αφού οι αλλαγές που κάνουν γίνονται σε μονό συνολικό αριθμό νομισμάτων, επομένως αλλάζουν μονό αριθμό νομισμάτων από Κ σε Γ– ζυγό αριθμό από Γ σε Κ ή το ανάποδο.
Αντιστοίχως, οι ζυγής σειράς παίκτες (2ος, 4ος, … , 2014ος), αφήνουν αμετάβλητες τις ισοτιμίες των αριθμών Κ και Γ, αφού κάνουν αλλαγές σε ζυγό συνολικό αριθμό νομισμάτων, οπότε οι αλλαγές από Κ σε Γ και από Γ σε Κ θα είναι είτε και οι δυο μονού είτε και οι δυο ζυγού αριθμού.
Ο 2015ος και τελευταίος παίκτης είναι ο 1008ος μονής σειράς παίκτης, και, αφού ο 1008 είναι ζυγός, στο τέλος οι ισοτιμίες των Κ και των Γ θα επανέλθουν αναγκαστικά στις τιμές που είχαν αρχικά. Για να δείχνουν όμως τελικά τα 2015 (δηλαδή μονός αριθμός) νομίσματα όλα Κ ή όλα Γ, αυτό μπορεί να συμβεί μόνο αν αρχικά υπάρχουν αντιστοίχως μονός αριθμός Κ ή Γ. Επομένως, για ν=2015, αν μπορούν να έχουν τελικά όλα τα νομίσματα την ίδια όψη, η όψη αυτή μπορεί να είναι μόνο η όψη που έχουν στην αρχή μονός αριθμός νομισμάτων.
Θανάση (papadim), ναι. Εξαιρετικά! Συγχαρητήρια!
ΑπάντησηΔιαγραφήΤο επιχείρημά σου όντως δείχνει πως -αν υπάρχει τέτοια διαδικασία- δεν είναι ανεξάρτητη ως προς την αρτιότητα (parity) που τελικά παράγει, σε σχέση με την αρχική parity. Επίτρεψέ μου να το επαναδιατυπώσω με άλλο τρόπο.
Αν λοιπόν η διαδικασία που ακολουθήσουν οι παίκτες δεν εξαρτάται από την αρχική διάταξη των νομισμάτων ως προς το αποτέλεσμα που παράγει, αυτό σημαίνει πως υπάρχει κάποια αρχική διάταξη που τελικά μπορεί να δώσει "όλα κεφάλια" ή "όλα γράμματα". Ας πάρουμε την περίπτωση "όλα κεφάλια" . Αντιστρέφοντας τη διαδικασία ,εξετάζοντας δηλαδή τα γυρίσματα των νομισμάτων ανάποδα από την κατάσταση "όλα κεφάλια" προς τα πίσω, μπορούμε να πάμε με
$2*(1+2+3+...+2015)$ γυρίσματα σε κατάσταση "όλα γράμματα". (αυτό είναι ουσιαστικά το επιχείρημα -κλειδί του Θανάση περί του ποιες ισοτιμίες μεταβάλουν parity).
Όμως, για να πάει οποιοδήποτε νόμισμα από κατάσταση "κεφάλι" σε κατάσταση "γράμματα" πρέπει να γυριστεί περιττό αριθμό φορών! άρα τα 2015 νομίσματα πρέπει να σουμάρουν περιττό αριθμό γυρισμάτων. Το $2*(1+2+3+...+2015)$ όμως είναι άρτιος. Αντίφαση. Άρα το αν θα είναι στο τέλος όλα κεφάλια ή όλα γράμματα, εξαρτάται όντως από την αρχική θέση των νομισμάτων.
Γιώργη, ευχαριστώ! Η απόδειξή σου για το ερώτημα β είναι ομολογουμένως ασυναγώνιστη.
ΑπάντησηΔιαγραφήΜια επαγωγική απόδειξη για το ερώτημα α θα μπορούσε να λειτουργήσει νομίζω ως εξής:
1. Ο ισχυρισμός ισχύει προφανώς για ν=1 και εύκολα μπορεί να δειχθεί ότι ισχύει και για ν=3.
2. Υποθέτουμε ότι ισχύει για κάποιον μονό ν, πράγμα που σημαίνει ότι με οποιεσδήποτε αρχικές όψεις ν νομισμάτων, οι ν παίχτες μπορούν να φέρουν μια τελική διάταξη με όλες τις όψεις ίδιες μεταξύ τους.
3. Προσθέτοντας τώρα 2 νομίσματα (και 2 ακόμα παίχτες), θα έχουμε, εκτός από τα 1+2+..+ν αρχικά, και άλλα (ν+1)+(ν+2)=2ν+3 γυρίσματα. Τα πρόσθετα 2 νομίσματα θα έχουν μεταξύ τους ή α) την ίδια αρχική όψη ή β) διαφορετικές αρχικές όψεις.
Στην περίπτωση α) μοιράζουμε τα 2ν+3 πρόσθετα γυρίσματα, από 1 επί πλέον γύρισμα σε καθένα από τα ν αρχικά νομίσματα και από (ν+3)/2 γυρίσματα σε καθένα από τα 2 πρόσθετα νομίσματα.
Στην περίπτωση β), έχοντας ήδη δεδομένες, εξ υποθέσεως, από τους ν αρχικούς παίχτες ν ίδιες όψεις, με την προσθήκη των 2 νομισμάτων και χωρίς άλλη επέμβαση, έχουμε ν+2 νομίσματα με ν+1 ίδιες όψεις και 1 διαφορετική, οπότε ο (ν+1)στός παίχτης γυρίζει τα νομίσματα με τις ν+1 ίδιες όψεις, φέρνοντας στον (ν+2)οστό παίχτη μια διάταξη με ν+2 νομίσματα με ίδιες όψεις, τα οποία ο τελευταίος τα γυρίζει όλα.
Σε όλες τις περιπτώσεις, στο τέλος τα ν+2 νομίσματα θα έχουν όλα την ίδια όψη μεταξύ τους .
Επομένως, αν η υπόθεση ισχύει για ν νομίσματα ίδιας αρχικής όψης, θα ισχύει και για ν+2 νομίσματα ίδιας αρχικής όψης. Και με αυτό ολοκληρώνεται η επαγωγή.
Διορθώνω την τελευταία παράγραφο:
ΑπάντησηΔιαγραφήΕπομένως, αν η υπόθεση ισχύει για ν νομίσματα , θα ισχύει και για ν+2 νομίσματα. Και με αυτό ολοκληρώνεται η επαγωγή
Αυτό το σχόλιο αφαιρέθηκε από τον συντάκτη.
ΑπάντησηΔιαγραφήΕναλλακτικά, για την περίπτωση α) της επαγωγής:
ΑπάντησηΔιαγραφήΑν στην αρχική διάταξη των ν νομισμάτων υπήρχε τουλάχιστον 1 νόμισμα διαφορετικής όψης με τα 2 προστιθέμενα, θα μπορούσε αυτό να εναλλαχθεί με το 1 από τα προστιθέμενα, οπότε έχουμε μια διάταξη με ν και 2 ακόμη διαφορετικών τώρα όψεων νομίσματα, οπότε η περίπτωση α) ανάγεται στην απλούστερη περίπτωση β).
Αν στην αρχική διάταξη των ν νομισμάτων δεν υπάρχει κανένα νόμισμα διαφορετικής όψης σε σχέση με τα 2 προστιθέμενα, έχουμε την περίπτωση ν+2 ίδιας αρχικής όψης νομισμάτων. Ο συνολικός αριθμός γυρισμάτων είναι 1+2+…+(ν+2) = (ν+2)(ν+3)/2, που διαιρείται με το ν+2. Στην περίπτωση αυτή, με κατάλληλο rotation των νομισμάτων (ο 1ος παίχτης το 1ο νόμισμα, ο 2ος τα 2ο και 3ο, ο 3ος τα 4ο, 5ο, 6ο κ.ο.κ μέχρι να τελειώσουν τα νομίσματα, να περάσει η σειρά πάλι από το 1ο και να συνεχίσει η διαδικασία μέχρι να ολοκληρωθούν όλα τα γυρίσματα), γυρίζεται κάθε νόμισμα (ν+3)/2 φορές, και όλα δείχνουν τελικά πάλι την ίδια όψη.
Θανάση, είσαι Γίγας του ΚΝΔ (ερώτημα β), αλλά και Γίγας της τεχνικής (α.)! Yποκλίνομαι στη διάννοιά σου!
ΑπάντησηΔιαγραφήΘα μπορούσα να ποστάρω και την αντιμετώπιση για το α. που έχω έτοιμη, αλλά θα ήταν αμαρτία να αποπροσανατολίσω το νού και το μάτι του αναγνώστη από τα σχόλιά σου.
Να προσθέσω μόνο,πως το ωραίο και δύστροπο αυτό πρόβλημα είναι από παλιότερο (1989) μαθηματικό διαγωνισμό της πόλης Νάν-τσάνγκ στην Κίνα. (με 1989 νομίσματα εκεί, αλλά το ίδιο κάνει)
Γιώργη, ευχαριστώ για τα καλά σου λόγια!
ΑπάντησηΔιαγραφήΉταν όντως ένα δύστροπο, αλλα πολύ ΄προκλητικό', πρόβλημα και το χάρηκα πραγματικά! Μπράβο σου, με τη σειρά μου, για την εξαιρετική επιλογή!
ΥΓ. Τι εστί ΚΝΔ;:-)