mathematica.gr

Δημοσιεύτηκε: **Τετ Μαρ 21, 2018 11:14 pm**

Έχουμε στη διάθεσή μας τα

φύλλα της τράπουλας A,2,3,...,10,J,Q,K

με αντίστοιχες αξίες

1,2,3,...,10,11,12,13.

Τα ανακατεύουμε και κοιτάμε το πρώτο. Αν η αξία του είναι

τότε

αντιμεταθέτουμε τα

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

κάποια στιγμή είναι πρώτο φύλλο ο

. Να αποδειχθεί ότι η διαδικασία δεν πρόκειται να πέσει σε αέναο κύκλο

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

.

-Μια πιθανή αρχική διάταξη είναι η η οποία μετά την πρώτη αντιμετάθεση θα γίνει

και στη δεύτερη τερματίζει.

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

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

Δημοσιεύτηκε: **Σάβ Μαρ 24, 2018 11:53 pm**

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

Έστω μια διάταξη των αριθμών 1, 2, ... ,n

. Σε κάθε βήμα, αν

είναι ο πρώτος αριθμός τότε αναδιατάσσουμε με αντίστροφη σειρά τους πρώτους

αριθμούς. Ισχύει ότι κάποια στιγμή ο αριθμός

θα βρεθεί στην πρώτη θέση και επομένως η διαδικασία θα σταματήσει.

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

αλλιώς η διαδικασία δεν θα αρχίσει καν.

Αν n=2

, δηλαδή αν έχουμε τη διάταξη 2, 1

τότε η διαδικασία ολοκληρώνεται μετά από

βήμα.
Αν n=3

, τότε ας εξετάσουμε τις παρακάτω διατάξεις:
2, 1, 3

η διαδικασία ολοκληρώνεται μετά από

βήμα

η διαδικασία ολοκληρώνεται μετά από

βήματα

η διαδικασία ολοκληρώνεται μετά από

βήματα

η διαδικασία ολοκληρώνεται μετά από

βήμα

Έστω ότι ισχύει για n=k

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

.

Αν αρχικά ο αριθμός k+1

βρίσκεται στην τελευταία θέση, τότε στις πρώτες

θέσεις βρίσκονται με κάποια διάταξη οι αριθμοί

έως

, οπότε ισχύει ότι η διαδικασία κάποια στιγμή θα σταματήσει.
Αν αρχικά ο αριθμός k+1

δεν βρίσκεται στην τελευταία θέση, τότε αν σε κάποιο βήμα βρεθεί στην πρώτη θέση, τότε στο αμέσως επόμενο βήμα θα βρεθεί στην τελευταία θέση, όπου είδαμε ότι τότε η διαδικασία κάποια στιγμή θα σταματήσει.
Αν αρχικά ο αριθμός k+1

δεν βρίσκεται στην τελευταία θέση, και σε κανένα βήμα δεν βρεθεί στην πρώτη θέση, τότε εφαρμόζουμε το εξής: Έστω

ο αριθμός που αρχικά βρίσκεται στην τελευταία θέση (παρατηρούμε ότι αυτός δεν αλλάζει σε κανένα από τα βήματα). Η διαδικασία δεν επηρεάζεται αν αντιμεταθέσουμε τον αριθμό

με τον αριθμό k+1

, αφού τότε και ο

σε κανένα βήμα δεν θα βρεθεί στην πρώτη θέση. Έτσι όμως ο αριθμός k+1

θα βρίσκεται στην τελευταία θέση, όπου είδαμε ότι τότε η διαδικασία κάποια στιγμή θα σταματήσει.

Δημοσιεύτηκε: **Κυρ Μαρ 25, 2018 11:07 am**

Έστω μια διάταξη

. Ορίζουμε A(T)

το σύνολο όλων των χαρτιών τα οποία βρίσκονται στην θέση τους και ορίζουμε

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

Είναι άμεσο ότι με κάθε αντιμετάθεση το f(T)