Todos os camiños levan a Roma (e 2)

Na entrada anterior propoñíamos un problema sobre grafos. De entre todos os tipos de grafos, podemos concordar en que os máis simples son os denominados grafos camiño ou grafos lineares. O grafo linear de lonxitude $n$ denótase $P_{n}$. Ilustraremos a idea co grafo linear $P_{4}$:

Camiños nun grafo linear. Cantos camiños de lonxitude $k$ hai entre os vértices de $P_{4}$?

Trátase de determinar a matriz dos camiños de lonxitude $k$ de $P_{4}$. Nesa referida entrada xa explicaramos o camiño a seguir para obter a solución. Debemos comezar pola matriz de adxacencia do grafo: $$A=\begin{pmatrix} 0 & 1& 0& 0 \\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 &1 \\ 0 & 0& 1& 0 \end{pmatrix}$$

A solución virá dada polas potencias da matriz de adxacencia. O elemento $(i,j)$ de $A^{k}$ indícanos o número de camiños de lonxitude $k$ entre os nodos $i$ e $j$. 

$A^{2}=\begin{pmatrix} 1 & 0&1 & 0\\ 0& 2 & 0 & 1\\ 1 & 0 & 2 & 0\\ 0 & 1 & 0& 1 \end{pmatrix}$ ; $A^{3}=\begin{pmatrix} 0 & 2& 0 & 1\\ 2& 0& 3 & 0\\ 0& 3& 0& 2\\ 1 & 0 &2 & 0 \end{pmatrix}$  ;   $A^{4}=\begin{pmatrix} 0 & 2 & 3&0 \\ 0& 5& 0&3 \\ 3& 0& 5&0 \\ 0 & 3& 0 & 2 \end{pmatrix}$   ;   $A^{5}=\begin{pmatrix} 0 & 5& 0 &3 \\ 5 & 0 & 8& 0 \\ 0& 8 & 0 & 5 \\ 3& 0& 5 & 0 \end{pmatrix}$

Curiosamente os elementos das matrices son vellos coñecidos. Efectivamente, son números da sucesión de Fibonacci (de aí o título da entrada: "Todos os camiños levan a Roma"; se para os de clásicas o centro do mundo se situa en Roma, os de matematemáticas caemos indefectiblemente na sucesisión argallada por Leonardo de Pisa). Volvamos a lembrar en que consiste a famosa sucesión:

$f_0$	$f_1$	$f_2$	$f_3$	$f_4$	$f_5$	$f_6$	$f_7$	$f_8$	$f_9$	$f_{10}$	$f_{11}$	$f_{12}$	$...$	$f_k$
$0$	$1$	$1$	$2$	$3$	$5$	$8$	$13$	$21$	$34$	$55$	$89$	$144$	$...$	$f_{k-1}+f_{k-2}$

Parece bastante evidente que as potencias pares seguen un patrón distinto das potencias impares. Seguindo a Martin Erickson en Beautiful Mathematics (MAA 2011)  conxecturaremos que:

Se $k$ é par: $A^{k}=\begin{pmatrix} f_{k-1} & 0&f_{k} & 0\\ 0& f_{k+1} & 0 & f_{k}\\ f_{k} & 0 & f_{k+1} & 0\\ 0 & f_{k} & 0& f_{k-1} \end{pmatrix}$

Se $k$ é impar: $A^{k}=\begin{pmatrix} 0 & f_{k}& 0 & f_{k-1}\\ f_{k}& 0& f_{k+1} & 0\\ 0& f_{k+1}& 0& f_{k}\\ f_{k-1} & 0 &f_{k} & 0 \end{pmatrix}$

Demostraremos por indución que este resultado é certo. Xa comprobamos máis arriba que o é para os valores de $k=1$, $k=2$, $k=3$, $k=4$ e $k=5$, algúns deles pares, outros impares. Supoñamos as fórmulas certas para un determinado valor $k$ e comprobaremos que serven para $k+1$.

Se $k$ é par: $A^{k+1}=A^{k}A=\begin{pmatrix} f_{k-1} & 0&f_{k} & 0\\ 0& f_{k+1} & 0 & f_{k}\\ f_{k} & 0 & f_{k+1} & 0\\ 0 & f_{k} & 0& f_{k-1} \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 0 \\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 &1 \\ 0 & 0& 1& 0 \end{pmatrix}=\begin{pmatrix} 0 & f_{k-1}+f_{k}& 0 & f_{k}\\ f_{k+1}& 0& f_{k+1}+f_{k} & 0\\ 0& f_{k}+f_{k+1}& 0& f_{k+1}\\ f_{k-1} & 0 &f_{k}+f_{k-1} & 0 \end{pmatrix}=$ $=\begin{pmatrix} 0 & f_{k+1}& 0 & f_{k}\\ f_{k+1}& 0& f_{k+2} & 0\\ 0& f_{k+2}& 0& f_{k+1}\\ f_{k} & 0 &f_{k+1} & 0 \end{pmatrix}$

Se $k$ é impar:

$A^{k+1}=A^{k}A=\begin{pmatrix} 0 & f_{k}& 0 & f_{k-1}\\ f_{k}& 0& f_{k+1} & 0\\ 0& f_{k+1}& 0& f_{k}\\ f_{k-1} & 0 &f_{k} & 0 \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 0 \\ 1 & 0 & 1 & 0\\ 0 & 1 & 0 &1 \\ 0 & 0& 1& 0 \end{pmatrix}=\begin{pmatrix} f_{k} & 0&f_{k}+f_{k-1} & 0\\ 0& f_{k}+f_{k+1} & 0 & f_{k+1}\\ f_{k+1} & 0 & f_{k+1}+f_{k} & 0\\ 0 & f_{k-1}+f_{k} & 0& f_{k} \end{pmatrix}=$

$=\begin{pmatrix} f_{k} & 0&f_{k+1} & 0\\ 0& f_{k+2} & 0 & f_{k+1}\\ f_{k+1} & 0 & f_{k+2} & 0\\ 0 & f_{k+1} & 0& f_{k} \end{pmatrix}$

Todos os camiños levan a Roma (1)

Non sei se agora se estuda algo de teoría de grafos no grao de Matemáticas. Na miña época non se tocaba ese tema, por iso eu non teño nin idea sobre o asunto. Con todo, como son algo atolondrado, non é esta a primeira entrada do blogue que leva a etiqueta "grafos". Ao meu favor teño que todas esas entradas son moi básicas pois nada hai que saber de teoría de grafos para poder seguilas sen dificultade. Velaquí un novo exemplo no que verificar esta afirmación. 

Vou poñer como referencia un texto de divulgación, En busca del grafo perdido (Ariel, 2021), escrito por Clara Grima. Nun dos seus capítulos, para explicar o que é a matriz de adxacencia dun grafo, recolle unha escena da película do 1997 O indomable Will Hunting (Good Will Hunting) na que un profesor do mítico MIT (Massachusetts Institute of Technology) propón o seguinte problema:

A matriz de adxacencia deste grafo será: $$ A=\begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix} $$

Onde cada elemento $a_{ij}$ indica o número de arestas que conectan o vértice $i$ co vértice $j$. A propia matriz describe o número de camiño de lonxitude $1$ entre os vértices. Que pasa cos camiños de lonxitude $2$, isto é, os formados por dúas arestas?

O vértice $1$ pode conectarse consigo mesmo por medio de dúas arestas de dúas formas: $(1,2,1)$ e $(1,4,1)$. 

Ese mesmo vértice pode conectarse co vértice $2$ mediante un único camiño de lonxitude $2$: $(1,4,2)$. 

O vértice $1$ pode conectarse mediante dous camiños de lonxitude $2$ co vértice $3$: $(1,2,3)$ seguindo a aresta superior, e outro seguindo a aresta inferior.

Finalmente o vértice $1$ pode conectarse co vértice $4$ mediante un único camiño de dúas arestas, o camiño $(1,2,4)$

