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úmero\quad de\quad casos \quad favorables\quad a \quad A }{número\quad de\quad casos\quad posibles}$$

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 $\binom{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':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'$. Será $A'_{0},A'_{1},...,A'_{k-1},A_{k}$, onde $A'_{0}=(-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},A'_{1},...,A'_{k-1},A_{k},...A_{n+m}$ que comeza en $A'_{0}=(-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}$. Estes terán $m+1$ segmentos horizontais e $n-1$ segmentos verticais que son $\binom{m+n}{n-1}$. Polo tanto o número de casos favorables obterase mediante a resta

$$\binom{m+n}{n}-\binom{m+n}{n-1}=\frac{\left ( m+n \right )!}{n!\cdot m!}-\frac{\left ( m+n \right )!}{\left ( n-1 \right )!\cdot \left ( m+1 \right )!}=\\=\frac{\left ( m+n\right )!\left ( m+1-n \right )}{n!\cdot \left ( m+1 \right )!}$$

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

$$\frac{\left ( m+n\right )!\left ( m+1-n \right )}{n!\cdot \left ( m+1 \right )!}:\binom{m+n}{n}=\frac{\left ( m+n\right )!\left ( m+1-n \right )}{n!\cdot \left ( m+1 \right )!}:\frac{\left ( m+n \right )!}{m!\cdot n!}=$$ $$=\frac{\left ( m+n\right )!\left ( m+1-n \right )m!\cdot n!}{n!\cdot \left ( m+1 \right )!\left ( m+n \right )!}=\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?

A identidade do pau de hóckey e outros diagramas sobre números combinatorios

Posiblemente a mellor forma de introducir un novo tema na aula, nun libro ou nun blogue coma este sexa mediante un problema. Neste caso trátase dun problema moi coñecido pero que a un alumno de secundaria lle pode supoñer todo un reto.

Paseos por unha cidade ortogonal. Nunha cidade as rúas son todas perpendiculares entre si formando unha rede de 5х3 bloques. Pídese obter todos os camiños que conectan os puntos A e B.

Para mergullarse no problema cómpre experimentar algo con el trazando distintos camiños. Na seguinte imaxe podemos ver dous deles, un en negro e outro en azul. 

Só nos podemos mover en dúas direccións, ou ben en horizontal (que identificaremos coa letra $x$), ou ben en vertical (que designaremos por $y$). Así o camiño negro poderíase nomear coa 8-tupla $(x,x,x,x,x,y,y,y)$ e o camiño azul mediante a 8-tupla $(y,x,y,x,x,x,y,x)$. Por pouco que continuemos xogando con este reto non tardaremos en decatarnos que calquera camiño constará de 5 $x$ e 3 $y$. 

Se sabemos algo de combinatoria recoñeceremos que o problema do reconto dos camiños como un caso típico das permutacións con repetición. Quen queira repasar en que consisten pode consultar outra entrada deste blogue dedicada a esta cuestión, Camões e as permutacións con repetición. 

Nesta ocasión trátase de obter todas as 8-tuplas formadas por dous elementos nas que o primeiro, $x$ se repite 5 veces e o segundo, $y$, repítese 3 veces. En termos combinatorios estamos diante dunha permutación con repetición:

$$PR_{8}^{5,3}=\frac{8!}{5!\cdot 3!}=56$$

Outro camiño e xeneralización

Aínda se podería abordar o problema desde outra perspectiva. Fagamos o reconto do número de camiños que hai ata chegar a un determinado vértice. Obsérvase claramente que tanto pola base horizontal como pola altura esquerda vertical do rectángulo só pode haber un camiño que nos leve a cada un dos vértices da rede. Ademais, para obter o número de camiños dun vértice calquera bastará sumar os que nos levan aos vértices inmediatamente anteriores (o situado á esquerda e o situado abaixo) tal e como se indica na seguinte imaxe.

1+2=3 (cousa inusitada)

Pero este é o mesmo procedemento polo que obtemos os elementos do triángulo de Pascal!, de aí que se continuamos calculando o número de camiños que hai a cada vértice obteremos os números combinatorios, onde cada fila do triángulo de Pascal agora aparece como unha diagonal.

Se identificamos os puntos da rede mediante as súas coordenadas cartesianas $(m,n)$ os elementos de cada diagonal son aqueles que teñen a mesma suma. Por exemplo, os vértices da última diagonal representada na anterior imaxe teñen coordenadas que suman 5. Ademais o número de camiños ata ese vértice vén dado polo número combinatorio $$\binom{m+n}{n}=\frac{\left ( m+n \right )!}{m!\cdot n!}=PR_{m+n}^{m,n}$$

Por fin a identidade do pau de hóckey

Por fin chegamos ao que motivou esta entrada, que non foi outra cousa que un resultado que recollo do libro dos xemelgos Akiva M. Yaglom e Isaak M. Yaglom, Challenging Mathematical Problems with Elementary Solutions, Vol. I: Combinational Analysis and Probability Theory. Demostraremos unha fórmula usando o mesmo tipo de diagramas que os que estivemos usando ata o momento.

Consideremos unha rede de dimensións $m-n+1\times n$ e poñámonos a contar camiños desde a orixe

Polo explicado anteriormente sabemos que hai un total de $\binom{m+1}{n}$ camiños distintos. Fagamos agora o reconto doutro xeito. Primeiro movámonos un paso en horizontal e consideremos todos os camiños que parten de $(1,0)$ e chegan a $(m-n+1,n)$. Aplicando a fórmula coñecida vemos que hai un total de $\binom{m}{n}$. Despracémonos agora un paso en vertical ata o $(0,1)$ e despois outro en horizontal ata o $(1,1)$ e desde aquí contabilizaremos ata $(m-n+1,n)$ un total de $\binom{m-1}{n-1}$. Continuemos subindo ata o punto $(1,2)$ e, despois de volver a desprazarnos en horizontal chegaremos ao punto $(2,2)$. Desde aquí ata o extremo superior haberá un total de $\binom{m-2}{n-2}$. Creo xa se está vendo o procedemento para facer este segundo reconto.

Continuaremos deste xeito ata alcanzar o punto $(1,n)$, lugar desde o que hai un total de $\binom{m-n}{0}$ camiños. Finalmente, a suma de todos estes recontos debe coincidir co total de camiños que hai desde o $(0,0)$, de aí a fórmula:

$$\binom{m+1}{n}=\binom{m}{n}+\binom{m-1}{n-1}+\binom{m-2}{n-2}+,,,+\binom{m-n}{0}\quad \quad [1]$$

Fagamos o exercicio de aplicala ao caso $m=7$ e $n=3$.

$$\binom{8}{3}=\binom{7}{3}+\binom{6}{2}+\binom{5}{1}+\binom{4}{0}$$

En números: $56=35+15+5+1$ ten unha curiosa representación sobre o triángulo de Pascal

Identidade do stick de hóckey levóxira

O diagrama que se forma aseméllase a un stick de hóckey.

Xa que temos un triángulo de Pascal á vista, é fácil de recoñecer a súa simetría. Podemos percorrer cada unha das súas filas de esquerda a dereita ou de dereita a esquerda, o resultado é o mesmo. Esta propiedade descríbese coa fórmula

$$\binom{m}{n}=\binom{m}{m-n}$$

Apliquémoslle este resultado a todos e cada un dos números combinatorios da fórmula [1]:

$$\binom{m+1}{m+1-n}=\binom{m}{m-n}+\binom{m-1}{m-n}+\binom{m-2}{m-n}+...+\binom{m-n}{m-n}$$

Substituíndo $m-n=k$ teremos:

$$\binom{m+1}{k+1}=\binom{m}{k}+\binom{m-1}{k}+\binom{m-2}{k}+...+\binom{k+1}{k}+\binom{k}{k}\quad\quad [2]$$

Esta fórmula, [2], que se coñece domo identidade do pau de hóckey, aínda que [1] merece tamén este nome. Para ilustrala imos considerar o caso $m=7$ e $k=2$:

$$\binom{8}{3}=\binom{7}{2}+\binom{6}{2}+\binom{5}{2}+\binom{4}{4}+\binom{3}{2}+\binom{2}{2}$$

Calculando os valores deses números combinatorios a identidade viría sendo $56=21+15+10+6+3+1$

Identidade do stick de hóckey destróxira

Epílogo

Non é esta a primeira vez que aparece a identidade do pau de hóckey neste blogue, xa se usara noutra ocasión para eludir o paso máis complicado da solución dada por Euler ao problema do xogo do recontre.

Problema do recontre. Dúas persoas, A e B, cunha baralla completa cada unha, sacan a un tempo cada súa carta. Se extraen a mesma carta gana A. Se repiten a operación ata esgotar todas as cartas e nunca coinciden, ganará B. Pídese a probabilidade de que gane cada un dos xogadores.

Daquela a identidade aparecía baixo a seguinte expresión:

 $$\sum_{i=k}^{n-1}\binom{k}{i}=\binom{n}{k+1}$$

O que menos me interesa de todo isto son as fórmulas obtidas. Se pasei o traballo de recoller e ordenar todas estas ideas foi por dúas razóns. Unha delas, xa comentada de pasada, é a de traballar con debuxiños para abordar cuestións que, nun principio, son puramente aritméticas. A outra é que usando o mesmo tipo de metodoloxía poderemos abordar un problema en aparencia (só en aparencia) moi simple, e cunha resolución realmente fermosa. Pero iso será na vindeira ocasión.