miércoles, 27 de mayo de 2015

1. Se tiene un alfabeto de 2015 letras. Hallar el menor entero positivo n tal que en toda palabra de longitud n formada con letras del alfabeto (se permiten repeticiones) se pueda encontrar un bloque de letras consecutivas en el que ninguna letra aparezca un numero impar de veces.

2. ¿Será posible partir a un cuadrado en una cantidad finita de triángulos acutángulos?

3 comentarios:

Juan dijo...

2: sí. http://i62.tinypic.com/j08b3k.jpg

Juan dijo...

1. la respuesta es $ 2^{2015} $. Un ejemplo de una palabra de longitud $ 2^{2015}-1 $ que no funciona es una palabra donde las letras son $ \ell_0, \ell_1, ..., \ell_{2014} $ y la $j$-ésima letra de la palabra es $\ell_{v_2(j)}$.

Ahora muestro que toda palabra de longitud $2^{2015}$ tiene un bloque así. Supongamos que tengo mis $2^{2015}$ letras en orden y pongo un guión bajo ( _ ) al principio.

A cada caractér le pregunto: "Dime cuáles letras han aparecido par veces antes que tú (e incluyéndote a tí también)."

El guión bajo me va a decir que todas

La primera letra, digamos $\ell$, me va a decir que todas excepto $\ell$, y etcétera.

Recibiré $2^{2015}+1$ respuestas, entonces dos respuestas deben ser iguales, digamos las que me dieron los caractéres en posiciones $i$ y $j$.

Entonces el bloque de letras $(i,j]$ cumple.

Juan dijo...

1. la respuesta es $ 2^{2015} $. Un ejemplo de una palabra de longitud $ 2^{2015}-1 $ que no funciona es una palabra donde las letras son $ \ell_0, \ell_1, ..., \ell_{2014} $ y la $j$-ésima letra de la palabra es $\ell_{v_2(j)}$.

Ahora muestro que toda palabra de longitud $2^{2015}$ tiene un bloque así. Supongamos que tengo mis $2^{2015}$ letras en orden y pongo un guión bajo ( _ ) al principio.

A cada caractér le pregunto: "Dime cuáles letras han aparecido par veces antes que tú (e incluyéndote a tí también)."

El guión bajo me va a decir que todas

La primera letra, digamos $\ell$, me va a decir que todas excepto $\ell$, y etcétera.

Recibiré $2^{2015}+1$ respuestas, entonces dos respuestas deben ser iguales, digamos las que me dieron los caractéres en posiciones $i$ y $j$.

Entonces el bloque de letras $(i,j]$ cumple.

Publicar un comentario