Resumindo, o número de camiños cos que o vértice $1$ pode conectarse con todos os vértices do grafo virá dado polos elementos da  fila $\begin{pmatrix} 2 & 1 & 2 &1 \end{pmatrix}$. Se fixeramos o mesmo co resto dos vértices obteriamos a seguinte matriz:$$A^{2}=\begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix} =\begin{pmatrix} 2 & 1& 2& 1\\ 1& 6 &0 & 1 \\ 2 &0 & 4 & 2 \\ 1& 1& 2 & 2 \end{pmatrix} $$  

Efectivamente, os camiños de lonxitude $2$ virán indicados polos coeficientes da matriz $A^{2}$. En xeral os coeficientes de $A^{n}$ resolven o problema de determinar a cantidade de camiños de lonxitude $n$. Daquela, a solución da segunda pregunta do problema da película obtense así:

$$A^{3}=A^{2}A=\begin{pmatrix} 2 & 1& 2& 1\\ 1& 6 &0 & 1 \\ 2 &0 & 4 & 2 \\ 1& 1& 2 & 2 \end{pmatrix} \begin{pmatrix} 0 & 1& 0& 1\\ 1& 0 &2 & 1 \\ 0 &2 & 0 & 0 \\ 1& 1& 0 & 0 \end{pmatrix}=\begin{pmatrix} 2 & 7& 2& 3\\ 7& 2 &12 & 7 \\ 2 &12 & 0 & 2 \\ 3& 7& 2 & 2 \end{pmatrix}$$

Ben, ata aquí temos todos os vimbios para propoñer, e resolver, un problemiña.

Un problema simple

De entre todos os tipos de grafos, podemos concordar en que os máis simples son os denominados grafos camiño ou grafos lineares. O grafo linear de lonxitude $n$ denótase $P_{n}$. Ilustraremos a idea co grafo linear $P_{4}$:

Camiños nun grafo linear. Cantos camiños de lonxitude $k$ hai entre os vértices de $P_{4}$?

Trátase de determinar a matriz dos camiños de lonxitude $k$ de $P_{4}$. Para saborear o problema podemos abordar primeiro algúns casos máis simples. Poderiamos comezar estudando os camiños de $P_{2}$:

A matriz de adxacencia deste grafo será $A=\begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$; como $A^{2}=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}=I$ teremos que :

$A^{k}=\begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix}=A$ se $k$ é impar e $A^{k}=\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}=I$ se $k$ é par.

Que sucede no caso de $P_{3}$? Mirando o grafo

Vemos que a súa matriz de adxacencia é $A=\begin{pmatrix} 0 &1 & 0 \\ 1&0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$  polo que $A^{2}=\begin{pmatrix} 1 &0 & 1 \\ 0&2 & 0 \\ 1 & 0 & 1 \end{pmatrix}$ ; $A^{3}=\begin{pmatrix} 0 &2 & 0 \\ 2&0 & 2 \\ 0 & 2 & 0 \end{pmatrix}=2\begin{pmatrix} 0 &1 & 0 \\ 1&0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$;         $A^{4}=\begin{pmatrix} 2 &0 & 2 \\ 0&2 & 0 \\ 2& 0 & 2 \end{pmatrix}=2\begin{pmatrix} 1 &0 & 1 \\ 0&2 & 0 \\ 1 & 0 & 1 \end{pmatrix}$ ; $A^{5}=\begin{pmatrix} 0 &4 & 0 \\ 4&0 & 4 \\ 0 & 4 & 0 \end{pmatrix}=4\begin{pmatrix} 0 &1 & 0 \\ 1&0 & 1 \\ 0 & 1 & 0 \end{pmatrix}$;         $A^{6}=\begin{pmatrix} 4 &0 & 4 \\ 0&8 & 0 \\ 4& 0 & 4 \end{pmatrix}=4\begin{pmatrix} 1 &0 & 1 \\ 0&2 & 0 \\ 1 & 0 & 1 \end{pmatrix}$  

Xa se ve como vai continuar.

Agora é o momento de abordar o problema orixinal, o dos camiños de $P_{4}$. É o teu turno. Prométoche que ten premio. Nunha próxima entrada, darei a solución.

A razón dun problema de optimización. 2

Trátase de resolver o problema proposto na entrada anterior. Lembro que non só pedía a solución, senón a razón do problema. Velaquí o enunciado:

Triángulo circunscrito a unha semicircunferencia. Dada unha semicircunfencia de raio $1$ pídense as dimensións do triángulo isóscele de perímetro mínimo circunscrito á circunferencia.

Sexa $D(x,y)$, un punto calquera da semicircunferencia. Como $x$ e $y$ son os catetos dun triángulo rectángulo de hipotenusa $1$: $x^{2}+y^{2}=1$ e, polo tanto $y=\sqrt{1-x^{2}}$. Derivamos para obter a pendente da recta tanxente $AB$: $y'=\frac{-x}{\sqrt{1-x^{2}}}$

Introducimos agora o ángulo $\alpha$, resulta que $x=cos\alpha$. Daquela

$y'=\frac{-cos\alpha}{\sqrt{1-cos^{2}}\alpha}=\frac{-cos\alpha}{sen\alpha}$

O punto $D$ ten coordenadas $(sen\alpha, cos\alpha)$. Usámolo para obter a ecuación punto-pendente da recta tanxente á semicircunferencia en $D$:

$y-sen\alpha=\frac{-cos\alpha}{sen\alpha}\left( x-cos\alpha \right)=\frac{-cos\alpha}{sen\alpha}x+\frac{cos^{2}\alpha}{sen\alpha}$

Se $x=0$:  $y-sen\alpha=\frac{cos^{2}\alpha}{sen\alpha}$ $y=\frac{cos^{2}\alpha}{sen\alpha}+sen\alpha=\frac{cos^{2}\alpha+cos^{\alpha}}{sen\alpha}=\frac{1}{sen\alpha}$. Así obtemos as coordenadas de $A(0, \frac{1}{sen\alpha})$

Se $y=0$:   $-sen\alpha=\frac{-cos\alpha}{sen\alpha}x+\frac{cos^{2}\alpha}{sen\alpha}$ $\frac{-cos\alpha}{sen\alpha}x=-sen\alpha-\frac{cos^{2}\alpha}{sen\alpha}=\frac{-sen^{2}\alpha-cos^{2}\alpha}{sen\alpha}=\frac{-1}{sen\alpha}$

$x=\frac{1}{cos\alpha}$. Así obtermos as coordenadas de $B\left( \frac{1}{cos\alpha},0 \right)$

Con estes antecedentes:

$$AB^{2}=\frac{1}{sen^{2}\alpha}+\frac{1}{cos^{2}\alpha}=\frac{1}{sen^{2}\alpha\cdot cos^{2}\alpha}\Longrightarrow AB=\frac{1}{sen\alpha\cdot cos\alpha}$$

Agora xa podemos escribir o perímetro do triángulo en función de $\alpha$: $$P\left( \alpha \right)=2\left( AB+OB \right)=2\left( \frac{1}{sen\alpha\cdot cos\alpha}+\frac{1}{cos\alpha} \right)=2\frac{1+sen\alpha}{sen\alpha\cdot cos\alpha }$$

Derivamos na procura dos extremos:

$$P'\left( \alpha \right)=2\frac{cos\alpha\left( sen\alpha\cdot cos\alpha \right)-\left( 1+sen\alpha \right)\left( cos^{2} \alpha-sen^{2}\alpha\right)}{sen^{2}\alpha\cdot cos^{2}\alpha}=$$ $$=2\frac{sen\alpha\cdot cos^{2}\alpha-cos^{2}\alpha+sen^{2}\alpha-sen\alpha\cdot cos^{2}\alpha+sen^{3}\alpha}{sen^{2}\alpha\cdot cos^{2}\alpha}=2\frac{sen^{3}\alpha+2sen^{2}\alpha-1}{sen^{2}\alpha\cdot cos^{2}\alpha}$$

