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?
Posted by Xavi at 3:53 p.m.

3 comentarios:

Juan dijo...

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

27 de mayo de 2015, 9:42 p.m.
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.

28 de mayo de 2015, 12:31 p.m.
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.

28 de mayo de 2015, 12:33 p.m.

Publicar un comentario

Suscribirse a: Comentarios de la entrada (Atom)