Combinatorics Word Derangements – Contest Style Problem
Αναδιατάξεις λέξεων χωρίς κανένα σωστό γράμμα
Μια αντιμετάθεση (derangement) μιας λέξης είναι μια αναγραμματισμένη μορφή της, στην οποία κανένα γράμμα δεν βρίσκεται στη σωστή του θέση.
Για παράδειγμα, η λέξη malem είναι αντιμετάθεση της lemma, αλλά η ammel δεν είναι.
Γνωρίζουμε ότι η λέξη solve έχει 44 αντιμεταθέσεις, η λέξη fathom έχει 265 αντιμεταθέσεις, και η λέξη unravel έχει 1854 αντιμεταθέσεις.
Ερώτηση: Πόσες αντιμεταθέσεις έχει η λέξη theorem;
Επιλογές:
(A) 640
(B) 907
(C) 1280
(D) 1814
(E) 1854
Word Derangements with Given Counts
Problem. A derangement of a word is an anagram of that word in which no letter is in its original position.
For example, “malem” is a derangement of “lemma”, but “ammel” is not.
You are told that the word “solve” has 44 derangements, the word “fathom” has 265 derangements, and the word “unravel” has 1854 derangements.
Question: How many derangements does the word “theorem” have?
Options:
(A) 640
(B) 907
(C) 1280
(D) 1814
(E) 1854
The answer is intentionally not revealed so that readers can work it out themselves.
1. Τα δύο e δεν μπορούν να πάνε στις θέσεις 3 και 6· μπορούν μόνο στις 5 θέσεις {1,2,4,5,7}. Άρα υπάρχουν: C(5,2)=5!/3!*2!=5*4*3*2*1/3*2*1*2*1=5*3*4/3*2*1=60/6=10 επιλογές θέσεων για τα e. 2. Αφού τοποθετηθούν τα e, μένουν οι 5 διαφορετικοί χαρακτήρες t,h,o,r,m να τοποθετηθούν σε 5 θέσεις. Από τις αρχικές τους θέσεις οι 5 αντίστοιχες (1,2,4,5,7) δύο εξ αυτών έχουν ήδη καταληφθεί από τα e — δηλ. μόνο 3 από τα 5 γράμματα έχουν την απαγόρευση «να μην πάνε στη θέση τους» ενεργή. 3. Γι' αυτόμε χρήση Inclusion–Exclusion (αρχή συμπερίληψης-αποκλεισμού) για 5! με 3 απαγορευμένες σταθερές θέσεις: C=5!−(3,1)*4!+(3,2)*3!−(3,3)*2!=120−3*24+3*6−2=120-72+18-2=64 Άρα για κάθε επιλογή θέσεων των e έχουμε 64 έγκυρες τοποθετήσεις των υπολοίπων. 4. Τελικό: 10*64=640 Άρα η λέξη theorem έχει 640 αντιμεταθέσεις. (A)
1 σχόλιο:
1. Τα δύο e δεν μπορούν να πάνε στις θέσεις 3 και 6· μπορούν μόνο στις 5 θέσεις {1,2,4,5,7}.
ΑπάντησηΔιαγραφήΆρα υπάρχουν:
C(5,2)=5!/3!*2!=5*4*3*2*1/3*2*1*2*1=5*3*4/3*2*1=60/6=10
επιλογές θέσεων για τα e.
2. Αφού τοποθετηθούν τα e, μένουν οι 5 διαφορετικοί χαρακτήρες t,h,o,r,m να τοποθετηθούν σε 5 θέσεις.
Από τις αρχικές τους θέσεις οι 5 αντίστοιχες (1,2,4,5,7) δύο εξ αυτών έχουν ήδη καταληφθεί από τα e — δηλ. μόνο 3 από τα 5 γράμματα έχουν την απαγόρευση «να μην πάνε στη θέση τους» ενεργή.
3. Γι' αυτόμε χρήση Inclusion–Exclusion (αρχή συμπερίληψης-αποκλεισμού) για 5! με 3 απαγορευμένες σταθερές θέσεις:
C=5!−(3,1)*4!+(3,2)*3!−(3,3)*2!=120−3*24+3*6−2=120-72+18-2=64
Άρα για κάθε επιλογή θέσεων των e έχουμε 64 έγκυρες τοποθετήσεις
των υπολοίπων.
4. Τελικό: 10*64=640
Άρα η λέξη theorem έχει 640 αντιμεταθέσεις. (A)