Pescudemos para que valores $P'=0$. Tomando $y=sen\alpha$ o numerador anúlase cando $y^{3}+2y^{2}-1=0$. Evidentemente $y=-1$ é unha raíz deste polinomio polo que podemos descompoñelo $y^{3}+2y^{2}-1=(y+1)\left( y^{2}+y-1 \right)=0$ Así que as outras solucións serán $-\phi$ e $\frac{1}{\phi}$. Como $\alpha$ é un angulo do primeiro cuadrante, $y=sen\alpha$ debe ser postivo. Daquela a única solución que nos serve é $sen\alpha=\frac{1}{\phi}$. Ademais como $y^{3}+2y^{2}-1=(y+1)\left( y+\phi \right)\left(  y-\frac{1}{\phi}  \right)$ a derivada no punto $x=\frac{1}{\phi}$ pasa de ser negativa a positiva, de aí que a función $P$ teña nese punto un mínimo.

$cos\alpha=\sqrt{1-sen^{2}\alpha}=\sqrt{1-\frac{1}{\phi^{^{2}}}}=\sqrt{\frac{\phi^{2}-1}{\phi^{2}}}=\frac{\sqrt{\phi-1-1}}{\phi}=\frac{\sqrt{\phi}}{\phi}$

$$A\left( 0,\frac{1}{sen\alpha} \right)=\left( 0,\phi \right)  \quad \quad B\left( \frac{1}{cos\alpha},0 \right)=\left( \sqrt{\phi},0 \right)$$  $$AB=\frac{1}{sen\alpha\cdot cos\alpha}=\frac{1}{\frac{1}{\phi}\frac{1}{\sqrt{\phi}}}=\phi\sqrt{\phi}$$  $$EB=\sqrt{\phi}-\frac{1}{\sqrt{\phi}}=\frac{\phi-1}{\sqrt{\phi}}=\frac{\frac{1}{\phi}}{\sqrt{\phi}}=\frac{1}{\phi\sqrt{\phi}}$$

O perímetro máximo terá un valor de $$P=2\left( AB+OB \right)=2\left( \phi\sqrt{\phi} +\sqrt{\phi}\right)=2\sqrt{\phi}\left(\phi+1  \right)=2\phi^{2}\sqrt{\phi}$$

Triángulos de Kepler

Chámanse triángulos de Kepler a aqueles triángulos rectángulos que teñen os lados en progresión xeométrica. Resulta evidente que a razón desta progresión debe ser $\sqrt{\phi}$. Botándolle un ollo á anterior imaxe poderemos distinguir varios triángulos de Kepler:

$EDB$ ten lados de lonxitudes $\frac{1}{\phi\sqrt{\phi}},\quad \frac{1}{\phi},\quad \frac{1}{\sqrt{\phi}}$

$OED$ ten lados de lonxitudes $ \frac{1}{\phi},\quad \frac{1}{\sqrt{\phi}}, \quad 1$

$OAD$ ten lados de lonxitudes $ \frac{1}{\sqrt{\phi}}, \quad 1, \quad \phi$

$OAB$ ten lados de lonxitudes $\sqrt{\phi}, \quad \phi, \quad \phi\sqrt{\phi}$

Fica claro que a razón sobre a que se preguntaba ao principio era unha razón dourada, unha razón da que temos mostras sobradas na solución dada.

A razón dun problema de optimización.1

Os problemas de optimización trátanse no bacharelato. Este tipo de problemas teñen o seu aquel. Vexamos por que. 

Moito do que se trata nas matemáticas non universitarias é de carácter algorítmico. Ben sei que tópicos, como por exemplo a resolución de ecuacións cadráticas, pode introducirse desde outros puntos de vista; mais, unha vez introducido vólvese unha cuestión puramente algorítmica e como tal hai que entrenala ata integrala dentro co coñecemento base para poder asaltar outras fronteiras. Porén os problemas de optimización parecen querer fuxir do corsé algorítmico. Dependendo das características particulares do que se queira resolver hai que pescudar as relacións que mellor nos permitan determinar unha función que modelice a cuestión para poder pasar ao estudo, agora si, algoritmico, da súa monotonía. 

Un dos problemas que lle pedín resolver ao alumnado de Matemáticas II foi o seguinte:

Rectángulo inscrito triángulo. Nun triángulo isóscele de base 12 e altura 10 inscribimos un rectángulo de área máxima. Determina as dimensións do rectángulo. Acha o valor desa área máxima.

A solución comezaría facendo un esquema como o da imaxe. A partir de aquí obtemos unha fórmula para a área:

 $A=2xy$

Como nesta fórmula temos dúas variables, non nos queda outra que intentar relacionalas entre si para, deste xeito, conseguir unha fórmula funcional dunha soa variable.

A lonxitude de calquera dos dous lados iguais do triángulo isóscele pode calcularse a partir do teorema de Pitágoras:

$\sqrt{6^{2}+10^{2}}=\sqrt{136}$

Esta valor tamén se pode obter como suma das hipotenusas dos dous triángulos rectángulos que vemos na dereita da imaxe:

$$\sqrt{\left( 10-y \right)^{2}+x^{2}}+\sqrt{y^{2}+\left( 6-x \right)^{2}}=\sqrt{136}$$

Este foi o camiño que seguiron algúns alumnos. Non tardaron en comprender que se estaban encerellando. Cómpre buscar unha alternativa. 

Unha das forma de solventar a situación sería decatándose de que calquera destes triángulos rectángulos é semellante ao delimitado pola altura e a metade da base do triángulo isóscele. Daquela poderiamos obter as seguintes relacións $\frac{10}{6}=\frac{y}{6-x}\quad ;\quad \frac{10}{6}=\frac{10-y}{x}$

Unha nova opción consistiría en botar man dos coñecementos de xeometría analítica plana ou de reprentación gráfica de rectas para determinar a ecuación da recta pola que se move o punto $P$ ( ten pendente $m=-\frac{10}{6}$ e ordenada na orixe $n=10$)

Un recordo e un problema

Entre os meus recordos como estudante está o dun día concreto de cando cursaba COU. Tiñamos exame ao día seguinte. O profesor déranos un boletín de problemas e quedaban moitos por facer. Un deles era un problema de optimización clásico:

Cono inscrito nunha esfera. Dada unha esfera de raio $r$ determinar as dimensións do cono inscrito na esfera de volume máximo

A cuestión era fermosa, así que abandonei o estudo do exame e centreime no problema. Intenteino unha e outra vez e non o daba resolto. Pero o problema tiña o seu aquel, así que tachaba e volvía unha e outra vez sobre el. Finalmente, rematando a tarde, decateime de que bastaba con realizar un esquema que me permitise relacionar as variables entre si por medio do dato, o raio da esfera. Levaba todo o tempo debuxando mal o raio.

Efectivamente, ata que non se me ocorreu representar o raio que aparece en azul na imaxe, non fun quen de asaltar o problema. Por certo, foi unha das peguntas do exame. :)

Para darlle un bo remate a esta entrada, non hai nada mellor que un problema:

Triángulo circunscrito a unha semicircunferencia. Dada unha semicircunfencia de raio $1$ pídense as dimensións do triángulo isóscele de perímetro mínimo circunscrito á circunferencia.

Non só vou pedir a solución ao problema (que darei na seguinte entrada), senón a súa razón. Esta petición non só é unha nova pregunta, senón que tamén dá unha pista de por onde van os tiros.

Moedas falsas

Antes de nada imos cumprir co prometido dando a solución do problema proposto na anterior entrada, Adiviña fibonacciana. A cuestión consistía en determinar a suma dos 10 primeiros termos dunha sucesión do estilo da de Fibonacci que comezase por dous termos descoñecidos $a$ e $b$ a partir do coñecemento dun dos 10 elementos desa sucesión. O problema é realmente curioso porque parece imposible poder determinar esa suma sabendo só un elemento. Basta con que elaboremos unha táboa como a seguinte indicando os termos da sucesión nunha fila e as sumas dos mesmos noutra. A resposta salta á vista.

