jueves, 11 de junio de 2015
11 de Junio
1. Encuentra todos los enteros positivos $n \geq 3$ tales que un tablero de $n \times n$ sin las cuatro esquinas puede ser cubierto con piezas así:
2. Sea $n$ un entero positivo impar. Si $\phi(n)$ y $\phi(n + 1)$ son ambos potencias de 2, muestra que $n + 1$ es una potencia de 2 o $n = 5$.
Suscribirse a:
Comentarios de la entrada (Atom)
2 comentarios:
2. Supongamos que ninguna se cumple. Defino $ F_m=2^{2^m}+1 $. Notemos que
$ F_m=F_{m-1}F_{m-2} \ldots F_0 +2 \implies $
$ F_m > F_{m-1} \ldots F_0 +1 $.
entonces todos los números de esta forma son distintos. Es fácil ver que
$ n = F_{k_1} F_{k_2} \ldots F_{k_x} $
$ n+1 = 2^a F_{m_1} F_{m_2} \ldots F_{m_y} $, $y>0$.
Sea $ F = \text{max} \{ F_{k_1}, ..., F_{k_x}, F_{m_1}, ..., F_{m_y} \} $. Entonces si $ F!n+1$ vemos que $n+1 \ge 2F > 2n \ge n+1$, imposible. Entonces $ F|n$.
Si $n=F$ entonces $F_{m_i} | F+1$ pero $F_{m_i} | F-2$ y entonces $ m_i=0$ y así $ n+1=3 \cdot 2^a = 2^{2^M}+2$ donde $F=F_M$. Por modulo 4, $a=1$ y así $n+1=6$, pero habíamos supuesto $n \neq 5$, contradicción.
Entonces $n>F$, y así $x > 1$. Entonces
$2^a F_{m_1} F_{m_2} \ldots F_{m_y} -1 = $
$n \ge FF_{k_1} \ge 3F > $
$3(F_{m_1} F_{m_2} \ldots F_{m_y}+1$
y así $ a \ge 2$. Defino $P = \frac{n+1}{2^a}$. Por lo tanto $ 4 | n+1 $ y así $ n \equiv 3 (\bmod 4)$. pero el único número de la forma $F_{\text{algo}}$ que es $ 3 \bmod 4$ es $3$, y así $ 3|n$. Entonces $ 3 $ no divide a $P$, y así $F > 3P+1$.
$ 2^a P -1 = n \ge 3F > 3(3P+1) > 9P -1$,
y así $2^a > 9$ por tanto $a \ge 4$. Como $ 16 | n+1 $, tengo $ n \equiv 15 (\bmod 16)$ pero los únicos $F_{\text{algo}}$ que no son $ 1 \bmod 16$ son $3$ y $5$, y así $ 5 | n$.
Si $ 5=F$ entonces $n+1=16$, contradicción. Entonces $ F > 5$. Además, $3,5$ no dividen a $n+1$, y por lo tanto $ F > 15P$. Entonces
$2^a P -1 = n \ge 15F > 15^2P -1 $
y así $ 2^a > 15^2 $ por lo que $2^8 | n+1$. Entonces $ n \equiv 2^8-1 (\bmod 2^8)$, pero los únicos $F_i$'s que no son $ 1 \bmod 256$ son $3,5,17$ y así $17 | n$.
En general, supongamos que ya demostré $ F_0, F_1, ..., F_b | n $ (y por lo tanto no dividen a $n+1$). Entonces si $n=F_0 \ldots F_b$ vemos que $n+1$ es potencia de 2, contradicción. De lo contrario $F > F_b$ y además como $F_i$ no divide a $n+1$ para $I \le b$, tenemos $F \ge (F_0 \ldots F_b)P$. Entonces
$ 2^a P > n \ge FF_0 \ldots F_b$
$\ge (F_0 \ldots F_b)^2P \implies$
$ 2^a > (F_0 \ldots F_b)^2 = (F_{b+1}-2)^2 = (2^{2^{b+1}}-1)^2 \implies $
$2^a > 2^{2^{b+2}} - 2^{2^{b+1}+1 \implies $
$ a \ge 2^{b+2}$
y entonces $2^{2^{b+2}} | n+1$ pero los únicos $F_i$'s no 1 modulo eso son $ F_0,...,F_b, F_{b+1}$ y entonces todos ellos dividen a $n$.
Por inducción todo $F_I | n $ entonces $n$ no es finito, contradicción
el 1 sale con coloración modulo 4
Publicar un comentario