FANDOM


Dizer que algo é no máximo igual a $ x $, significa que ele é menor ou igual a $ x $ e existe algum momento que ele pode ser igual a $ x $.

Dizer que algo é no mínimo igual a $ x $, significa que ele maior ou igual a $ x $ e existe algum momento que ele pode ser igual a $ x $.

Uma estratégia interessante para maximizarmos uma quantidade de coisas que satisfazem uma condição é a seguinte: minimizar o que não satisfaz.

Da mesma forma para minimizarmos uma quantidade de coisas que satisfazem uma condição, basta maximizarmos a quantidade de coisas que não satisfazem.

Exemplo (Cone Sul 2000) Editar

Em um tabuleiro $ 8 \times 8 $ distribuímos os inteiros de $ 1 $ a $ 64 $, um em cada casa. A seguir, colocam-se sobre o tabuleiro fichas quadradas $ 2 \times 2 $, que cobrem exatamente quatro casas (sem superposição) e de modo que os quatro números cobertos por cada ficha determinem uma soma menor que $ 100 $.

Mostrar uma distribuição desses inteiros que permita colocar o maior número de fichas, e demonstrar que não é possível obter uma distribuição que permita colocar mais fichas.

Solução: É importante focar: é você quem escolhe a distribuição dos números! Dá para preencher todo o tabuleiro? Se isso fosse possível, então

$ 1+2+\dots+64<100.64, $

o que não é verdade. Logo, não é possível preenchermos todo o tabuleiro. Façamos o número de fichas que ficam de fora ser mínimo. Se deixamos para fora números "grandes", conseguimos usar uma quantidade maior de fichas (pois conseguimos mais números cuja soma é menor que $ 100 $).

Ou seja, a cada ficha a menos que colocamos, devemos fazer com que os números que ficariam nessa ficha tenham a maior soma possível. Por causa disso, a primeira ficha que deixamos de fora, terá os números $ 64,63,62,61 $. Já a segunda terá os números $ 60,59,58,57 $ e assim por diante. Devemos fazer isso até que a soma de todos os cartões restantes seja menor que $ 100 $.

Vamos usar um pouco mais de álgebra para entender isto melhor. Se $ n $ é a quantidade de fichas retiradas, as outras $ 16-n $ fichas devem possuir cada números cuja soma é menor que $ 100 $, ou seja, a soma dos números cobertos pelas fichas deverá ser menor que $ 100(16-n) $.

Mas quais números serão cobertos pelas fichas depois de tirarmos $ n $ fichas? Observe que ao retirarmos a $ n $-ésima ficha, teremos deixado de fora os números $ 64-4n+4,64-4n+3,64-4n+2,64-4n+1 $. Com isso, após tirarmos $ n $ fichas, teremos os números $ 1,2,\dots,64-n $. Com a soma deles deve ser menor que $ 100(16-n) $:

$ 1+2+\dots+(64-4n)<100(16-n) \Leftrightarrow \frac{(64-4n)(65-4n)}{2}<100(16-n) \Leftrightarrow $

$ \Leftrightarrow 4n^2-79n+240<0. $

Então $ 3,75<n<16 $. Queremos $ n $ mínimo, ou seja, $ n=4 $. Mas realmente dá para ter uma solução com $ 16-4=12 $ fichas? Sim, basta tomarmos as fichas que cobrem os números:

$ 1,24,25,48 $

$ 2,23,26,47 $

$ \dots $

$ 12,13,36,37 $,

isto é, as fichas terão os números $ 1+k,24-k,25+k,48-k $ para $ k=0,1,\dots,11 $.

ConeSul2000q2

Exemplo (Cone Sul 2002) Editar

Considere o conjunto $ A=\{1,2,\dots,n\} $. Para cada inteiro $ k $, seja $ r_k $ a maior quantidade de elementos distintos de $ A $ que podemos escolher de maneira que a diferença entre dois números escolhidos seja sempre diferente de $ k $. Determine o maior valor possível de $ r_k $, onde $ 1 \leq k \leq \frac{n}{2} $.

Solução: Vamos analisar pequenos casos.

1º Caso: $ A=\{1,2,3,4,5,6,7,8\} $

Comecemos calculando $ r_1 $. Dá para pegar quatro números cuja diferença é diferente de $ 1 $: $ 1,3,5 $ e $ 7 $. Mas dá para pegar $ 5 $ ou mais? Não! De fato, se pegarmos um número, não podemos pegar o seu antecessor e nem seu sucessor. Logo, $ r_1=4 $.