n	1	2	3	4	5	6	7	8	9	$10$
$f_{n}$	$a$	$b$	$a+b$	$a+2b$	$2a+3b$	$3a+5b$	$5a+8b$	$8a+13b$	$13a+21b$	$21a+34b$
$S_{n}$	$a$	$a+b$	$2a+2b$	$3a+4b$	$5a+7b$	$8a+12b$	$15a+20b$	$21a+33b$	$34a+54b$	$55a+88b$

Por se hai alguén con falta de vista, que se fixe no valor de $f_{7}$

Esta cuestión recollina do libro The Mathematics of Various Entertaining Subjects (Princenton University Press, 2016), un libro no que cada capítulo está asinado por un autor distinto. Chamoume a atención o de Anany Levitin, que trata sobre adiviñas matemáticas que se resolven nun só paso. A autora destaca este tipo de retos porque son sorprendentes e escasos, un par de características que os fan moi valiosos. Por se esta perla non anima o suficiente a botarlle un ollo ao capítulo de Levitin, vou recoller un par de problemas máis desta mesma fonte. Cando lin o enunciado do primeiro vin inmediatamente a solución. Claro! foi divulgado por Martin Gardner e seguramente xa non era a primeira vez que o tiña diante.

Unha pía de moedas falsas. Hai 10 pías de 10 moedas de aparencia idéntica. Todas as moedas dunha destas pías son falsas, mentres que todas as moedas das outras pías son auténticas. Cada moeda auténtica pesa w gramos, mentres que cada moeda falsa pesa w + 1 gramos, onde w é coñecido.

Tamén existe unha báscula dun só prato que pode determinar o peso exacto de calquera número de moedas. Identifica a pía coas moedas falsas nunha soa pesada.

O segundo trata o mesmo tópico, moedas legais vs. moedas falsas. Deste vou dar a solución máis abaixo, así que se queres gozar con el, non fagas scroll máis abaixo da imaxe. Por certo, na imaxe aparecen moedas de peseta. Os que xa temos certa idade lembramos que as moedas de 5 pesetas chamábanselle pesos. Normalmente non se falaba dos billetes de cen pesetas, senón dos de vinte pesos.Tiven o malicioso pensamento de usar no seguinte enunciado a palabra peso no canto de moeda para encerellar máis o problema, pero contívenme. Retrospectivamente creo que fixen mal, así que queda como exercicio ao lector que lea o enunciado facendo o cambio e verá que o meu espírito malicioso tiña razón.

Unha moeda sospeitosa. De 101 moedas, 50 son falsas. O peso dunha moeda auténtica é un número enteiro descoñecido, mentres que todas as moedas falsas teñen o mesmo peso, que difire do peso dunha moeda auténtica en 1 gramo. Pedro ten unha báscula de dous pratos que mostra a diferenza de peso entre os obxectos colocados en cada prato. Pedro elixe unha moeda e quere determinar nunha soa pesada se é auténtica ou falsa. Pode facelo?

Tanto monta, monta tanto

Canto pesan 20 pesos?

O curioso do caso é que podemos dar a solución de dúas formas completamente distintas. Vexamos a primeira.

Colócase nun prato da balanza a moeda escollida e no outro o resto. Sexa $a$ o peso dunha moeda auténtica e $f=a\pm 1$ o dunha moeda falsa. 

Se a moeda escollida é falsa a diferenza entre os pratos  será $51a+49f-f=51a+48f=51a+48(a\pm1)=99a\pm48$ que é múltiplo de $3$

Se a moeda escollida é auténtica a diferenza entre os pratos será $50a+50f-a=49a+50f=49a+50(a\pm1)=99a\pm50$ que non é múltiplo de $3$

Tamén podemos resolver o problema segundo as indicacións de Fomin et al, do libro Círculos matemáticos (SM&RSME 2012), editado na colección Estímulos Matemáticos. Agora déixase a un lado a moeda escollida e colócanse 50 moedas en cada prato da balanza.

Estudemos o que sucede se a moeda retirada é auténtica. Nese caso quedan 50 de cada tipo. Supoñamos que no primeiro prato poñemos as 50 auténticas que pesan $50a$ e no segundo as 50 falsas, que pesan $50(a\pm1)=50a\pm50$.  Daquela a diferenza de peso entre os pratos será $\pm50$. Se intercambiamos unha moeda falsa do primeiro prato cunha falsa do segundo, a diferenza variará en $\pm2$. Se repetimos o intercambio a diferenza seguirá sendo par.

Se a moeda retirada fora falsa quedarían 49 falsas e 51 auténticas. Supoñamos que no primeiro prato temos 50 auténticas e no segundo están as 49 falsas máis a outra auténtica. Entón a diferenza entre os pesos dos pratos será $50a-(49f+a)=49a-49f=49a-49(a\pm1)=\pm49$, un número impar. Outra vez, se intercambiamos unha moeda auténtica dun prato con outra falsa do outro, a variación da diferenza será de $\pm2$. En conclusión, cando a moeda retirada é falsa, a diferenza de peso entre os pratos é impar. 

Números de Catalan (A000108) e triángulo de Narayana (A001263)

 por Andrés Ventas

