Wiki Olimpédia
Registre-se
Advertisement

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

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

Desta forma, uma maneira de encontrar o máximo de alguma quantidade é mostrar um exemplo para e mostrar que é impossível um exemplo para números maiores do que .

Da mesma maneira, para minimizarmos, basta darmos um exemplo para , mas mostrar que é impossível para números menores do que .

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.

Observação[]

Quando dizemos pelo menos queremos dizer "maior ou igual a ".

Exemplo (Cone Sul 2007)[]

Considere um tabuleiro . São pintadas algumas casas do tabuleiro. Dizemos que o tabuleiro é charrua se nenhuma linha está totalmente pintada e nenhuma coluna está totalmente pintada.

(a) Qual é o número máximo de casas pintadas que um tabuleiro charrua pode ter?

(b) Para tal número , calcular o número de tabuleiros charruas distintos que existem.

Solução:

(a) Como nenhuma coluna está totalmente pintada, cada coluna deve ter no máximo casas pintadas. E já que são colunas, o número de casas pintadas deve ser menor ou igual a . Conseguimos algum exemplo de tabuleiro charrua com esta quantidade de casas? Sim:

ConeSul2007q4

(b) Como iremos pintar casas em cada coluna, devemos escolher qual casa não será pintada. Note que não podemos ter duas casas sem serem pintadas em uma mesma linha, pois teríamos uma linha completamente preenchida.

Na primeira coluna, casas da primeira coluna podem não ser preenchidas. Já na segunda coluna, existem possibilidades, pois não podemos escolher a mesma linha que escolhemos na primeira coluna. Pelo mesmo motivo, existem escolhas na terceira coluna, na quarta e assim por diante.

Desta forma, o número de tabuleiros charruas será

Exemplo (Cone Sul 2010)[]

Marcam-se em uma reta pontos, numerados da esuqerda para a direita. Vários grilos saltam na reta. Cada grilo parte do ponto , salta por pontos marcados e termina no ponto . Além disso, cada grilo sempre ssalta de um ponto marcado a outro ponto marcado com um número maior.

Quando todos os grilos terminam de saltar, notou-se que para cada par com , há um grilo que saltou diretamente do ponto para o ponto , sem pousar em nenhum dos pontos entre eles.

Determine a menor quantidade de grilos para que isso seja possível.

Solução: Precisamos de grilos para os pulos da forma com .

Parece que precisamos de grilos para os pulos da forma com . Porém todos estes fizeram um pulo da forma . Ou seja, um deles já foi contado anteriormente. Logo, precisamos aumentar grilos em nossa contagem.

Parece também que precisamos de grilos para os pulos da forma com . Mas estes fizeram pulos ou da forma ou da forma , que já foram contados. Assim precisamos, neste caso, de grilos.

Se continuarmos repetindo o raciocínio, precisaremos de grilos para os pulos das formas , respectivamente.

E a partir de agora? Todos os grilos conseguem "cobrir" os puloos da forma com e (basta repetirmos o raciocínio anterior).

Portanto, a quantidade mínima de gafanhotos será

Exemplo (Cone Sul 2000)[]

Em um tabuleiro distribuímos os inteiros de a , um em cada casa. A seguir, colocam-se sobre o tabuleiro fichas quadradas , 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 .

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

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 ).

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 . Já a segunda terá os números e assim por diante. Devemos fazer isso até que a soma de todos os cartões restantes seja menor que .

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

Mas quais números serão cobertos pelas fichas depois de tirarmos fichas? Observe que ao retirarmos a -ésima ficha, teremos deixado de fora os números . Com isso, após tirarmos fichas, teremos os números . Com a soma deles deve ser menor que :

Então . Queremos mínimo, ou seja, . Mas realmente dá para ter uma solução com fichas? Sim, basta tomarmos as fichas que cobrem os números:

,

isto é, as fichas terão os números para .

ConeSul2000q2


Exemplo (Cone Sul 2013)[]

Seja o conjunto dos números inteiros de até inclusive. A cada um dos subconjuntos de atribuímos uma das cores disponíveis, com a condição de que, se dois conjuntos distintos e cumprem que , então aos conjuntos e são atribuídas cores distintas. Qual é o menor valor possível que pode ter ?

Solução: Vamos começar mostrando que precisamos de pelo menos cores. Para isto, tomaremos conjuntos: o conjunto e os subconjuntos de que possuem elementtos.

A união de quaisquer dois deles é o próprio conjunto . Desta forma, não pode haver quaisquer dois conjuntos nesta lista com a mesma cor. Com isso, precisamos de pelo menos cores.

Para terminarmos, basta conseguirmos fazer uma coloração com cores. Faremos isto da seguinte maneira: considere o conjunto de todos os subconuntos de que não contém (para ).

Vamos pintar os conjuntos (nesta ordem) da seguinte forma: o conjunto receberá a cor . Porém, quando um conjunto tiver a cor e você pintá-lo com a cor , então ele passará a ter a cor .

No final das colorações, um conjunto terá a cor se, e somente se, o maior elemento que não pertence a for .

Desta forma, se dois conjuntos possuem a cor , então a união deles não pode ser , pois não pertencerá a união (já que não pertence a nenhum dos dois conjuntos).

E quanto a cor do conjunto (que possui todos os elementos)? Basta pintá-lo com uma ª cor. Desta forma, existe uma coloração com cores, o que faz desta a quantidade mínima.

Exemplo (OBM 2011 - 3ª Fase - Nível 3)[]

