Cinco problemas equivalentes al de Fibonacci

Voy a plantear en este post cinco problemas de combinatoria que son equivalentes al problema de los conejos de Fibonacci, en el sentido de que dan lugar a la misma sucesión (y a la misma recurrencia). La solución de cada uno de ellos se detiene en el modelo, es decir, en el razonamiento por recurrencia que conduce a plantearlo. 

1. Subconjuntos sin consecutivos

¿De cuántas formas se puede elegir un subconjunto de {1,2,…,n} de manera que no contenga números consecutivos?

Solución
Sea un el número de subconjuntos de {1,2,….n} sin números consecutivos. Cada subconjunto aceptable según la restricción, ya sea que contiene el 1 o bien no lo contiene.

Si contiene el 1 entonces no puede contener el 2 y se ve que el número de subconjuntos que contienen el 1 es un−2 --pues es el número de subconjuntos de {3,4,…,n}.

Por otro lado, si el subconjunto no contiene el 1, entonces el número de subconjuntos de esta clase son un−1 --dado que es el número de subconjuntos de {2,3,…,n}.

En resumen, un=un−1+un−2. (Claramente, u1=1,u2=2 --se deja como ejercicio su justificación.)

2. n-Cadenas binarias con dos ceros consecutivos

¿De cuántas formas se puede construir una n-cadena de ceros y unos con dos ceros consecutivos?

Solución
Sea un el número de cadenas binarias de longitud n con dos ceros
consecutivos. Claramente, una cadena de longitud 1 no puede tener dos ceros consecutivos, y solamente hay una de longitud dos con dos ceros consecutivos. Es decir, u1=0,u2=1.

Consideremos ahora el caso general. Cada cadena de longitud n con dos ceros consecutivos es de una de tres clases: empieza con 00 o con 01 o con 1.

Si empieza con 00, el resto de la cadena es una cadena de longitud n−2 sin restricción.

Por otro lado, si empieza con 01, el resto de la cadena es una cadena de longitud n−2 con dos ceros consecutivos.

Finalmente, si empieza con 1, el resto de la cadena es una cadena de longitud n−1 con dos ceros consecutivos.

En resumen, el modelo recursivo para este problema es:

un=2n−2+un−2+un−1

con u1=0,u2=1

3. Sus dígitos son 1 y/o 2 y suman n

¿Cuántos números con 1 y 2 como dígitos son tales que éstos suman n? Ejemplo: 111, 12, 21 son los tres números que cumplen para n=3.

Solución
Sea un el número de números que cumplen para n. Claramente, u1=1,u2=2. En el caso de n mayor que 2, se puede razonar recursivamente como sigue:
Los números que cumplen se pueden clasificar en dos clases excluyentes y exhaustivas. Los que empiezan con 1 y los que empiezan con 2.
Si empiezan con 1, son un−1 --pues el problema se reduce a contar los números con 1 y 2 como dígitos y tales que éstos suman n−1.
Si empiezan con 2, son Un−2 --siguiendo un razonamiento similar. Por tanto un=un−1+un−2.
Otra forma: Considerando el último dígito, éste puede ser 1 o bien 2. Los números que terminan en 2 son un−2 y los que terminan en 1 son un−2

4. n-Cadenas binarias sin unos consecutivos

¿De cuantas formas se puede formar una cadena de ceros y unos de longitud n sin unos consecutivos?

Solución
Los números ya sea que inician con cero o bien con uno. Los que empiezan con cero son un−1 y los que empiezan con uno son un−2 --porque en realidad deben empezar con 10. Por tanto, un=un−1+un−2.

5. Tiempo de espera hasta dos águilas consecutivas

En una secuencia de n volados ¿cuántos resultados no tienen dos águilas consecutivas, excepto al final?

Solución
Sea un el número buscado. Los resultados, ya sea inician con águila (A) o bien con sello (S). Si inician con águila son un−2; si con sello, son un−1. Por tanto, un=un−1+un−2

Tomado de:

Mate Mat

Teorema de la altura: una prueba visual

En nuestra sociedad globalizada, en la que el espectáculo y la diversión han sido puestos en el centro por los mass media, es muy difícil ser profesor, de cualquier cosa, pero sobre todo de matemáticas. ¿Tiene que ser convertida el aula  en un reality show para atraer la atención de nuestros estudiantes?

Con demasiada frecuencia sigo escuchando el argumento de que las matemáticas son difíciles porque el profesor no sabe enseñarlas. Y el argumento se refuerza con anécdotas de la vida escolar adolescente. Puedo leer entre líneas --es decir, puedo "maliciar" en ese argumento-- la hipótesis oculta de que el profesor no sabe armar un espectáculo con su tema a enseñar. Mínimo, que hay una forma correcta (la cual puede depender del opinante) de enseñar las matemáticas mientras todas las demás están equivocadas. Permítaseme documentar la idea con un relato.