$\newcommand{\tei}[1]{\lceil #1 \rceil} \newcommand{\teib}[1]{\Big\lceil #1 \Big\rceil} \newcommand{\teig}[1]{\Bigg\lceil #1 \Bigg\rceil} \newcommand{\fa}[2]{\rlap{#1}\rule[9pt]{#2}{0.8pt}} \newcommand{\fd}[2]{\rlap{#1}\rule[-3pt]{#2}{0.8pt}}$ Esta entrada é un entretenemento numérico que xorde de botar unha ollada ás secuencias da OEIS A000108 Catalan numbers e OEIS A001263 Triangle of Narayana numbers.

Imos ver como se obteñen a partir dunha serie hiperxeométrica e unha fracción continua teito.

Recollendo o que se comenta na wikipedia (Catalan number) temos que se calculan como $C_{n}=\dfrac{1}{n+1}\displaystyle\binom{2n}{n}= \dfrac{(2n)!}{(n+1)!n!}$ dando lugar á secuencia:

$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, \ldots$

Teñen varias interpretacións combinatorias como por exemplo ser o número de particións non cruzadas dun conxunto de $n$ elementos.

Aquí partición non cruzada defínese como:

Sexa $n$ un número natural e $P = \{B_1,\dots,B_k\}$ unha partición do conxunto $\{1,\dots,n\}$. Dise que esta partición é non cruzada se para todo $i \neq j$, os bloques $B_i$ e $B_j$ non se cruzan, é dicir, para todo $a,b \in B_i; \ c,d \in B_j,$ non é certo que $a \lt c \lt b \lt d$.

Por exemplo, $\{ \{1,2\}, \{3,4\} \}$ é unha partición sen cruzamento para $n=4$ pero $\{\{1,3\}, \{2,4\}\}$ non o é.

Números de Catalan xerados mediante unha función hiperxeométrica

Na páxina Wolfran Mathworld Catalan Number aparece que os números ce Catalan pódense obter mediante a función hiperxeométrica $_2F_1(1-n, -n; 2; 1)$, imos botar contiñas:

$ \begin{align} C_n={}_2F_1(1-n, -n; 2; 1) &= \sum_{k=0}^{\infty}\dfrac{(1-n)^{\fa{k}{7pt}}(-n)^{\fa{k}{7pt}}}{2^{\fa{k}{7pt}}k!}z^k; \\ &= 1 + \dfrac{(1-n)(-n)}{2}+ \dfrac{(1-n)(2-n)(-n)(1-n)}{2\cdot 3 \cdot 2!} + \\ & \quad\quad + \dfrac{(1-n)(2-n)(3-n)(-n)(1-n)(2-n)}{2\cdot 3 \cdot 4 \cdot 3!} + \\ & \quad\quad + \dfrac{(1-n)(2-n)(3-n)(4-n)(-n)(1-n)(2-n)(3-n)}{5! \cdot 4!} + \cdots \\ \end{align} $

E coidado aquí co símbolo de Pochhammer porque existe un lío de nomenclatura precisamente por mor das series hiperxeométricas. Os parámetros das series hiperxeométricas son factoriais ascendentes pero escríbense tradicionalmente co índice abaixo: $(a)_n$ sería $ a(a+1)(a+2) \cdots (a+n-1)$ e cando necesitas usar na mesma fórmula factoriais ascendentes con descendentes non fica claro como representar os descendentes. Así que aquí vou usar o subliñado e sobreliñado de Donald Knuth $x^{\fd{k}{7pt}}=x(x-1)(x-2)\cdots (x-(k-1))$ para o factorial descendente e $x^{\fa{k}{7pt}}=x(x+1)(x+2)\cdots (x+k-1)$ para o factorial ascendente.

O último parámetro é $z=1$. Tendo en conta que as series hiperxeométricas rematan cando $a$ ou $b$ son números enteiros non positivos, e por tanto aquí remataría cando un termo $a - n$ faise cero, temos para cada $n$:

$ \begin{align} n=0; C_0 &= 1 + \dfrac{1\cdot 0}{2}= 1;\\ n=1; C_1 &= 1 + \dfrac{0\cdot -1}{2}= 1;\\ n=2; C_2 &= 1 + \dfrac{-1\cdot -2}{2} + \dfrac{0\cdot -1}{6\cdot 2}= 1 + 1 = 2;\\ n=3; C_3 &= 1 + \dfrac{-2\cdot -3}{2} + \dfrac{(-2)(-1)(-3)(-2)}{6\cdot 2}= 1 + 3 + 1 = 5;\\ n=4; C_4 &= 1 + \dfrac{-3\cdot -4}{2} + \dfrac{(-3)(-2)(-4)(-3)}{6\cdot 2} \\ & \quad\quad + \dfrac{(-3)(-2)(-1)(-4)(-3)(-2)}{24\cdot 6}= 1 + 6 + 6 + 1 = 14;\\ n=5; C_5 &= 1 + \dfrac{-4\cdot -5}{2} + \dfrac{(-4)(-3)(-5)(-4)}{6\cdot 2} + \dfrac{(-4)(-3)(-2)(-5)(-4)(-3)}{24\cdot 6} \\ & \quad\quad + \dfrac{(-4)(-3)(-2)(-1)(-5)(-4)(-3)(-2)}{120\cdot 24} = 1 + 10 + 20 + 10 + 1 = 42;\\ &\cdots \end{align} $

E vemos que os sumandos van formando os valores do triángulo de Narayana.

Como o triángulo de Narayana comeza con $k=1$ e aquí os sumandos comezan en $k=0$ e a maiores $(1-n){^\fa{k-1}{15pt}} (-n)^{\fa{k-1}{15pt}} = (n-1)^{\fd{k-1}{15pt}} \ n^{\fd{k-1}{15pt}},$ daquela temos que os coeficientes do triángulo de Narayana poden definirse como $N(n,k) = \dfrac{(n-1)^{\fd{k-1}{15pt}} \ n^{\fd{k-1}{15pt}}}{k!(k-1)!}$ e isto coincide coa fórmula usual dos coeficientes do triángulo de Narayana:

$ \begin{align} C_n &= \dfrac{1}{n}\displaystyle\binom{n}{k} \displaystyle\binom{n}{k-1} \\ &= \dfrac{1}{n} \cdot \dfrac{n^{\fd{k}{7pt}}}{k!} \cdot \dfrac{n^{\fd{k-1}{15pt}}}{(k-1)!} \\ &= \dfrac{(n-1)^{\fd{k-1}{15pt}} \ n^{\fd{k-1}{15pt}}}{k!(k-1)!}. \end{align} $

Números de Catalan xerados mediante unha fracción continua

Imos ampliar ampliar a fórmula da entrada de retallos Relación entre series infinitas, fraccións continuas teito e constantes. Series hiperxeométricas. Final. para recoller tamén a fórmula dos converxentes:

Para a suma $S=\frac{1}{u_0}+\frac{1}{u_0 u_1}+\frac{1}{u_0 u_1 u_2}+\cdots $

Se pasamos a unha $fctx$ temos: $ S^{-1}= \teig{ \begin{matrix} - & u_0 & u_1 & u_2 & u_3 &\ldots\\ u_0 & u_1 + 1 & u_2 + 1 & u_3 + 1 & u_4 + 1 & \ldots \end{matrix} }$

Os converxentes da inversa da fracción continua serían $B_i/A_i$. $ S^{-1}= \teig{ \begin{matrix} A_i & 1 & u_0 & u_0 (u_1+1) - u_0 =u_0u_1 & u_2 u_1 u_0 + u_1 u_o - u_1 u_0 = u_2 u_1 u_0 &\ldots \\ B_i & 0 & 1 & u_1 + 1 & (u_1 + 1)(u_2+1) - u_1 = u_2(u_1 + 1) +1 & u_3 (u_2(u_1 + 1)+1) + 1 & \ldots \end{matrix} }$

Observamos outra forma de expresar os $B_i$, por exemplo $u_3 (u_2(u_1 + 1)+1) + 1=u_3 u_2u_1 + u_3u_2 + u_3 +1$.

Por tanto $A_i= \prod_{j=0}^{i}u_j; \quad B_i = \big(\sum_{k=1}^{i} \prod_{j=k}^{i}u_j \big) + 1.$

E aquí perden a súa maxia as fraccións continuas teito xeneralizadas pois se realizamos esta suma do xeito tradicional e sen simplificar temos un resultado cuspidiño:

$S=\frac{1}{u_0}+\frac{1}{u_0 u_1}+\frac{1}{u_0 u_1 u_2}+\cdots = \frac{u_1 + 1}{u_0 u_1} + \frac{1}{u_0 u_1 u_2}+\cdots = \frac{u_2(u_1 + 1)+1}{u_0 u_1 u_2} +\cdots$

No noso caso partindo da función hiperxeométrica

$ \begin{align} C_n={}_2F_1(1-n, -n; 2; 1) &= 1 + \dfrac{(1-n)(-n)}{2}+ \dfrac{(1-n)(2-n)(-n)(1-n)}{2\cdot 3 \cdot 2!} + \\ & \quad\quad + \dfrac{(1-n)(2-n)(3-n)(-n)(1-n)(2-n)}{2\cdot 3 \cdot 4 \cdot 3!} + \\ & \quad\quad + \dfrac{(1-n)(2-n)(3-n)(4-n)(-n)(1-n)(2-n)(3-n)}{5! \cdot 4!} + \cdots \\ \end{align} $

Temos $u_0=1, u_1=\dfrac{2}{(1-n)(-n)}, u_2=\dfrac{3 \cdot 2}{(2-n)(1-n)}, u_3=\dfrac{4 \cdot 3}{(3-n)(2-n)}, u_4=\dfrac{5 \cdot 4}{(4-n)(3-n)},\cdots;$

Imos botar contas para $n=4$ e $n=5$:

Para $n=4$

$ \begin{align} & u_0=1; u_1=\dfrac{1}{6}; u_2=1; u_3= 6. \\ A_3 &= 1\cdot \dfrac{1}{6} \cdot 1 \cdot 6 = 1. \\ B_3 &= \dfrac{1}{6} \cdot 1 \cdot 6 + \cdot 1 \cdot 6 + 6 + 1= 1 + 6 + 6 + 1 = 14. \\ \end{align} $

Para $n=5$

$ \begin{align} & u_0=1; u_1=\dfrac{1}{10}; u_2=\dfrac{1}{2}; u_3=2; u_4= 10. \\ A_4 &= 1\cdot \dfrac{1}{10} \cdot \dfrac{1}{2} \cdot 2 \cdot 10 = 1. \\ B_4 &= \dfrac{1}{10} \cdot \dfrac{1}{2} \cdot 2 \cdot 10 + \dfrac{1}{2} \cdot 2 \cdot 10 + \cdot 2 \cdot 10 + 10 +1 = 1 + 10 + 20 + 10 + 1 = 42. \\ \end{align} $

E pouco máis que agregar, todo cadra despois de botar contas de diversos xeitos.

Teorema de Hall. Aplicacións.

 Xa levamos varias entradas dándolle voltas ao seguinte resultado.

Teorema do matrimonio de Hall. Dado un grafo bipartito $G=(X,Y)$, unha condición necesaria e suficiente para que $X$ teña un emparellamento perfecto (condición de Hall) é que  $\forall A\subset X$ se verifique que $ \left| A \right|\le \left| N\left( A \right) \right|$

Xa vimos como se podía aplicar ao establecemento de trucos de maxia ou á resolución do problema do matrimonio. Agora toca aplicalo a novos problemas.

Unha carta de cada valor. Colocamos as 40 cartas dunha baralla española en 10 columnas de 4 cartas. Poderemos sempre, escollendo unha carta de cada columna, obter todos os valores (do as ao rei)?

Na seguinte imaxe temos un exemplo. Podes comprobar que neste caso si que podemos escoller unha carta de cada columna.

No exemplo da imaxe podemos coller de dereita a esquerda 1, 2, 3, 4, 5, 6, 7, Sota, Rei e Cabalo. A cuestión, claro, é se sempre é posible. 

Para iso establecemos un grafo bipartito. Por unha banda temos os 10 vértices que nos representan os 10 valores das cartas: 1, 2, 3, ,4 5, 6, 7, S, C, R. Por outra os 10 vértices que representan os 10 montóns $m_{1},m_{2},...,m_{10}$. Conectamos cada montón con todos os valores que conteña. Dado un subconxunto $A$ calquera de $k$ valores teremos  a súa veciñanza $ N\left( A \right) $  isto é, o conxunto de vértices (montóns) que están conectados con algún dos vértices de $A$. Supoñamos que $\left| N\left( A \right) \right|\lt k$. Isto significa que hai como moito $k-1$ montóns que conteñen as $4k$ cartas representadas por $A$. Pero en $k-1$ montóns só hai $4k-4$ cartas! De aí que a suposición que fixemos debe ser falsa. A conclusión é que se verifica a condición de Hall para calquera colección de valores: $\left| A \right|\le \left| N\left( A \right) \right|$. De aí que sempre poidamos establecer un emparellamento perfecto entre valores e montóns. Ademais este razoamento é completamente xeral polo que tamén é valido no caso de que quixeramos escoller os 13 valores distintos dunha baralla francesa distribuídos nunha matriz $4 \times 13$. Quizais sobra dicilo, pero tamén é factible escoller sempre unha carta de cada pau collendo unha carta de cada fila. Claro que esta posibilidade preséntase como menos espectacular.

Sempre gañadores

O seguinte problema ten certo empaque. Apareceu na competición Putnam do ano 2012. 

Sempre gañadores. $2n$ equipos xogan un torneo de todos contra todos. Durante $2n-1$ días cada equipo xoga exactamente contra un adversario distinto. Non hai empates.

Demostra que podemos escoller un equipo gañador diario sen que repitamos ningún equipo dúas veces.

O razoamento terá moitas concomitancias co anterior. Realizarémolo por redución ao absurdo. Comezamos establecendo un grafo bipartito con $2n-1$ vértices representando a cada un dos dos días do torneo e  outros $2n$ vértices identificando cada un dos equipos participantes. As arestas unen cada equipo cos días nos que gaña.

Razoaremos por redución ao absurdo. Supoñamos que non hai un emparellamento perfecto. Daquela non se verificará a condición de Hall e existirá un subconxunto $A$ de $k$ días tal que $\left| N\left( A \right) \right|\lt k$: neses días hai menos de $k$ gañadores. Velaí que haberá un xogador que perdeu todos os partidos durante eses $k$ días. Pero isto asegura que debe haber $k$ equipos gañadores diferentes nese período. Xa obtivemos a contradición.

Agochado no enunciado hai outro problema, o de establecer un calendario para unha liga na que $2n$ equipos xoguen todos contra todos. Pódese facer? Como? A pouco que un o pense decatarase de que é posible realizala, e de moitas maneiras distintas. No libro de Oystein Ore, Graphs and their uses (MAA 1990) ofrécese unha solución para o caso xeral.

Problemas chegados desde Moscú. 3

Esta é a terceira e última entrada adicada a recoller problemas de Boris Kordemsky. As anteriores pódense consultar aquí e aquí.

Imos cun problema moi simple. Con todo moita xente dirá que lle faltan datos.

Un barco diésel e un hidroavión. Un barco diésel parte de viaxe. Cando está a 180 millas da costa envíase un hidroavión co correo que ten unha velocidade dez veces superior á do barco. A que distancia alcanza o barco?

O encantador do seguinte problema é que a pregunta é inesperada. 

En coche e a cabalo. Un mozo e un home maior saen da vila cara a cidade; un vai a cabalo e outro en coche. Pronto queda claro que se o home maior chegase tres veces máis lonxe de onde está, quedaríalle a metade para viaxar do que lle queda. E se o mozo viaxara a metade do que xa fixo, quedaríanlle tres veces máis para viaxar do que lle queda. Quen vai a cabalo?

Sei que non hai que recorrer á combinatoria para resolver a seguinte cuestión. Con todo, desde que o coñecín coloqueino entre os problemas a resolver cando trato na clase as técnicas de reconto combinatorio.

Novas estacións. Cada estación vende billetes a todas as outras estacións do percorrido. Cando se engaden algunhas estacións hai que imprimir 46 billetes adicionais. Cantas estacións se engadiron? Cantas había antes?

Teño preferencia polos problemas de matemáticas sen referencias externas. Matemáticas para estudar as propias matemáticas. Dentro deste ámbito está o estudo do propio sistema de numeración. Quizais o pouco traballo/reflexión sobre o sistema decimal, quizais a propia abstracción deste tipo de cuestións, o certo é que normalmente vólvenselle moi dificultosas ao alumnado.

Un número de cinco díxitos. Dime un número de cinco díxitos tal que se lle engades un 1 despois do mesmo é tres veces maior que se llo engades antes.

Cando un se enfronta ao seguinte enunciado cómprelle unha gran dose de imaxinación. Temos un avión, unha motocicleta e un cabalo andando dun lado para outro. O curioso é que non nos dan ningunha velocidade.

O motociclista e o xinete. Envían un motociclista desde a oficina de correos a tempo para a chegada dun avión ao aeroporto. O avión chega antes de tempo e o correo é transportado á oficina de correos a cabalo. Despois de media hora o xinete crúzase co motociclista e dálle o correo. A motocicleta volve á oficina de correos 20 minutos antes do esperado. Cantos minutos antes aterrizou o avión?

O tradutor do libro ao inglés, Albert Perry, especialista en ruso da Colgate University, fixo unha curiosa anotación ao seguinte problema:" Non hai árbores de nadal na URRS, oficialmente só os hai de aninovo". En canto ao contido, é un clásico.

Regalos de aninovo. O noso comité executivo do sindicato xestionou unha árbore de aninovo para os nenos. Despois de distribuir caramelos e galletas en paquetes de regalo, comezamos coas laranxas. Pero decatámonos de que se poñemos 10 laranxas por paquete, un paquete só terá 9, se colocamos 9, un paquete só derá 8; se poñemos 8, 7; e así sucesivamente ata dúas laranxas por paquete cun paquete con só 1. Cantas laranxas temos? 

Para entender os comentarios ao seguinte problema cómpre ler antes o enunciado.

Unha suma palindrómica. Este problema aínda non foi resolto. Suma a un enteiro o propio número invertido. Engade á suma o invertido da suma. Continúa ata que a suma sexa un palíndromo (que se le igual de esquerda a dereita que de dereita a esquerda) $$\begin{matrix} 38 & & 139 & & 48017 & & \\ \underline{83} & & \underline{931} & &\underline{71084} & & \\ 121& &1170 & &119101 & & \\ & &\underline{0711} & & \underline{101911 }& & \\ & & 1881 & & 221012 & & \\ & & & & \underline{210122} & & \\ & & & & 431134 & & \\ \end{matrix} $$

Pode que sexan necesarios moitos pasos. (de 89 a 8.813.200.023.188 precísanse 24 pasos). Unha hipótese é que calquera enteiro produce, antes ou despois, un palíndromo. Segundo Kordemsky, un traballador industrial de Riga chamado P. R. Mols, decatouse de que o número 196, despois de setenta e cinco pasos, non produce un palíndromo. Kordemsky pídenos que no canto de continuar a partir do número de 36 díxitos da septuaxésima quinta suma, intentemos refutar ou demostrar a conxectura mediante un razoamento.

Martin Gardner comenta que xa se realizaran daquela miles de sumas a partir do 196 e que non se achara ningún palíndromo. Tamén informa que a conxectura foi demostrada falsa para os números binarios. Sospéitase que hai números que non darán lugar a un palíndromo. A eses números chámaselles números de Lychrel. En concreto 196 é un candidato destacado para ser un número de Lychrel. É curioso que este tipo de números teñan nome, aínda que non se sabe se realmente existe algún.

Problemas chegados desde Moscú.2

Unha explicación de Perelman

Hoxe en día cando escoitamos o apelido Perelman pensamos inmediatamente en Grigori Perelman (1966-), o matemático ruso que resolveu a conxectura de Poincairé. No entanto, hai un par de décadas o usual sería asociar ese apelido con Yákov Perelman (1882-1942), un famoso divulgador da ciencia que morrería no asedio a Leningrado durante a II Guerra Mundial. 

Nun dos seus libros, Aritmética recreativa, explícanos o método ruso para facer produtos. Faino cun exemplo. Se quixermos calcular o produto de $32\cdot13$ procederiamos da seguinte maneira. En cada paso dividimos o factor da esquerda por $2$ e multiplicamos o da dereita por $2$. Así o produto non varía.

$$\begin{matrix} 32\cdot 13 \\16\cdot 26 \\8\cdot 52 \\4\cdot 104 \\2\cdot 208 \\1\cdot 416 \end{matrix}$$

Velaí que o resultado sería $32\cdot13=1\cdot 416=416$. Claro que, calquera ve enseguida o problema. Neste caso $32$ é unha potencia de $2$ polo que podemos dividilo unha e outra vez pola metade. Pero que pasaría se na columna da esquerda temos un número impar? Yákov Peremal tamén explica como proceder neste caso. Cada vez que teñamos un número negativo, restámoslle $1$; agora podemos dividir por $2$ sen problema. En compensación teremos que sumar todos os números da dereita que teñan un impar á súa esquerda. Para facelo máis sistemático e fácil, tachamos todos os produtos que presenten á esquerda un número par. Poñamos que agora queiramos multiplicar $19\cdot17$:

$$\begin{matrix} 19\cdot 17 \\9\cdot 34 \\4\cdot 68 \\2\cdot 136 \\1\cdot 272 \end{matrix}$$

O resultado será $17+34+272=323$. Por que temos que proceder deste xeito? Perelman tamén nolo explica. Resulta que ao restar $1$ estamos eliminando algúns valores, necesarios para obter o produto final. Todo fica claro cando presentamos as seguintes operacións:

$$\begin{matrix}19\cdot17=\left ( 18+1 \right )\cdot17=18\cdot17+17\\ 9\cdot 34=\left ( 8+1 \right )\cdot 34=8\cdot34+34\end{matrix}$$

Ao restar eses uns estamos subtraendo tamén eses restos, $17$ e $34$; esa é a razón de porque debemos sumalos ao final.

Máis problemas de Kordemsky

Na anterior entrada presentárase unha pequena escolma dos Enigmas de Moscú de Boris Kordemsky. Imos seguir tirando dese fío. Algunha das cuestións presentadas por Perelman teñen un sabor moi semellante ás de Kordemsky. En especial a seguinte, da que, sen que serva de precedente, darei tamén a solución.

O volume dunha botella. Se unha botella parcialmente chea de líquido, ten un cu redondo, cadrado ou rectangular, podes saber o seu volume só cunha regra? Non podes engadir sin sacar líquido.

Está claro que o volume total da botella virá dado pola suma do volume que ocupa o líquido xunto co da parte sen el. Creo que non cómpre dicir nada máis. 

O trato pouco reflexivo cun tópico tan básico como o das porcentaxes dá lugar a interpretacións bárbaras. É habitual escoitar, non xa a rapaces, senón a ilustres licenciados, que se aumentamos unha cantidade nun 20% e despois facemos unha rebaixa do 20%, obtemos o valor inicial.

Podes aforrar o 100%? Un invento aforra o 30% do combustible, outro un 45% e un terceiro un 25%. Se usas todos estes inventos a un tempo, podes aforrar o 100% ? En caso contrario, cal é a porcentaxe de aforro?

Nalgúns casos Kordemsky non só presenta un problema senón que fai unha pequena digresión para chamar a atención sobre algúns procesos propios das matemáticas. Continuamos con porcentaxes.

Falsa analoxía. Os descubrimentos científicos fanse a veces mediante analoxía. A analoxía tamén ten lugar nas matemáticas, pero tamén existe a falsa analoxía.

40 é 8 unidades maior que 32. 40 é un 25% maior que 32.

32 é 8 unidades menor que 40. 32 non é un 25% menor que 40. Cal é a porcentaxe correcta?

a) Supón que os teus ingresos mensuais aumentan un 30%. En canto aumenta o teu poder adquisitivo?

