Συνδυαστική για Ολυμπιάδες
Δημοσιεύτηκε: Δευ Μαρ 02, 2020 1:34 pm
Θεωρείστε ένα 3*3 πίνακα , όπου κάθε κελί περιέχει έναν αριθμό από νομίσματα. Για παράδειγμα ο ακόλουθος πίνακας αντιπροσωπεύει μια πιθανή κατανομή των νομισμάτων στα κελιά (ο ακέραιος σε κάθε κελί είναι ο αριθμός των νομισμάτων που βρίσκονται σε αυτό το κελί) :
12 3 1
1 8 4
2 13 0
Η παραπάνω κατανομή αλλάζει με τον ακόλουθο τρόπο : σε κάθε βήμα , κάθε κελί στέλνει ένα νόμισμα σε όλα τα γειτονικά κελιά (οριζόντια ή κάθετα , όχι διαγώνια ) . Αλλά αν δεν υπάρχουν αρκετά νομίσματα εξ' αρχής σε κάποιο κελί ώστε να στείλει από ένα σε κάθε γείτονά του , δε στέλνει κανένα νόμισμα .Για παράδειγμα το σχήμα (1) , μετά από ένα ''βήμα '' θα μετασχηματιζόταν στο παρακάτω :
11 2 3
4 7 2
1 12 2
α) Να δείξετε ότι κάθε κατανομή καταλήγει σε σταθερή κατανομή ( μία κατανομή που δεν αλλάζει με το πέρασμα των κινήσεων) ή παρουσιάζει ένα μοτίβο , με το πέρασμα των κινήσεων . ( δηλαδή για έναν ακέραιο Κ , εμφανίζονται επαναλαμβανόμενα αυτές οι Κ κατανομές καθώς προχωρά η διαδικασία ) .
β) Στην περίπτωση που η αρχική κατανομή παρουσιάζει επαναλαμβανόμενα , Κ κατανομές να βρείτε τις πιθανές τιμές του Κ .
γ) Να αποδείξετε ότι είτε για κάποιον ακέραιο αριθμό Β , κάθε κατανομή καταλήγει σε σταθερή κατανομή ή σε επαναλαμβανόμενα μοτίβα μέσα σε Β ή λιγότερες κινήσεις , ή να δείξετε ότι δεν υπάρχει τέτοιο Β .
12 3 1
1 8 4
2 13 0
Η παραπάνω κατανομή αλλάζει με τον ακόλουθο τρόπο : σε κάθε βήμα , κάθε κελί στέλνει ένα νόμισμα σε όλα τα γειτονικά κελιά (οριζόντια ή κάθετα , όχι διαγώνια ) . Αλλά αν δεν υπάρχουν αρκετά νομίσματα εξ' αρχής σε κάποιο κελί ώστε να στείλει από ένα σε κάθε γείτονά του , δε στέλνει κανένα νόμισμα .Για παράδειγμα το σχήμα (1) , μετά από ένα ''βήμα '' θα μετασχηματιζόταν στο παρακάτω :
11 2 3
4 7 2
1 12 2
α) Να δείξετε ότι κάθε κατανομή καταλήγει σε σταθερή κατανομή ( μία κατανομή που δεν αλλάζει με το πέρασμα των κινήσεων) ή παρουσιάζει ένα μοτίβο , με το πέρασμα των κινήσεων . ( δηλαδή για έναν ακέραιο Κ , εμφανίζονται επαναλαμβανόμενα αυτές οι Κ κατανομές καθώς προχωρά η διαδικασία ) .
β) Στην περίπτωση που η αρχική κατανομή παρουσιάζει επαναλαμβανόμενα , Κ κατανομές να βρείτε τις πιθανές τιμές του Κ .
γ) Να αποδείξετε ότι είτε για κάποιον ακέραιο αριθμό Β , κάθε κατανομή καταλήγει σε σταθερή κατανομή ή σε επαναλαμβανόμενα μοτίβα μέσα σε Β ή λιγότερες κινήσεις , ή να δείξετε ότι δεν υπάρχει τέτοιο Β .