Solução - Problemas da semana 01/05/2023-08/05/2023

Solução 1:

Primeiro, vejamos o que acontece se um dos números é igual a $0$.  Assumimos sem perda de generalidade que o número é o $a$

$\implies 0^2b+c=b^2c+0=c^20+b\implies b=c$

mas $1=ab+bc+ca=bc=b^2\implies b=c=\pm 1$ nos dando as soluções $(\pm 1$,$\pm 1$,$0)$ e permutações.

Agora, assumimos que todos são não-nulos:

$a^2b+c=b^2c+a\implies a(ab-1)=c(b^2-1)$

Como $ab-1=-bc-ca$,

$-ac(a+b)=c(b^2-1)\implies -a(a+b)=b^2-1\implies a^2+ab+b^2=1$

Assim, analogamente, $b^2+bc+c^2=1$ e $c^2+ca+a^2=1$. Somando essas 3 equações:

$2(a^2+b^2+c^2)+ab+bc+ca=3\implies2(a^2+b^2+c^2)+1=3\implies a^2+b^2+c^2=1$

Finalmente, como $a^2+b^2+c^2=1=ab+bc+ca$

$2a^2+2b^2+2c^2=2ab+2bc+2ca\implies (a-b)^2+(b-c)^2+(c-a)^2=0\implies a-b=b-c=c-a=0$

Então $a=b=c$. Daí as únicas soluções que nos restam são $a=b=c=\pm \frac{1}{\sqrt 3}$

Solução 2:

Veja que quando colocamos fatoriais no meio desses números o expoente dos primos que dividem o produto muda muito! (O expoente de p na fatoração desse produto será chamado de $v_p$ daqui em diante) Mas será que dá para controlá-lo?

O que acontece se colocarmos um fatorial após um primo $p$, o $v_p$ do produto muda? Não! pois $p!=1\cdot2\cdot3\cdot\dots\cdot p$ que tem $v_p=1$, que é o mesmo de $p$. Além disso, os expoentes também não mudam para primos $q$ maiores que $p$. Assim, é natural pensar que todos os expoentes podem ser controlados a serem pares na maioria dos casos.

se $n=p$ for primo? Independente de onde colocarmos os fatoriais o $v_p$ do produto continuará igual a 1. Assim, o produto nunca pode ser quadrado perfeito. Caso contrário, vamos fazer um algoritmo para que ele seja um QP: Primeiramente, seja $q_1$ o maior primo menor que $n$, se o expoente de $q_1$ no produto no começo for ímpar, colocamos um ! após $(q_1+1)$, assim, o expoente de $q_1$ aumenta em exatamente um, se tornando par, caso contrário, não faremos nada e seguiremos para o próximo passo: Ao final de cada passo $i$ passamos de $q_i$ para $q_{i+1}$, onde $q_{i+1}$ é o maior primo menor que $q_i$, e assim por diante. Veja que, ao aplicarmos esse algoritmo várias vezes, teremos um produto com todos os expoentes pares, pois ao colocar um fatorial em $q_i$ nenhum expoente de um primo anterior muda. Ou seja, um quadrado perfeito! Como queríamos.

Solução 3:

Inicialmente, vamos tentar achar essa constante. Seja $G$ um grafo associado ao nosso tabuleiro $n\times n$ onde os vértices são as casas do tabuleiro e ligamos dois vértices se as casas associadas a eles são adjacentes no tabuleiro. Veja que um conjunto tropical é o mesmo que um conjunto de vértices cujo complementar em $G$ é um subgrafo que é uma floresta. Vamos tentar achar o número mínimo de vértices que precisamos tirar de $G$ para que o grafo resultante seja uma floresta (é equivalente a achar o menor tamanho de um subconjunto tropical). Inicialmente, temos $n^2$ vértices e $2n(n-1)$ arestas (cada linha e cada coluna tem $n-1$ arestas) assim, para o grafo resultante seja uma floresta, precisamos que $|A|\le |V|-1$. Sabemos que cada vértice tem grau no máximo $4$, pois cada casa tem no máximo 4 vizinhos. Assim, se tiramos k vértices do grafo no mínimo para ele se tornar uma floresta:

$2n(n-1)-4k\le |A|\le |V|-1=n^2-k-1$

Logo,

$2n^2-2n-4k\le n^2-k-1\implies n^2-2n+1\le 3k$

Nosso objetivo é achar as constantes $C$ tal que $k\le Cn^2$, para todo $n$, portanto,

$(n-1)^2\le3k\le 3Cn^2\implies C\ge \frac{(n-1)^2}{3n^2}$

fazendo $n\rightarrow \infty\implies C\ge \frac 13$. Logo, temos que os $C$'s possíveis são $\ge \frac 13$. Vamos provar que $C\ge \frac13$ funciona:

Tome a seguinte cobertura de um tabuleiro $n\times n$:

Em que pintamos todas as diagonais de casas $(x$,$y)$ em que $3\mid x-y$. Veja que este conjunto é tropical e usa no máximo $\frac 13$ das casas do tabuleiro. Como queríamos!