Τράπουλα

Συντονιστές: Demetres, socrates, silouan

Λάμπρος Κατσάπας
Δημοσιεύσεις: 398
Εγγραφή: Σάβ Ιουν 17, 2017 10:17 pm
Τοποθεσία: Αθήνα

Τράπουλα

#1

Μη αναγνωσμένη δημοσίευση από Λάμπρος Κατσάπας » Τετ Μαρ 21, 2018 11:14 pm

Έχουμε στη διάθεσή μας τα 13 φύλλα της τράπουλας A,2,3,...,10,J,Q,K με αντίστοιχες αξίες

1,2,3,...,10,11,12,13. Τα ανακατεύουμε και κοιτάμε το πρώτο. Αν η αξία του είναι i τότε

αντιμεταθέτουμε τα i πρώτα φύλλα και επαναλαμβάνουμε τη διαδικασία. Η διαδικασία τερματίζεται προφανώς αν

κάποια στιγμή είναι πρώτο φύλλο ο A. Να αποδειχθεί ότι η διαδικασία δεν πρόκειται να πέσει σε αέναο κύκλο

(loop) και όντως κάποια στιγμή τερματίζει με πρώτο φύλλο τον A.

-Μια πιθανή αρχική διάταξη είναι η 4,2,5,7,J,K,A,10,3,Q,8,9,6 η οποία μετά την πρώτη αντιμετάθεση θα γίνει

7,5,2,4,J,K,A,10,3,Q,8,9,6 και στη δεύτερη τερματίζει.


-Ένα ανοικτό (άλυτο) πρόβλημα που σχετίζεται με το παραπάνω είναι να βρεθεί ποια (ποιες) αρχικές διατάξεις των φύλλων

μας δίνουν το μέγιστο αριθμό κινήσεων μέχρι να τερματιστεί η διαδικασία



Λέξεις Κλειδιά:
Άβαταρ μέλους
Διονύσιος Αδαμόπουλος
Δημοσιεύσεις: 782
Εγγραφή: Σάβ Μαρ 19, 2016 5:11 pm
Τοποθεσία: Πύργος Ηλείας

Re: Τράπουλα

#2

Μη αναγνωσμένη δημοσίευση από Διονύσιος Αδαμόπουλος » Σάβ Μαρ 24, 2018 11:53 pm

Θα δείξουμε με επαγωγή τη γενίκευση:

Έστω μια διάταξη των αριθμών 1, 2, ... ,n. Σε κάθε βήμα, αν i είναι ο πρώτος αριθμός τότε αναδιατάσσουμε με αντίστροφη σειρά τους πρώτους i αριθμούς. Ισχύει ότι κάποια στιγμή ο αριθμός 1 θα βρεθεί στην πρώτη θέση και επομένως η διαδικασία θα σταματήσει.

Θεωρούμε ότι αρχικά ο πρώτος αριθμός δεν είναι το 1 αλλιώς η διαδικασία δεν θα αρχίσει καν.

Αν n=2, δηλαδή αν έχουμε τη διάταξη 2, 1 τότε η διαδικασία ολοκληρώνεται μετά από 1 βήμα.
Αν n=3, τότε ας εξετάσουμε τις παρακάτω διατάξεις:
2, 1, 3 η διαδικασία ολοκληρώνεται μετά από 1 βήμα
2, 3, 1 η διαδικασία ολοκληρώνεται μετά από 2 βήματα
3, 1, 2 η διαδικασία ολοκληρώνεται μετά από 2 βήματα
3, 2, 1 η διαδικασία ολοκληρώνεται μετά από 1 βήμα

Έστω ότι ισχύει για n=k ότι η διαδικασία κάποια στιγμή θα σταματήσει.
Θα αποδείξουμε ότι το ίδιο θα γίνει και για n=k+1.

Αν αρχικά ο αριθμός k+1 βρίσκεται στην τελευταία θέση, τότε στις πρώτες k θέσεις βρίσκονται με κάποια διάταξη οι αριθμοί 1 έως k, οπότε ισχύει ότι η διαδικασία κάποια στιγμή θα σταματήσει.
Αν αρχικά ο αριθμός k+1 δεν βρίσκεται στην τελευταία θέση, τότε αν σε κάποιο βήμα βρεθεί στην πρώτη θέση, τότε στο αμέσως επόμενο βήμα θα βρεθεί στην τελευταία θέση, όπου είδαμε ότι τότε η διαδικασία κάποια στιγμή θα σταματήσει.
Αν αρχικά ο αριθμός k+1 δεν βρίσκεται στην τελευταία θέση, και σε κανένα βήμα δεν βρεθεί στην πρώτη θέση, τότε εφαρμόζουμε το εξής: Έστω m ο αριθμός που αρχικά βρίσκεται στην τελευταία θέση (παρατηρούμε ότι αυτός δεν αλλάζει σε κανένα από τα βήματα). Η διαδικασία δεν επηρεάζεται αν αντιμεταθέσουμε τον αριθμό m με τον αριθμό k+1, αφού τότε και ο m σε κανένα βήμα δεν θα βρεθεί στην πρώτη θέση. Έτσι όμως ο αριθμός k+1 θα βρίσκεται στην τελευταία θέση, όπου είδαμε ότι τότε η διαδικασία κάποια στιγμή θα σταματήσει.


Houston, we have a problem!
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8097
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Τράπουλα

#3

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Μαρ 25, 2018 11:07 am

Έστω μια διάταξη T. Ορίζουμε A(T) το σύνολο όλων των χαρτιών τα οποία βρίσκονται στην θέση τους και ορίζουμε

\displaystyle  f(T) = \sum_{k \in A(T)} 2^k

Είναι άμεσο ότι με κάθε αντιμετάθεση το f(T) αυξάνεται. Πράγματι αν το αρχικό χαρτί όταν κάνουμε την αντιμετάθεση είναι το r, τότε το r μπαίνει στο σύνολο f(T) ενώ κάθε k > r που ανήκει στο f(T) παραμένει στο f(T). Ακόμα και αν όλα τα k < r ανήκαν στο f(T) ενώ τώρα δεν ανήκουν θα έχουμε αύξηση κατά 2^r - (2^1 + 2^2 + \cdots + 2^{r-1}) = 1.

Επειδή όμως το f(T) μπορεί να πάρει μόνο πεπερασμένες τιμές, τότε η διαδικασία θα τερματιστεί.


Απάντηση

Επιστροφή σε “Συνδυαστική - Προχωρημένο Επίπεδο (Seniors)”

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

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