Final 22/02/2013

Acá dejo el final que pusieron en la pagina, el que tomaron el viernes pasado.

Solo pensé el primero. El segundo no entiendo a donde apunta la sugerencia.
Los demás todavía no los agarré. Cualquier aporte viene bien, gracias!

Ejercicio 1:

Un mazo de 50 cartas españolas, posee 10 cartas especiales que son los 8 y 9
de cada palo, mas los dos comodines. Ademas de estas 10 cartas especiales,
vienen las 40 cartas cl´asicas. Un f´abrica de cartas decide empaquetar
sus cartas poniendo las 40 cartas comunes ordenadas por n´umero y palo
(viniendo primero los oros, luego las copas, luego las espadas y por ´ultimo
los bastos) y colocando las otras 10 cartas especiales en cualquier orden,
intercaladas entre las 40 cartas comunes. ¿De cu´antas maneras puede
venir el mazo?

Se me ocurre que podemos pensarlo como primero ver de cuantas maneras se pueden intercalar las 10 cartas entre las otras 40 que "ya estan ubicadas". Se puede pensar entonces como una distribucion de barras y cruces donde las barras son las 40 cartas del maso(recordar que es 40 + 10 - 1 = 49), y las cruces serian las 10 que nos quedan. Una vez que tenemos todas las distribuciones posibles, nos quedaria la permutacion pues podemos ordenar esas 10 cartas de cualquier manera, entonces multiplicamos por 10! y listo.
Aclaracion: interpreto el ejercicio como que uno puede intercalar las cartas de cualquier manera, es decir, puede pasar que pongamos las 10 cartas al principio, las 10 al final, o 5 entre carta y carta, o como sea. No se si habra que interpretarlo como 1 carta especial, 1 carta del maso, 1 carta especial, 1 del maso.. etc..

EDIT: Supongamos que intercaladas se refiere a que puede haber a lo sumo 1 carta especial entre 2 comunes. Y supongamos que ademas, puede haber una carta especial adelante de todo, y otra atras de todo del maso. Entonces el problema se reduce a que nos dieron un maso de 40 cartas, ya ordenado y armado, y nos dijeron "pone estas 10 cartas, sin poner mas de una entre 2 normales" entonces por cada carta normal, tenemos que elegir si "poner una carta especial adelante, o no poner una carta especial adelante".

Luego, la idea quedaria en que tenemos 41 lugares (porque podemos poner una carta atras de todo) para ubicar 10 cartas.
Para la primer carta especial tenemos 41 lugares, para la segunda 40, para la tercera 39.. etc.. nos quedaria el numero 41.39.38...31

Ejercicio 2:

El objetivo de este ejercicio es demostrar el resultado conocido de la conmutatividad
del producto de n´umeros naturales (con lo cual no se puede
usar esta propiedad). Para ello definimos una funci´on p : N×N → N dada
por:

Probar que para todo par de naturales m,n vale que:

Sugerencia: hacer induccion en \(max(n,m)\)

Pido ayuda en este pues realmente no capto la sugerencia. A donde apunta con el max(n,m) ?

Ejercicio 3:

(a) Encontrar un numero primo p y un numero primo q, tales que la ecuacion \(x^{2} + 1 \equiv 0 (\ mod \ p)\) sea resoluble pero la ecucacion \(x^{2} + 1 \equiv 0 (\ mod \ q)\) no tenga soluciòn.

(b) Encontrar un numero natural m que sea producto de 3 primos, y ademas la ecuacion \(x^{2} +1 \equiv 0 \ (mod \ m)\) tenga exactamente 4 soluciones modulo m.

(c) Encontrar un numero natural m que sea producto de 3 primos, y ademas la ecuacion \(x^{2} +1 \equiv 0 \ (mod \ m)\) tenga exactamente 8 soluciones modulo m.

Para el inciso (a) podemos tomar p = 5, q = 3.
Tendriamos entonces \(x^{2} + 1 \equiv 0 \ (mod \ 5)\) y \(x^{2} + 1 \equiv 0 \ (mod\ 3)\)
x=2 es solucion de la primer ecuacion. Veamos que la segunda no tiene solucion.
Como 3 es primo, y claramente 3 no divide a X, entonces vale el teorema de fermat, y luego \(x^{2} \equiv 1 \ (mod \ 3)\) Y esto vale para todo x tal que 3 no divide a x. Si 3 divide a X, luego \(x^{2} \equiv 0 \ (mod 3)\)