Um álbum, composto por figurinhas, está sendo colecionado por amigos. Uma distribuição de figurinhas entre os amigos é incompleta quando existe pelo menos uma figurinha que nenhum dos amigos tem. Determinar o menor valor de com a seguinte propriedade: toda distribuição de figurinhas entre os amigos tal que, para quaisquer dois amigos, faltam, para ambos, pelo menos figurinhas em comum, é incompleta.

Solução: Para nos organizarmos melhor, vamos chamar uma distribuição que não é incompleta de completa. Provaremos que o menor valor possível de é . Para isso, vamos mostrar que se for menor ou igual a , então a propriedade do enunciado não será válida. Depois, para mostrarmos que para igual a a propriedade do enunciado funciona.

1ª Parte: Mostrar que para igual a a propriedade do enunciado não funciona

Para provarmos isto, basta encontrarmos uma distribuição completa com , ou seja, de forma que quaisquer dois amigos não tenham pelo menos figurinhas em comum. Observe que, como há figurinhas, eles não terem pelo menos figurinhas em comum equivale a dizer que eles possuem, no máximo, figurinhas diferentes. Ou seja, ao menos devemos tomar cuidado de que, na distribuição, os dois amigos que mais tiverem figurinha não tenham mais do que figurinhas juntos.

Observe que dividido por e sobra . Ou seja, algum deles deve ficar com pelo menos figurinhas, pois se todos ficassem com sobrariam . Das figurinhas que sobram nessa divisão, não podemos dar mais do que uma extra para algum amigo. Por isso, é interessante dar figurinhas para vários amigos. Faremos a seguinte distribuição então: figurinhas diferentes para cada um de amigos e para o outro amigo. Note que já distribuímos as figurinhas nessa distribuição, já que .

Se compararmos um amigo de figurinhas com um de , eles não possuem ao todo figurinhas. Da mesma forma , se compararmos dois de , veremos que figurinhas que eles não possuem.

2ª Parte: Mostrar que não pode ser menor do que

Em outras palavras, mostrar que existe uma distribuição completa em que quaisquer dois amigos não têm pelo menos figurinhas (com menor do que ) . Mas isso significa que o número máximo de figurinhas que eles possuem é menor do que um número maior do que (que corresponde a ). Isso já acontece na distribuição da primeira parte. Desta forma, não pode ser menor do que .

3ª Parte: Mostrar que pode ser

Para isso, vamos mostrar que toda distribuição de figurinhas entre os amigos tal que, para quaisquer dois amigos, faltam, para ambos, pelo menos figurinhas em comum, é incompleta. Tomemos uma distribuição qualquer. Vamos mostrar que ela é incompleta. A ideia aqui é a seguinte: se mostrarmos que o máximo de figurinhas diferentes que todos os amigos podem ter juntos é um número menor do que , então a distribuição é necessariamente incompleta.

Vejamos dois amigos: qual é o número máximo de figurinhas diferentes que eles podem ter. Como a quantidade de figurinhas que eles não tem juntos aqui é pelo menos , segue que no máximo eles possuem figurinhas. Mas isso não parece nos ajudar muito a concluir sobre o total de figurinhas de todos os amigos.

Por isso, vamos pensar em três amigos juntos. Digamos que as quantidades de figurinhas diferentes de cada um sejam , e . Como a quantidade máxima de figurinhas de dois deles juntos é , podemos concluir que


Ao somarmos estas três desigualdades,

Como , e são inteiros, segue que . Ou seja, três amigos têm juntos, no máximo, figurinhas.

Divida todos os amigos em grupos de três amigos cada. No final, a quantidade diferente máxima de figurinhas que eles devem ter é . Isso é menor do que . Desta forma, a distribuição deverá ser necessariamente incompleta.

Portanto, o menor valor que pode assumir é .

Exemplo (OBM 2006 - 3ª Fase - Nível 3)[]

Seja um inteiro, . Definimos como a maior quantidade possível de triângulos isósceles cujos vértices pertencem a algum conjunto de pontos do plano sem três pontos colineares. Prove que existem constantes positvas e tais que , para todo inteiro, .

Solução: Vamos começar provando que existe que satisfaz as condições do enunciado. Para isso, vamos começar mostrando que é menor do que uma certa expressão do segundo grau. Como podemos fazer aparecer uma? Observe que para formarmos um segmento devemos escolhers dois pontos entre os e podemos fazer isto de maneiras. Como isso pode se relacionar com a quantidade de triângulos isósceles?

Observe que a base de um triângulo isósceles deve ser um desses segmentos. Se soubermos a quantidade máxima de triângulos isósceles que podemos formar tendo como base um desses segmentos, podemos limitar a quantidade de triângulos isósceles. Veremos que não podemos ter três triângulos isósceles com base em um mesmo segmento. Suponha, por absurdo, que isso seja possível. Note que um vértice oposto à base deve pertencer à mediatriz dela (justamente por ser equidistante). Se tivéssesmos três desses pontos, eles pertenceriam à mediatriz e teríamos três pontos colineares. Absurdo. Logo, só deve existir dois triângulos isósceles no máximo cuja base seja um segmento formado pelos vértices do problema. Desta forma,

Esta última desigualdade se deve ao fato de que . Logo, basta tomarmos para satisfazer as condições do enunciado.

Mostraremos agora que existe satisfazendo as condições do enunciado. Para isto, devemos encontrar uma expressão do segundo grau que é sempre menor do que o máximo. Observe que se encontrarmos um exemplo com uma certa quantidade de triângulos isósceles, esta quantidade será menor do que o máximo. Dividiremos nossa análise em dois casos: quando é ímpar e depois quando é par.

