Εννέα άτομα συμμετέχουν σε ένα παιχνίδι «Secret Santa» στο χριστουγεννιάτικο πάρτι του γραφείου. Ο καθένας φέρνει ένα δώρο, το οποίο θα δοθεί σε κάποιον άλλον, ώστε κάθε άτομο να προσφέρει ένα δώρο και να λάβει ένα δώρο.
Τα ονόματα όλων μπαίνουν σε έναν σάκο· κάθε άτομο τραβάει ένα όνομα στην τύχη. Έπειτα, το κάθε άτομο δίνει το δώρο του στο άτομο του οποίου το όνομα τράβηξε. Στη συνέχεια, κάθε άτομο δίνει το δώρο που έλαβε στο άτομο του οποίου το όνομα έχει τραβήξει εκείνο. Για παράδειγμα, αν ο Andy τραβήξει το όνομα της Betty και η Betty τραβήξει το όνομα της Chiara, τότε το δώρο του Andy καταλήγει στη Chiara. Ο λόγος που τα δώρα περνούν δύο φορές είναι για να μην ξέρει κανείς από πού προήλθε το τελικό του δώρο.
Ο υπεύθυνος του γραφείου, που δεν νοιάζεται ιδιαίτερα για τη μυστικότητα, δημοσιεύει αργότερα την ακόλουθη αναφορά:
Τα δώρα πήγαν: Andy → Chiara, Betty → Harriet, Chiara → Ivan, David → Greg, Elinor → Betty, Frederica → Andy, Greg → Elinor, Harriet → David, Ivan → Frederica.
Να αποδείξετε ότι η αναφορά είναι λανθασμένη.
1 σχόλιο:
Το προσεγγίζω, ελπίζω σωστά, με (ελαφρώς προχωρημένη ίσως) συνδυαστική ανάλυση..
ΑπάντησηΔιαγραφήΓια εξοικονόμηση χώρου, κρατώ μόνο τα αρχικά των ονομάτων των 9 ατόμων.
Σύμφωνα με την αναφορά, η σειρά δοτών δώρου:
(A,B,C,D,E,F,G,H,I)
αντιστοιχίζεται ακριβώς στη σειρά δεκτών:
(C,H,I,G,B,A,E,D,F)
Οι δύο πιο πάνω σειρές είναι μετάθεση η μία της άλλης
Κάθε δώρο φτάνει από τον αρχικό δότη στον τελικό δέκτη, σύμφωνα με την περιγραφή, έπειτα από 2 αντιμεταθέσεις δύο κάθε φορά στοιχείων (από ταν α στον β και από τον β στον γ), συνεπώς ο συνολικός αριθμός αντιμεταθέσεων, για να φτάσουν όλα τα δώρα στούς τελικούς δέκτες, είναι άρτιος, δηλαδή η σειρά δεκτών πρέπει να είναι άρτια μετάθεση της σειράς δοτών.
Αντιθέτως, η σειρά δεκτών είναι περιττή μετάθεση της σειράς δοτών, π.χ. μπορεί να προκύψει από τις ακόλουθες 7 αντιμεταθέσεις δύο στοιχείων της σειράς δοτών:
(A,C)(B,H)(A,I)(D,G)(B,E)(A,F)(D,E)
Επομένως, η αναφορά είναι εσφαλμένη...