Xa teño comentado por acó que un momento importante da miña formación tivo lugar cando na biblioteca da Facultade de Matemáticas da USC permitiron ao alumnado acceder aá totalidade do fondo, antes diso só se podía acceder a unha sala cos típicos libros para undergraduates. Agora isto ten que soar ridículo, daquela xa soaba a pouco que reparases, o que ocorría era que moitos estudantes nin eran conscientes da existencia da zona vedada. Para que vexades a magnitude do absurdo no que vivía aquela biblioteca de facultade, eu atopara no catálogo Diophantine Equations, de L.J. Mordell, e ninguén sabía onde estaba.
Como xa comentei, alén da magnitude do fondo bibliográfico, unha das primeiras sorpresas que levei foi o descubrimento da categoría 05-Combinatoria(aínda que na que máis estiven pescudando foi a 11-Teoría de Números). Na miña cabeza, a combinatoria non era máis que aquela parte das Matemáticas que dera na 2ª avaliación de 1º de BUP xusto antes da probabilidade, e que tiña como obxecto resolver problemas nos que o reconto directo dos casos posibles e favorables non era factible. E que volvera aparecer como special guest star no pouco de variables aleatorias que estudamos ao final de COU(=Binomial e Normal). Polo que ver unha categoría enteira dedicada a esa materia, a priori anódina, provocou que pasase un tempo mirando naqueles libros. E atopei cousas que me soaban daquela, como os grafos, e outras que non, como as matroides ou a fermosísima teoría de Ramsey.
Confeso que a combinatoria do instituto fora un tema que me gustara e que se me dera ben; como sempre, é complicado discernir en que sentido funciona a relación entre motivación e desempeño. E tamén confeso que non cheguei a entender a idea crucial por embaixo de toda a materia que dera ata moitos anos despois, lendo algún libro de resolución de problemas.
Comecemos por un chisco de choio de libro de texto, o cálculo efectivo de $\binom{n}{k}$, i.e., o cómputo do coeficiente combinatorio, a partir de operacións elementais, traballadas previamente na aula. E que é $\binom{n}{k}$ ? É o símbolo que denota o número de xeitos de escoller k elementos dentro dun conxunto de n elementos, cuxo nome tradicional é "combinacións de n elementos tomados de k en k". Collamos un caso sinxelo, o conxunto con 5 elementos {a,b,c,d,e} do que imos coller subconxuntos de 3 elementos, i.e., $\binom{5}{3}$. Moi grande non é :
{a,b,c},{a,b,d},{a,b,e},{a,c,d},{a,c,e},{a,d,e},{b,c,d},{b,c,e}{b,d,e}{c,d,e}
Vemos arriba que $\binom{5}{3}=10$. A explicación xenérica das combinacións funciona deste xeito:
Calculamos cantos xeitos hai de asignar as 3 medallas no conxunto de 5 elementos, o que se coñece tradicionalmente como "variacións de 5 elementos collidos de 3 en 3", e denotamos $V_{5}^3$, e que só require entender a regra do produto:
Hai 5 opcións para asignar a medalla de ouro, para cada unha desas, hai 4 opcións para a medalla de prata, e finalmente hai 3 para a medalla de bronce, polo que $V_{5}^3$=5 cdot 4 cdot 3=60
Pero para chegar as combinacións hai que ter en conta que as variacións abc, acb, bac, bca, cab e cba corresponden á mesma combinación, {a,b,c} (en linguaxe de 1º de BUP, "a orde non importa nas combinacións"), polo que:
$\binom{5}{3}=\frac{V_{5}^3}{3!}=\frac{5 \cdot 4 \cdot 3}{3!}=\frac{5!}{2! \cdot 3!}$
O razoamento xeral troca 5 e 3 por n e k:
$\binom{n}{k}=\frac{V_{n}^k}{k!}=\frac{n \cdot (n-1) \dots (n-k+1)}{k!}=\frac{n!}{(n-k)! \cdot k!}$
Isto é o que nos explicaron en 1º de BUP a todos, máis ou menos, e tamén actualmente nas Matemáticas Académicas de 4º de ESO(os afortunados que chegan).
Daquela(e agora tamén) había alumnos que aos 14 anos aínda non tiñan asimilada a regra do produto, na que se sostén toda esta estrutura de enumeración, e que vén culminar o pensamento multiplicativo desenvolvido durante a educación primaria. Por isto era pouco probable que un alumno chegase a albiscar a idea esencial: contar maneiras de agrupar elementos de xeito indirecto, mediante outros agrupamentos máis inmediatos, ou ben, atopar un número contando de dous xeitos distintos na mesma situación. Esta é unha das dúas posibles definicións de "demostración combinatoria"; a outra é unha proba que se fai atopando unha bixección entre dous conxuntos para amosar que teñen o mesmo cardinal(un dos recordos máis lisérxicos que gardo da carreira foi o día que en Álxebra non conmutativa unha demostración comezaba por amosar que certo ente matemático que non lembro estaba en bixección cun conxunto, co obxectivo de amosar que ese ente misterioso era efectivamente un conxunto)
Vexamos uns casos elementais que no instituto se adoitaban demostrar de xeito puramente alxébrico, a partir da expresión das combinacións atopada arriba.
Comecemos por un chisco de choio de libro de texto, o cálculo efectivo de $\binom{n}{k}$, i.e., o cómputo do coeficiente combinatorio, a partir de operacións elementais, traballadas previamente na aula. E que é $\binom{n}{k}$ ? É o símbolo que denota o número de xeitos de escoller k elementos dentro dun conxunto de n elementos, cuxo nome tradicional é "combinacións de n elementos tomados de k en k". Collamos un caso sinxelo, o conxunto con 5 elementos {a,b,c,d,e} do que imos coller subconxuntos de 3 elementos, i.e., $\binom{5}{3}$. Moi grande non é :
{a,b,c},{a,b,d},{a,b,e},{a,c,d},{a,c,e},{a,d,e},{b,c,d},{b,c,e}{b,d,e}{c,d,e}
Vemos arriba que $\binom{5}{3}=10$. A explicación xenérica das combinacións funciona deste xeito:
Calculamos cantos xeitos hai de asignar as 3 medallas no conxunto de 5 elementos, o que se coñece tradicionalmente como "variacións de 5 elementos collidos de 3 en 3", e denotamos $V_{5}^3$, e que só require entender a regra do produto:
Hai 5 opcións para asignar a medalla de ouro, para cada unha desas, hai 4 opcións para a medalla de prata, e finalmente hai 3 para a medalla de bronce, polo que $V_{5}^3$=5 cdot 4 cdot 3=60
Pero para chegar as combinacións hai que ter en conta que as variacións abc, acb, bac, bca, cab e cba corresponden á mesma combinación, {a,b,c} (en linguaxe de 1º de BUP, "a orde non importa nas combinacións"), polo que:
$\binom{5}{3}=\frac{V_{5}^3}{3!}=\frac{5 \cdot 4 \cdot 3}{3!}=\frac{5!}{2! \cdot 3!}$
O razoamento xeral troca 5 e 3 por n e k:
$\binom{n}{k}=\frac{V_{n}^k}{k!}=\frac{n \cdot (n-1) \dots (n-k+1)}{k!}=\frac{n!}{(n-k)! \cdot k!}$
Isto é o que nos explicaron en 1º de BUP a todos, máis ou menos, e tamén actualmente nas Matemáticas Académicas de 4º de ESO(os afortunados que chegan).
Daquela(e agora tamén) había alumnos que aos 14 anos aínda non tiñan asimilada a regra do produto, na que se sostén toda esta estrutura de enumeración, e que vén culminar o pensamento multiplicativo desenvolvido durante a educación primaria. Por isto era pouco probable que un alumno chegase a albiscar a idea esencial: contar maneiras de agrupar elementos de xeito indirecto, mediante outros agrupamentos máis inmediatos, ou ben, atopar un número contando de dous xeitos distintos na mesma situación. Esta é unha das dúas posibles definicións de "demostración combinatoria"; a outra é unha proba que se fai atopando unha bixección entre dous conxuntos para amosar que teñen o mesmo cardinal(un dos recordos máis lisérxicos que gardo da carreira foi o día que en Álxebra non conmutativa unha demostración comezaba por amosar que certo ente matemático que non lembro estaba en bixección cun conxunto, co obxectivo de amosar que ese ente misterioso era efectivamente un conxunto)
Vexamos uns casos elementais que no instituto se adoitaban demostrar de xeito puramente alxébrico, a partir da expresión das combinacións atopada arriba.
- Demostrar que $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$
O lector observará aí a condición de recorrencia que define o Triángulo de Pascal, e unha das primeiras identidades que se demostraban nos libros de texto de 1º de BUP. Que representa o número combinatorio do membro da esquerda? O número de xeitos de escoller k persoas dun conxunto de n persoas. E a suma de números combinatorios do membro da dereita? Collamos a 1ª das persoas das n. Poden pasar dúas cousas: que estea na selección de k persoas ou que non estea. No 1º caso hai $\binom{n-1}{k-1}$ xeitos de completar a selección das k persoas(pois el xa está); no 2º caso hai $\binom{n-1}{k}$ xeitos, pois están aínda os k postos vacantes. Sinxelo, non si? Na miña opinión, ademais é fermoso.
- Demostrar que $k \binom{n}{k}=n\binom{n-1}{k-1}$
Tradicionalmente esta identidade ilústrase do seguinte xeito: cantas maneiras hai de escoller un comité formado por k persoas, das cales unha actúa como presidenta, dentro dun conxunto de n persoas? O camiño obvio está no membro da esquerda, temos $\binom{n}{k}$ de escoller o comité de k persoas, e logo hai k opcións para o presidente. O membro da dereita pode interpretarse así: escollemos primeiro o presidente, que pode ser calquera das n persoas, e despois completamos o comité con k-1 persoas do resto de n-1 persoas do conxunto.
- A identidade anterior é o primeiro caso dunha identidade máis xeral, $\binom{n}{k} \binom{k}{l}=\binom{n}{l} \binom{n-l}{k-l}$, que Martin Erickson chama "identidade do subcomité", e que se deixa como exercicio ao amable lector.
- Achar unha fórmula para a o número de subconxuntos dun conxunto de cardinal n.
Para isto hai varios ataques posibles. Por unha banda hai $\binom{n}{0}$ subconxuntos con 0 elementos, $\binom{n}{1}$ subconxuntos cun elemento,... , $\binom{n}{n-1}$ subconxuntos con n-1 elementos, e $\binom{n}{n}$ subconxuntos con n elementos. Por outro, cada un dos n elementos do conxunto ten dúas opcións en cada subconxunto: pertencer ou non pertencer. Por tanto haberá $2 \cdot 2 \cdot \dots 2=2^n$ subconxuntos. Acabamos de demostrar que $\sum_{k=1}^{n} {\binom{n}{k}}=2^n$, identidade ben fermosa que se deduce automaticamente do binomio de Newton collendo x=1=y
- Atopar o valor de $\sum_{k=1}^{n}{k \binom{n}{k}}$
Observamos que a sucesión que sumamos é a que apareceu hai tres puntos, o cal dá unha pauta. Dun conxunto con n persoas, facemos comités con k persoas, unha delas facendo de presidenta, variando k desde 1 ata n. Pensemos agora en facer eses comités con presidente doutro xeito: temos n xeitos de escoller o presidente, e logo temos que completar os comités co resto de participantes, desde o caso extremo no que o presidente está só ata o extremo no que o comité é todo o conxunto(isto lémbrame que cando eu tiña ~7 anos, estaba nunha banda no colexio con 6 membros, denominados sucesivamente 1º xefe, 2º xefe, ... ata chegar ao moi digno 6º xefe); e hai $2^{n-1}$ maneiras de escoller eses "restos de comités", pois non son máis que os subconxuntos dun conxunto con n-1 elementos, tal e como vimos no apartado previo.
Por hoxe xa está ben de tolear contando, mais non quería rematar este voo sobre estes feitos básicos sen apuntar unha demostración fermosísima, que non entra exactamente na categoría de demostración combinatoria, xoga con estas mesmas ideas(e que xa apareceu por acó hai 6 anos):
- $$\sum_{k=0}^{n-1} {2^k}=1+2^1+2^2+2^3+ \dots + 2^{n-1}=2^n-1 $$
A suma do membro da esquerda non é máis que a suma dos números que se escriben con n bits $0 \dots 1$, $0 \dots 01$, ..., $01 \dots 0$, $1 \dots 0$, suma que vale $11 \dots 11$. Que sucede se sumamos 1 a este número? Pois que obtemos o número $10 \dots 0$(n+1 bits), i.e., $2^n$
Simplemente amosando as ideas básicas das demostracións combinatorias coido que xa temos abondo por hoxe. Emprázovos a unha eventual entrada futura na que aparezan máis demostracións e tamén menos elementais.
0 comentarios:
Publicar un comentario