Παίγνιο με κέρματα

taratoris · #1

Έστω μία ακολουθία απο ρίψεις κερμάτων x=x_1,x_2,...,x_n

όπου $x_i \in \{0,1\}$ . Το

συμβολίζει κορόνα και το

γράμματα.

Μία ακολουθία x=x_1,x_2,...,x_n

λέγεται π-καλή εάν για κάθε k=1,2,...,n

ισχύει οτι η υπακολουθία x=x_1,x_2,...,x_k

περιέχει περισσότερες κορόνες απ'οτι γράμματα. Πχ για n=4

έχουμε τις εξής π-καλές ακολουθίες:

(1,1,1,1),(1,1,1,0),(1,1,0,1)

Παίζετε το εξής παίγνιο με έναν φίλο σας. Ο φίλος σας διαλέγει μια τυχαία ακολουθία με

στοιχεία (απο τις $2^{12}$ που υπάρχουν συνολικά). Εάν είναι π-καλή τότε κερδίζετε εσείς διαφορετικά κερδίζει ο φίλος σας. Επειδή ο φίλος σας θεωρεί οτι είναι εξαιρετικά απίθανο να βρεθεί μία ακολουθία οπου το πλήθος των κορόνων είναι σε κάθε χρονική στιγμή μεγαλύτερο απο αυτό των γραμμάτων, σας δίνει 1000 Ευρώ εάν κερδίσετε και εσείς του δίνετε μόνο 100 εάν χάσετε.

Ωστόσο είστε κλεισμένος σε μία αίθουσα χωρίς βοήθεια υπολογιστή και ο φίλος σας θέλει απάντηση μέσα στην επόμενη ώρα. Δέχεστε να παίξετε το παίγνιο ή όχι?

(Συγγνώμη για την πολυλογία. Απλώς ήθελα να τονίσω οτι το πρόβλημα λύνεται χωρίς την χρήση υπολογιστή αν και χρειάζεται λίγες πράξεις (πάντως όχι $2^{12}$ ). Επιπλέον δεν είμαι σίγουρος αν η δυσκολία είναι για Αρχιμήδη οπότε το αφήνω στους συντονιστές να αποφασίσουν)

#2

Γράφουμε $T_{n}$ για το πλήθος τον π-καλών ακολουθιών μήκους

.

Έχουμε $\displaystyle{ T_{2n+1} = 2T_{2n}}$ . Πράγματι είναι απλό ότι αν η ακολουθία $x_1 , \ldots x_{2n} , x_{2n+1}$ είναι π-καλή το ίδιο ισχύει και για την ακολουθία $x_1 , \ldots x_{2n}$ . Αντιστρόφως αν η $x_1 , \ldots x_{2n}$ είναι π-καλή τότε το ίδιο ισχύει και για τις ακολουθίες $x_1 , \ldots x_{2n},1$ και $x_1 , \ldots x_{2n},1$ . [Ο λόγος είναι ότι η π-καλή ακολουθία $x_1 , \ldots x_{2n}$ πρέπει να έχει τουλάχιστον n+1

κορώνες.]

Επιπλέον έχουμε $\displaystyle{ T_{2n+2} = 2(T_{2n+1}-S_n) + S_n}$ όπου S_n

είναι το πλήθος των π-καλών ακολουθιών $x_1,\ldots,x_{2n+1}$ οι οποίες έχουν n+1

κορώνες και

γράμματα. Είναι άμεσο ότι S_n = C_n

όπου

είναι οι αριθμοί Catalan. [Αναγκαστικά είναι x_1 = 1

και η ακολουθία $x_2,\ldots,x_{2n+1}$ έχει

άσσους,

μηδενικά με κάθε υπακολουθία $x_2,\ldots,x_k$ να έχει τουλάχιστον τόσους άσσους όσα μηδενικά. Αυτός όμως είναι ένας από τους γνωστούς ορισμούς της ακολουθίας Catalan.]

Άρα $\displaystyle{ T_{2n+2} = 2T_{2n+1} - C_n = 4T_{2n} - \frac{1}{n+1}\binom{2n}{n}}$

Η ακολουθία C_n

ξεκινάει με 1,2,5,14,35

. (Εύκολος υπολογισμός με βάση τον τύπο.) Έχουμε T_4 = 3

. Άρα $T_6 = 12-2=10, T_8 = 40 - 5 = 35, T_{10} = 140-14 = 126$ και τέλος $T_{12} = 504-42 = 462$ .

