Problema 4 OIM 1997

Versión para impresión
Su voto: Ninguno Media: 5 (2 votos)

 Sea n un entero positivo. Consideremos la suma $x_1y_1 + x_2y_2 + \ldots + x_ny_n$, donde los valores que pueden tomar las variables $x_1, x_2, \ldots, x_n, y_1, y_2, \ldots, y_n$ son únicamente 0 y 1. Sea $I(n)$ el número de $2n$-adas $(x_1, x_2, \ldots, x_n, y_1, y_2, \ldots, y_n)$ para las cuales el valor de la suma es un número impar y sea $P(n)$ el número de $2n$-adas $(x_1, x_2, \ldots, x_n, y_1, y_2, \ldots, y_n)$ para las cuales la suma toma valor par. Probar que

$$\frac{P(n)}{ I(n)}=\frac{2^n + 1}{2^n - 1}$$




Imagen de jesus

Pongo este problema para que

Pongo este problema para que vean en dónde pueden llegar a encontrarse problemas de combinatoria.

Imagen de j_ariel

Tengo la sospecha de

Tengo la sospecha de que

\[ P(n) + I(n) = 2^{2n} \]

Intenté utilizar un argumento en donde se cambiaban parejas (1,1) por (0,y) donde y puede ser 0 ó 1, pero tiene algunos defectos aun. Seguiré pensando, es muy interesante el problema, gracias por ponerlo :D. Otra idea que tengo pero que no me convence es cambiar lo que se quiere demostrar por

\[ (P(n))(2^n - 1) = (I(n))(2^n + 1) \]

ssi

\[ 2^nP(n) - P(n) = 2^nI(n) + I(n) \]

ssi

\[ 2^n (P(n) - I(n)) = P(n) + I(n) \]

pero sigue sin gustarme eso, debe haber algún argumento combinatorial matón que haga pedacitos el problema xD (cuando veo los problemas "IMO" como que me da cosa xD, jajaja xD, a veces mi mente se pone una barrera que dice "no lo podrás hacer" y no me deja pensar a gusto xD, pero nah, se me va quitando ese malísimo hábito).

Gracias :D. Saludos :D.

Imagen de jesus

Son ideas muy interesantes.

Son ideas muy interesantes. Creo que este problema no se te va dificultar mucho. 

Te aclaro que no es un problema IMO, es un OIM (Olimpiada Iberoamericana de Matemáticas). Cuando lo escribí me preocupó el parecido, pues es una permutación de letras y facilmente se podría entender como "Olimpiada Interncacional de Matemáticas". Tal vez, debería ponerle "Iberoamericana" o simplemente "Ibero". 

Imagen de Luis Brandon

Ahi te va Jesus, espero y

5

Ahi te va Jesus, espero y este bien, Primero que nada sabemos que hay 4 formas posibles para cada una de las parejas $x_j y_j$, por lo tanto, hay $4^n$ arreglos de la suma pedida(cuatro por cada pareja). De ahi obtenemos que:

$P(n)+I(n)=4^n$...igualdad1

Para $n=1,2$ se tiene que $[P(n),I(n)]=(3,1),(10,6)$

Para calcular $P(n+1)$ Se debe multiplicar $P(n)$ por tres, ya que al agregar la nueva pareja a la suma esta puede tomar cuatro posibilidades, de las cuales tres son pares las cuales al sumar con las anteriores sumas pares, seguiran siendo par. Pero tambien hay que sumar $I(n)$ ya que uno de los cuatro valores de la nueva pareja es impar, de donde al sumarlo con $I(n)$ las nuevas sumas seran par. De ahi:

$P(n+1)=3P(n)+I(n)$...resultado1

Para calcular $I(n+1)$ usamos un procedimiento similar, al agregar la nueva pareja a la suma, puede tomar 4 posibilidades, 3 pares y 1 impar, asi que multiplicamos $I(n)$ por 3, ya que cualquiera de las tres posibilidades pares al sumarlo con $I(n)$ dara impar, y se le agrega $P(n)$ ya que la posibilidad impar del nuevo elemento de la suma al sumarlo con $P(n)$ dara impar. De ahi:

$I(n+1)=P(n)+3I(n)$...resultado2

de ahi es facil ver que:

$P(n+1)-I(n+1)=2[P(n)-I(n)]$ Usando que $P(1)-I(1)=2$ se llega facilmente a que

$P(n)-I(n)=2^n$...igualdad2

Usemos las dos igualdades que obtubimos :

$P(n)+I(n)=4^n$
$P(n)-I(n)=2^n$

de ahi es facil llegar a que

$P(n)=2^{n-1}(2^n+1)$
$I(n)=2^{n-1}(2^n-1)$

De donde el resultado pedido es claro. espero y este bien Jesus, los ejemplos de $n=(1,2)$ los use para darme la idea de como obtener los resultados 1 y 2. Saludos jesus!!!!

Imagen de jesus

Muy buena solución Brandon,

Muy buena solución Brandon, la idea recursiva fue muy buena. Yo participé en esa iberoamericana, la verdad no recuerdo cómo lo hice en aquel entonces, pero lo que sí recuerdo es que también calculé los valores de P(n) e I(n). 

Te comento que aquél día que me hablaste por google talk hice el problema 5 de la IMO, no me he puesto a escribirlo pues he estado ocupado dibujando los globotios que aparecen ahora en los comentarios de Matetam.

Como sea, te puse unas sugerencias en ese problema  para ver si te sirven, es más o menos como yo lo resolví.

Saludos

Imagen de Luis Brandon

O ya veo, dibujando los

O ya veo, dibujando los globitos de matetam, pues asi se ve mejor (se ven mas claros los comentarios, antes la primera parte estaba mas obscura), Asi que en esa Ibero participaste, ahora que recuerdo ya habias puesto un problema de esa ibero creo...

Ahora mismo vere el problema 5 de la IMO, gracias jesus saludos!!!!!!

Imagen de Usuario anónimo

no entedi esta parte: Pero

no entedi esta parte: Pero tambien hay que sumar I(n) ya que uno de los cuatro valores de la nueva pareja es impar, de donde al sumarlo con I(n) las nuevas sumas seran par
Imagen de j_ariel

jajaja, cierto, OIM lo usan

jajaja, cierto, OIM lo usan para la ibero xD, es que confieso que ayer tenía muchísimo sueño y lo primero que se me vino a mi mente somnolienta fue "OIM ... mmm, olimpiada internacional de matemáticas ... mmm, va a estar pesado" xD. Gracias por la aclaración :D.

Brandon :D, hola :D, está genial tu solución! :D! Gracias por compartirla con nosotros :D.

Saludoz :D

Imagen de Luis Brandon

Gracias zzq, sabes, no estaba

Gracias zzq, sabes, no estaba del todo seguro de ella(sobretodo por los resultados), hasta que me puse a analisarlos bien y me di cuenta de que si estaba en lo correcto, Lo mas dificil fue ver apartir de los resultados la relacion $P(n)-I(n)=2^n$ lo cual si me tarde en ver, saludos!!!y me alegra que te gustara!!!(es mas corta que lo que escribi originalmente haha)

Imagen de Diana.L

Bueno necesito ayuda en un

Bueno necesito ayuda en un problema

Cambiado un poco de tema claro,

¿Cuál es la mitad de 2^98?

¿Existen reglas aplicadas a la reducción de exponentes?

Gracias y perdon por las molestias.

Imagen de Rosario92

Pues mira Diana, es muy

Pues mira Diana, es muy sencillo tenemos qe "la mitad" de 2^98 es lo mismo que dividir

$\frac{2^{98}}{2}$ y como recordaras una de las leyes de los exponentes nos dice: q al dividir, si tenemos bases iguales (en este caso el 2) los exponentes se restan ...

por lo tanto la mitad de 2^98 = 2^97 porque el exponente de 2 es 1, espero me haya dado a entender :)

Imagen de jmd

Checa porfa el acordeón de

Checa porfa el acordeón de álgebra.

Saludos

jmd

PD: ¿no me digas que stás en la preselección? :(

Imagen de Diana.L

No, no estoy en la

No, no estoy en la preselección

Soy novata y me estoy entrenando para la olimpiada del próximo año

ya había consultado ese acordeon pero no encuentro el método

Imagen de jmd

OK Ya me habías asustado

OK Ya me habías asustado :)

Checa entonces el blog del profesor Huertas para un curso en álgebra. Allí encontrarás el material de álgebra que necesitas.

Saludos

jmd