E quanto a $ r_2 $? Observe que conseguimos escolher quatro número cuja diferença entre quaisquer dois deles é diferente de $ 2 $: $ 1,2,5 $ e $ 6 $. Dá para pegar mais do que quatro números? Não! Para vermos isto, vamos separar os números em pares $ \{1,3,5,7\} $ e $ \{2,4,6,8\} $. Observe que não podemos pegar dois números consecutivos de algum conjunto. Desta forma, podemos escolher no máximo dois de cada conjunto, ou seja, podemos pegar no máximo quatro números cuja diferença entre quaisquer dois deles é diferente de $ 2 $. Desta forma, $ r_2=4 $.

Calculemos $ r_3 $. Podemos escolher cinco números cuja diferença entre quaisquer deles é diferente de $ 3 $: $ 1,2,3,7,8 $. E mais do que cinco, dá? Para explorarmos isto, vamos repartir o conjunto $ \{1,2,3,4,5,6,7,8\} $ nos seguintes:

Números com resto $ 0 $: $ \{3,6\} $

Números com resto $ 1 $: $ \{1,4,7\} $

Números com resto $ 2 $: $ \{2,5,8\} $

Como não podemos pegar dois consecutivos de algum conjunto, dá para pegar no máximo $ 1 $ do primeiro conjunto, $ 2 $ do segundo conjunto e $ 2 $ do terceiro. Desta forma, o máximo que podemos pegar é $ 1+2+2=5 $. Com isso, $ r_3=5 $.

Pelo mesmo raciocínio, $ r_4=4 $.

2º Caso: $ A=\{1,2,3,4,5,6,7,8,9\} $

Pelo mesmo raciocínio, $ r_1=5 $, $ r_2=5 $, $ r_3=6 $ e $ r_4=5 $.

3º Caso: $ A=\{1,2,3,4,5,6,7,8,9,10\} $

Pelo mesmo raciocínio, $ r_1=5 $, $ r_2=6 $, $ r_3=6 $, $ r_4=6 $, $ r_5=5 $.

Com pequenos casos, parece que $ r_k $ é no máximo maior ou igual a $ \lfloor \frac{2n}{3} \rfloor $. Comecemos mostrando que $ r_k \leq \frac{2n}{3} $. Depois provaremos que existe $ k $ tal que $ r_k=\lfloor \frac{2n}{3} \rfloor $.

Para isto, o primeiro passo é mostrar que se tomarmos uma lista dos números com certo resto na divisão por $ k $ e esta tiver $ j $ termos, então não podemos pegar mais do que $ \frac{2j}{3} $. Depois disso seremos capazes de mostrar que $ r_k \leq \frac{2n}{3} $. Seja $ x $ a quantidade de números escolhidos. Podemos relacionar $ x $ e $ j $?

Observe que se escolhermos $ x $ números, pelo menos $ x-1 $ terão seus sucessores não escolhidos. Mas se contarmos os $ x $ escolhidos e os $ x-1 $ não poderemos ter mais do que $ j $ termos. Desta forma,

$ x+(x-1) \leq j \Leftrightarrow 2x-1 \leq j. $

Observe que queremos provar que

$ x \leq \frac{2j}{3}. (*) $

Provemos, por enquanto, que isto é verdade para $ x \geq 2 $. De fato, suponha, por absurdo, que $ x>\frac{2j}{3} $, isto é, $ 3x>2j $. Note que

$ j \geq 2x-1 \Leftrightarrow 2j \geq 4x-2. $

Com isso,

$ 3x>4x-2 \Leftrightarrow x<2. $

Contradição. Logo, $ (*) $ está provada para $ x \geq 2 $. Vejamos o que acontece no caso em que $ x=1 $. Neste caso, $ (*) $ equivale a $ j \geq \frac{3}{2} $. Com isso, basta mostrarmos que $ j $ não pode ser igual a $ 1 $. Quando isto acontece? Quando fizermos alguma lista de números com certo na divisão por $ k $ e obtivermos apenas um número. Isto acontece quando $ k>\frac{n}{2} $. De fato, teremos se pegar os números com resto $ 0 $ na divisão por $ k $ aparecerá somente o $ k $. Porém isto contradiz o enunciado.

Desta forma, $ (*) $ é válido para todo $ x $ natural. E agora, como provamos que $ r_k \leq \frac{2n}{3} $? Considere $ a_i $ o máximo de elementos que podemos escolher no conjunto dos números de resto $ i $ na divisão por $ k $, enquanto $ b_i $ sreá o número de elementos que possuem resto $ i $ na divisão por $ k $.

Observe que acabamos de provar que $ a_i \leq \frac{2}{3} $ e além disso $ b_0+b_1+\dots+b_{k-1} = n $. Desta forma,

$ r_k = a_0b_0+a_1b_1+\dots+a_{k-1}b_{k-1} \leq \frac{2}{3}(b_0+b_1+\dots+b_{k-1})=\frac{2n}{3}. $

Com isso, $ r_k \leq \lfloor \frac{2n}{3} \rfloor $.