b)Supón que os teus ingresos mensuais non cambian. No entanto, os prezos baixan un 30%. En canto aumenta o teu poder adquisitivo?

c)Cando unha tenda de libros de segunda man fai unha rebaixa do 10% do prezo, obtén unha ganancia do 8% por cada libro vendido. Cal era o beneficio antes da rebaixa?

d)Se un obreiro metalúrxico reduce o seu tempo por peza nun p%. Canto aumenta a súa produtividade?

Un deses enunciados que nunca verás nun libro de texto. Trátase de traballar o volume pero non preguntan polo volume. A última pregunta incide nun dos procesos máis importantes dentro das matemáticas, o da xeneralización.

Que caixa pesa máis?. Unha caixa cúbica contén 27 bólas grandes congruentes; a súa xemelga contén 64 bólas congruentes máis pequenas. Todas as bólas están feitas do mesmo material. Ambas caixas están completamente cheas. En cada caixa, cada capa ten o mesmo número de bólas e as bólas exteriores de cada capa tocan os lados da caixa. Que caixa pesa máis? Intenta con outros números, pero que sexan sempre cubos. Escribe unha conclusión xeral.

O seguinte enunciado ten o atractivo de estar redactado como unha pequena lenda. Trata o tema do pacto co demo, algo que, como todos sabemos, nunca debemos facer. É tamén un deses problemas que convén resolver "ao revés"

