Escrito por Gabriel Mota
Problema 5 Na figura abaixo, um quadradinho branco é cercado por quatro quadradinhos pretos e três quadradinhos brancos são cercados por sete quadradinhos pretos.
Qual o número máximo de quadradinhos brancos que podem ser cercados por $n$ quadradinhos pretos?
Comentário:
Antes de começar a solução, é preciso entender que este problema é muito mais difícil que os problemas 5 (ou até problemas 6) da OBM nível 3, quanto mais da OBM nível 2! Provavelmente este problema foi proposto com uma solução com erros que a banca não havia percebido na elaboração da prova. Porém isso não significa que o problema está erado ou é impossível, só é muito mais difícil do que esperado!
Se você é do nível 2 e procura entender a solução deste problema, recomendo focar em entender as ideias, que vão estar destacadas em caixas azuis ao longo da solução.
Solução.
Inicialmente, assuma que o tabuleiro de quadradinhos $1\times 1$ (que, daqui em diante, chamaremos de casas) seja infinito na horizontal e na vertical. Veja que uma configuração máxima existe, uma vez que há somente um número finito de configurações. Iremos mostrar que:
Se $n = 4t$, a resposta é $2t^2 – 2t + 1$.
Se $n = 4t +1$, a respota é $2t^2 – t$.
Se $n = 4t +2$, a respota é $2t^2$.
Se $n = 4t +3$, a respota é $2t^2 + t$.
Ideia principal: Para resolver este problema, basta construir a configuração máxima (ou as configurações máximas), e provar que ela é de fato a melhor configuração. Não é tão difícil encontrar a configuração máxima para $n$ multiplo de $4$, e adaptar essa construção para todo $n$, e se convencer que elas são máximas (tente fazer isso!). Porém, realmente provar que de fato essas configurações são máximas parece quase impossível de primeira, pois temos liberdade até demais de como podemos colocar no plano os quadradinhos pretos. Então a ideia é restringir a liberdade excessiva do problema aos poucos, provando e definindo várias coisas pequenas, até que a nossa figura máxima tenha que ser uma das configurações que construímos!
Ideia 1 (casos iniciais): Tentar construir exemplos pequenos e simples, sem se preucupar se as figuras são máximas ou não. Depois tentar mover alguns quadradinhos pretos individualmente no intuito de maximizar a área da figura. A ideia é tentar perceber características que a sua figura nova tem e a antiga não, para termos um direcionamento do que precisamos provar.
Definição 1. Uma sequência de $k$ quadrados pretos horizontais consecutivos, verticais ou diagonais é definido como um segmento de tamanho $k$, horizontal, vertical ou diagonal, respectivamente, como mostrado na figura abaixo.
Uma configuração com $n$ quadradinhos brancos cercados é máxima se o número de quadradinhos pretos que cercam os quadradinhos brancos for máximo.
Afirmação 1. Na configuração máxima, todos os segmentos verticais e horizontais vão ter tamanho 1 ou 2.
Isso é imediato, pois, se tivermos uma figura com um segmento horizontal ou vertical de tamanho 3 ou mais, então poderemos facilmente aumentar a quantidade de quadrados brancos, procedendo como mostrado na figura abaixo. $\blacksquare$
Afirmação 2. A configuração máxima é uma figura conexa.
Suponha que a configuração máxima seja composta por pelo menos duas figuras conexas distintas e escolha duas delas. Transladando as demais componentes conexas, e procedendo como na figura abaixo, unimos as duas componentes escolhidas e aumentamos a quantidade de quadrados brancos circundados por quadrados pretos em pelo menos uma unidade. Absurdo. $\blacksquare$
Afirmação 3. A configuração máxima é uma figura convexa.
Se tivermos uma figura não convexa, então, procedendo conforme mostrado na figura abaixo, podemos mover algumas casas pretas de forma a aumentar a quantidade de quadrados brancos envolvidos por elas e tornar a figura convexa. $\blacksquare$
Ideia 2 (olhar os extremos): em problemas de combinatória como esses, sempre é bom tentar analisar os extremos ou as bordas da figura (nesse caso, podemos definir as bordas da figura como o seu fecho convexo). Note que por termos conseguido mostar que a figura tem que ser convexa e conexa, ela já está razoavelmente bem definida, sendo semelhante a um polígono convexo. A ideia é tentar definir o formato desse polígono, para tentarmos entender melhor a figura máxima.
As afirmações feitas até aqui garantem que a figura máxima é um octógono $ABCDEFGH$ (veja a figura abaixo, na qual $A$, $B$, $C$, $D$, $E$, $F$, $G$, $H$ representam casas), em que $AH$ e $DE$ são segmentos horizontais, $BC$ e $GF$ são segmentos verticais e $AB$, $EF$, $HG$, $CD$ são segmentos diagonais, com $AB\parallel EF$ e $HG\parallel CD$. (Veja que não descartamos a possibilidade de que $A=H$, $D=E$, $B=C$ ou $G=F$.) Realmente, um momento de reflexão deixa claro que outras configurações dos segmentos formariam uma figura não convexa.
No que segue, dadas casas $X$ e $Y$ tais que $XY$ é um segmento horizontal, vertical ou diagonal, denotemos por $XY$ seu tamanho, conforme estabelecido na Definição 1.
Afirmação 4. Se $n$ for par, então $AH = DE$ e $BC = FG$. Se $n$ for ímpar, então $AH \ne DE$ e $BC \ne FG$.
De fato, como $AH$ e $DE$ são segmentos horizontais, temos que $AB+BC+CD$ e $HG + FG + FE$ medem a separação vertical entre as retas que contém $AH$ e $DE$; portanto, $AB+BC+CD = HG + FG + FE:=m$. Agora, recorde que
$$\underbrace{(AB+BC+CD)+(HG+FG+FE)}_{=2m}+AH+DE=n.$$
Então se $n$ for par, temos pela afirmação 1 que $AH$ e $DE$ são iguais; por outro lado, se $n$ for ímpar, esses tamanhos são distintos. $\blacksquare$
Para a próxima afirmação, recorde que, pela Afirmação $1$, os segmentos horizontais e os verticais da figura máxima têm tamanho $1$ ou $2$. Por outro lado, pela Afirmação $4$, os tamanhos desses segmentos são iguais se $n$ for par e distintos se $n$ for ímpar.
Afirmação 5. A figura de área máxima depende somente das posições dos segmentos $AH$, $DE$ ou $BC$, $FG$.
Também não é difícil nos convencermos disso a partir de duas ilustrações. Por exemplo, supondo $n$ par (o caso $n$ ímpar é análogo), as figuras acima deixam claro que, uma vez que $AH$ e $DE$ estejam marcados no plano (com $AH=DE=1$ ou $2$), há somente uma maneira de construir um octógono como desejado, isto é, com $BC$ e $FG$ segmentos de tamanhos iguais (a $1$ ou $2$) e $AB$, $CD$, $EF$, $GH$ segmentos diagonais. $\blacksquare$
Um corolário imediato da justificativa da Afirmação $5$ é que o octógono da configuração máxima tem um eixo de simetria.
Ideia 3 (como calcular os quadrados brancos da figura?): Já temos uma figura muito bem definida, mas ainda não está claro como podemos calcular e maximizar a sua quantidade de quadrados brancos. Porém, já podemos facilmente conjecturar o exemplos para $n$ par (se ainda não conseguiu enxergar o exemplo, olhe para a figura abaixo), ela parece fácil de calcular. Se conseguirmos generalizar a configuração máxima (para ganharmos mais liberdade e ainda conseguirmos calcular com certa facilidade a quantidade de quadrados brancos), talvez seja mais fácil primeiro provar que a figura que temos é análoga a essa generalização, e depois provar que a generalização é máxima quando for a figura abaixo. Em resumo, a ideia é que às vezes precisamos dar um passo para trás para dar dois passos para frente.
Para continuar, precisamos da seguinte definição
Definição 2. Um retângulo torto $x\times y$ é um octógono $ABCDEFGH$ de lados horizontais e verticais iguais a 1 que satisfaz as condições anteriores da figura de área máxima (afirmações 4 e 5) e tal que seus outros quatro lados são dois segmentos diagonais paralelos de comprimento $x$ e dois segmentos diagonais paralelos de comprimento $y$.
A figura abaixo ilustra uma possibilidade com $x=4$ e $y=5$.
Definição 3. A área de um retângulo torto $x\times y$ é a quantidade de casas que ele contém (isto é, inclusive aquelas em seu perímetro), ou seja, $xy + (x-1)(y-1)$. A área interna de um retângulo torto $x\times y$ é a quantidade de casas brancas que ele contém (isto é, excluindo as de seu perímetro), ou seja, $(x-1)(y-1)+(x-2)(y-2)$.
É fácil nos convecermos de que as fórmulas acima estão corretas colorindo as casas brancas de azul e vermelho, como em um tabuleiro de xadrez (veja a figura abaixo).
Afirmação 6. Para $n$ par, podemos assumir que a configuração máxima é algum retângulo torto.
Se $AH = DE = BC = GF = 1$, a figura já seria um retângulo torto. Se $AH = DE = BC = GF = 2$ (veja a figura abaixo), ou $AH = DE = 2$ e $BC = GF = 1$ (veja a figura abaixo), basta realizar o movimento ilustrado nas imagens, transformando a figura em um retângulo torto sem diminuir sua área interna (o que é possível devido à simetria já observada da figura máxima).
Note que é preciso tomar cuidado em como transformamos a figura em um retângulo torto, pois podemos acidentalmente diminuir sua área (como mostrado na figura abaixo). Caso isso ocorra, é suficiente mover as casas no sentido oposto, pois, como a figura é simétrica, se a área interna diminuir ao movermos as casas em um sentido, ela aumentará ao movermos as casas no outro sentido. $\blacksquare$
Ideia 3 (continuação): Agora basta só fazer a conta e adaptar o mesmo agurmento para $n$ ímpar, o problema essencialmente já acabou!
Agora, ainda no caso $n$ par e já supondo que a figura máxima seja um retângulo torto $x\times y$, temos de maximixar sua área interna. Assim, temos que
$$n = 2x + 2y – 4$$
e que a área interna da figura vale
$$(x-1)(y-1) + (x-2)(y-2).$$
Pela desigualdade entre as médias, a área interna é máxima quando $x = y = \frac{n+4}{4}$; então, a área interna máxima é menor ou igual que
$$\left\lfloor\left(\frac{n}{4}\right)^2 +\frac{n-4}{4}\right\rfloor.$$
Para $n = 4t$, isso dá $t^2 + (t-1)^2 = 2t^2 – 2t + 1$; para $n = 4t +2$, isso dá $2t^2$.
A seguir, verificamos que esses valores podem ser atingidos quando $n$ for par:
-
Para $n=4t$, tome o retângulo torto $(t+1)\times(t+1)$ como mostrado na figura abaixo. Sua área interna é $t^2 + (t-1)^2 = 2t^2 – 2t + 1$.
área interna máxima quando $n = 4t$. -
Para $n = 4t +2$, pegue o retângulo torto $(t+1)\times(t+1)$ do item anterior, e adicione uma casa preta em $AH$ e outra em $DE$; em seguida, transforme a figura como mostrado na figura abaixo, de modo que ela ganhe $2t -1$ casas brancas. Sua área interna será $2t^2 – 2t + 1 + (2t – 1) = 2t^2$.
área interna máxima quando $n = 4t + 2$.
Afirmação 7. Se $n$ for ímpar, a área interna máxima vale $\left\lfloor \frac{(n-2)^2}{8}\right\rfloor$.
Note que, pelas afirmações 4 e 5, a configuração máxima para $n$ ímpar tem a forma mostrada na figura abaixo ($AH \neq NE$, $BC \neq FG$ e $AB$, $EF$, $HG$, $CD$ estão determinados ou por $DE$ e $AH$ ou por $BC$ e $FG$).
Isso nada mais é do que um retângulo torto $x\times y$ com $y-2$ casas adicionais. Assim,
$$n = 2x + 2y – 3$$
e a área interna vale
$$(x-1)(y-1) + (x-2)(y-2) + y-2$$
$$= (x-1)(y-1) + (x-1)(y-2)$$
$$= (x-1)(2y-3)$$
$$= (x-1)(n-2x).$$
Desconsiderando por enquanto que $x$ é inteiro, queremos encontrar o valor máximo de $f(x) = (x-1)(n-2x)$; derivando, temos $f'(x) = -4x + (n+2) = 0$, logo, $x = \frac{n+2}{4}$. Então, o valor máximo da área interna da figura é menor ou igual que
$$\left\lfloor\left(\frac{n-2}{4}\right)\left(\frac{n-2}{2}\right)\right\rfloor = \left\lfloor\frac{(n-2)^2}{8}\right\rfloor.$$
Se $n = 4t + 1$, a expressão acima dá
$$\left\lfloor\frac{(4t -1)^2}{8}\right\rfloor =\left\lfloor2t^2 – t + \frac{1}{8}\right\rfloor = 2t^2 – t;$$
se $n = 4t + 3$, ela dá
$$\left\lfloor\frac{(4t +1)^2}{8}\right\rfloor=\left\lfloor2t^2 + t + \frac{1}{8}\right\rfloor = 2t^2 + t.$$
Se mostrarmos que há exemplos nesses dois casos, concluiremos que esses são, de fato, os valores máximos.
Para $n=4t+1$, basta pegar a configuração máxima para $4t$, adicionar uma casa e transformar o resultado como mostrado na figura abaixo.
Para $n=4t+3$, basta pegar a configuração máxima para $4t+2$, adicionar uma casa e transformar o resultado como mostrado na figura abaixo.
Isso conclui a afirmação 7 e o problema. $\blacksquare$