Para el (b): Tenemos que m es producto de 3 primos, digamos \(m = p.q.k\). Y tenemos que \(m | x^{2} + 1 \Leftrightarrow \ p.q.k | x^{2} + 1 \Leftrightarrow p | x^{2} + 1 \land \ q | x^{2} + 1 \ \land \ k | x^{2} + 1\)

Nos quedan entonces 3 ecuaciones de congruencia:

Ahora, depende el p,q, y k que tomemos, de la cantidad de soluciones que tengamos. Por ejemplo, si tomamos p = 5, entonces \(x^{2} \equiv 4 \ (mod \ 5)\) tiene como soluciones \(x \equiv 2 \ (5) \land \ x \equiv 3 \ (5)\) (se ve con la tabla de restos).
Como queremos exactamente 4 soluciones, lo que necesitamos es que 2 de nuestras ecuaciones tengan 2 soluciones exactamente, y la otra una sola. Por ejemplo, tomando p = 5, q= 2 y k = 13, nos quedaria

y podemos descomponer en

Luego, para cada combinacion de esas ecuaciones (que son 4 combinaciones) existe una unica solucion mod (5 . 13 . 2) por el teorema chino del resto.

Para el (c) es analogo, pero en vez de usar el q= 2 que tiene solo una solucion, usan otro primo, cuya ecuacion \(x^{2} \equiv q-1 \ (mod \ q)\) tenga dos soluciones.

Ejercicio 4:

Consideremos un polinomio cubico \(q(x) = x^{3} + ax^{2} + bx + c. \ donde \ a,b,c \in C,\) y supongamos que q(x) tenga al menos dos raices racionales.

(a) Probar que si \(a \in Q \ entonces \ q\in Q(x) \ y \ todas \ sus \ raices \ son \ racionales.\)
(b) ¿Es cierto que si \(c \in Q \ entonces \ q\in Q(x)\) \ y \ todas \ sus \ raices \ son \ racionales? (dar una demostracion o un contraejemplo)

(c)¿Es cierto que si\(b \in Q \ entonces \ q \in Q[x]\) y todas sus raices son
racionales? (dar una demostraci´on o un contraejemplo).

Para el (a) :
Si tomamos la relacion entre coeficientes y raices, y digamos que \(\alpha , \beta , \gamma \ son \ raices \ de \ q\)
entonces :

y sabemos que \(a = - (\alpha + \beta + \gamma) \in Q\) y ademas sabemos que dos raices son racionales, digamos \(\alpha , \beta \in Q\) Luego, sea \(\alpha + \beta = \delta \in Q \ entonces \ \delta + \gamma \in Q \Leftrightarrow \gamma \in Q\) pues la suma es cerrada en los racionales, por leyes de composicion interna. Entonces llegamos a que sus tres raices son racionales. Como el producto y la suma de racionales cae en los racionales, tenemos que todos sus coeficientes escritos segun su relacion con las raices, tienen que ser racionales. Luego el polinomio q(x) pertenece a Q[x].

El (b) y (c) son analogos, dado que siempre sabemos que dos raices son racionales, llegamos a que la tercera debe ser racional en (c). En (b) resulta que con un contraejemplo sale. Por ejemplo, que dos raíces sean 0, luego c = 0, y nos queda que la tercer raíz puede no estar en los racionales. (gracias flopy)

Ejercicio 5:

Recordar que si n es un n´umero natural, el n-´esimo n´umero de Fermat se
define como

Probar las siguientes afirmaciones:

Probar las siguientes afirmaciones:
(a) El numero \(F_{n}\) es divisible por 5 si y solo si n = 1.
(b) El numero \(F_{n}\) nunca es divisible por 7.
(c) El numero\(F_{n}\) nunca es divisible por 11.

En este ultimo estoy seguro que me faltan justificaciones, pero acá va:

Para el (a): Si reemplazamos por n= 1, es claro que vale.
Veamos para el resto.

Esto ocurre si y solo si: Por fermat sabemos que \(2^{4} \equiv 1 \ (mod \ 5)\) entonces \(2^{2^{n}} \equiv 2^{r_{4} 2^{n}} \ (mod \ 5)\) (2 elevado a los posibles restos de dividir 2^n por 4)

Haciendo una tabla de restos obtenemos que para todo \(n \geq 2 \ vale\ que \ 4 | 2^{n}\) entonces \(2^{2^{n}} \equiv 1 \ (\ mod \ 5) \ para \ todo \ n \ mayor \ a \ 1\) Entonces 5 solo lo divide para n=1.