O folgazán e o demo. Un folgazán expresa a súa ansia por facerse rico e de súpeto aparéceselle o Diabo quen lle di: "Ben, o traballo que teño para ti é fácil, e serás rico. Ves a ponte? Crúzaa e dobrareiche o diñeiro que tes agora mesmo. De feito, cada vez que a cruces volveri a dobrarche os cartos.

"Non pode ser!" contestou o folgazán

"Só hai unha condición. Xa que son tan xeneroso debes darme 24 € despois de cada cruce".

O folgazán acepta. Cruza a ponte e conta os seus cartos... Miragre! Era o dobre.

Dálle 24 € ao Diabo e volve a cruzar outra vez. Dóbrase o seu diñeiro e paga outros 24€, cruza unha terceira vez. O seu diñeiro volve a duplicarse pero agora só ten 24€ e tan que darllos ao Diabo que desaparace entre gargalladas.

Cando un se enfronta a un enunciado cómpre que o entenda moi ben. Iso significa, entre outros aspectos, que debe ter ben asimilados os conceptos e as relacións que se determinan entre os distintos aspectos en xogo. No seguinte problema xira arredor do cálculo dunha media de velocidades de trancrición dun manuscrito. Debemos ter claro que a velocidade mídese a respecto do tempo, non a respecto do número de páxinas, como enganosamente pretende convencernos Vera.

