The game starts with one blue disc and one red disc in the bag. On turn \(t\), the player draws one disc uniformly at random, notes its color, returns it, and then an extra red disc is added. Therefore the bag contains exactly one blue disc and \(t\) red discs on turn \(t\), so
$$P(\text{blue on turn }t)=\frac{1}{t+1},\qquad P(\text{red on turn }t)=\frac{t}{t+1}.$$
There are \(15\) turns in total, and the player wins exactly when blue appears more often than red. Since \(15\) is odd, that means at least \(8\) blue draws. If the total prize fund is \(M\) pounds, including the original stake, then the banker does not lose money on average precisely when \(M \cdot P(\text{win}) \le 1\). The task is to compute the largest integer \(M\) satisfying that inequality.
The crucial quantity is not the order of the draws, but how many blue draws have occurred after each turn. That turns the problem into a small distribution update over the possible blue counts.
Let \(B_t\) be the number of blue draws after the first \(t\) turns, and let
$$P_t(b)=P(B_t=b).$$
Only the values \(0 \le b \le t\) are possible. To end at exactly \(b\) blue draws after turn \(t\), there are only two possibilities:
$$P_t(b)=P_{t-1}(b)\cdot \frac{t}{t+1}+P_{t-1}(b-1)\cdot \frac{1}{t+1},$$
with base condition \(P_0(0)=1\) and \(P_0(b)=0\) for \(b \ne 0\). The first term means turn \(t\) was red, so the blue count stayed at \(b\). The second term means turn \(t\) was blue, so the previous count had to be \(b-1\).
After \(t\) turns, every probability \(P_t(b)\) has denominator
$$D_t=\prod_{i=1}^{t}(i+1)=(t+1)!.$$
Define the scaled quantity
$$A_t(b)=D_t\,P_t(b).$$
Multiplying the probability recurrence by \(D_t=(t+1)D_{t-1}\) removes every fraction and yields
$$A_t(b)=t\,A_{t-1}(b)+A_{t-1}(b-1).$$
This is the invariant exploited by the exact integer versions of the solution. The factor \(t\) comes from the \(t\) red discs available on turn \(t\), while the blue branch contributes a factor of \(1\) because there is always exactly one blue disc.
At the end, the winning probability is
$$P(\text{win})=\sum_{b=8}^{15} P_{15}(b)=\frac{\sum_{b=8}^{15} A_{15}(b)}{16!}.$$
If we collect the scaled values into a polynomial
$$F_t(x)=\sum_{b=0}^{t} A_t(b)x^b,$$
then the recurrence above becomes
$$F_t(x)=(t+x)F_{t-1}(x),\qquad F_0(x)=1,$$
so
$$F_t(x)=\prod_{i=1}^{t}(i+x).$$
The coefficient of \(x^b\) is exactly the scaled numerator for the event “there are \(b\) blue draws after \(t\) turns.” The implementations never need to manipulate this polynomial symbolically, but it explains why the integer recurrence is so clean.
The four-turn case is small enough to inspect by hand. Starting from \(A_0(0)=1\), the recurrence produces:
$$ \begin{aligned} t=0 &: [1] \\ t=1 &: [1,1] \\ t=2 &: [2,3,1] \\ t=3 &: [6,11,6,1] \\ t=4 &: [24,50,35,10,1]. \end{aligned} $$
These are the coefficients of
$$F_4(x)=(1+x)(2+x)(3+x)(4+x).$$
After four turns the common denominator is \(D_4=2\cdot3\cdot4\cdot5=120\). A win requires more blue than red, so with four turns the player needs \(3\) or \(4\) blue draws. Therefore
$$P(\text{win in 4 turns})=\frac{10+1}{120}=\frac{11}{120}.$$
The maximum profitable prize fund is then
$$\left\lfloor \frac{120}{11} \right\rfloor = 10,$$
which is a good sanity check for the recurrence.
For the actual problem, \(n=15\). Let
$$W=\sum_{b=8}^{15} A_{15}(b).$$
Then
$$P(\text{win})=\frac{W}{16!}.$$
If the prize fund \(M\) includes the returned stake, the banker's expected payout per game is \(M \cdot P(\text{win})\). To avoid an expected loss we need
$$M \le \frac{1}{P(\text{win})}=\frac{16!}{W}.$$
Hence the required answer is
$$\boxed{M_{\max}=\left\lfloor \frac{16!}{W} \right\rfloor.}$$
The implementation keeps a one-dimensional table indexed by the number of blue draws seen so far. Initially only the state “zero blue draws after zero turns” is nonzero. For each new turn, a fresh table is created and every reachable state contributes to two next states: one red transition that keeps the same blue count and one blue transition that increases it by one.
The Python implementation stores the probabilities themselves as exact rational numbers, so each transition multiplies by \(t/(t+1)\) or \(1/(t+1)\). The C++ and Java implementations clear the common denominator at every stage and store only the scaled numerators \(A_t(b)\). That is why their update rule uses integer multiplication by \(t\) for the red branch and plain addition for the blue branch.
After the fifteenth turn, the implementation sums all states with more blue draws than red draws, namely \(b=8,9,\dots,15\). In the rational version that sum is already the exact winning probability. In the scaled-integer versions, that sum is the numerator \(W\), while the common denominator is \(16!\). The final answer is obtained by one exact integer division, \(\left\lfloor 16!/W \right\rfloor\).
For \(n\) turns, the table has size \(n+1\), and turn \(t\) processes only the states \(0,1,\dots,t\). The total number of state updates is therefore
$$1+2+\cdots+n = O(n^2).$$
The memory usage is \(O(n)\), because only the current row and the next row are needed at any time. In this problem \(n=15\), so the computation is tiny. Even with exact fractions or big integers, the numbers remain small enough that arithmetic cost is negligible compared with the simplicity gained from keeping the calculation exact.
Zu Beginn liegen genau eine blaue und eine rote Scheibe im Beutel. In Runde \(t\) zieht der Spieler eine Scheibe zufällig, merkt sich die Farbe, legt die Scheibe zurück und fügt danach eine weitere rote Scheibe hinzu. Daher enthält der Beutel in Runde \(t\) genau eine blaue und \(t\) rote Scheiben, also
$$P(\text{blau in Runde }t)=\frac{1}{t+1},\qquad P(\text{rot in Runde }t)=\frac{t}{t+1}.$$
Insgesamt gibt es \(15\) Runden. Gewonnen wird genau dann, wenn Blau häufiger erscheint als Rot. Weil \(15\) ungerade ist, bedeutet das mindestens \(8\) blaue Ziehungen. Ist der gesamte Preisfonds \(M\) Pfund groß und enthält er den zurückgegebenen Einsatz bereits, dann verliert der Veranstalter im Erwartungswert genau dann kein Geld, wenn \(M \cdot P(\text{Gewinn}) \le 1\) gilt. Gesucht ist also das größte ganzzahlige \(M\), das diese Bedingung erfüllt.
Entscheidend ist nicht die genaue Reihenfolge der Farben, sondern nur, wie viele blaue Ziehungen nach jeder Runde bereits aufgetreten sind. Damit reduziert sich das Problem auf eine kleine Verteilung über mögliche Blau-Anzahlen.
Sei \(B_t\) die Anzahl blauer Ziehungen nach den ersten \(t\) Runden und
$$P_t(b)=P(B_t=b).$$
Möglich sind nur Werte \(0 \le b \le t\). Um nach Runde \(t\) genau \(b\) blaue Ziehungen zu haben, gibt es genau zwei Fälle:
$$P_t(b)=P_{t-1}(b)\cdot \frac{t}{t+1}+P_{t-1}(b-1)\cdot \frac{1}{t+1},$$
mit Anfangsbedingung \(P_0(0)=1\) und \(P_0(b)=0\) für \(b \ne 0\). Der erste Summand steht für einen roten Zug in Runde \(t\), der zweite für einen blauen Zug.
Nach \(t\) Runden besitzen alle Wahrscheinlichkeiten \(P_t(b)\) denselben Nenner
$$D_t=\prod_{i=1}^{t}(i+1)=(t+1)!.$$
Definiere deshalb
$$A_t(b)=D_t\,P_t(b).$$
Multipliziert man die Wahrscheinlichkeitsrekursion mit \(D_t=(t+1)D_{t-1}\), verschwinden alle Brüche und man erhält
$$A_t(b)=t\,A_{t-1}(b)+A_{t-1}(b-1).$$
Genau dieses Invariante nutzen die exakten Integer-Lösungen. Der Faktor \(t\) entsteht durch die \(t\) roten Scheiben in Runde \(t\); der blaue Zweig trägt nur den Faktor \(1\), weil es immer genau eine blaue Scheibe gibt.
Am Ende ist die Gewinnwahrscheinlichkeit
$$P(\text{Gewinn})=\sum_{b=8}^{15} P_{15}(b)=\frac{\sum_{b=8}^{15} A_{15}(b)}{16!}.$$
Fasst man die skalierten Werte in einem Polynom zusammen,
$$F_t(x)=\sum_{b=0}^{t} A_t(b)x^b,$$
dann wird die Rekursion zu
$$F_t(x)=(t+x)F_{t-1}(x),\qquad F_0(x)=1,$$
also
$$F_t(x)=\prod_{i=1}^{t}(i+x).$$
Der Koeffizient von \(x^b\) ist genau der skalierte Zähler für das Ereignis „nach \(t\) Runden sind genau \(b\) blaue Ziehungen aufgetreten“. Die Implementierungen arbeiten nicht symbolisch mit Polynomen, aber diese Sicht erklärt die saubere Form der Rekursion.
Für vier Runden kann man die Rekursion von Hand ausführen. Ausgehend von \(A_0(0)=1\) erhält man:
$$ \begin{aligned} t=0 &: [1] \\ t=1 &: [1,1] \\ t=2 &: [2,3,1] \\ t=3 &: [6,11,6,1] \\ t=4 &: [24,50,35,10,1]. \end{aligned} $$
Dies sind genau die Koeffizienten von
$$F_4(x)=(1+x)(2+x)(3+x)(4+x).$$
Nach vier Runden ist der gemeinsame Nenner \(D_4=2\cdot3\cdot4\cdot5=120\). Ein Sieg erfordert mehr blaue als rote Ziehungen, also bei vier Runden genau \(3\) oder \(4\) blaue Ziehungen. Damit gilt
$$P(\text{Gewinn in 4 Runden})=\frac{10+1}{120}=\frac{11}{120}.$$
Der maximale profitable Preisfonds ist also
$$\left\lfloor \frac{120}{11} \right\rfloor = 10,$$
und dieses Beispiel dient als saubere Kontrolle der Herleitung.
Für die eigentliche Aufgabe ist \(n=15\). Setze
$$W=\sum_{b=8}^{15} A_{15}(b).$$
Dann ist
$$P(\text{Gewinn})=\frac{W}{16!}.$$
Wenn der Preisfonds \(M\) den zurückgegebenen Einsatz bereits enthält, beträgt die erwartete Auszahlung pro Spiel \(M \cdot P(\text{Gewinn})\). Um keinen Erwartungsverlust zu haben, braucht man also
$$M \le \frac{1}{P(\text{Gewinn})}=\frac{16!}{W}.$$
Damit lautet die gesuchte Antwort
$$\boxed{M_{\max}=\left\lfloor \frac{16!}{W} \right\rfloor.}$$
Die Implementierung hält eine eindimensionale Tabelle, die nach der bisher erreichten Anzahl blauer Ziehungen indiziert ist. Anfangs ist nur der Zustand „null blaue Ziehungen nach null Runden“ ungleich null. Für jede neue Runde wird eine frische Tabelle erzeugt, und jeder erreichbare Zustand verteilt seinen Beitrag auf zwei Folgezustände: rot lässt die Blau-Anzahl unverändert, blau erhöht sie um eins.
Die Python-Implementierung speichert die Wahrscheinlichkeiten selbst als exakte rationale Zahlen und multipliziert daher in jedem Schritt mit \(t/(t+1)\) bzw. \(1/(t+1)\). Die C++- und Java-Implementierungen entfernen den gemeinsamen Nenner in jeder Runde und speichern nur die skalierten Zähler \(A_t(b)\). Deshalb besteht ihre Aktualisierung aus einer ganzzahligen Multiplikation mit \(t\) für den roten Zweig und einer einfachen Addition für den blauen Zweig.
Nach Runde fünfzehn summiert die Implementierung alle Zustände mit mehr blauen als roten Ziehungen, also \(b=8,9,\dots,15\). In der rationalen Variante ist diese Summe bereits die exakte Gewinnwahrscheinlichkeit. In den skalierten Integer-Varianten ist dieselbe Summe der Zähler \(W\), während der gemeinsame Nenner \(16!\) ist. Die Antwort entsteht dann durch eine einzige exakte Ganzzahldivision \(\left\lfloor 16!/W \right\rfloor\).
Für \(n\) Runden hat die Tabelle Größe \(n+1\), und in Runde \(t\) müssen nur die Zustände \(0,1,\dots,t\) verarbeitet werden. Die Gesamtzahl der Zustandsübergänge ist daher
$$1+2+\cdots+n = O(n^2).$$
Der Speicherverbrauch ist \(O(n)\), weil zu jedem Zeitpunkt nur die aktuelle und die nächste Tabellenzeile benötigt werden. Hier ist \(n=15\), also ist die Rechnung extrem klein. Selbst mit exakten Brüchen oder großen Ganzzahlen bleibt der Aufwand verschwindend gering, während die exakte Arithmetik jede Rundungsfrage sauber vermeidet.
Oyunun başında torbada tam olarak bir mavi ve bir kırmızı disk vardır. \(t\). turda oyuncu rastgele bir disk çeker, rengini not eder, diski geri koyar ve ardından torbaya bir kırmızı disk daha eklenir. Bu yüzden \(t\). turda torbada her zaman bir mavi ve \(t\) kırmızı disk bulunur; dolayısıyla
$$P(\text{\(t\). turda mavi})=\frac{1}{t+1},\qquad P(\text{\(t\). turda kırmızı})=\frac{t}{t+1}.$$
Toplam \(15\) tur vardır. Oyuncu ancak mavi sonuçların sayısı kırmızı sonuçların sayısından fazla olursa kazanır. \(15\) tek sayı olduğu için bu koşul en az \(8\) mavi çekiş anlamına gelir. Toplam ödül fonu, oyuncunun geri aldığı başlangıç parasını da içerecek şekilde \(M\) sterlin ise, kasa sahibinin beklenen kaybının olmaması için tam olarak \(M \cdot P(\text{kazanma}) \le 1\) gerekir. İstenen, bu eşitsizliği sağlayan en büyük tam sayı \(M\)'dir.
Burada önemli olan çekişlerin sırası değil, her aşamada kaç kez mavi geldiğidir. Bu bakış açısı problemi, olası mavi sayıları üzerinde küçük bir dağılım güncellemesine indirir.
\(B_t\), ilk \(t\) tur sonunda görülen mavi çekiş sayısı olsun ve
$$P_t(b)=P(B_t=b)$$
olarak tanımlansın. Olası değerler yalnızca \(0 \le b \le t\) aralığındadır. \(t\). turun sonunda tam olarak \(b\) maviye ulaşmanın iki yolu vardır:
$$P_t(b)=P_{t-1}(b)\cdot \frac{t}{t+1}+P_{t-1}(b-1)\cdot \frac{1}{t+1}.$$
Başlangıç koşulu \(P_0(0)=1\) ve \(P_0(b)=0\) (\(b \ne 0\)) şeklindedir. İlk terim son turun kırmızı gelmesini, ikinci terim ise mavi gelmesini temsil eder.
\(t\) turdan sonra tüm olasılıkların ortak paydası
$$D_t=\prod_{i=1}^{t}(i+1)=(t+1)!$$
olur. Bu nedenle
$$A_t(b)=D_t\,P_t(b)$$
tanımını yapalım. Olasılık bağıntısını \(D_t=(t+1)D_{t-1}\) ile çarpınca tüm kesirler kaybolur ve
$$A_t(b)=t\,A_{t-1}(b)+A_{t-1}(b-1)$$
elde edilir. C++ ve Java uygulamalarının dayandığı tam sayı değişmezi tam olarak budur. \(t\) katsayısı, \(t\). turda torbada bulunan \(t\) kırmızı diskten gelir; mavi dalında ise her zaman yalnızca bir mavi disk bulunduğu için katsayı \(1\)'dir.
Son durumda kazanma olasılığı
$$P(\text{kazanma})=\sum_{b=8}^{15} P_{15}(b)=\frac{\sum_{b=8}^{15} A_{15}(b)}{16!}$$
şeklindedir.
Ölçeklenmiş değerleri
$$F_t(x)=\sum_{b=0}^{t} A_t(b)x^b$$
polinomunda toplarsak, yukarıdaki bağıntı
$$F_t(x)=(t+x)F_{t-1}(x),\qquad F_0(x)=1$$
haline gelir; dolayısıyla
$$F_t(x)=\prod_{i=1}^{t}(i+x).$$
\(x^b\)'nin katsayısı, \(t\) tur sonunda tam olarak \(b\) mavi görülmesinin ölçeklenmiş payına eşittir. Uygulamalar sembolik polinomlarla uğraşmaz; buna rağmen bu yorum, tam sayı bağıntısının neden bu kadar düzenli olduğunu açıklar.
Dört turluk küçük örnekte bağıntıyı elle açmak mümkündür. \(A_0(0)=1\) ile başlayınca şu satırlar elde edilir:
$$ \begin{aligned} t=0 &: [1] \\ t=1 &: [1,1] \\ t=2 &: [2,3,1] \\ t=3 &: [6,11,6,1] \\ t=4 &: [24,50,35,10,1]. \end{aligned} $$
Bunlar aynı zamanda
$$F_4(x)=(1+x)(2+x)(3+x)(4+x)$$
çarpımının katsayılarıdır. Dört turun ortak paydası \(D_4=2\cdot3\cdot4\cdot5=120\)'dir. Kazanmak için kırmızıdan fazla mavi gerektiğinden, dört turda ancak \(3\) veya \(4\) mavi ile kazanılır. Bu yüzden
$$P(\text{4 turda kazanma})=\frac{10+1}{120}=\frac{11}{120}.$$
Maksimum kârlı ödül fonu da
$$\left\lfloor \frac{120}{11} \right\rfloor = 10$$
olur. Bu örnek, ana formülün doğru çalıştığını açık biçimde gösterir.
Asıl soruda \(n=15\) için
$$W=\sum_{b=8}^{15} A_{15}(b)$$
olsun. O zaman
$$P(\text{kazanma})=\frac{W}{16!}.$$
Ödül fonu \(M\), başlangıç parasını da kapsıyorsa, oyun başına beklenen ödeme \(M \cdot P(\text{kazanma})\) olur. Beklenen zararı önlemek için
$$M \le \frac{1}{P(\text{kazanma})}=\frac{16!}{W}$$
gereklidir. Sonuç olarak cevap
$$\boxed{M_{\max}=\left\lfloor \frac{16!}{W} \right\rfloor}$$
şeklindedir.
Uygulama, o ana kadar görülmüş mavi sayısına göre indekslenen tek boyutlu bir tablo tutar. Başlangıçta yalnızca “sıfır tur sonunda sıfır mavi” durumu sıfırdan farklıdır. Her yeni tur için yeni bir tablo oluşturulur ve her erişilebilir durum iki sonraki duruma katkı yapar: kırmızı kolu mavi sayısını korur, mavi kolu ise sayıyı bir artırır.
Python uygulaması olasılıkları doğrudan tam kesirlerle tutar; bu yüzden her geçişte \(t/(t+1)\) veya \(1/(t+1)\) ile çarpılır. C++ ve Java uygulamaları ise ortak paydayı her aşamada temizler ve yalnızca \(A_t(b)\) ölçekli paylarını saklar. Bu nedenle onların güncellemesi, kırmızı dal için \(t\) ile tam sayı çarpımı ve mavi dal için basit toplama biçimindedir.
On beşinci turun sonunda uygulama, mavi sayısı kırmızı sayısından büyük olan tüm durumları toplar; yani \(b=8,9,\dots,15\). Kesirli sürümde bu toplam doğrudan kesin kazanma olasılığıdır. Ölçeklenmiş tam sayı sürümlerinde aynı toplam \(W\) payıdır ve ortak payda \(16!\)'dir. Son yanıt tek bir tam sayı bölmesiyle bulunur: \(\left\lfloor 16!/W \right\rfloor\).
\(n\) tur için tablo boyutu \(n+1\)'dir ve \(t\). turda yalnızca \(0,1,\dots,t\) durumları işlenir. Dolayısıyla toplam durum güncellemesi sayısı
$$1+2+\cdots+n = O(n^2)$$
olur. Bellek kullanımı \(O(n)\)'dir; çünkü aynı anda yalnızca mevcut satır ile bir sonraki satır tutulur. Bu problemde \(n=15\) olduğundan hesap çok küçüktür. Kesin kesir veya büyük tam sayı kullanmanın ek maliyeti pratikte ihmal edilebilir düzeydedir ve buna karşılık tüm hesap yuvarlama hatasından tamamen arındırılmış olur.
El juego comienza con una bolsa que contiene exactamente un disco azul y uno rojo. En el turno \(t\), el jugador extrae un disco al azar, anota el color, devuelve el disco a la bolsa y después se añade un disco rojo adicional. Por tanto, en el turno \(t\) la bolsa contiene siempre un disco azul y \(t\) discos rojos, de modo que
$$P(\text{azul en el turno }t)=\frac{1}{t+1},\qquad P(\text{rojo en el turno }t)=\frac{t}{t+1}.$$
Hay \(15\) turnos en total. El jugador gana si el número de azules supera al número de rojos. Como \(15\) es impar, eso equivale a obtener al menos \(8\) azules. Si el fondo total del premio es \(M\) libras e incluye la devolución de la apuesta inicial, entonces el organizador no pierde dinero en esperanza exactamente cuando \(M \cdot P(\text{ganar}) \le 1\). El objetivo es hallar el mayor entero \(M\) que satisface esa condición.
La clave no es el orden preciso de las extracciones, sino cuántas veces ha salido azul después de cada turno. Eso convierte el problema en una actualización pequeña de una distribución sobre el número posible de azules.
Sea \(B_t\) el número de extracciones azules después de los primeros \(t\) turnos y definamos
$$P_t(b)=P(B_t=b).$$
Solo son posibles los valores \(0 \le b \le t\). Para terminar el turno \(t\) con exactamente \(b\) azules hay dos caminos:
$$P_t(b)=P_{t-1}(b)\cdot \frac{t}{t+1}+P_{t-1}(b-1)\cdot \frac{1}{t+1},$$
con condición inicial \(P_0(0)=1\) y \(P_0(b)=0\) si \(b \ne 0\). El primer término corresponde a que el turno \(t\) fue rojo; el segundo, a que fue azul.
Después de \(t\) turnos, todas las probabilidades \(P_t(b)\) comparten el denominador
$$D_t=\prod_{i=1}^{t}(i+1)=(t+1)!.$$
Definamos entonces
$$A_t(b)=D_t\,P_t(b).$$
Al multiplicar la recurrencia probabilística por \(D_t=(t+1)D_{t-1}\), desaparecen todas las fracciones y obtenemos
$$A_t(b)=t\,A_{t-1}(b)+A_{t-1}(b-1).$$
Ese es exactamente el invariante que aprovechan las soluciones enteras. El factor \(t\) proviene de los \(t\) discos rojos disponibles en el turno \(t\), mientras que la rama azul aporta un factor \(1\) porque siempre existe exactamente un disco azul.
Al final, la probabilidad de victoria es
$$P(\text{ganar})=\sum_{b=8}^{15} P_{15}(b)=\frac{\sum_{b=8}^{15} A_{15}(b)}{16!}.$$
Si reunimos los valores escalados en el polinomio
$$F_t(x)=\sum_{b=0}^{t} A_t(b)x^b,$$
la recurrencia anterior se convierte en
$$F_t(x)=(t+x)F_{t-1}(x),\qquad F_0(x)=1,$$
y por tanto
$$F_t(x)=\prod_{i=1}^{t}(i+x).$$
El coeficiente de \(x^b\) es exactamente el numerador escalado del evento “después de \(t\) turnos han salido \(b\) azules”. La implementación no necesita manipular ese polinomio de forma simbólica, pero esta perspectiva explica por qué la recurrencia entera es tan natural.
El caso de cuatro turnos se puede verificar a mano. Partiendo de \(A_0(0)=1\), la recurrencia produce:
$$ \begin{aligned} t=0 &: [1] \\ t=1 &: [1,1] \\ t=2 &: [2,3,1] \\ t=3 &: [6,11,6,1] \\ t=4 &: [24,50,35,10,1]. \end{aligned} $$
Esos son precisamente los coeficientes de
$$F_4(x)=(1+x)(2+x)(3+x)(4+x).$$
Tras cuatro turnos, el denominador común es \(D_4=2\cdot3\cdot4\cdot5=120\). Para ganar hacen falta más azules que rojos, así que con cuatro turnos se necesita obtener \(3\) o \(4\) azules. Por ello
$$P(\text{ganar en 4 turnos})=\frac{10+1}{120}=\frac{11}{120}.$$
El fondo máximo rentable es entonces
$$\left\lfloor \frac{120}{11} \right\rfloor = 10,$$
lo que sirve como comprobación concreta de toda la derivación.
En el problema real, \(n=15\). Sea
$$W=\sum_{b=8}^{15} A_{15}(b).$$
Entonces
$$P(\text{ganar})=\frac{W}{16!}.$$
Si el premio total \(M\) incluye la apuesta devuelta, el pago esperado por partida es \(M \cdot P(\text{ganar})\). Para no tener pérdida esperada hace falta
$$M \le \frac{1}{P(\text{ganar})}=\frac{16!}{W}.$$
Así, la respuesta pedida es
$$\boxed{M_{\max}=\left\lfloor \frac{16!}{W} \right\rfloor.}$$
La implementación mantiene una tabla unidimensional indexada por el número de azules observados hasta el momento. Al inicio solo es no nulo el estado “cero azules después de cero turnos”. En cada turno se crea una tabla nueva y cada estado alcanzable reparte su masa en dos estados siguientes: una transición roja que conserva el número de azules y una transición azul que lo incrementa en uno.
La implementación en Python guarda las probabilidades como fracciones exactas, de modo que cada transición multiplica por \(t/(t+1)\) o por \(1/(t+1)\). Las implementaciones en C++ y Java eliminan el denominador común en cada etapa y almacenan solo los numeradores escalados \(A_t(b)\). Por eso su regla de actualización usa multiplicación entera por \(t\) en la rama roja y suma simple en la rama azul.
Después del turno quince, la implementación suma todos los estados con más azules que rojos, es decir, \(b=8,9,\dots,15\). En la versión racional, esa suma ya es la probabilidad exacta de victoria. En las versiones enteras escaladas, esa misma suma es el numerador \(W\), mientras que el denominador común es \(16!\). La respuesta final se obtiene con una única división entera exacta, \(\left\lfloor 16!/W \right\rfloor\).
Para \(n\) turnos, la tabla tiene tamaño \(n+1\), y en el turno \(t\) solo es necesario procesar los estados \(0,1,\dots,t\). Por tanto, el número total de actualizaciones es
$$1+2+\cdots+n = O(n^2).$$
El uso de memoria es \(O(n)\), porque solo se necesitan la fila actual y la siguiente. En este problema \(n=15\), así que el cálculo es diminuto. Incluso usando fracciones exactas o enteros grandes, el costo adicional es despreciable frente a la ventaja de evitar cualquier error de redondeo.
游戏开始时，袋子里恰好有一个蓝色圆盘和一个红色圆盘。第 \(t\) 轮时，玩家随机取出一个圆盘，记录颜色后放回，然后再额外加入一个红色圆盘。因此在第 \(t\) 轮，袋中始终有一个蓝盘和 \(t\) 个红盘，所以
$$P(\text{第 }t\text{ 轮抽到蓝盘})=\frac{1}{t+1},\qquad P(\text{第 }t\text{ 轮抽到红盘})=\frac{t}{t+1}.$$
总共进行 \(15\) 轮。只有当蓝色出现次数严格多于红色出现次数时玩家才获胜。由于 \(15\) 是奇数，这等价于至少抽到 \(8\) 次蓝色。若总奖金为 \(M\) 英镑，并且包含玩家原本投入的那 \(1\) 英镑，那么庄家想要在期望意义下不亏损，就必须满足 \(M \cdot P(\text{获胜}) \le 1\)。题目要求的就是满足这一条件的最大整数 \(M\)。
这道题真正重要的不是颜色出现的具体顺序，而是每一轮结束后蓝色一共出现了多少次。这样一来，问题就变成了对“蓝色次数分布”的逐轮更新。
记 \(B_t\) 为前 \(t\) 轮中蓝色出现的次数，并定义
$$P_t(b)=P(B_t=b).$$
显然只有 \(0 \le b \le t\) 这些状态可能出现。第 \(t\) 轮结束后恰好得到 \(b\) 次蓝色，只有两种来源：
$$P_t(b)=P_{t-1}(b)\cdot \frac{t}{t+1}+P_{t-1}(b-1)\cdot \frac{1}{t+1}.$$
初始条件是 \(P_0(0)=1\)，而当 \(b \ne 0\) 时 \(P_0(b)=0\)。第一项表示第 \(t\) 轮抽到红色，所以蓝色次数不变；第二项表示第 \(t\) 轮抽到蓝色，因此上一轮必须有 \(b-1\) 次蓝色。
进行到第 \(t\) 轮时，所有概率 \(P_t(b)\) 的公共分母都是
$$D_t=\prod_{i=1}^{t}(i+1)=(t+1)!.$$
于是定义缩放后的整数
$$A_t(b)=D_t\,P_t(b).$$
把上面的概率递推乘上 \(D_t=(t+1)D_{t-1}\)，所有分数都会消失，得到
$$A_t(b)=t\,A_{t-1}(b)+A_{t-1}(b-1).$$
这正是整数实现所利用的不变量。系数 \(t\) 来自第 \(t\) 轮时袋中有 \(t\) 个红盘；蓝色分支的系数是 \(1\)，因为蓝盘始终只有一个。
最终的获胜概率为
$$P(\text{获胜})=\sum_{b=8}^{15} P_{15}(b)=\frac{\sum_{b=8}^{15} A_{15}(b)}{16!}.$$
如果把这些缩放后的值收集成一个多项式
$$F_t(x)=\sum_{b=0}^{t} A_t(b)x^b,$$
那么递推式就变成
$$F_t(x)=(t+x)F_{t-1}(x),\qquad F_0(x)=1,$$
因此
$$F_t(x)=\prod_{i=1}^{t}(i+x).$$
\(x^b\) 的系数恰好就是“前 \(t\) 轮恰有 \(b\) 次蓝色”的缩放分子。实际实现并不需要做符号多项式运算，但这个角度能很好地解释为什么整数递推如此整齐。
四轮时可以把整个过程手算出来。从 \(A_0(0)=1\) 出发，递推得到：
$$ \begin{aligned} t=0 &: [1] \\ t=1 &: [1,1] \\ t=2 &: [2,3,1] \\ t=3 &: [6,11,6,1] \\ t=4 &: [24,50,35,10,1]. \end{aligned} $$
这正好也是
$$F_4(x)=(1+x)(2+x)(3+x)(4+x)$$
的系数。四轮结束后的公共分母是 \(D_4=2\cdot3\cdot4\cdot5=120\)。若想赢，蓝色次数必须多于红色次数，因此四轮时只能是 \(3\) 次或 \(4\) 次蓝色获胜。于是
$$P(\text{四轮获胜})=\frac{10+1}{120}=\frac{11}{120}.$$
最大可接受奖金就是
$$\left\lfloor \frac{120}{11} \right\rfloor = 10,$$
这个小例子也正好验证了递推和奖金公式的正确性。
对于正式题目，\(n=15\)。令
$$W=\sum_{b=8}^{15} A_{15}(b).$$
那么
$$P(\text{获胜})=\frac{W}{16!}.$$
若奖金 \(M\) 包含返还的本金，则庄家每局的期望支付为 \(M \cdot P(\text{获胜})\)。为了不产生期望亏损，必须有
$$M \le \frac{1}{P(\text{获胜})}=\frac{16!}{W}.$$
所以答案就是
$$\boxed{M_{\max}=\left\lfloor \frac{16!}{W} \right\rfloor.}$$
实现使用一个一维表，索引表示到当前为止出现了多少次蓝色。初始时只有“零轮后出现零次蓝色”这一状态非零。每处理一轮，就创建一个新的表，把每个可达状态分别转移到两个后继状态：红色分支保持蓝色次数不变，蓝色分支把次数加一。
Python 实现直接把概率存成精确分数，因此每一步都乘上 \(t/(t+1)\) 或 \(1/(t+1)\)。C++ 和 Java 实现则在每一轮把公共分母消掉，只保存缩放后的整数 \(A_t(b)\)。这就是为什么那两种实现中，红色分支表现为乘以 \(t\)，蓝色分支表现为直接相加。
完成第十五轮之后，实现把所有“蓝色次数多于红色次数”的状态相加，也就是 \(b=8,9,\dots,15\)。在有理数版本中，这个和已经是精确的获胜概率；在整数缩放版本中，这个和就是分子 \(W\)，而公共分母为 \(16!\)。最后再做一次精确整数除法 \(\left\lfloor 16!/W \right\rfloor\)，就得到要求的最大奖金。
若总共有 \(n\) 轮，则表的大小为 \(n+1\)，而第 \(t\) 轮只需要处理状态 \(0,1,\dots,t\)。因此总状态更新次数是
$$1+2+\cdots+n = O(n^2).$$
空间复杂度为 \(O(n)\)，因为任意时刻只需要当前一行和下一行。在本题中 \(n=15\)，所以计算量极小。即使使用精确分数或大整数，额外代价也几乎可以忽略，而换来的好处是整个计算过程完全没有浮点误差。
В начале игры в мешке лежат ровно один синий и один красный диск. На ходе \(t\) игрок случайно вытягивает один диск, фиксирует его цвет, возвращает диск обратно, а затем в мешок добавляется еще один красный диск. Значит, на ходе \(t\) в мешке всегда один синий и \(t\) красных дисков, поэтому
$$P(\text{синий на ходе }t)=\frac{1}{t+1},\qquad P(\text{красный на ходе }t)=\frac{t}{t+1}.$$
Всего проводится \(15\) ходов. Игрок выигрывает тогда и только тогда, когда синих результатов больше, чем красных. Поскольку \(15\) нечетно, это означает как минимум \(8\) синих вытягиваний. Если общий призовой фонд равен \(M\) фунтам и уже включает возврат исходной ставки, то организатор не несет ожидаемого убытка ровно при условии \(M \cdot P(\text{выигрыш}) \le 1\). Требуется найти наибольшее целое \(M\), удовлетворяющее этому условию.
Главное здесь не точный порядок цветов, а только то, сколько раз синий уже появился после каждого хода. Тогда задача сводится к небольшой динамике распределения по возможному числу синих результатов.
Пусть \(B_t\) обозначает число синих вытягиваний после первых \(t\) ходов, и пусть
$$P_t(b)=P(B_t=b).$$
Возможны только значения \(0 \le b \le t\). Чтобы после хода \(t\) получить ровно \(b\) синих результатов, есть лишь два варианта:
$$P_t(b)=P_{t-1}(b)\cdot \frac{t}{t+1}+P_{t-1}(b-1)\cdot \frac{1}{t+1}.$$
Начальное условие равно \(P_0(0)=1\), а для \(b \ne 0\) имеем \(P_0(b)=0\). Первый член соответствует красному исходу на ходе \(t\), второй член соответствует синему исходу.
После \(t\) ходов все вероятности \(P_t(b)\) имеют общий знаменатель
$$D_t=\prod_{i=1}^{t}(i+1)=(t+1)!.$$
Определим масштабированную величину
$$A_t(b)=D_t\,P_t(b).$$
Если умножить вероятностную рекурсию на \(D_t=(t+1)D_{t-1}\), все дроби исчезают, и получается
$$A_t(b)=t\,A_{t-1}(b)+A_{t-1}(b-1).$$
Именно этот инвариант используют целочисленные реализации. Коэффициент \(t\) отражает наличие \(t\) красных дисков на ходе \(t\); синяя ветвь дает коэффициент \(1\), потому что синий диск всегда только один.
В конце вероятность победы равна
$$P(\text{выигрыш})=\sum_{b=8}^{15} P_{15}(b)=\frac{\sum_{b=8}^{15} A_{15}(b)}{16!}.$$
Если собрать масштабированные величины в полином
$$F_t(x)=\sum_{b=0}^{t} A_t(b)x^b,$$
то рекурсия принимает вид
$$F_t(x)=(t+x)F_{t-1}(x),\qquad F_0(x)=1,$$
а значит
$$F_t(x)=\prod_{i=1}^{t}(i+x).$$
Коэффициент при \(x^b\) и есть масштабированный числитель для события «после \(t\) ходов выпало ровно \(b\) синих». Реализации не работают с этим полиномом символически, но такая форма хорошо объясняет структуру рекурсии.
Случай с четырьмя ходами можно полностью просчитать вручную. Начиная с \(A_0(0)=1\), рекурсия дает:
$$ \begin{aligned} t=0 &: [1] \\ t=1 &: [1,1] \\ t=2 &: [2,3,1] \\ t=3 &: [6,11,6,1] \\ t=4 &: [24,50,35,10,1]. \end{aligned} $$
Это в точности коэффициенты полинома
$$F_4(x)=(1+x)(2+x)(3+x)(4+x).$$
После четырех ходов общий знаменатель равен \(D_4=2\cdot3\cdot4\cdot5=120\). Для победы нужно иметь больше синих, чем красных, то есть при четырех ходах требуется \(3\) или \(4\) синих. Следовательно,
$$P(\text{выигрыш за 4 хода})=\frac{10+1}{120}=\frac{11}{120}.$$
Максимальный выгодный призовой фонд равен
$$\left\lfloor \frac{120}{11} \right\rfloor = 10,$$
и это служит хорошей проверкой всей схемы.
Для исходной задачи \(n=15\). Обозначим
$$W=\sum_{b=8}^{15} A_{15}(b).$$
Тогда
$$P(\text{выигрыш})=\frac{W}{16!}.$$
Если призовой фонд \(M\) уже включает возврат ставки, то ожидаемая выплата за игру равна \(M \cdot P(\text{выигрыш})\). Чтобы не иметь ожидаемого убытка, необходимо
$$M \le \frac{1}{P(\text{выигрыш})}=\frac{16!}{W}.$$
Отсюда ответ:
$$\boxed{M_{\max}=\left\lfloor \frac{16!}{W} \right\rfloor.}$$
Реализация хранит одномерную таблицу, индексируемую числом синих вытягиваний на данный момент. Изначально ненулевым является только состояние «ноль синих после нуля ходов». На каждом новом ходе создается новая таблица, и каждое достижимое состояние вносит вклад в два последующих: красная ветвь сохраняет число синих, синяя увеличивает его на единицу.
Реализация на Python хранит сами вероятности как точные рациональные числа, поэтому на каждом переходе умножает на \(t/(t+1)\) или на \(1/(t+1)\). Реализации на C++ и Java избавляются от общего знаменателя на каждом шаге и хранят только масштабированные числители \(A_t(b)\). Поэтому их обновление состоит из целочисленного умножения на \(t\) для красной ветви и обычного сложения для синей.
После пятнадцатого хода код суммирует все состояния, где синих больше, чем красных, то есть \(b=8,9,\dots,15\). В рациональной версии это уже точная вероятность победы. В целочисленных версиях та же сумма равна числителю \(W\), а общий знаменатель равен \(16!\). Последний шаг - одна точная целочисленная операция деления \(\left\lfloor 16!/W \right\rfloor\).
Для \(n\) ходов таблица имеет размер \(n+1\), а на ходе \(t\) обрабатываются только состояния \(0,1,\dots,t\). Поэтому общее число обновлений равно
$$1+2+\cdots+n = O(n^2).$$
Память составляет \(O(n)\), поскольку одновременно нужны только текущая и следующая строки. В этой задаче \(n=15\), так что вычисление очень маленькое. Даже с точными дробями или большими целыми дополнительная стоимость ничтожна по сравнению с преимуществом полностью точного результата без ошибок округления.
تبدأ اللعبة بكيس يحتوي على قرص أزرق واحد وقرص أحمر واحد فقط. في الدور \(t\)، يسحب اللاعب قرصًا عشوائيًا، يسجل لونه، ثم يعيده إلى الكيس، وبعد ذلك يضاف قرص أحمر إضافي. لذلك يحتوي الكيس في الدور \(t\) دائمًا على قرص أزرق واحد و\(t\) أقراص حمراء، ومن ثم
$$P(\text{blue on turn }t)=\frac{1}{t+1},\qquad P(\text{red on turn }t)=\frac{t}{t+1}.$$
عدد الأدوار الكلي هو \(15\). يفوز اللاعب إذا ظهر اللون الأزرق عدد مرات أكبر من اللون الأحمر. وبما أن \(15\) عدد فردي، فهذا يعني الحاجة إلى \(8\) مرات زرقاء على الأقل. إذا كان صندوق الجائزة الكلي يساوي \(M\) جنيهًا ويشمل إعادة رهان اللاعب الأصلي، فإن المنظم لا يتعرض لخسارة متوقعة بالضبط عندما يتحقق الشرط \(M \cdot P(\text{win}) \le 1\). المطلوب هو أكبر عدد صحيح \(M\) يحقق هذا الشرط.
العنصر المهم هنا ليس ترتيب الألوان بالتحديد، بل عدد المرات التي ظهر فيها الأزرق بعد كل دور. بهذه الصياغة يتحول السؤال إلى تحديث صغير لتوزيع عدد النتائج الزرقاء الممكنة.
لنرمز بـ \(B_t\) إلى عدد السحوبات الزرقاء بعد أول \(t\) أدوار، ولنعرف
$$P_t(b)=P(B_t=b).$$
القيم الممكنة هي فقط \(0 \le b \le t\). ولكي ننتهي بعد الدور \(t\) بعدد يساوي بالضبط \(b\) من السحوبات الزرقاء، فهناك حالتان فقط:
$$P_t(b)=P_{t-1}(b)\cdot \frac{t}{t+1}+P_{t-1}(b-1)\cdot \frac{1}{t+1}.$$
شرط البداية هو \(P_0(0)=1\)، و\(P_0(b)=0\) عندما \(b \ne 0\). الحد الأول يعني أن نتيجة الدور \(t\) كانت حمراء، فيبقى عدد النتائج الزرقاء كما هو. والحد الثاني يعني أن نتيجة الدور \(t\) كانت زرقاء، ولذلك كان العدد السابق يساوي \(b-1\).
بعد \(t\) أدوار، تمتلك جميع الاحتمالات \(P_t(b)\) المقام المشترك
$$D_t=\prod_{i=1}^{t}(i+1)=(t+1)!.$$
لذلك نعرف الكمية المضروبة
$$A_t(b)=D_t\,P_t(b).$$
عند ضرب العلاقة الاحتمالية في \(D_t=(t+1)D_{t-1}\)، تختفي الكسور كلها ونحصل على
$$A_t(b)=t\,A_{t-1}(b)+A_{t-1}(b-1).$$
هذا هو الثابت الرياضي الذي تستفيد منه التطبيقات الصحيحة. العامل \(t\) يأتي من وجود \(t\) أقراص حمراء في الدور \(t\)، بينما تساهم الحالة الزرقاء بمعامل \(1\) لأن عدد الأقراص الزرقاء يظل دائمًا واحدًا.
وفي النهاية يكون احتمال الفوز
$$P(\text{win})=\sum_{b=8}^{15} P_{15}(b)=\frac{\sum_{b=8}^{15} A_{15}(b)}{16!}.$$
إذا جمعنا القيم المضروبة في كثير الحدود
$$F_t(x)=\sum_{b=0}^{t} A_t(b)x^b,$$
فإن العلاقة السابقة تصبح
$$F_t(x)=(t+x)F_{t-1}(x),\qquad F_0(x)=1,$$
ومن ثم
$$F_t(x)=\prod_{i=1}^{t}(i+x).$$
معامل \(x^b\) هو بالضبط البسط المضروب للحالة «بعد \(t\) أدوار ظهر الأزرق \(b\) مرة». التنفيذ لا يحتاج إلى معالجة رمزية لهذا كثير الحدود، لكن هذه الصياغة توضح لماذا تظهر علاقة صحيحة بهذه البساطة.
في حالة أربع أدوار يمكن تتبع الحساب يدويًا. انطلاقًا من \(A_0(0)=1\) تعطي العلاقة الصفوف التالية:
$$ \begin{aligned} t=0 &: [1] \\ t=1 &: [1,1] \\ t=2 &: [2,3,1] \\ t=3 &: [6,11,6,1] \\ t=4 &: [24,50,35,10,1]. \end{aligned} $$
وهذه هي معاملات
$$F_4(x)=(1+x)(2+x)(3+x)(4+x).$$
بعد أربع أدوار يكون المقام المشترك هو \(D_4=2\cdot3\cdot4\cdot5=120\). ولأن الفوز يتطلب عددًا من الأزرق أكبر من الأحمر، فإن اللاعب يحتاج في أربع أدوار إلى \(3\) أو \(4\) نتائج زرقاء. لذلك
$$P(\text{win in 4 turns})=\frac{10+1}{120}=\frac{11}{120}.$$
وعليه فإن أكبر صندوق جائز مربح هو
$$\left\lfloor \frac{120}{11} \right\rfloor = 10,$$
وهذا مثال عملي ممتاز للتحقق من صحة الاشتقاق.
في المسألة الأصلية لدينا \(n=15\). لنكتب
$$W=\sum_{b=8}^{15} A_{15}(b).$$
إذن
$$P(\text{win})=\frac{W}{16!}.$$
إذا كان صندوق الجائزة \(M\) يتضمن إعادة الرهان الأصلي، فإن الدفعة المتوقعة لكل لعبة تساوي \(M \cdot P(\text{win})\). ولكي لا توجد خسارة متوقعة يجب أن يتحقق
$$M \le \frac{1}{P(\text{win})}=\frac{16!}{W}.$$
ومن ثم تكون الإجابة
$$\boxed{M_{\max}=\left\lfloor \frac{16!}{W} \right\rfloor.}$$
يحافظ التنفيذ على جدول أحادي البعد مفهرس بعدد النتائج الزرقاء التي ظهرت حتى اللحظة. في البداية تكون الحالة غير الصفرية الوحيدة هي «صفر نتائج زرقاء بعد صفر أدوار». في كل دور جديد يُنشأ جدول جديد، ثم تساهم كل حالة قابلة للوصول في حالتين تاليتين: انتقال أحمر يبقي عدد النتائج الزرقاء كما هو، وانتقال أزرق يزيده بمقدار واحد.
تنفيذ Python يخزن الاحتمالات نفسها على شكل كسور دقيقة، ولذلك يضرب في كل انتقال بـ \(t/(t+1)\) أو \(1/(t+1)\). أما تنفيذا C++ وJava فيزيلان المقام المشترك في كل مرحلة ويخزنان فقط البسوط المضروبة \(A_t(b)\). لهذا تظهر قاعدة التحديث فيهما على شكل ضرب صحيح في \(t\) للفرع الأحمر وجمع مباشر للفرع الأزرق.
بعد الدور الخامس عشر، يجمع التنفيذ جميع الحالات التي يكون فيها عدد النتائج الزرقاء أكبر من عدد النتائج الحمراء، أي \(b=8,9,\dots,15\). في النسخة الكسرية يكون هذا المجموع هو احتمال الفوز الدقيق نفسه. وفي النسخ الصحيحة يكون المجموع هو البسط \(W\)، بينما المقام المشترك يساوي \(16!\). ثم يُحسب الجواب بعملية قسمة صحيحة واحدة: \(\left\lfloor 16!/W \right\rfloor\).
إذا كان عدد الأدوار هو \(n\)، فإن حجم الجدول يساوي \(n+1\)، وفي الدور \(t\) لا نحتاج إلا إلى معالجة الحالات \(0,1,\dots,t\). لذلك يكون العدد الكلي للتحديثات
$$1+2+\cdots+n = O(n^2).$$
أما الذاكرة فهي \(O(n)\)، لأننا نحتاج في كل لحظة إلى الصف الحالي والصف التالي فقط. وفي هذه المسألة \(n=15\)، لذا فالحساب صغير جدًا. وحتى مع استعمال كسور دقيقة أو أعداد صحيحة كبيرة يبقى العبء الإضافي ضئيلًا، بينما نحصل في المقابل على حساب خالٍ تمامًا من أخطاء التقريب.