Resta mostrarmos que existe $ k $ tal que $ r_k = \lfloor \frac{2n}{3} \rfloor $. E para isso, precisamos encontrar um $ k $ que satisfaça essa igualdade. E como? Alguns pequenos casos nos permite suspeitar que $ k=\lceil \frac{n}{3} \rceil $.

Mas como calcular $ r_k $ se não sabemos nada numérico sobre ele? Façamos alguns casos pequenos para ver se conseguimos algo. Parece que se $ k $ é divisor de $ n $, então também divisor de $ r_n $. Mais especificamente,

Lema: Se $ n=mk $, parece que $ r_k=k.\lfloor \frac{m+1}{2} \rfloor $.

Prova: Queremos mostrar que se $ m $ é par, então $ r_k=k.\frac{m}{2} $, enquanto se $ m $ é ímpar, então $ r_k= k.(\frac{m+1}{2}) $.

Vamos separar os números em listas com que contém os números que possuem certo resto na divisão por $ k $. Por exemplo, os números que possuem resto $ 0 $ são $ k,2k,3k,\dots,mk $. Note que desta lista, não podemos escolher dois números consecutivos. Vejamos cada caso.

Se $ m $ for par, então podemos escolher no máximo $ \frac{m}{2} $ números. De fato, ao tomarmos os $ \frac{m+1}{2} $ teríamos pelo menos $ \frac{m}{2} $ não escolhidos (pelo menos $ \frac{m}{2} $ dos sucessores dos escolhidos). Isto nos daria pelo menos $ \frac{m+1}{2}+\frac{m}{2}>m $ números. Absurdo.

Pelo mesmo raciocínio, se $ m $ for ímpar, teremos no máximo $ \frac{m+1}{2} $ números escolhidos.

Desta forma, $ r_k = k\lfloor \frac{m+1}{2} \rfloor $, o que termina a prova do lema.

$ \blacksquare $

Observe que se $ n=1 $, não podemos falar nada sobre $ k $. Vejamos o que acontece quando $ n \geq 2 $. Vejamos que se $ k=\lceil \frac{n}{3} \rceil $, então $ r_k=\lfloor \frac{2n}{3} \rfloor $. Mas quanto vale $ \lceil \frac{n}{3} \rceil $. Ele pode valer $ \frac{n}{3},\frac{n+2}{3} $ e $ \frac{n+1}{3} $ quando $ n $ possui restos $ 0,1 $ e $ 2 $ na divisão por $ 3 $, respectivamente. Vejamos cada caso separadamente.

1º Caso: $ n $ possui resto $ 0 $ na divisão por $ 3 $.

Aqui $ k=\lceil \frac{n}{3} \rceil=\frac{n}{3} $, ou seja, $ n=3k $. Pelo lema anterior,

$ r_k=k.\lfloor \frac{3+1}{2} \rfloor=2k=\frac{2n}{3}=. $

2º Caso: $ n $ possui resto $ 1 $ na divisão por $ 3 $.

Neste caso, $ k=\lceil \frac{n}{3} \rceil=\frac{n+2}{3} $, ou seja, $ n=3k-2 $. Em relação ao caso anterior, temos dois números a menos na lista e assim o número máximo a ser escolhido é 2 a menos que o anterior, isto é,

$ r_k=2k-2=2(\frac{n+2}{3})-2=\frac{2n-2}{3}. $

Para terminarmos, basta verificarmos que $ \lfloor \frac{2n}{3} \rfloor=\frac{2n-2}{3} $. Observe que

$ \lfloor \frac{2n}{3} \rfloor=\lfloor \frac{2(n-1+1)}{3} \rfloor=\lfloor \frac{2(n-1)}{3}+\frac{2}{3} \rfloor=\frac{2(n-1)}{3}+\lfloor \frac{2}{3} \rfloor=\frac{2n-2}{3}. $


3º Caso: $ n $ possui resto $ 2 $ na divisão por $ 3 $.

Neste caso, $ k=\lceil \frac{n}{3} \rceil=\frac{n+1}{3} $, ou seja, $ n=3k-1 $. Em relação ao 1º caso anterior, temos um número a menos na lista e assim o número máximo a ser escolhido é 1 a menos que o anterior, isto é,

$ r_k=2k-1=2(\frac{n+1}{3})-1=\frac{2n-1}{3}. $

Para terminarmos, basta verificarmos que $ \lfloor \frac{2n}{3} \rfloor=\frac{2n-1}{3} $. Observe que

$ \lfloor \frac{2n}{3} \rfloor=\lfloor \frac{2(n-2+2)}{3} \rfloor=\lfloor \frac{2(n-2)}{3}+\frac{4}{3} \rfloor=\frac{2(n-1)}{3}+\lfloor \frac{4}{3} \rfloor=\frac{2n-4}{3}+1=\frac{2n-1}{3}. $