Vera pasa un manuscrito a máquina. Vera recibe da súa nai o encargo de pasar a máquina un manuscrito. Vera indica que fará unha media de 20 páxinas por día.

A primeira metade fainas con pereza, 10 páxinas diarias. Para recuperar o tempo perdido fai a segunda metade a 30 páxinas por día.

"Ves?, fixen unha media de 20 páxinas por día". Conclúe Vera. "A media de 10 e 30 é 20"

"Non, non é certo" di a súa nai.

Quen ten a razón?

Dicimos que estes problemas chegaron de Moscú porque alí os publicou Kordemsky. En realidade son universais. O seguinte problema con pequenas variantes aparece nalgún libro de Adrián Paenza. 

Que tal vas de enxeño?. Unha lancha sae da beira A ao tempo que outra sae da beira B; móvense polo lago a unha velocidade constante. Encóntrase por vez primeira a 500 metros de A. Continúan o seu camiño, dando a volta na beira oposta. Encóntranse por segunda vez a 300 m. de B. Cal é a lonxitude do lago e cal é a relación entre as velocidades das lanchas? 

Na seguinte entrada remataremos esta serie de problemas de Boris Kordemsky.

Problemas chegados desde Moscú.1

O descoñecemento doutras culturas ou doutras linguas empequenece o noso mundo. Hai factores que nos afastan de realidades distintas á nosa. Un deles pode ser o alfabeto. Unha portada dun libro como o da figura 1 pode significa unha barreira insalvable. Hai outros muros aínda máis infranqueables. Durante a Guerra Fría houbo un bloqueo total a todo o que se elaborase alén do telón de aceiro. Así, un libro de matemática recreativa editado no 1954 cun enorme éxito na URSS non foi coñecido no occidente ata 1972, que foi traducido ao inglés e publicado cunha introdución de Martin Gardner. O título orixinal, Математическая смекалка pasou a ser The Moscow Puzzles. 359 Mathematical Recreations. O autor Boris Kordemsky (1907-1999), un profesor de matemáticas moscovita, editaría máis libros do mesmo estilo. Tamén hai unha versión en español; neste caso a editorial Gedisa cortou o texto en dúas partes: Los enigmas de Moscú e Un elefante y un mosquito.

Vou compartir algúns dos problemas de Kordemsky. 

O libro Mate-glifos (Xerais, 2018) dos profesores da Universidade de Vigo Nicanor Alonso e Miguel MIrás, está elaborado arredor dos símbolos matemáticos. Os símbolos son importantes, incluso poden ser o cerne dun problema.

Distintas operacións, mesmo resultado. Dados un par de 2, o símbolo "+" pode cambiarse por "x" sen cambiar o resultado: $ 2+2=2\times 2$. A solución con tres números tamén é sinxela: $ 1+2+3=1\times 2\times 3$. Pídese a resposta para catro números. E para cinco?

A central eléctria de Tsimilyansk está situada no río Don. Rematada no 1954 considérase como un dos grandes proxectos de construción da época comunista.  A imaxe reflicte a súa icona oficial. Esta central aparece como identificador próximo ao posible lector do seguinte enunciado que presenta dunha forma pouco habitual un problema sobre a media.

Para a central eléctrica de Tsimilyansk. Unha fábria de equipos de medición ten un encargo urxente da célebre central eléctrica de Tsimlyansk. A fábrica conta cunha brigada de dez excelentes traballadores: o capataz (un home maior con experiencia) e 9 xoves diplomados de formación profesional.

Cada un dos 9 xoves traballadores produce 15 pezas de medición ao día mentres que o seu xefe fai 9 máis que a media dos dez traballadores. Cantos instrumentos de medición produce a brigada diariamente?

A primeira vez que lin o problema, fíxeno a todo correr e, en consecuencia lino mal. Unha vez visto o primeiro parágrafo pensei que preguntaría cal é a suma dos primeiros mil millóns de números. Non é esa a pregunta.

De 1 a 1.000.000.000. Cando o acreditado matemático alemán Karl Friederich Gauss(1777-1855) tiña nove anos, pedíronlle que sumara todos os números enteiros do 1 a 100. Sumou rapidamente o 1 co 100, o 2 co 99, e así sucesivamente ata un total de 50 pares de números, todos eles de suma 101. A resposta foi $50\times 101=5050$.

Agora acha a suma de todos os díxitos dos números enteiros de 1 a 1.000.000.000. Isto quere dicir todos os díxitos en todos os números, non a suma de todos os números por si mesmos.

Eu teño unha certa aversións aos deportes e especialmente, polo que representa, ao fútbol. Velaí que, nun principio, non sería do meu gusto un problema enmarcado neste tema. O que si me pareceu moi curiosa foi a forma de presentar o problema, é realmente estraña, mediante unha conversión kafkiana. No libro non vén a imaxe, nin  tampouco se aclara que o que se debe establecer é a relación que debe haber entre os raios das dúas pelotas.

O pesadelo dun afeccionado ao fútbol. A un afeccionado ao fútbol, triste pola derrota do seu equipo, cústalle durmir. No soño, un porteiro practica nunha gran habitación amoblada, lanzando unha pelota contra a parede e despois atrapándoa coas mans. Pero o porteiro cada vez faise máis pequeno e despois transfórmase nunha pelota de pimpón mentres que a pelota de fútbol se incha ata converterse nunha gran bóla de ferro forxado. A bóla de ferro xira violentamente intentando aplastar a pelota de pimpón que se move por todas partes desesperadamente. Pode a pelota de pimpón encontrar un lugar seguro sen separarse do chan?

Dúas pelotas

O seguinte é un problema simple e curioso. Todo un reto para un alumno de 1º da ESO. Un exemplo de como as matemáticas en si mesmas son interesantes. Non precisamos buscar enunciados trapalleiros que introduzan a vida cotiá con calzador e sen xeito.

Fraccións interesantes. Se ao numerador e ao denominador da fracción $1/3$ lles sumamos o seu denominador, $3$, a fracción duplícase.

Acha unha fracción que sexa o triplo cando o seu denominador se sume ao seu numerador e ao seu denominador; acha outra que sexa o cuádruplo.

De seguido unha desas cuestións aritméticas sobre velocidades que dan moito xogo. Claro que non se trata do típico problema de que un tren parte de A a 90 km/h....

Aforraríase tempo? Ostap volve a casa desde Kiiv. Fixo en bici a metade do camiño quince veces máis rápido que a pé. A segunda metade montou nun carro de bois. Camiñando pode ir o dobre de rápido. Aforraríase tempo se fixera todo o camiño a pé? Canto tempo?

Un enunciado distinto ao anterior, pero os fundamentos son os mesmos:

O sarxento propón un problema. O sarxento Semochkin propón o seguinte problema aos soldados exploradores. Digamos que dous de vós cubrides a mesma distancia. O primeiro corre a metade do tempo e camiña a outra. O segundo corre a metade do percorrido e camiña o resto. Ningún dos dous camiña ou corre máis rápido que o outro. Se primeiro camiñan e despois corren, quen chega primeiro?

Na seguinte entrada continuaremos con algunha outra achega deste moscovita.

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.