Tema

Final 18-02-05, Ej 1 y 2

3 respuestas 5273 visitas 2009-08-14

#1 FJL 2009-08-14 01:23

Probar que

\sum_{k=1}^{n} \binom{k+3}{3} = \binom{n+4}{n}-1

Para todo $n \in \mathbb{N}$.

Primero probemos el caso base, P(1).

\sum_{k=1}^1 \binom{k+3}{3} = \binom{5}{1} - 1

\binom{4}{3} = 5 - 1

$$4 = 4$$

Entonces es cierto para el primer natural.

Ahora probemos por inducción. Sabiendo que $\sum_{k=1}^{n} \binom{k+3}{3} = \binom{n+4}{n}-1$, queremos probar que $\sum_{k=1}^{n+1} \binom{k+3}{3} = \binom{n+5}{n+1}-1$

Una vez mas, partimos de lo que queremos probar, y mediante una serie de si-y-solo-si's, llegamos a una expresión verdadera.

\sum_{k=1}^{n+1} \binom{k+3}{3} = \binom{n+4}{3} + \sum_{k=1}^{n} \binom{k+3}{3} = \binom{n+5}{n+1} - 1

{\textrm{H.I.}\atop \iff} \binom{n+4}{n}-1+\binom{n+4}{3} = \binom{n+5}{n+1} - 1

\iff \binom{n+4}{n} + \binom{n+4}{3} = \binom{n+4}{n} + \binom{n+4}{n+1}

\iff \binom{n+4}{3} = \binom{n+4}{n+1}

\iff \frac{(n+4)!}{3!(n+4-3)!} = \frac{(n+4)!}{(n+1)!(n+4-n-1)!}

\iff \frac{(n+4)!}{3!(n+1)!} = \frac{(n+4)!}{3!(n+1)!}

Y listo.

PD: En la línea 3 estoy usando que $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.

Agrego el ej. 2 ya que estamos.

Determinar el número de boletos capicúas de 7 dígitos que contienen por lo menos dos 8's.

Esto es lo mismo que hacer la pregunta con exactamente 2 8's, exactamente 3 8's, ..., exactamente 7 8's. Cada boleto se identifica con la 7-upla $\{\varphi(1), \varphi(2), \varphi(3), \varphi(4), \varphi(3), \varphi(2), \varphi(1)\}$.

Para hacer un número par de 8's, pongo un 8 en alguna de las casillas de la izquierda, y dejo las demas, incluida la del centro, con algo que no sea un ocho (osea 9 posibles digitos). Cuando pongo k 8's, me quedan 4 - k lugares donde no poner 8's. Entonces las formas de obtener los números pares de 8 es $\sum_{k=1}^{3} \binom{3}{k} \cdot 9^{4-k}$.
Para hacer un número impar de 8's, pongo un ocho en el centro, y uno o mas 8's en alguna de las primeras 3. Lleno el resto con cualquier cosa que no sea un 8. Cuando pongo k 8's, me quedan 3-k lugares donde poner 8's. Entonces el número de impares es $\sum_{k=1}^{3} \binom{3}{k} \cdot 9^{3-k}$. El último miembro de este conjunto es el boleto 8888888.

Entonces la solución es $\sum_{k=1}^{3} \binom{3}{k} \cdot 9^{4-k} + \sum_{k=1}^{3} \binom{3}{k} \cdot 9^{3-k}$.

Firma

Por qué los poetas usan integrales?
Porque Riemann.

#2 Erizo 2009-11-20 02:14

A mi pal dos se me ocurrió una forma creo que más fácil, la dejo a ver si alguien le sirve.
$$"total de boletos capic\'uas de 7 d\'igitos: 9.10.10.10 tomo 9 elecciones en el primer lugar (no puede ser 0 pues el n\'umero tendr\'ia 6 d\'igitos), 10 para el segundo, 10 para el tercero y 10 para el cuarto, a partir de ah\'i, necesariamente se tienen que repetir as\'i que la elecci\'on es \'unica.$

$$$Ahora me tengo que sacar de encima los que tienen 1 solo 8 y los que no tienen 8. Estos son:$$

$$$Con 0 ochos: 8.9.9.9 El primero no puede ser ni 8 ni 0, y el resto no puede ser 8$$

$Con ex\'actamente 1 ocho: 8.9.9.1. El 8 s\'olo puede estar en el medio, si no, habr\'ia dos lugares con 8

$Lo que estamos buscando es: "Total de casos" - "Casos con exactamente un ocho" - "casos con exactamente 0 ochos" = "casos con m\'as de 1 ocho". En conclusi\'on

$9.10^3 - 8.9^2 - 8.9^3= 2520$

me dio distinto a fjl... a donde le habré pifiado???? :S

Firma

#3 Costa 2010-02-09 19:06

Yo lo hice contando todos los casos menos los que no tienen ningun 8 y menos los que tienen un solo 8, de la forma que hizo erizo, pero tiene que ser 7 digitos (no cifras), el 0 puedo estar primero, contando esos casos me dio 2710 como a FJL.

#4 Rush 2012-07-29 18:57

Un detalle para el 1 que ahorra desarrollar el combinatorio:

\binom{n+4}{3} = \binom{n+4}{n+4-3} = \binom{n+4}{n+1}

usando que $\binom{n}{k} = \binom{n}{n-k}$