• Registro
Foro de preguntas y respuestas de matemáticas, de cualquier nivel. Cuánto más interesantes, divertidas o intrépidas, mejor.
Aviso: Te invitamos a conocer la página de Facebook de la UCIM

Ganas puntos al hacer preguntas, contestarlas y, sobre todo, si tu respuesta es seleccionada como la mejor.
Registrate como usuario para participar en el foro. También puedes utilizar tu identidad de FB Utiliza el botón azul para ingresar (si usas tu identidad de FB y estás logeado en FB, automáticamente te reconoce).

El irracional tiene una página en FB. El Irracional






Generar todos los enteros usando dos operaciones.

+6 votos
Demostrar la siguiente afirmación:

Sea $n \geq 2$ un entero dado, cualquier entero $k \in \{1, \ldots, n\}$ puede obtenerse a partir de $n$ aplicando repetidamente las siguientes funciones $f(x) = \lfloor \frac{x}{2} \rfloor$,  y $g(x) = n-x$.
preguntado por dlara (1,780 puntos) Ago 5, 2013 en Torito
Este problema está bastante bonito. Si lo inventaste, siento que lo desperdiciaste aquí, hubiera estado bien para algún concurso.
No lo inventé, lo leí en un artículo. Y sí, está super bonito :)

1 Respuesta

+2 votos
 
Mejor respuesta
Supongamos que existe $x \in \{1,\dots,n\}$ de tal manera que $x$ no se puede obtener aplicando $f$ y $g$.

Vamos a probar que para todo $k$ existen $k$ numeros consecutivos en $\{1,\dots,n\}$ que tampoco se pueden obtener de esa manera. Esto nos dara una contradiccion pues obviamente $n$ se puede obtener asi.

Por induccion: es cierto para $k=1$ tomando $x$. Supon que es cierto para alguna $k$. Entonces existen $y+1,\dots.y+k \in  \{1, \ldots, n\}$ que no se pueden obtener de esa forma. Como $\lfloor \frac{n}{2} \rfloor$ se puede obtener de esa forma, podemos suponer (tal vez despues de aplicar $g$ a los $y+i$) que $y+i\leq n/2$ para todo $i=1,\dots,k$. Ahora observamos que si $y+i$ no se puede obtener de esa forma entonces tampoco $2y+2i$ y $2y+2i+1$, asi que no podemos obtener $2y+2,2y+3,\dots,2y+2k\leq n$. En particular encontramos $k+1$ numeros consecutivos que no podemos obtener aplicando $f$ y $g$.
respondido por Carlos (17,280 puntos) Ago 6, 2013
seleccionada por dlara Ago 19, 2013
Generar [0,1] usando dos operaciones.
Licencia Creative Commons
Este obra está bajo una Licencia Creative Commons Atribución-NoComercial-CompartirIgual 2.5 México.

powered by UCIM

...