Para el (b):

Esencialmente lo mismo.
Por fermat vale que \(2^{6} \equiv 1 (\ mod \ 7) \\)
Entonces, queremos ver los posibles restos de dividir \(2^{n} \ por \ 6\) Para lo que hacemos una tabla de restos. Obtenemos entonces que los restos posibles son 2 y 4 para todo n natural.
Entonces tenemos que \(2^{2^{n}} \equiv 2^{2} \ (mod \ 7) \lor \ 2^{2^{n}} \equiv \ 2^{4} \ (mod \ 7)\) Por lo que 7 nunca lo divide.

Para el (c):

Nuevamente, como \(2^{10} \equiv 1 (mod \ 11)\) entonces hacemos una tabla de posibles restos de dividir \(2^{n} \ por \ 10\) y obtenemos que los posibles restos son:
2, 4, 8 y 6 (si hice bien las cuentas)

Entonces,

Y por lo tanto 11 nunca divide a \(2^{2^{n}} + 1\)

Creo sin embargo, que para usar las tablas de restos en el final piden alguna justificacion mas concreta de porque la tabla vale. Justificacion que claramente no se cual es. Espero alguien me peuda decir si está bien lo que hice o no, gracias!

Editado 7 veces.

Hola.

Ejercicio 2:

No voy a usar la sugerencia.

Lo que voy a proponer, es probar por inducción en \(n\) lo siguiente:
Para cada \(n \in \mathbb{N}\), vale que \(\forall m \in \mathbb{N}\) \(p(n,m)=p(m,n)\)

Entonces voy a tener una doble inducción.

Caso \(n=1\):
Quiero ver que \(\forall m \in \mathbb{N}\) \(p(1,m)=p(m,1)\)
Hago inducción en \(m\)
Si \(m=1\) nos queda \(p(1,1)=p(1,1)\) (trivial)
Paso inductivo: sé que \(p(1,m)=p(m,1)\), quiero ver que \(p(m+1,1)=p(1,m+1)\)
Por definición de la función tenemos que:

Por hipótesis inductiva, \(p(1,m)=p(m,1)=m\), entonces \(p(1,m+1)=p(m,1)+1=m+1=p(m+1,1)\), como queríamos probar. Esto concluye el caso \(n=1\).

Paso inductivo:
HP1: Sé que \(p(n,m)=p(m,n) \, \forall m \in \mathbb{N}\), quiero ver que \(p(n+1,m)=p(m,n+1) \, \forall m\in \mathbb{N}\)
Hacemos la inducción en \(m\).
Si \(m=1\) tenemos que probar que \(p(1,n+1)=p(n+1,1)\), sabiendo que vale \(p(1,n)=p(n,1)\) (es lo mismo de antes)
Paso inductivo:
Sé que: \(p(n+1,m)=p(m,n+1)\) (HP2), quiero ver que \(p(n+1,m+1)=p(m+1,n+1)\)
\(p(n+1,m+1)=p(n+1,m)+n =p(m,n+1)+n=p(m,n)+m+n\) donde usé la hipótesis inductiva HP2 y la definición de la función.
\(p(m+1,n+1)=p(m+1,n)+m=p(n,m+1)+m\), usé HP1
\(p(m+1,n+1)=p(n,m+1)+m=p(n,m)+n+m=p(n+1,m+1)\), como queríamos probar.

Entonces vale que \(\forall m \in \mathbb{N} \, p(n+1,m)=p(m,n+1)\), entonces vale la inducción en \(n\), entonces vale el resultado que queríamos probar.

Saludos.

Gracias kevin!

A mi se me ocurrio otra forma de demostrarlo, pero no sé si estara bien... aca va:

Sin usar la sugerencia. Quiero ver que \(p(m,n) = \sum_{i=1}^{n} m = p(n,m)\) para todo n.

Probamos por inducciòn:

Suponiendolo cierto para n, veamos que vale para n+1 :

\(p(m,n+1) = p(m,n) + m = \sum_{i=1}^{n} m \ + \ m = \sum_{i=1}^{n+1} m\) (usamos la hipotesis inductiva en p(m,n) )

Probamos entonces que \(p(m,n) = \sum_{i=1}^{n} m\)
Si tomamos p(n,m), sabemos por lo que acabamos de probar que \(p(n,m)= \sum_{i=1}^{m} n\)
Entonces basta probar que \(\sum_{i=1}^{n} m = \sum_{i=1}^{m} n \ para \ todo \ n\)