Οπότε η πιθανότητα νίκης είναι $\displaystyle{ \frac{462}{4196} > \frac{1}{10} > \frac{1}{11}}$ οπότε συμφέρει να παίξουμε.

$\rule{600pt}{0.8pt}$

Επεξεργασία: Ισχύει ότι $\displaystyle{ T_{2n} = \binom{2n-1}{n}}$ αλλά δεν βλέπω κάποια άμεση συνδυαστική απόδειξη.

taratoris · #3

Πολύ όμορφη η λύση του Δημήτρη.

Σε παρόμοιο πνεύμα:

Ορίζουμε T(n,m)

(με $n\geq 1$ φυσικό,

ακέραιο) το πλήθος των κ-καλών ακολουθιών μήκους

με

να ορίζεται ως το πλήθος των άσσων πλήν το πλήθος των μηδενικών στην ακολουθία.

Εύκολα βλέπουμε οτι T(n,m)=0

για $m\leq0$ εφόσον οι άσσοι πρέπει να είναι πάντα περισσότεροι απο τα μηδενικά. Επιπλέον T(n,n)=1

$\forall n>0$ εφόσον υπάρχει μονάχα μία ακολουθία με

στοιχεία που να έχει

περισσότερους άσσους απο μηδενικά. Η ακολουθία αυτή είναι αυτή που αποτελείται μονάχα απο άσσους. Τέλος T(n,m)=0

για

προφανώς.

Άρα μένει να βρούμε όλες τις κ-καλές ακολουθίες μήκους

με δοσμένο m<n

. Τότε κάθε μία απο αυτές δημιουργείται είτε απο:

(i) μία κ-καλή ακολουθία μήκους n-1

η οποία έχει m-1

περισσότερους άσσους απο μηδενικά προσθέτοντας

στο τέλος της. (πιθανώς να μην υπάρχουν τέτοιες ακολουθίες εάν T(n-1,m-1)=0

)

(ii) μία κ-καλή ακολουθία μήκους n-1

η οποία έχει m+1

περισσότερους άσσους απο μηδενικά προσθέτοντας

στο τέλος της. O λόγος για τον οποίο η νεα ακολουθία θα είναι κ-καλή είναι επειδή υποθέσαμε n>m

.

Άρα συμπεραίνουμε οτι για n>m>0

ισχύει

Συνεπώς μπορούμε εύκολα να δημιουργήσουμε τον πίνακα T(n,m)

. Βάζουμε άσσους στην διαγώνιο και το κάθε κελί είναι το άθροισμα των 2 κελιών πάνω δεξιά και πάνω αριστερά (αν δεν υπάρχει πάνω αριστερά κελί τότε εννοείται οτι έχει τιμή

)

$\begin{center} \begin{tabular}{ | c | c | c | c | c | c | c | c | c | c | c | c | } \hline 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \\ \hline 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \\ \hline 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \\ \hline 0 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \\ \hline 2 & 0 & 3 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \\ \hline 0 & 5 & 0 & 4 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & \\ \hline 5 & 0 & 9 & 0 & 5 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & \\ \hline 0 & 14 & 0 & 14 & 0 & 6 & 0 & 1 & 0 & 0 & 0 & 0 & \\ \hline 14 & 0 & 28 & 0 & 20 & 0 & 7 & 0 & 1 & 0 & 0 & 0 & \\ \hline 0 & 42 & 0 & 48 & 0 & 27 & 0 & 8 & 0 & 1 & 0 & 0 & \\ \hline 42 & 0 & 90 & 0 & 75 & 0 & 35 & 0 & 9 & 0 & 1 & 0 & \\ \hline 0 & 132 & 0 & 165 & 0 & 110 & 0 & 44 & 0 & 10 & 0 & 1 & \\ \hline \end{tabular} \end{center}$

Το σύνολο των κ-καλών κελιών μήκους

είναι

. Αθροίζοντας την τελευταία γραμμή βρίσκουμε

132+165+110+44+10+1=462

άρα η πιθανότητα να κερδίσουμε είναι $\displaystyle \frac{462}{2^{12}}>\frac{1}{10}$ και συνεπώς μας συμφέρει να παίξουμε.

Παίγνιο με κέρματα

Παίγνιο με κέρματα

Re: Παίγνιο με κέρματα

Re: Παίγνιο με κέρματα

Μέλη σε σύνδεση