Κρατάτε στο χέρι σας 5 χαρτιά που τα έχω επιλέξει εγώ κατά τύχη από μια συνηθισμένη τράπουλα (με 52 χαρτιά). Απέναντί σας βρίσκεται ο φίλος σας στον οποίο δείχνετε 4 από τα χαρτιά σας το ένα μετά το άλλο, όποια εσείς θέλετε. Ο φίλος (συνεργάτης) σας πρέπει να μαντέψει ποιο είναι το πέμπτο χαρτί. Πώς θα το κάνετε;
Μπορείτε φυσικά να έχετε συνεννοηθεί (από πριν πάρετε τα χαρτιά στα χέρια σας) με το φίλο σας για το πώς θα ενεργήσετε αλλά η μόνη πληροφορία που επιτρέπεται να περάσει ανάμεσά σας είναι τα 4 αυτά χαρτιά. Ούτε κλείσιμο του ματιού, ούτε αναποδογύρισμα των χαρτιών, ούτε άλλα τέτοια κόλπα.
Προβλήματα Μαθηματικών 
Τα χαρτιά της τράπουλας μπορεί κανείς να τα δεί σα ζεύγη (χρώμα, αριθμός) όπου το χρώμα παίρνει 4 τιμές και ο αριθμός 13, ή μπορεί να τα δεί σαν αριθμούς από 1 έως 52. Οι λύσεις μπορούν να περιγραφούν έτσι κι αλλιώς.
Η πρώτη παρατήρηση που κάνουμε είναι ότι σίγουρα στα 5 χαρτιά που υπάρχουν στα χέρια μας υπάρχουν δύο με το ίδιο χρώμα. Μπορούμε να ακολουθήσουμε τη σύμβαση (με το συμπαίκτη μας) ότι το πρώτο χαρτί που ρίχνουμε κάτω έχει το ίδιο χρώμα με το χαρτί που πρέπει να μαντέψει. Μένει να του μεταδώσουμε και την πληροφορία για τον αριθμό χρησιμοποιώντας τα επόμενα τρία φύλλα που θα του δείξουμε, και όχι μόνο …
Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 27 Αυγούστου, 2009 @ 2:33 πμ
Πιστεύω ότι έχω βρει μια λύση, αλλά δεν έχω τώρα τον χρόνο να την καθαρογράψω. Πάντως η «βοήθεια» για το χρώμα του χαρτιού, μου φαίνεται «παραπλανητική». Συγκεκριμένα μάλιστα, προσπαθώντας να «βελτιώσω» τη λύση μου, κατέληξα (??) ότι η λύση που δίνω είναι κατά κάποιο τρόπο βέλτιστη (δεν έχω απόδειξη για αυτό), δηλαδή δεν μπορεί να απόδώσει περισσότερη πληροφορία… Πάντως με την σύμβαση «το πρώτο χαρτί που ρίχνω να προσδιορίζει το χρώμα του κρυφού χαρτιού», δεν μπόρεσα να βρω λύση.
Θα προσπαθήσω αν βρω χρόνο το βράδυ ή μια απο τις επόμενες ημέρες να κάνω το σχεδιάγραμμα του τεχνάσματος.
ΥΓ: Συγχωρήστε με για το πολύ «Fermat» ύφος μου, απλά η αλήθεια είναι ότι ο χρόνος με πιέζει πολύ… 😦
Μου αρέσει!Μου αρέσει!
Σχόλιο από nefelh — 6 Σεπτεμβρίου, 2009 @ 2:58 μμ
Και τώρα που επιτέλους βρήκα λίγο χρόνο…
Μια σύντομη version της ιδέας μου. Αρχικά διατάσουμε τα χαρτιά με κάποιο τρόπο. πχ θεωρούμε 1ο χαρτί τον άσσο μπαστούνι δε’υτερο το δύο μπαστούνι, τρίτο το τρία μπαστούνι …(κλπ)… 13ο το ρήγα μπαστούνι 14ο τον άσσο σπαθι …(κλπ)… 27ο τον άσσο καρό …(κλπ)… 40ο τον άσσο κούπα …(κλπ)… και 52ο τον ρήγα κούπα.
Έστω Α,Β,Γ,Δ,Ε τα πέντε χαρτιά που τραβάμε διατεταγμένα με την σειρά που ανέφερα παραπάνω (Α<Β<Γ<Δ<Ε). Διακρίνω περιπτώσεις:
i) Το Β βρίσκεται το πολύ 24 χαρτιά μετά το Α.
Τότε ανοίγω τα χαρτιά Α,Γ,Δ,Ε. Τα χαρτιά αυτά είναι τέσσερα άρα μπορώ να τα ανοίξω με 4!=24 τρόπους. Μπορεί να έχει προσυμφωνηθεί ο κάθε ένας από αυτούς να μεταφράζεται σε έναν αριθμό από το 1 έως το 24 που θα δηλώνει στον συμπαίκτη το πόσο απέχει το Β από το Α. (σημ: η διάταξη είναι γνωστή και στον συμπάικτη μου, άρα αφού δει και τα 4 χαρτιά, μπορεί να τα διατάξει και αυτό θα επιτρέπει και την αποκωδικοπίηση της διάταξης.
ii) Το Β βρίσκεται περισσότερα από 24 χαρτιά μετά το Α.
Τότε ανοίγω τα φύλλα Β,Γ,Δ,Ε και υπολογίζω πόσα χαρτιά ΜΕΤΑ το Β είναι το Α (εννοώντας ότι μετά τον ρήγα κούπα το "επόμενο" φύλλο είναι ο άσσος μπαστούνι – δηλαδή τα χαρτιά κάνουν "κύκλο"). Σε αυτή την μέτρηση ΔΕΝ υπολογίζω τα τρία φύλλα που θα ανοίξω. Μπορεί να αποδειχθεί ότι η απόσταση αυτή είναι το πολύ 24 χαρτιά. Οπότε πάλι μπορώ να την κωδικοποιήσω ανάλογα με την σειρά που θα βγάλω τα 4 χαρτιά.
Αποκωδικοποίηση: Ο φίλος μου αριχκά βλέπει τα 4 φύλλα και νοερά τα διατάσσει σύμφωνα με την (όποια και αν είναι) προσυμφωνημένη διάταξη. Έπειτα από την σειρά που στέκονται στο τραπέζι βλέπει ότι έχουν την n-οστή διάταξη. Τέλος, ξεκινόντας από το μικρότερο χαρτί (με την διάταξη που έχουμε συμφωνήσει πάντοτε) υπολογίζει ποιό χαρτί βρίσκεται n θέσεις μπροστά από το αρχικό, μη υπολογίζοντας στην αρίθμηση αυτά που ήδη έχουν εμφανιστεί.
Μου αρέσει!Μου αρέσει!
Σχόλιο από nefelh — 6 Σεπτεμβρίου, 2009 @ 10:05 μμ
Πολύ σωστά, μπράβο.
Ιδού και η (ίδια ουσιαστικά) λύση χρησιμοποιώντας τα χρώματα:
Σίγουρα έχουμε στην πεντάδα δύο φύλλα του ίδιου χρώματος, έστω τα Α και Β. Αν θεωρήσουμε τα φύλλα του ίδιου χρώματος ως τους αριθμούς 0-12 (π.χ. άσος το 1, 2 το 2, …, 10 το 10, J το 11, Q το 12 και K το 0) τότε στον κύκλο 0..12 (κοιτώντας δηλ. τους αριθμούς mod 13) ή το Β θα είναι το πολύ 6 μετά το Α ή το Α θα είναι το πολύ 6 μετά το Β. Στην πρώτη περίπτωση το πρώτο φύλλο που δείχνουμε είναι το Α και στη δεύτερη το Β. Με τη διάταξη των υπολοίπων τριώ κωδικοποιούμε 3!=6 αριθμούς, το οποίο αρκεί για να προδιορίσουμε την απόσταση του Β μετά το Α (στην πρώτη περίπτωση και ομοίως στη δεύτερη).
Η λύση είναι φυσικά η ίδια. Το μόνο πλεονέκτημα της λύσης με τα χρώματα είναι ότι είναι κάπως πιο εύκολη στην υλοποίηση σε πραγματικές συνθήκες αφού οι πράξεις γίνονται με μικρά νούμερα.
Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 7 Σεπτεμβρίου, 2009 @ 12:25 πμ
Αν και η ιδέα είναι ίδια, η λύση σας είναι πραγματικά πολύ πιο όμορφη και (το κυριοτερο για μένα σε αυτό το πρόβλημα) εύκολα υλοποιήσιμη! Τι να το κάνουμε τόσο χρόνο σκέψη, αν δεν μπορέσουμε να το υλοποιήσουμε με κάποιο φίλο για να εντυπωσιάσουμε τη παρέα?!
—–
Παραμπιτπόντως -και σκόπιμα δημοσιως!- να σας ευχαριστήσω για την προσπάθεια που κάνετε σε αυτό το blog. Μέσα από αυτή τη σελίδα αφενός έχω κρατήσει επαφή με το αντικείμενο των μαθηματικών, τώρα που εξ ανάγκης έχω απομακρυνθεί, και αφεταιρου μου έχει κρατήσει υπέροχη παρέα (ιδιέταιρα με αυτά τα «παιχνίδια» που δημοσιεύετε) στην πληκτική και μονότονη θητεία μου στον Ε.Σ.
Μου αρέσει!Μου αρέσει!
Σχόλιο από nefelh — 8 Σεπτεμβρίου, 2009 @ 8:53 μμ
Νά’σαι καλά, και καλός πολίτης.
Τα μαθηματικά μπορούν να είναι πολύ καλή παρέα στις ώρες της μοναξιάς που, μ’ένα καλό πρόβλημα, μπορούν και να τη μετατρέψουν σε απόλαυση.
Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 8 Σεπτεμβρίου, 2009 @ 9:02 μμ
Μία παραλλαγή της λύσης είναι να κάνουμε simulate τον γνωστό «binary search algorithm» για τα εναπομείναντα 12 χαρτιά (Πράγματι το πρώτο χαρτί θα δηλώνει το χρώμα του 5ου χαρτιού, αλλά και κάτι ακόμη)
Θεωρώ την εξής διάταξη των χαρτιών ίδιου χρώματος:
Α, 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K
που αντιστοιχούν στην κατάταξη αριθμών:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13
Στη συνέχεια υιοθετώ ένα παράδειγμα για να είναι πιο εύκολη η κατανόηση. Μπορεί εύκολα να γραφεί με φορμαλισμούς.
ΠΑΡΑΔΕΙΓΜΑ:
Έστω ότι τα δύο χαρτιά ίδιου χρώματος (π.χ. κόκκινες κούπες) είναι το 4 και το 10.
Πρώτα κατεβάζω το μεγαλύτερο από τα δύο, το 10. Ήδη ο φίλος μου γνωρίζει πως το χαρτί προς εύρεση, έστω x (στο παράδειγμα x=4), είναι κόκκινη κούπα από Α εώς 9 (που αντιστοιχούν στις θέσεις 1-9). Έστω min=1, max=9. Στό διάστημα [1, 9] εφαρμόζω το binary search. Επιπλέον για κάθε χαρτί που κατεβάζω ορίζω «οριζόντια» και «κάθετη» τοποθέτηση του με την εξής σύμβαση: Οριζόντια τοποθέτηση του χαρτιού ( _ ) δηλώνει πως το x είναι μικρότερο από τον αριθμό med = (min+max)/2 (στο παράδειγμά μας είναι med=5. Κατά σύμβαση αγνοώ το δεκαδικό μέρος της διαίρεσης, εάν και όποτε προκύπτει). Κάθετη τοποθέτηση του χαρτιού ( | ) δηλώνει πως το x είναι μεγαλύτερο απο το med. Επειδή θέλουμε να καθοδηγήσουμε την εύρεση στο x=4, τοποθετούμε την κόκκινη κούπα 10 οριζόντια. Με την κίνηση αυτή έχουμε περιορίσει το πεδίο τιμών του x στο διάστημα [1, 5]. Η διαδικασία αυτή ορίζεται επαναλληπτικά εώς ότου καταλήξουμε σε μία μοναδικά ορισμένη τιμή για το x. Επομένως, στο παράδειγμά μας, για το επόμενο χαρτί που θα κατεβάσουμε ισχύει ότι min=1, max=5, med=3. Αρκεί να κατεβάσουμε το επόμενο χαρτί με κάθετη τοποθέτηση, υπονοώντας πως το x είναι μεγαλύτερο από 3. Όταν το επόμενο χαρτί ταυτίζεται με το καινούριο med τότε είναι περιττό να κατεβάσουμε επιπλέον χαρτί και επομένως αρκεί να δηλώσουμε ότι σταματάμε. Στο παράδειγμά μας σταματάμε, καταδεικνύωντας έτσι στον φίλο μας πως το x προς εύρεση ήταν το 4.
Άρα οι κινήσεις μας στο παράδειγμα θα ήταν:
_ |
Παρακάτω αναφέρω μερικά επιπλέον παραδείγματα. Σε κάθε περίπτωση ρίχνουμε κάτω το μεγαλύτερο απο τα δύο χαρτιά με όμοιο χρώμα και απλά προσέχουμε την οριζόντια/κάθετη τοποθέτηση.
Αν είχαμε το 3 και το 10, ορίζεται binary search στο διάστημα [1, 9]. Οι κινήσεις μας θα ήταν:
_ (Γνωριζουμε απο το πρώτο χαρτί πως είναι στο [1, 5] και επειδή δε ρίχνουμε άλλο χαρτί υπονοείται πως x = ο καινούριος med = 3).
Αν είχαμε το 3 και το K (i.e., 13), ορίζεται binary search στο διάστημα [1, 12]. οι κινήσεις μας θα ήταν:
_ (Γνωριζουμε απο το πρώτο χαρτί πως είναι στο [1, 6] και επειδή δε ρίχνουμε άλλο χαρτί υπονοείται πως x = ο καινούριος med = 3).
Αν είχαμε το 8 και το K (i.e., 13), ορίζεται binary search στο διάστημα [1, 12]. οι κινήσεις μας θα ήταν:
| _ | (Γνωριζουμε απο το πρώτο χαρτί πως είναι στο [7, 12], από το δεύτερο πως είναι στο [7, 8] (άν ήταν x=9 δε θα ρίχναμε δεύτερο χαρτί) και από το τρίτο καταδεινύεται πως x = 8 (άν ήταν x=7 δε θα ρίχναμε τρίτο χαρτί)).
Μία ιδιαίτερη περίπτωση προκύπτει εάν έχουμε το 3 και το 10, ή 6 και 12, κτλ. (περιπτώσεις όπου ταυτίζεται το πρώτο med με τον x). Σε αυτήν την περίπτωση η τοποθέτηση του μεγάλου χαρτιού οριζόντια ή κάθετα θα ήταν παραπλανητική. Αρκεί μία ιδιαίτερη και απλή σύμβαση για αυτήν την περίπτωση η οποία επαφίεται στην φαντασία των συμπαικτών 🙂
Πλεονεκτήματα:
– Δε χρειάζεται να διακρίνουμε μεταξύ Α και Β. Πάντοτε κατεβάζουμε το μεγαλύτερο απο τα δύο με βάση τη προκαθορισμένη διάταξη (1-13).
– Δε χρειάζεται να κωδικοποιούμε όλους τους αριθμούς και επομένως μπορούμε να τελειώσουμε γρηγορότερα τη διαδικασία, π.χ. κατεβάζοντας μόνο 2 ή 3 χαρτια. Σε κάθε βήμα το πεδίο τιμών περιορίζεται κατά μισό.
– Χρειάζονται μόνο 3 χαρτιά για τη χειρότερη περίπτωση. Σε πολλές περιπτώσεις 1 ή 2 μόνο χαρτιά είναι αρκετά για να περάσω στον φίλο μου την πληροφορία για το χαρτί ίδιου χρώματος που κρατάω.
– Είναι πιο πρακτικό γιατί δε χρειάζεται να κάνουμε πολλές πράξεις. Θα μπορούσαμε επίσης να ορίζουμε πάντα το binary search στο διάστημα [1-12], ανεξάρτητα από την τιμή του μεγάλου χαρτιού. Σε αυτήν την περίπτωση έχουμε σταθερούς meds κάθε φορά (π.χ. ο πρώτος είναι πάντα 6, ο δεύτερος είτε 3 είτε 9 ανάλογα με την τοποθέτηση του πρώτου χαρτιού, κτλ.) και γλυτώνουμε τις πράξεις υπολογισμού των meds δυναμικά (όπως αυτοί ορίζονται απο το αρχικό διάστημα [1, max]).
Μου αρέσει!Μου αρέσει!
Σχόλιο από Manos Papagelis — 9 Νοεμβρίου, 2009 @ 3:38 μμ
Πρακτική λύση αλλά έχεις παραβεί τους κανόνες του προβλήματος. Η οριζόντια και κατακόρυφη τοποθέτηση συνιστούν μετάδοση πληροφορίας πέρα από τη σειρά με την οποία αποκαλύπτουμε τα χαρτιά και απαγορεύεται.
Μου αρέσει!Μου αρέσει!
Σχόλιο από Mihalis Kolountzakis — 9 Νοεμβρίου, 2009 @ 3:58 μμ