Probamos con n=1:

Suponemos cierto para n, veamos que vale para n+1: por otro lado \(\sum_{i=1}^{m} n+1 = \sum_{i=1}^{m} n + \sum_{i=1}^{m} 1\)

Si igualamos ambas, nos queda que \(m = \sum_{i=1}^{m} 1\) que valido.

Entonces probamos que \(p(m,n) = \sum_{i=1}^{n} m = \sum_{i=1}^{m} n = p(n,m)\)

Lo que no se es si hace falta probar que es cierto para todo m, pues llegamos a algo que va a valer siempre para m.

Por favor si alguien me dice si esta bien, se lo agradezco!

creo que "intercaladas" tiene muchas interpretaciones... tendrían que haber sido mas específicos

Firma

$$A\; flight\; of\; fancy\; on\; a\; windswept\; field...\;$$

1)Como las cartas no especiales ya tienen un orden, lo unico que nos interesa es ver donde van las especiales y cual es su orden. Asi, si pensamos al mazo como 50 lugares ordenados, las cartas especiales pueden ir en 10 de esos 50, o sea 50 tomados de a 10 = \(50!/(40!10!)\). Y para cada una de esas eleeciones, podemos ordenar las cartas especiales de \(10!\) formas, con lo cual la respuesta es \(50!/(40!.10!) . 10!\) = \(50!/40!\)

Lo que acabo de publicar en el 1 es suponiendo que puedan ser vecinas las cartas especiales, sino:

Lo que vamos a hacer es intercalar a las no especiales entre las especiales. Empezamos con las 10 especiales en cualquier orden, y si o si tenemos que meter 1 no especial en el medio de la 1ra y la 2da, la 2da y la 3ra .... la 9na y la 10ma, eso es meter 9 cartas. Ahora nos quedan 31 cartas para meter, en 11 lugares: _ E _ E _ E _ E _ E _ E _ E _ E _ E _ E _ . Con lo cual basta encontrar todas las maneras de meter 31 cartas en 11 espacios, porque al meterlas ya quedan ordenadas por enunciado. Podemos suponer que son iguales entonces las 31 cartas que tenemos que meter, en 11 espacios, y esto es lo mismo que tener 31 bolitas B, y 10 separaciones "|" y dar todas las formas de ordenar esto: un ejemplo seria, si yo quiero 28 en el lugar 1, 1 en el lugar 5, 2 en el lugar 11: (28B)| | | |B | | | | | |BB . Con lo cual, la cantidad de formas de ordenar esto es de \(41!/31!.10!\) Esto multiplicado a las \(10!\) formas de ordenar las especiales nos da un total de \(41!/31!\) formas de hacer lo pedido.

Para mi el primero, es considerandolo por bozones, el combinatorio (51 10) *10! /2!
Consideré que hay 41 cajitas (espacios entre cartas contando ademas los que estan en los extremos) y bueno 10 bolitas (de ahi el 51) y el 10, la forma de acomodar las 10 cartas en esos lugares, luego multiplicar por 10! para las permutaciones de las posibilidades, y luego dividir por 2! porque considere que los 2 comodines son indistinguibles.

En el 4 b qué pasa si pienso que c=0? no podría llegar a que la tercera raíz no es racional??

Firma

Un tejón? Pamplinas debe ser Milhouse!

flopy624 escribió:

En el 4 b qué pasa si pienso que c=0? no podría llegar a que la tercera raíz no es racional??

Tenes razón. Creo que con un contraejemplo sale. Pones que \(\alpha \ y \beta \ sean \ 0\) y los coeficientes te quedan de la forma , \(q = x^{3} - \gamma x^{2} + 0x +0.\) Y gamma puede ser cualquier cosa, es decir, puede ser raiz no racional.

No me habia dado cuenta, gracias.

exacto! ese es un lindo contraejemplo... si c=0 entonces nada te asegura que la tercer raiz sea racional. pues c es el producto de las tres raices. armate un polinomio que tenga a 0 como raiz doble y al numero \(i\) como raiz simple.

En el 4c tomar -1, 1 y sqrt2 de raices.

Y pero siendo (en el 4b)
r + s + t = -a
rs + st + rt = b
rst = -c

Ok, si se "c" es 0, entonces una de las 3 puede ser real (considerando una raiz cualquiera y la otra 0, de las 2 que te dan como que son racionales en el enunciado), pero "a" va a ser igual perteneciente a los reales.

Ejemplo 1, 0 , sqrt 2.