As entradas do cine e outras cuestións difíciles

Presentamos un problema de apariencia anódina. Así como é facil de comprender o enunciado, a súa resolución non é nada simple. Agora ben, que non sexa simple non significa que non sexa marabillosa, que o é.

As entradas do cine. n+m persoas están nunha cola do despacho do cine; m teñen un billete de 5 € e as outras n só teñen billetes de 10 €. Cada entrada custa 5 €. Na billeteira non teñen ningún tipo de cambio. Se cada cliente compra só unha entrada, cal é a probabilidade de que ningún cliente teña que agardar polo cambio?

Para responder cómpre que teñamos presente a regra da probabilidade de Laplace que nos di que no caso de termos un experimento aleatorio no que todos os sucesos elementais teñen a mesma probabilidade, a probabilidade dun suceso A virá dada polo cociente entre o número de casos favorables a A e o de casos posibles:

$$P(A)=\frac{númerodecasosfavorablesaA}{númerodecasosposibles}$$

O noso propósito é determinar os dous elementos deste cociente. Para facelo colleremos un camiño encantador que recollo do mesmo lugar do que recollín o enunciado do problema, o libro dos irmáns Yaglom, Challenging Mathematical Problems with Elementary Solutions, Vol. I: Combinational Analysis and Probability Theory. 

Podemos pensar o problema mediante unha rede de dimensións $m\times n$ colocada sobre un sistema de coordenadas cartesiano. Se lle imos preguntando a cada un dos clientes que tipo de billetes ten, por orde e comezando desde o primeiro da cola, podemos ir elaborando un camiño sobre esta rede cartesiana, partindo do $(0,0)$ e trazando un segmento horizontal dunha unidade por cada persoa que teña 5 € e un segmento unitario vertical por cada unha que teña 10 €. Ao final teremos un segmento poligonal que unirá o $(0,0)$ co punto $(m,n)$. 

figura 1

Recomendo consultar a entrada anterior porque utilizaremos técnicas semellantes ás traballadas alí. En particular, nela víramos que o número total de camiños entre os puntos $(0,0)$ e$(m,n)$ era $(\genfrac{}{}{0ex}{}{m+n}{n})$, o que nos dá o número de colas posibles. Máis dificultoso será determinar os casos favorables. 

Se trazamos a recta $r$ de ecuación $y=x$, está claro que os camiños favorables serán aqueles, como o trazado na figura 1, que van por debaixo desa recta; son os que representan os casos nos que os clientes non teñen que agardar polo cambio.

Designemos $A_0,A_1,A_2,...,A_{n+m}$ aos vértices consecutivos dun destes camiños, onde $A_0=(0,0)$ é sempre o punto inicial e $A_{n+m}=(m.n)$ o final. Que pasa se $m<n$? A figura 2 explícao claramente.

figura 2

Efectivamente, se $m<n$, como no rectángulo da dereita, será imposible alcanzar o punto final mediante un camiño que transcorra por debaixo de $r$. Nese caso a probabilidade será nula. Pasemos a considerar o outro caso, no que $m>n$.

Agora, no canto de facer o reconto dos camiños favorables, contabilizaremos os desfavorables. Para iso vainos ser de axuda a recta $r^{\prime }:y=x+1$. Calquera camiño desfavorable debe ter un punto sobre esa recta. Sexa $A_k$ o primeiro punto dun deses camiños. Centrémonos agora no primeiro tramo do camiño, o que vai desde a orixe ata $A_k$, isto é, o tramo $A_0,A_1,...,A_{k-1},A_k$ e construamos o seu simétrico respecto de $r^{\prime }$. Será $A_0^{\prime },A_1^{\prime },...,A_{k-1}^{\prime },A_k$, onde $A_0^{\prime }=(-1,1)$.

figura 3

Mediante esta construción, para cada camiño desfavorable $A_0,A_1,...,A_{k-1},A_k,...A_{n+m}$ podemos construir un novo camiño $A_0^{\prime },A_1^{\prime },...,A_{k-1}^{\prime },A_k,...A_{n+m}$ que comeza en $A_0^{\prime }=(-1,1)$. De aí que contabilizar todos os camiños desfavorables equivale a contabilizar todos os que teñen a súa orixe en $A_0^{\prime }$. Estes terán $m+1$ segmentos horizontais e $n-1$ segmentos verticais que son $(\genfrac{}{}{0ex}{}{m+n}{n-1})$. Polo tanto o número de casos favorables obterase mediante a resta

$$\begin{gathered} (\genfrac{}{}{0ex}{}{m+n}{n})-(\genfrac{}{}{0ex}{}{m+n}{n-1})=\frac{(m+n)!}{n!\cdot m!}-\frac{(m+n)!}{(n-1)!\cdot (m+1)!}= \\ =\frac{(m+n)!(m+1-n)}{n!\cdot (m+1)!} \end{gathered}$$

Para obter a probabilidade pedida no problema teremos que dividir este valor polo número de casos posibles:

$$\frac{(m+n)!(m+1-n)}{n!\cdot (m+1)!}:(\genfrac{}{}{0ex}{}{m+n}{n})=\frac{(m+n)!(m+1-n)}{n!\cdot (m+1)!}:\frac{(m+n)!}{m!\cdot n!}=$$ $$=\frac{(m+n)!(m+1-n)m!\cdot n!}{n!\cdot (m+1)!(m+n)!}=\frac{m+n-1}{m+1}$$

Pode que haxa  obras de arte que nos ofrezan tanta beleza como a que se transmite nestas liñas, pero non serán moitas.

Máis alá.

No mencionado libro dos xemelgos Yalgom van maís alá. Dan unha demostración deste mesmo resultado por indución e outra usando os mesmos camiños que os trazados na que se presentou aquí, pero imaxinando agora que son esqueiras e que incide sobre elas a luz do sol cunha inclinación de 45º. 

Ademais os Yaglom propoñen outras variantes deste mesmo problema. Nunha delas piden que supoñamos que no despacho do cine teñen p billetes de 5€. Noutra piden que resolvamos un problema semellante ao ofrecido aquí pero partindo do suposto de que houbese billetes de 3 €:

As entradas do cine con billetes de 3 €. n+m persoas están nunha cola do despacho do cine; m teñen un billete de 1 € e as outras n só teñen billetes de 3 €. Cada entrada custa 1 €. Na billeteira non teñen ningún tipo de cambio. Se cada cliente compra só unha entrada, cal é a probabilidade de que ningún cliente teña que agardar a que na billeteira teñan cambio?

E aínda máis. Explícase como a solución do problema pode aplicarse para resolver este outro, ben complexo:

Cordas sen interseción. Márcanse 2n puntos sobre unha circunferencia. De cantas formas poden unirse en n pares de tal xeito que as cordas de formadas  non se intersequen entre si?

A partir disto Yaglom e Yaglom explican como se pode obter a solución á seguinte e difícil cuestión, discutida por Euler no 1751 nunha carta a Golbach:

Triangulacións. De cantas formas se pode triangular un n-ágono convexo?