¿Por qué nadie me lo había explicado así?

Recientemente un profesor (de sociología) me comentaba muy entusiasmado que "ahora sí había entendido el binomio al cuadrado". Según le entendí, había asistido a una conferencia sobre educación matemática y el expositor había planteado el binomio al cuadrado de manera diagramática (o visual). Según su explicación, la visualidad que tanto impactó a mi amigo habría sido ésta:

Yo le comenté que esa manera de ilustrar el binomio al cuadrado está desde hace ya tiempo en los libros de secundaria y que no entendía qué era lo extraordinario de ello. El sociólogo replicó que si así le hubieran enseñado a él, posiblemente habría elegido estudiar la licenciatura en matemáticas, bla, bla , bla. La conversación continuó un poco más, pero ante el entusiasmo de mi sociólogo desistí de indagar el motivo de su entusiasmo.

Pues es muy difícil bajar a un estusiasta de su nube. Lo que pude inferir de su conversación es que, por alguna razón, se conectó al tema de la conferencia como nunca antes lo había hecho y tuvo una revelación... Aparte está el hecho de que el binomio al cuadrado requiere un mínimo de conocimientos previos para su comprensión --en contraste con otros productos notables como la factorización por las fórmulas de Vieta.

Por otro lado, las pruebas visuales están orientadas a atraer la atención del aprendiz --lo cual está cañón, pues una prueba visual es incomparablemente menos atractiva que el espectáculo montado por un videojuego. Además de que su utilidad didáctica de largo plazo es cuestionable --pues, en el caso de los productos notables, lo que verdaderamente estaría en juego ahí es la regla distributiva... Quiero decir, la prueba visual es atractiva y cumple una función didáctica pero...

Teorema de la altura y su contexto

Un poco como el profesor de sociología del relato --y a pesar de las contraindicaciones de las pruebas visuales-- voy a compartir con los lectores de MaTeTaM una prueba visual del teorema de la altura que logró entusiasmarme (aunque quizá por razones diferentes a las de mi sociólogo). Tiene la desventaja de que no es para todo público (como la del binomio al cuadrado). Pues hay que saber dos o tres cosas de semejanza de triángulos rectángulos.

La configuración geométrica para el teorema de la altura es un triángulo ABC, rectángulo en A, con h la altura relativa a la hipotenusa y p y q los segmentos en que aquélla divide a ésta. En otras palabras, si llamamos D al pie de la altura, entonces h=AD,p=BD,q=DC

Es fácil ver --por complementariedad-- que los triángulos CDA y ADB son semejantes. De aquí que sus lados sean proporcionales. Es decir 

BDDA=ADDC

O bien, sustituyendo las longitudes de los segmentos,

ph=hq

Este teorema se acostumbra formular como

h2=pq

Y se enuncia así:

En un triángulo rectángulo, la altura asociada a la hipotenusa es media geométrica de los segmentos en que la hipotenusa queda dividida por la altura.

Importancia didáctica del teorema de la altura

A pesar de que es elemental y su demostración es consecuencia directa de una evidente semejanza de triángulos, este teorema es importante porque permite al aprendiz ejercitar su comprensión de la semejanza de triángulos. Y aprovechando su cercanía con el teorema del cateto, se puede armar una secuencia didáctica que culmine en la demostración clásica más elemental del teorema de Pitágoras. Enseguida las demostraciones del teorema del cateto y el de Pitágoras.

Según la notación usual, el cateto opuesto al vértice B se denota con b y el opuesto al vértice C con c. Entonces, con referencia a la figura anterior, el teorema del cateto diría: b2=qa,c2=pa. Sumando ambas ecuaciones se obtiene Pitágoras.

La prueba visual

Con referencia de nuevo a la figura anterior, imaginemos que recortamos el triángulo ABC sobre su altura AD y que separamos los triángulos CDA y ADB --los cuales son semejantes, como se dijo arriba. Entonces, si giramos el triángulo ADB 90 grados sobre A, obtenemos una configuración como la siguiente.

Y si intercambiamos las posiciones de los dos triángulos se obtiene la siguiente configuración:

 

Y si tomamos una copia del triángulo CDA, ambas configuraciones se combinan en la siguiente:

La prueba visual consiste en observar que los triángulos BCS y A′AT son rectángulos y congruentes y, en consecuencia, tienen la misma área. Así que si a cada uno de ellos le quitamos los dos triángulos cortados del original, las áreas que quedan son iguales. Es decir, h2=pq.

Tomado de:

MateTam