1º Caso: é ímpar

Vamos escolher este exemplo de forma que seja fácil de se mexer: quando os vértices formam um polígono regular. Encontraremos uma expressão do segundo grau de forma que o número de triângulos isósceles nesta configuração seja maior do que ela. Assim será maior do que essa quantidade. Contaremos nos baseando em cada vértice. Em cada um, quantos são os triângulos isósceles que possuem ele como vértice oposto à base.

Para entender melhor isto, vejamos este exemplo com um polígono regular de lados:

OBM2006q2n3

Quais são os triângulos isósceles que possuem como vértice oposto à base? São quatro: , , e . Ou seja, para o vértice existem pares de vértices equidistantes: , , e .

Vamos pensar no caso geral: em um polígono de lados. Escolha um vértice qualquer. Para ele, existem pares de vértices de forma que cada par é formado por dois vértices equidistantes ao escolhido (observe que é inteiro, pois é ímpar e assim é par). Com efeito, para encontrarmos um par, basta andarmos vértices para o sentido horário e para o anti-horário. Além disso, como existem outros vértices além do escolhido, teremos pares de vértices.

Quem garante que não existe nenhum outro par de vértices além desses? Suponha que seja o ponto escolhido e que seja um par de vértices equidistantes a . Se existisse outro vértice, digamos tal que , então existirá uma circunferência de centro que passa por , e . Observe que a circunferência circunscrita ao polígono também passa por esses três pontos. Mas dados três pontos não colineares, existe apenas uma única circunferência que passa por eles. Isso não pode acontecer, pois uma delas não passa por , mas a outra passa. Absurdo. Logo, esses são os únicos pares possíveis.

Como são vértices e triângulos isósceles para cada, significa que a quantidade de triângulos isósceles é ? Não! Por exemplo, volte na figura do eneágono que demos como exemplo. Observe que lá o triângulo é equilátero e assim ele foi contado vezes (uma vez para cada vértice).

Se todos os triângulos fosse contados três vezes, então a quantidade de triângulos equiláteros seria . Mas alguns não são. Logo a quantidade de triângulos isósceles neste caso é maior do que e assim

Para terminarmos este caso, precisamos encontrar tal que

para todo . Vamos isolar :

Como (e assim ) e com isso o último membro da expressão acima é maior ou igual a . Desta forma, qualquer que seja menor que funciona.

2º Caso: é par

Podemos aproveitar o caso que fizemos anteriormente. Para isso montaremos um polígono regular de lados e um ponto no centro. Vamos descobrir uma quantidade de triângulos isósceles menor do que a formada por esses pontos (em uma expressão do segundo grau) e aí será maior do que essa expressão.

Já sabemos, pelo caso anterior, que o polígono de forma mais do que triângulos isósceles. Quantos triângulos isósceles ganhamos com este ponto extra no centro? Repare que se ligarmos o centro com vértices, teremos segmentos e quaisquer dois destes formam um triângulo isósceles (pois todos eles possuem a mesma medida). Podemos fazer esta escolha de maneiras. Desta forma,

Queremos encontrar tal que

para todo (já que , porém par). Vamos isolar . Se dividirmos ambos os lados da igualdade por ,

Logo, isto serve para qualquer .

Para satisfazer os dois casos, basta tomarmos qualquer que seja menor que (ele também irá satisfazer o segundo caso já que todo número menor que também é menor que ).

Exemplo (OBM 2007 - 3ª Fase - Nível 3)[]

Dados números reais , suponha que todo número real ocorre no máximo duas vezes entre as diferenças , com . Prove que há pelo menos números reais que ocorrem exatamente uma vez entre tais diferenças.

(Dica: Você pode saber mais sobre aqui.)

Solução: O que fazer com ? Observe que se é par (pois é inteiro) e se é ímpar. De fato, se é ímpar, então é par e assim é inteiro. Com isso,

.

Desta forma, vale a pena dividir em dois casos: o que é par e o que ele é ímpar. Façamos aqui o caso em que é par (o caso em que ele for ímpar será análogo).

Para organizar o nosso raciocínio, vamos considerar para . Observe que todos os elementos deste conjunto são distintos. De fato, se e são distintos, então e também serão e o mesmo ocorre para e . Portanto, para resolvermos o problema, precisamos determinar a quantidade de números que aparecem em exatamente um dos 's.

Observe que um elemento pode aparecer apenas em um ou dois conjuntos 's. Sejam e a quantidade de elementos que aparecem em um e dois conjuntos, respectivamente. Para sabermos a quantidade de elementos que aparecem em um conjunto, basta somarmos a quantidade de elementos dos e subtrairmos para cada elemento que aparece duas vezes (já que estamos excluindo eles da contagem, precisamos excluir duas vezes). Ou seja,

Observe que, pela definição, . Então

Note que para minimizarmos , precisamos maximizar .

Por isso, é interessante explorar as intersecções. Como as diferenças aparecem no máximo duas vezes, parece que as intersecções não possuem tantos elementos assim. Na verdade, podemos provar que nelas existem no máximo um elemento. Com efeito, considere e suponha, por absurdo, que tenha pelo menos dois elementos.

Então um deles pode ser escrito da forma e também da forma . O outro das formas e , para distintos. Desta forma,

e

Asssim , ou seja, uma diferença aparece três vezes distintas. Absurdo. Logo, pode ter no máximo um elemento.

