Παίγνιο με κέρματα
Συντονιστές: Demetres, silouan
Παίγνιο με κέρματα
Έστω μία ακολουθία απο ρίψεις κερμάτων όπου . Το συμβολίζει κορόνα και το γράμματα.
Μία ακολουθία λέγεται π-καλή εάν για κάθε ισχύει οτι η υπακολουθία περιέχει περισσότερες κορόνες απ'οτι γράμματα. Πχ για έχουμε τις εξής π-καλές ακολουθίες:
(1,1,1,1),(1,1,1,0),(1,1,0,1)
Παίζετε το εξής παίγνιο με έναν φίλο σας. Ο φίλος σας διαλέγει μια τυχαία ακολουθία με στοιχεία (απο τις που υπάρχουν συνολικά). Εάν είναι π-καλή τότε κερδίζετε εσείς διαφορετικά κερδίζει ο φίλος σας. Επειδή ο φίλος σας θεωρεί οτι είναι εξαιρετικά απίθανο να βρεθεί μία ακολουθία οπου το πλήθος των κορόνων είναι σε κάθε χρονική στιγμή μεγαλύτερο απο αυτό των γραμμάτων, σας δίνει 1000 Ευρώ εάν κερδίσετε και εσείς του δίνετε μόνο 100 εάν χάσετε.
Ωστόσο είστε κλεισμένος σε μία αίθουσα χωρίς βοήθεια υπολογιστή και ο φίλος σας θέλει απάντηση μέσα στην επόμενη ώρα. Δέχεστε να παίξετε το παίγνιο ή όχι?
(Συγγνώμη για την πολυλογία. Απλώς ήθελα να τονίσω οτι το πρόβλημα λύνεται χωρίς την χρήση υπολογιστή αν και χρειάζεται λίγες πράξεις (πάντως όχι ). Επιπλέον δεν είμαι σίγουρος αν η δυσκολία είναι για Αρχιμήδη οπότε το αφήνω στους συντονιστές να αποφασίσουν)
Μία ακολουθία λέγεται π-καλή εάν για κάθε ισχύει οτι η υπακολουθία περιέχει περισσότερες κορόνες απ'οτι γράμματα. Πχ για έχουμε τις εξής π-καλές ακολουθίες:
(1,1,1,1),(1,1,1,0),(1,1,0,1)
Παίζετε το εξής παίγνιο με έναν φίλο σας. Ο φίλος σας διαλέγει μια τυχαία ακολουθία με στοιχεία (απο τις που υπάρχουν συνολικά). Εάν είναι π-καλή τότε κερδίζετε εσείς διαφορετικά κερδίζει ο φίλος σας. Επειδή ο φίλος σας θεωρεί οτι είναι εξαιρετικά απίθανο να βρεθεί μία ακολουθία οπου το πλήθος των κορόνων είναι σε κάθε χρονική στιγμή μεγαλύτερο απο αυτό των γραμμάτων, σας δίνει 1000 Ευρώ εάν κερδίσετε και εσείς του δίνετε μόνο 100 εάν χάσετε.
Ωστόσο είστε κλεισμένος σε μία αίθουσα χωρίς βοήθεια υπολογιστή και ο φίλος σας θέλει απάντηση μέσα στην επόμενη ώρα. Δέχεστε να παίξετε το παίγνιο ή όχι?
(Συγγνώμη για την πολυλογία. Απλώς ήθελα να τονίσω οτι το πρόβλημα λύνεται χωρίς την χρήση υπολογιστή αν και χρειάζεται λίγες πράξεις (πάντως όχι ). Επιπλέον δεν είμαι σίγουρος αν η δυσκολία είναι για Αρχιμήδη οπότε το αφήνω στους συντονιστές να αποφασίσουν)
Λέξεις Κλειδιά:
- Demetres
- Γενικός Συντονιστής
- Δημοσιεύσεις: 8989
- Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
- Τοποθεσία: Λεμεσός/Πύλα
- Επικοινωνία:
Re: Παίγνιο με κέρματα
Γράφουμε για το πλήθος τον π-καλών ακολουθιών μήκους .
Έχουμε . Πράγματι είναι απλό ότι αν η ακολουθία είναι π-καλή το ίδιο ισχύει και για την ακολουθία . Αντιστρόφως αν η είναι π-καλή τότε το ίδιο ισχύει και για τις ακολουθίες και . [Ο λόγος είναι ότι η π-καλή ακολουθία πρέπει να έχει τουλάχιστον κορώνες.]
Επιπλέον έχουμε όπου είναι το πλήθος των π-καλών ακολουθιών οι οποίες έχουν κορώνες και γράμματα. Είναι άμεσο ότι όπου είναι οι αριθμοί Catalan. [Αναγκαστικά είναι και η ακολουθία έχει άσσους, μηδενικά με κάθε υπακολουθία να έχει τουλάχιστον τόσους άσσους όσα μηδενικά. Αυτός όμως είναι ένας από τους γνωστούς ορισμούς της ακολουθίας Catalan.]
Άρα
Η ακολουθία ξεκινάει με . (Εύκολος υπολογισμός με βάση τον τύπο.) Έχουμε . Άρα και τέλος .
Οπότε η πιθανότητα νίκης είναι οπότε συμφέρει να παίξουμε.
Επεξεργασία: Ισχύει ότι αλλά δεν βλέπω κάποια άμεση συνδυαστική απόδειξη.
Έχουμε . Πράγματι είναι απλό ότι αν η ακολουθία είναι π-καλή το ίδιο ισχύει και για την ακολουθία . Αντιστρόφως αν η είναι π-καλή τότε το ίδιο ισχύει και για τις ακολουθίες και . [Ο λόγος είναι ότι η π-καλή ακολουθία πρέπει να έχει τουλάχιστον κορώνες.]
Επιπλέον έχουμε όπου είναι το πλήθος των π-καλών ακολουθιών οι οποίες έχουν κορώνες και γράμματα. Είναι άμεσο ότι όπου είναι οι αριθμοί Catalan. [Αναγκαστικά είναι και η ακολουθία έχει άσσους, μηδενικά με κάθε υπακολουθία να έχει τουλάχιστον τόσους άσσους όσα μηδενικά. Αυτός όμως είναι ένας από τους γνωστούς ορισμούς της ακολουθίας Catalan.]
Άρα
Η ακολουθία ξεκινάει με . (Εύκολος υπολογισμός με βάση τον τύπο.) Έχουμε . Άρα και τέλος .
Οπότε η πιθανότητα νίκης είναι οπότε συμφέρει να παίξουμε.
Επεξεργασία: Ισχύει ότι αλλά δεν βλέπω κάποια άμεση συνδυαστική απόδειξη.
Re: Παίγνιο με κέρματα
Πολύ όμορφη η λύση του Δημήτρη.
Σε παρόμοιο πνεύμα:
Ορίζουμε (με φυσικό, ακέραιο) το πλήθος των κ-καλών ακολουθιών μήκους με να ορίζεται ως το πλήθος των άσσων πλήν το πλήθος των μηδενικών στην ακολουθία.
Εύκολα βλέπουμε οτι για εφόσον οι άσσοι πρέπει να είναι πάντα περισσότεροι απο τα μηδενικά. Επιπλέον εφόσον υπάρχει μονάχα μία ακολουθία με στοιχεία που να έχει περισσότερους άσσους απο μηδενικά. Η ακολουθία αυτή είναι αυτή που αποτελείται μονάχα απο άσσους. Τέλος για προφανώς.
Άρα μένει να βρούμε όλες τις κ-καλές ακολουθίες μήκους με δοσμένο . Τότε κάθε μία απο αυτές δημιουργείται είτε απο:
(i) μία κ-καλή ακολουθία μήκους η οποία έχει περισσότερους άσσους απο μηδενικά προσθέτοντας στο τέλος της. (πιθανώς να μην υπάρχουν τέτοιες ακολουθίες εάν )
(ii) μία κ-καλή ακολουθία μήκους η οποία έχει περισσότερους άσσους απο μηδενικά προσθέτοντας στο τέλος της. O λόγος για τον οποίο η νεα ακολουθία θα είναι κ-καλή είναι επειδή υποθέσαμε .
Άρα συμπεραίνουμε οτι για ισχύει
Συνεπώς μπορούμε εύκολα να δημιουργήσουμε τον πίνακα . Βάζουμε άσσους στην διαγώνιο και το κάθε κελί είναι το άθροισμα των 2 κελιών πάνω δεξιά και πάνω αριστερά (αν δεν υπάρχει πάνω αριστερά κελί τότε εννοείται οτι έχει τιμή )
Το σύνολο των κ-καλών κελιών μήκους είναι . Αθροίζοντας την τελευταία γραμμή βρίσκουμε
άρα η πιθανότητα να κερδίσουμε είναι και συνεπώς μας συμφέρει να παίξουμε.
Σε παρόμοιο πνεύμα:
Ορίζουμε (με φυσικό, ακέραιο) το πλήθος των κ-καλών ακολουθιών μήκους με να ορίζεται ως το πλήθος των άσσων πλήν το πλήθος των μηδενικών στην ακολουθία.
Εύκολα βλέπουμε οτι για εφόσον οι άσσοι πρέπει να είναι πάντα περισσότεροι απο τα μηδενικά. Επιπλέον εφόσον υπάρχει μονάχα μία ακολουθία με στοιχεία που να έχει περισσότερους άσσους απο μηδενικά. Η ακολουθία αυτή είναι αυτή που αποτελείται μονάχα απο άσσους. Τέλος για προφανώς.
Άρα μένει να βρούμε όλες τις κ-καλές ακολουθίες μήκους με δοσμένο . Τότε κάθε μία απο αυτές δημιουργείται είτε απο:
(i) μία κ-καλή ακολουθία μήκους η οποία έχει περισσότερους άσσους απο μηδενικά προσθέτοντας στο τέλος της. (πιθανώς να μην υπάρχουν τέτοιες ακολουθίες εάν )
(ii) μία κ-καλή ακολουθία μήκους η οποία έχει περισσότερους άσσους απο μηδενικά προσθέτοντας στο τέλος της. O λόγος για τον οποίο η νεα ακολουθία θα είναι κ-καλή είναι επειδή υποθέσαμε .
Άρα συμπεραίνουμε οτι για ισχύει
Συνεπώς μπορούμε εύκολα να δημιουργήσουμε τον πίνακα . Βάζουμε άσσους στην διαγώνιο και το κάθε κελί είναι το άθροισμα των 2 κελιών πάνω δεξιά και πάνω αριστερά (αν δεν υπάρχει πάνω αριστερά κελί τότε εννοείται οτι έχει τιμή )
Το σύνολο των κ-καλών κελιών μήκους είναι . Αθροίζοντας την τελευταία γραμμή βρίσκουμε
άρα η πιθανότητα να κερδίσουμε είναι και συνεπώς μας συμφέρει να παίξουμε.
Μέλη σε σύνδεση
Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 7 επισκέπτες