Soluções Matemática - Semana 17

Iniciante

Coloque o número $1$ em um conjunto $A$ e o $2$ em um $B$ quaisquer. Agora, temos duas opções para colocarmos o número $3$, colocá-lo junto ao $A$ ou em um novo conjunto $C$, pois ele não pode ficar junto ao $2$. Feito isso, temos novamente duas opções de conjuntos para colocarmos o número $4$: qualquer um dos conjuntos em que não colocamos o $3$.

De maneira geral, podemos colocar o número $n$ em qualquer um dos dois conjuntos em que não colocamos o número $n-1$. Assim, temos duas possibilidades de conjunto para qualquer número entre $3$ e $1995$, o que dá $2^{1993}$ possibilidades. Entretanto, note que existe um caso que precisamos tirar.

Entretanto, a contagem feita acima não elimina o caso em que todos os ímpares estão no conjunto $A$ e todos os ímpares no conjunto $B$, mas isso deixaria o conjunto $C$ vazio, o que o problema não permite, logo devemos retirar uma das possibilidades contadas acima e a resposta do problema fica $2^{1993}-1$.

Intermediário

Se $A$ é um camaleão que tem $5$ amigos, cada um de seus amigos tem um único amigo: o próprio $A$. Então todos os camaleões estão distribuídos na ilha em pequenos grupos de $6$: $5$ amarelos, que só têm um amigo cada, e $1$ verde, que é amigo dos outros $5$ de seu grupo.

Feita essa distribuição entre amarelos e verdes, ocorre a segunda mudança e, após ela, todos só têm amigos da mesma cor. Primeiro, veja os $30$ amarelos que ficam verdes. Note que se em um grupo um camaleão amarelo fica verde, todos os outros do mesmo grupo também devem ficar, pois são todos amigos do camaleão verde central, e um não pode ser amigo de dois camaleões de cores distintas, pois no final, todos devem ter a mesma cor. Desse modo, os $30$ camaleões que mudaram para o verde, eram de $6$ grupos distintos em que todos os amarelos ficaram verdes. Agora, já temos $6$ grupos em que todos os camaleões têm a mesma cor.

Falta agora vermos os $40$ verdes que ficaram amarelos. Cada um deles, por ser um camaleão verde, está no centro de um grupo com outros $5$ amarelos. No momento em que eles ficam amarelos, ficam da cor de todos os seus amigos, o que gera 40 novos grupos em que todos os camaleões que são amigos têm a mesma cor. Note que agora temos $46$ grupos, ou seja, $6 \times 46 = 276$ camaleões que atendem às demandas do enunciado.

Se houver qualquer outro grupo de camaleões, ele terá um verde amigo de $5$ amarelos, o que é absurdo pois todos os camaleões amigos têm a mesma cor, logo a Ilha Colorida tem apenas aqueles $276$ camaleões.

Avançado

$\forall a\ /\ mdc(a,n) = 1 \Rightarrow a \equiv a (mod \ n) \Rightarrow a^2 \equiv 1 (mod \ n)$

Seja $n = 2^\alpha \times P_1^{\alpha_1} \times P_2^{\alpha_2} \times ...\times P_k^{\alpha_k}.$*

Sempre que encontramos $a \in \mathbb{Z} \ / \ mdc(a,P_i^{\alpha_i}) = 1, \forall i = 1, 2, ..., k \Rightarrow mdc(a,n) = 1.$

Seja $a \equiv 1 (mod \ P_i^{\alpha_i}). \forall i = 1, 2, ..., k.$

$\Rightarrow$ Pelo Teorema Chinês dos Restos, $a$ existe $\Rightarrow a^2 \equiv 1 (mod \ P_i^{\alpha_i}), \forall i = 1, 2, ..., k.$

$\Rightarrow 2^2-1 \equiv 0 (mod \ P_i^{\alpha_i}), \forall i = 1, 2, ..., k\Rightarrow P_i^{\alpha_i}|3 \Rightarrow P_i=3$ e $\alpha_i=1.$

Obs.: * é a fatoração em primos de $n$, com $P_i \neq 2, \forall i$ e $\alpha$ pode ser $0$.

Também pelo Teorema Chinês dos Restos, existe $\mathbb{Z}$ tal que

$b \equiv 3 (mod \ 2^{\alpha})$ e $b \equiv 1 (mod \ 3).$

$\Rightarrow mdc(b,n) = 1 \Rightarrow 3^2 \equiv 1 (mod \ 2^{\alpha}) \Rightarrow 2^{\alpha}| 8 \Rightarrow \alpha \leq 3.$

$\Rightarrow$ Nosso $n$ só pode ser um divisor de $2^3 \times 3 = 24$ e, sendo assim, é fácil verificar que se $n|24 \Rightarrow n$ é solução. (Por conta que $n$ pode ser $1, 2, 4, 8$ e também $3$, daí, pelo Teorema Chinês dos Restos vale para $n = 2^{\alpha} \times 3^{\beta}$, com $\alpha \leq 3$ e $\beta \leq 1$).

Daí, os possíveis valores de $n$ são $2, 4, 6, 8, 3, 12$ e $24$.