Agora podemos ter mais controle sobre os que aparecem duas vezes. E para nos organizarmos, faremos uma tabela (justificaremos as contas que aparecem nela a seguir).

ConjuntoQuantidade de elementosReais que Aparecem em Conjuntos de Índice Menor
Menor ou igual a
Menor ou igual a
Menor ou igual a
Menor ou igual a
Menor ou igual a

Faremos a contagem da seguinte forma: começaremos de e chegaremos até . Para entendermos a segunda coluna, basta lembrarmos que . Na terceira coluna relativa ao conjunto colocaremos a quantidade de elementos dele que podem ter aparecido nos conjuntos de índice menor. Vamos determinar esta quantidade.

Vamos dividir em casos. Comecemos com o que . Observe que isto equivale a dizer que (pois ). Como aparece no máximo um elemento em dois conjuntos ao mesmo tempo e existem conjuntos de índices menores que o de , segue que a quantidade de elementos de que já apareceram em conjuntos de índices menores é menor ou igual a .

Já no caso em que (que equivale a , a gente pode até dizer que a quantidade de elementos de que aparecem em conjuntos de índices menores é menor ou igual a . Mas dizer que essa quantidade de elementos é menor do que é ainda mais preciso. É isso que está na terceira coluna para . Com isso, terminamos de explicar a tabela.

Com isso, a quantidade de elementos que aparecem duas vezes nos conjuntos será menor ou igual à soma dos números que estão na terceira coluna, ou seja,

Se voltarmos a ,

Isto prova o caso em que é par. O caso em que é ímpar é totalmente análogo.

Exemplo (Cone Sul 2002)[]

Considere o conjunto . Para cada inteiro , seja a maior quantidade de elementos distintos de que podemos escolher de maneira que a diferença entre dois números escolhidos seja sempre diferente de . Determine o maior valor possível de , onde .

Solução: Vamos analisar pequenos casos.

1º Caso:

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

E quanto a ? Observe que conseguimos escolher quatro número cuja diferença entre quaisquer dois deles é diferente de : e . Dá para pegar mais do que quatro números? Não! Para vermos isto, vamos separar os números em pares e . 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 . Desta forma, .

Calculemos . Podemos escolher cinco números cuja diferença entre quaisquer deles é diferente de : . E mais do que cinco, dá? Para explorarmos isto, vamos repartir o conjunto nos seguintes:

Números com resto :

Números com resto :

Números com resto :

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

Pelo mesmo raciocínio, .

2º Caso:

Pelo mesmo raciocínio, , , e .

3º Caso:

Pelo mesmo raciocínio, , , , , .

Com pequenos casos, parece que é no máximo maior ou igual a . Comecemos mostrando que . Depois provaremos que existe tal que .

Para isto, o primeiro passo é mostrar que se tomarmos uma lista dos números com certo resto na divisão por e esta tiver termos, então não podemos pegar mais do que . Depois disso seremos capazes de mostrar que . Seja a quantidade de números escolhidos. Podemos relacionar e ?

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

Observe que queremos provar que

Provemos, por enquanto, que isto é verdade para . De fato, suponha, por absurdo, que , isto é, . Note que

Com isso,

Contradição. Logo, está provada para . Vejamos o que acontece no caso em que . Neste caso, equivale a . Com isso, basta mostrarmos que não pode ser igual a . Quando isto acontece? Quando fizermos alguma lista de números com certo na divisão por e obtivermos apenas um número. Isto acontece quando . De fato, teremos se pegar os números com resto na divisão por aparecerá somente o . Porém isto contradiz o enunciado.

Desta forma, é válido para todo natural. E agora, como provamos que ? Considere o máximo de elementos que podemos escolher no conjunto dos números de resto na divisão por , enquanto sreá o número de elementos que possuem resto na divisão por .

Observe que acabamos de provar que e além disso . Desta forma,

Com isso, .

Resta mostrarmos que existe tal que . E para isso, precisamos encontrar um que satisfaça essa igualdade. E como? Alguns pequenos casos nos permite suspeitar que .

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

Lema: Se , parece que .

Prova: Queremos mostrar que se é par, então , enquanto se é ímpar, então .

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

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

Pelo mesmo raciocínio, se for ímpar, teremos no máximo números escolhidos.

Desta forma, , o que termina a prova do lema.

Observe que se , não podemos falar nada sobre . Vejamos o que acontece quando . Vejamos que se , então . Mas quanto vale . Ele pode valer e quando possui restos e na divisão por , respectivamente. Vejamos cada caso separadamente.

1º Caso: possui resto na divisão por .

Aqui , ou seja, . Pelo lema anterior,

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

Neste caso, , ou seja, . 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 é,

Para terminarmos, basta verificarmos que . Observe que


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

Neste caso, , ou seja, . 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 é,

Para terminarmos, basta verificarmos que . Observe que

Exemplo (OBM 1998 - 3ª Fase - Nível 3)[]

Dois matemáticos, perdidos em Berlim, chegam à esquina da rua Barbarossa com a rua Martin Luther, e precisam chegar à esquina da rua Meininger com a rua Martin Luther. Infelizmente eles não sabem para que lado fica a rua Meininger, nem a que distância ela está, logo são obrigados a ir e voltar ao longo da rua Martin Luther até chegarem à esquina desejada.

Qual é o menor valor para o número positivo tal que eles podem ter certeza de que se há quarteirões (ou quadras) entre as ruas Barbarossa e Meininger então eles conseguem chegar ao destino andando no máximo quarteirões (ou quadras)?

Solução: Nesta solução, vamos considerar o caso em que os matemáticos não se separam. Como os matemáticos não sabiam para que lado nem a que distância estava a rua Meininger, eles deveriam usar a seguinte estratégia: andar quarteirões para algum lado (digamos direito) e depois voltar ao ponto inicial, andar para a esquerda (e voltar ao ponto inicial), para a direita (e voltar ao ponto inicial), para a esquerda (e voltar ao ponto inicial) e assim por diante.

Observe que, se alguém andar para alguma direção alguma vez uma certa quantidade de quarteirões, na próxima vez, deverá andar mais quarteirões ainda, já que sabe quais são as ruas por onde já passou. Por isso, (quantidades de quarteirões andadas para a direita) e (quantidade de quarteirões andadas para a direita).

A estratégia aqui será a seguinte: queremos falar sobre o máximo de quarteirões que eles andaram. Para isto, iremos maximizar o pior caso (ou seja, o que eles andaram mais), pois assim os outros casos já terão sido maximizados também.

Os piores casos são quando a Meininger está a quarteirões à direita do ponto inicial (ou seja, eles quase chegaram quando andaram quarteirões, mas tiveram que andar mais quarteirões à toa) ou à esquerda, com natural. Em ambos os casos, entre o ponto inicial e o destino há quarteirões. Neles, a quantidade de quarteirões que os matemáticos irão andar é

Queremos encontrar tal que se há quarteirões (ou quadras) entre o ínicio e onde eles querem chegar então eles a quantidade de quarteirões que eles irão andar é no máximo . Note que a quantidade de quarteirões que eles andam aqui é . Desta forma,

Se fizermos , então

Provaremos que o é mínimo: primeiro daremos um exemplo para e depois mostraremos que é impossível ter . Um caso em que é quando para todo natural. Aqui, como teremos a soma de uma progressão geométrica,

Resta provarmos que não podemos ter . Suponha, por absurdo, que isto aconteça. Para facilitar a escrita, consideremos em que (observe que ). Então

Mas como mexer nessa conta se ela tem e ? Basta observarmos que . Assim

Vamos "eliminar" esse que está no lado direito da desigualdade nos atrapalhando. Para isto, façamos . Assim

Temos uma coisa chata aqui, pois aparecem três termos da sequência: e . Para eliminarmos um deles, uma boa maneira é considerarmos (já veremos o porquê disto). Mas quem garante que não estamos dividindo por zero?

Vejamos que é positivo para . Para isto é suficiente mostrarmos que . Observe que , e , de onde segue que para ,

Logo pode ser definido para (repare que nesta definição ). Neste caso, se dividirmos ambos os lados de por ,

Agora sim, podemos trabalhar apenas com dois termos: e . Observe que esta desigualdade só vale para , pois só aí podemos falar de . Antes de continuarmos as nossas contas, provaremos o seguinte: . Para isto, vamos subtrair em ambos os lados de

Se usarmos o método de completar quadrados no lado direito da desigualdade

Qual a vantagem de termos feito isto? É que todo número elevado ao quadrado é maior ou igual a zero e isto nos ajuda a simplificar as contas. De fato, se usarmos isto

A última desigualdade vem dos seguintes fatos: , além de (para vermos isto basta usarmos a definição de e que ) e . Desta forma,

para todo . E o que ganhamos com isto? Observe que para vale que e assim ao voltarmos em (e considerarmos que ),

Se usarmos esta desigualdade, mas no lugar do usarmos e combinarmos todas elas

Observe que, no lado direito desta desigualdade, é negativo. Ou seja, quanto maior o valor de , menor o valor do lado direito da desigualdade. Assim para suficientemente grande ele ficará negativo. De fato, se , então o lado direito da desigualdade é negativo, ou seja, também é. Mas isto é uma contradição. Logo, não podemos ter . Assim o menor valor para é .

Exemplo (OBM 1999 - 3ª Fase - Nível 3)[]

Temos um tabuleiro quadrado .

Desejamos colocar peças em casas do tabuleiro de tal forma que não existam peças formando um retângulo de lados paralelos aos lados do tabuleiro.

Determine o maior valor de para o qual é possível fazer esta construção.

Solução: Vamos escolhar uma boa notação para lidar com este problema. Para isto iremos usar conjuntos. Considere conjuntos que funcionarão da seguinte forma: o número pertence a se, e somente se, existe uma peça na -ésima linha e -ésima coluna. Como existem dez colunas, segue que todos estes conjuntos estão contidos em .

Lembre-se: queremos maximizar o número de peças. Como podemos encontrar este número em função do que já temos? Considere a quantidade de elementos de . Observe que não é nada menos do que a quantidade de peças da linha (qualquer coisa, faça um tabuleiro pequeno para você conferir). Então a quantidade total de peças do tabuleiro é

É este valor que devemos maximizar. Mas como lidar podemos lidar com o fato de que não podem existir retângulos usando a ideia de conjuntos? Analisemos o caso abaixo em que as figuras formam um retângulo.

OBM1999q3n3

Nela, tanto quanto pertencem a e , ou seja, é subconjunto de e . Assim a distribuição não tem retângulos se, e somente se, e possuem no máximo um elemento em comum (para diferente de ).

Desta forma, observe que possui subconjuntos de dois elementos. Nenhum desses pode ser subconjunto de outro conjunto (para diferente de ). Observe também que possui subconjuntos. Desta forma, a quantidade de subconjuntos totais de não pode ser maior do que , isto é,

Se soubermos alguma maneira estratégica de colocar mais peças sem aumentar esta soma, podemos a partir dai encontrar o máximo de peças. Uma maneira de fazermos isto (relaxa vamos provar o porquê) é para quaisquer e o seguinte: . Com efeito, suponha, por absurdo, que . Veremos que, neste caso, a soma em fica maior do que se pegarmos aumentarmos se tomarmos e com e elementos, respectivamente (isto é, aproximarmos a quantidade de elementos dos dois sem alterar a quantidade de peças). De fato,

Como a última é verdadeira, logo a primeira é verdadeira. Assim para maximizarmos a quantidade de peças precisamos ter para quaisquer e . Desta forma, existem alguns conjuntos 's com elementos e outros com . Chamaremos de a quantidade de conjuntos com elementos, de onde segue que terão elementos.

Repare que o caso não maximiza o número de peças. Por isso, vamos considerar aqui que seja maior do que (isto vai acontecer para que exista).

A soma da quantidade de subconjuntos dos 's será

Lembre-se que, por esta expressão acima deve ser menor ou igual a . Vejamos que, por causa disso, não deve tão grande assim.

Suponha que . Da expressão em e pelo fato de que podemos garantir que

Desta forma, devemos ter . Como já eliminamos o caso em que sobra para analisarmos os casos em que e .

Comecemos analisando o caso em que . Vejamos qual a quantidade máxima de peças neste caso e a soma das quantidades de subconjuntos dos . Vamos começar por esta última. Pela expressão que aparece em e pelo fato de que ,

Nunca chega a . Parece que este caso não maximiza, pois não usa todas as intersecções possíveis. Aliás, a soma da quantidade de peças deste caso é

Se o caso nos der alguma possibilidade com mais de peças, nem precisamos olhar para o caso em que . Olhemos então para o caso em que . Pela expressão em , a soma das quantidades de subconjuntos dos 's será

Mas por , esta quantidade é menor ou igual a . Desta forma

Com isso, podemos dizer sobre a quantidade de peças que

Será que conseguimos um exemplo com peças? Observe que, acima, a igualdade vale se, e somente se, , ou seja, quando existem conjuntos 's com elementos e com elementos. Neste caso, quanto vale a soma das quantidades de subconjuntos dos 's? Se voltarmos a ,

Desta forma, todo subconjunto de de dois elementos deve estar contido em exatamente um .

Observe que se um número pertence a um conjunto de elementos, então ele está junto de outros dois números, enquanto se ele estiver em um de , ele estará junto com outros três. Sejam e a quantidade de conjuntos de e elementos, respectivamente, que ele pertence. Como cada número está no mesmo conjunto que cada um dos outros nove exatamente uma vez, segue que

Já que queremos apenas as soluções inteiras, podemos pensar nisto como sendo uma equação diofantina. Observe que , de onde segue que e como , podemos concluir que . Além disso, como , segue que , ou seja, . Os únicos múltiplos de não negativos menores ou iguais a são e . Desta forma, as soluções da equação são e .

Será que para todos os números devemos ter e , isto é, eles devem aparecer três vezes em conjuntos de elementos e uma vez em conjuntos de ? Se isto ocorresse, todos os conjuntos de teriam ao todo elementos. Porém existem cinco conjuntos de elementos e eles possuem ao todo elementos. Desta forma, existe algum número em que e , isto é, que não aparece em conjuntos de elementos e aparece três vezes em conjuntos de .

Vamos supor, sem perda de generalidade, que este número é o e que , e . Além desses, existem outros dois conjuntos de quatro elementos. Vamos chamar um desses de . Se lembrarmos do fato de que a intersecção entre quaisquer dois 's distintos deve ter no máximo um elementos, segue que deve ter no máximo um elemento em comum com cada um dos conjuntos e , ou seja, deve ter no máximo elementos. Absurdo.

Portanto, é impossível um exemplo com peças. E com é possível? Sim:

OBM1999q3n31

Desta forma, o máximo de peças possível é .

Estimativas[]

Exemplo (IMO 2001)[]

Vinte e uma garotas e vinte um garotos participaram de um concurso de matemática.

  • Cada participante resolveu no máximo seis problemas.
  • Para cada garota e cada garoto, pelo menos um problema foi resolvido por ambos.

Prove que existe algum problema que foi resolvido por pelo menos três garotas e pelo menos três garotos.

Solução: Por que este problema está nesse artigo? Observe que dizer que ele foi resolvido por pelo menos três garotas e pelo menos três garotos é o mesmo que dizer que ele foi resolvido por no mínimo três garotos e no mínimo três garotas.

Vamos chamar um problema de difícil para garotos se no máximo garotos resolveram. Analogamente, podemos definir problemas difíceis para garotas. Nosso problema consiste em mostrar que existe um problema que não é difícil nem para garotos e nem para garotas.

Uma maneira de fazermos isso é calcularmos a quantidade de pares tais que algum deles resolveu um problema difícil para garotos junto com a quantidade de pares em que algum deles resolveu algum problema difícil para garotas. Se mostrarmos que existe algum par que não está nessas condições, ou seja, existir um par em que nenhum deles resolveu um problema difícil para garotos ou para garotas, o problema estará resolvido (afinal, para cada par, existe um problema resolvido).

Uma maneira de fazermos isso, é calcularmos fazermos uma estimativa: se mostrarmos que a quantidade de pares em que algum deles resolveu um problema difícil para garotos ou para garotas é menor do que a quantidade total de pares , então existirá algum par em que eles resolveram um problema que não é difícil nem para garotos e nem para garotas.

Observe que a quantidade de pares é (já que existem garotos e garotas). E quanto a quantidade de pares em que eles resolveram algum problema difícil para garotos? Uma maneira de fazermos isso seria

  • escolhermos uma garota (que pode ser feito de maneiras);
  • descobrir a quantidade máxima de problemas que essa essa garota resolveu que são difíceis para garotos
  • multiplicar por (já que cada problema foi resolvido por no máximo garotos).

Portanto, vale a pena correr atrás da quantidade máxima de problemas que essa garota resolveu que são difíceis para garotos. Se para uma garota, dos seus problemas resolvidos forem difíceis para garotos, então a quantidade de garotos que resolveram o mesmo problema que ela é menor ou igual a . Logo a quantidade de problemas que essa garota resolveu que são difíceis para garotos é menor ou igual a .

Desta forma, a quantidade de pares em que eles resolveram algum problema difícil para garotos é menor do que . Analogamente, a quantidade de pares em que eles resolveram algum problema difícil para garotas também é menor do que . Portanto, a quantidade de pares em que eles resolveram algum problema difícil para garotos ou garotas é .

Só que a quantidade de pares é . Desta forma, existe pelo menos um par em que nenhum deles resolveu um problema difícil para garoto ou para garota, ou seja, existe algum problema que foi resolvido por pelo menos três garotas e pelo menos três garotos.

Indução[]

Você pode saber mais sobre isso aqui.

Exemplo (OBM 2003 - 3ª Fase - Nível 3)[]

Seja um conjunto de elementos. Determine o menor inteiro positivo com a seguinte propriedade: dados quaisquer subconjuntos disjuntos de , existe uma escolha adequada dos sinais e de modo que , onde e é o complementar de em relação a .

Solução: Consideremos a menor quantidade de subconjuntos que satisfaz as condições do enunciado para determinado (este sendo a quantidade de elementos de ). Mostraremos que .

Como podemos mexer com essa parte inteira aqui? Lembre-se que para qualquer número real , se encontrarmos inteiro tal que , poderemos concluir que . Desta forma, se encontrarmos inteiro tal que , podemos reescrever esta desigualdade como (basta aplicarmos o logaritmo na base em todos os membros) e concluir que .

Desta maneira, a ideia da prova será a seguinte: tomaremos um natural tal que e provaremos que . Esta prova será feita em duas partes:

1ª Parte: Mostraremos que

2ª Parte: Provaremos que .

Como é natural, poderemos concluir que .

Vamos começar pela 1ª Parte. Para provarmos que , basta vermos que conjuntos sempre irão satisfazer as condições do enunciado. Para isto, vamos mostrar por indução em que se , então para quaisquer subconjuntos de , podemos escrever . Afinal, como , com o resultado, poderemos concluir que para quaisquer subconjuntos de , podemos escrever . Como é a menor quantidade possível, isto nos permite concluir que . Vamos então para a indução em .

Comecemos com o caso em que , ou seja, com , ou seja, . Basta provarmos aqui que para qualquer subconjunto de vale ou . Observe que se for um subconjunto de , então existem apenas duas possibilidades para ele: ser vazio ou o próprio . Se ele for vazio, então podemos escrever . Caso for o próprio , podemos escrever .

Suponha, por hipótese de indução, que se um conjunto tiver menos do que elementos e forem subconjuntos de , então podemos escrever .

Vamos usar isto para provar que se tem elementos, com elementos e forem subconjuntos de , então podemos escrever . Vamos obter um conjunto com menos de elementos para podermos usar a hipótese de indução. Observemos que . Daí segue que ou . Com efeito, suponha por absurdo que seja o contrário, ou seja, e . Então e . Como e são disjuntos

pois se é par, então e se é ímpar, então . Contradição. Logo, algum dos conjuntos ou possui pelo menos elementos.

Vamos supor sem perda de generalidade que . Então

por causa de e pelo fato de que se é par, então , enquanto se é ímpar, .

Como , segue que

Assim podemos usar a hipótese de indução para . Consideremos para . Como são subconjuntos de e este tem menos do que elementos, por hipótese de indução,

para alguma escolha de sinais e . Se unirmos ambos os lados a , como é subconjunto de então

Resta provarmos que o lado direito da igualdade é igual a . Para isto, é suficiente mostrarmos que (pois repare que unir cada membro de uma união a equivale a unir a união deles com ). Com efeito, notemos que

Além disso,

Desta forma, para a mesma escolha de sinais de . Isto terminar a indução em e assim completamos a 1ª Parte do exercício.

Vamos para a 2ª Parte do exercício. Para mostrarmos que , basta darmos um exemplo de conjuntos que não satisfazem as condições do enunciado. Para nos ajudar, podemos supor, sem perda de generalidade, que .

O exemplo que escolheremos será feito usando base . Consideraremos para os conjuntos de números naturais menores do que cujo -ésimo algarismo na base (da direita para a esquerda) seja igual a , ou seja, os números sejam da forma , onde é igual a ou para e .

Queremos mostrar que nunca pode ser igual a para qualquer escolha de sinais e . Para isto, é suficiente mostrarmos que o complementar de em relação a é sempre não vazio.

Observemos que , onde é o sinal trocado em relação a . Desta forma, o complementar de é . Observe que este é não vazio, pois nele mora o conjunto que possui -ésimo algarismo se o sinal em cima de for e caso contrário.

Assim nunca pode ser igual a para qualquer escolha de sinais e e com isso encontramos conjuntos que não satisfazem as condições do enunciado, ou seja, . Como é natural, segue que .

Colorações[]

Do mesmo jeito que fazemos em problemas de invariantes, colorir as coisas pode nos ajudar.

Exemplo (IMO 1999)[]

Considere um tabuleiro , onde é um inteiro positivo par fixo. O tabuleiro é dividido em quadrados unitários. Dizemos que dois quadrados diferentes no tabuleiro são adjacentes se eles possuem um lado em comum.

quadrados unitários no tabuleiro são marcados de forma que cada quadrado (marcado ou não marcado) no tabuleiro é adjacente a pelo menos um quadrado marcado.

Determine o menor valor possível de .

Solução: Como é par, vamos considerar para inteiro. Vamos fazer uma coloração conforme a da figura:

IMO1999Q3


Ela foi preenchida da seguinte maneira:

  • colorimos as células na borda de preto;
  • depois as células da borda do quadriculado restante de branco;
  • repetimos o processo até pintar todos os quadrados do tabuleiro.

Para nos ajudar a organizar o raciocínio, vamos chamar figuras conforme as que aparecem a seguir de quadros (que podem ser pretos ou brancos):

IMO1999Q31

Quantas casas brancas e quantas pretas existem no tabuleiro após a pintura? Vamos contar a quantidade de quadrados pretos. Para isso, é interessante notarmos que se um quadro preto é a borda de um quadrado de lado , então ele possui quadradinhos.

Só para fazermos a contagem, vale a pena dividirmos em casos.

(i) é ímpar

Aqui irá sobrar um quadradinho no centro. Por isso, nossa contagem será:

(ii) é par

Neste caso, a soma dos quadrados será

Ou seja, em qualquer caso, teremos casas pretas. Vamos usá-las para controlarmos a quantidade de marcações. Mas além dela, vale a pena usarmos um pouco de contas. Nas casas marcadas, vamos atribuir o número , enquanto nas casas não marcadas atribuímos o número . Considere o número da casa que fica na linha e na coluna . Observe que a quantidade de casas marcadas é justamente a soma dos 's.

Tomemos uma casa preta qualquer. Sejam os valores de suas casas adjacentes. Como pelo menos uma delas deve estar marcada (pelo enunciado), podemos concluir que . Somemos essas igualdades para cada uma das casas pretas.

Como cada casa do tabuleiro é adjacente a exatamente duas casas pretas, segue que cada aparece duas vezes no lado esquerdo da igualdade. Por isso, a soma das igualdades irá nos dar

Portanto, devemos ter pelo menos casas marcadas. Se conseguirmos um exemplo com exatamente casas marcadas, teremos encontrado o menor valor possível de que satisfaça as condições do enunciado.

Uma maneira de fazermos isso é passando ao longo dos quadrados pretos e marcando duas células consecutivas, depois pulando duas células consecutivas e assim por diante. Cada célula no quadrado preto terá um vizinho marcado. Depois podemos fazer isso nos próximos quadros de forma que cada célula nos quadros brancos possua exatamente um vizinho marcado. Por exemplo, no tabuleiro :

IMO1999Q32

Como metade das casas pretas são marcadas, conseguimos um exemplo com casas e esse é o menor valor possível de . Caso você queira dar a resposta em função de , basta fazermos e obtermos .

Princípio da Casa dos Pombos[]

Você pode saber mais sobre isso aqui.

Exemplo (Cone Sul 2011)[]

Algumas casas de um tabuleiro são pintadas de preto, de modo que qualquer quadrado de contenha, no máximo, casas pretas. Achar o número máximo de casas pretas que o tabuleiro pode ter.

(Este problema é uma generalização do Problema 4 da Cone Sul 2008).

Solução: Vamos mostrar que a quantidade máxima de casas pretas é . Para isso, vejamos um exemplo com casas e depois mostraremos que é impossível ter mais do que essa quantidade de casas pretas.

Comecemos com o exemplo. Para isto, vamos marcar as colunas com os números . Pinte as casas das colunas de preto. Assim teremos um exemplo com colunas pintadas de preto e por isso, casas pretas.

Vejamos agora que não é possível ter mais do que esta quantidade de casas pretas. Suponha, por absurdo, que seja possível ter casas pretas. Vamos dividir nosso tabuleiro em partes conforme a figura a seguir:

Pelo Princípio da Casa dos Pombos, alguma destas partes terá pelo menos casas pretas. Tomemos esta parte e vamos dividí-la em partes novamente conforme a figura a seguir:

Observe que nos primeiros blocos (de cima para baixo) existem, no máximo, casas pretas. Assim, o último bloco terá as duas casas pretas. Assim a única coloração possível será:

Agora vamos dividir nosso tabuleiro da seguinte maneira: um retângulo (em vermelho) e outros retângulos (em verde), de tal forma que o pedaço em vermelho englobe um pedaço pintado de branco e preto alternadamente (que englobe um pedaço da figura vista anteriormente).

Estes pedaços verdes terão casas pretas. Se cada um destes pedaços tiver , ou menos, casas pretas, então eles terão no máximo casas pretas.

Com isso, algum pedaço verde deve ter pelo menos casas pretas. Isso é impossível. Logo, o máximo de casas que um tabuleiro pode ter é .

Lugares Para Estudar[]

Advertisement