Wiki Olimpédia
Registre-se
Advertisement

Existem alguns problemas em que precisamos usar Combinatória e Teoria dos Números para resolvê-los.

Exemplo (Cone Sul 2012)[]

Ao redor de uma circunferência estão escritos números, cada um deles é igual a ou a . Se não há números consecutivos cuja soma seja , ache todos os valores possíveis da soma dos números.

Solução: Sejam os números ao redor da circunferência. Já que o enunciado nos fala sobre soma de quaisquer números consecutivos. Considere a soma de dez números consecutivos na circunferência, começando por .

Como queremos falar sobre as somas , será que conseguimos encontrar alguma informação sobre elas? Observe que e são números ímpares. Então , que é a soma de dez números ímpares, será par.

Vejamos agora a relação entre e . Para isto, vamos explorar . Observe que o resultado disto será a diferença entre dois números: a úlima parcela de e primeira de (afinal, todas as outras se cancelarão). Como cada um destes dois podem ser ou , os possíveis valores de são , ou .

Em outras palavras, de para podem acontecer três coisas: aumentar , diminur ou permanecer igual.

Se existirem e tais que e possuam sinais opostos (ou seja, um é positivo e o outro negativo), então existe algum tal que , o que contradiz o enunciado. Desta forma, os 's são todos positivos ou todos negativos.

Vamos analisar cada um dos casos. Comecemos com quando todos eles são positivos. Neste caso, para todo . Logo, a soma de todos os 's será maior ou igual a (afinal existem somas). Mas na soma dos 's, cada um dos aparece vezes. Com isso, a soma dos 's é maior ou igual a . Mas a soma destes é inteira e par. Logo, ela é maior ou igual a .

Tem como essa soma ser igual a ? Sim: precisamos de números 's e números 's. Uma das maneiras de termos isto é fazermos

Quem garante que a soma de dez consecutivos destes números nunca é ? Basta pensarmos que para obtermos soma , precisamos de cinco 's e cinco 's. Se for menor ou igual a , então, como na soma de dez números consecutivos aparecem todos os restos possíveis na divisão por , então a soma terá seis 's e quatro , nunca sendo igual a . Já se for maior que a quantidade de 's na soma nunca vai ser maior que . Logo, nunca teremos soma de dez números consecutivos sendo igual a zero.

E além disso, podemos fazer a soma dos 's ser algum número par maior do que ? Sim: basta termos a quantidade apropriada de 's e . Para isto, cada vez que quisermos subir a soma em , basta trocarmos um número por .

Desta forma, neste caso, a soma pode ser qualquer número par tal que . E quanto ao caso em que todas as somas são negativas? Basta fazermos um raciocínio análogo e concluir que aqui as somas possíveis são todos os números pares tais que .

Portanto, as somas são todos os valores pares tais que .

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

Duas pessoas disputam um jogo de maneira descrita a seguir.

Inicialmente escolhem dois números naturais: (o número de rodadas) e (o incremento máximo).

Na primeira rodada o jogador escolhe um natural e, posteriormente, o jogador escolhe um natural positivo .

Para , na rodada o jogador escolhe um natural com e posteriormente o jogador escolhe um natural com . Após essas escolhas, nessa -ésima rodada, o jogador ganha pontos e o jogador ganha pontos. Ganha o jogo o jogador com maior pontuação total ao fim das rodadas. Em caso de pontuações totais iguais o jogador é considerado vencedor.

Para cada escolha de e , determine qual dos jogadores possui estratégia vencedora.

Solução: Ao lidarmos com a pontuação dada em mdc's, lembre-se de que, para e positivos, vale que é menor ou igual a e .

Observe que, na -ésima rodada, o jogador ganha pontos, ou seja, ele não pode ganhar mais do que pontos. E como escolhe depois, ele pode ganhar se fazer o seu mdc ser igual a . E para isto, ele deve lembrar-se que se, e somente se, .

Mas qual deverá ser o número que deve escolher para que a sua pontuação sempre seja ? Vamos considerar que escolha para algum . E qual será este ? Vamos explorar o problema com mais precisão para descobrir. Precisamos um valor de que force a pontuação de ser igual a . Já vimos que isto ocorre quando que é verdade se, e somente se, , para todo .

Desta forma, deve ser múltiplo de todos os valores de . Mas como pode fazer isto, se ele nem sabe quais valores vai escolher? Ele pode ser uma pessoa prevenida: pegar como sendo múltiplo de todos os valores possíveis que pode escolher para . Como ele pode saber quais são estes valores possíveis? Observe o seguinte: se escolhe o valor , então valor máximo para (ou seja, o maior número que ele pode escolher) já está determinado. Observe que

Desta forma, vai escolher valores entre os números . Façamos então ser múltiplo de todos estes. Uma maneira possível de se fazer isto é tomarmos . Desta forma, para todo e assim sempre obtem pontos, ou seja, uma quantidade maior ou igual a de .

Mas aqui temos um problema: o enunciado diz que "em caso de pontuações totais iguais o jogador é considerado vencedor". Para provar que possui a estratégia vencedora, precisariamos mostrar então que não pode fazer exatamente pontos. Suponha, por absurdo, que ele faça.

Então, a pontuação de , ou seja, é igual a o que ocorre se, e somente se,

Mas , de onde segue que e pela Limitação , o que contradiz o enunciado. Logo, nunca ganhará pontos e assim pode sempre ficar com mais pontos do usando sua estratégia. Desta forma, possui a estratégia vencedora.

Mas você pode estar se perguntando: para as escolhas de , quem garante que ? Basta lembrarmos que escolheu de forma que , somarmos em todos os membros da desigualdade e lembrarmos que para todo .

Exemplo (Cone Sul 2004)[]

Utilizando triangulinhos equiláteros de papel, de lado , forma-se um triângulo de lado . Desse triângulo retira-se o triangulinho de lado cujo centro coincide com o centro do triângulo maior.

Determine se é possível cobrir totalmente a superfície restante, sem superposições nem buracos, dispondo-se somente de fichas em forma de trapézio isósceles, cada uma formada por três triangulinhos equiláteros de lado .

Solução: Uma primeira ideia aqui seria usar indução em no número de lados, que podemos chamar de . Temos um problema: ao aumentarmos o número de lados de para , não parece que a parte da figura que aumento pode ser coberta por trapézios conforme o enunciado.

Mas parece que se aumentarmos o número de lados de para teremos um "complemento" que pode ser preenchido conforme o enunciado (veja a figura a seguir). Em outras palavras, parece que um triângulo de lado satisfaz as condições do enunciado, então um de lado também satisfaz.

ConeSul2004q5

Desta forma, não faremos indução para mostrar que algo vale para todo número natural . Mas fique tranquilo, ainda podemos salvar a nossa indução. Observe que e possuem o mesmo resto na divisão por

Então podemos provar que algo vale para todo com certo resto na divisão por . Mas estamos interessados em . Qual o resto de na divisão por ? Observe que

Logo, é suficiente provarmos que a afirmação do enunciado vale para todo .

(i) Para o caso , não há o que fazer, pois o triângulo do centro foi removido e não teremos nenhuma figura para ser preenchida.

(ii) Vamos supor que um triângulo de lado possa ser preenchido. Provaremos que o de lado também pode. Para isso, é suficiente mostrarmos que o complemento pode ser preenchido com trapézios.

Comece escolhendo um vértice qualquer e cubra um dos lados que o contém até restarem dois espaços para trapézios deitados(se você quiser acompanhar na figura acima, comece com o vértice que fica embaixo e na esquerda e faça isso com o lado horizontal).

Quanto a segunda linha (debaixo para cima), cubra até restar espaços. Na terceira linha (debaixo para cima), deixe um espaço à esquerda e preencha até onde foi a segunda linha. Além disso, coloque uma peça acima das duas primeiras peças da terceira linha. Repita este procedimento para os outros dois vértices.

Desta forma, o complemento é preenchido e assim terminamos o passo indutivo. Logo todo pode ser preenchido conforme o enunciado e assim vale para o caso em que .

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

Em Tumbólia existem times de futebol.

Deseja-se organizar um campeonato em que cada time joga exatamente uma vez com cada um dos outros. Todos os jogos ocorrem aos domingos, e um time não pode jogar mais de uma vez no mesmo dia.

Determine o menor inteiro positivo para o qual é possível realizar um tal campeonato em domingos.

Solução: Vamos analisar dividir em dois casos: em que é par e depois o que ele é ímpar. Para nos organizarmos melhor, em ambos os casos, nomearemos os times da seguinte maneira: .

1º Caso: é par

Segundo o enunciado, cada time deve jogar exatamente uma vez com cada um dos outros . Como ninguém pode jogar duas vezes no mesmo domingo, precisamos de pelo menos domingos para este campeonato. Conseguimos encontrar um campeonato com exatamente domingos? Vejamos que isto é possível.

Considere o domingo em que os times e se enfrentam (para diferente de ). Observe que . Faremos um campeonato da seguinte forma:

(1) se e forem diferentes de ;

(2) se é diferente de .

Mas quem garante que estes domingos conseguem formar um campeonato conforme as condições do problema? Para vermos isto, basta provarmos que um time não pode jogar com dois diferentes no mesmo dia. Suponha, por absurdo, que exista um time que jogue com os times e no mesmo domingo (para diferente de ), isto é, . Para lidarmos com isto, lembre-se: o significado de depende se ou são iguais a ou não. Por isso, vamos dividir em casos:

(i)

Neste caso se transforma em

Como é par, segue que é ímpar e assim e assim

Como e pertencem à lista , segue que o que é uma contradição. Logo, neste caso, um time não pode jogar com outros distintos.

(ii) , e são diferentes de

Aqui se voltarmos a ,

Como e pertencem a lista , segue que . Contradição.

(iii) diferente de , mas algum dos números ou é igual a

Suponha, sem perda de generalidade, que (e como não pode ser igual a , segue que ele é diferente de ). Então se torna

Como e pertencem a lista , segue que . Absurdo.

Logo, no caso em é par, o número mínimo de domingos que precisamos para fazer um campeonato com times é .

2º Caso: é ímpar

Como cada time tem que jogar com todos os outros, precisamos de pelo menos domingos. Conseguimos um exemplo de campeonato com exatamente domingos? Não, pois em cada dia, algum time fica sem jogar (já que existe uma quantidade ímpar de times).

E quanto a um exemplo com domingos? Veremos que conseguimos sim. Para isto, usaremos o caso em que o número de times é par. Vejamos como. Consideremos um time virtual, onde jogar com significa não jogar naquele dia. Assim teremos times, com par.

Basta usarmos o que concluimos no caso anterior para descobrir que a quantidade de campeonatos aqui é . Portanto, a quantidade mínima de domingos para este caso é .

Exemplo (IMO 2004)[]

Defina um "gancho" como sendo a figura formada por seis quadrados unitários conforme mostrado na figura, ou qualquer figura obtida aplicando rotações e reflexões dessa figura.

IMO2004Q3

Determine todos os retângulos . que podem ser cobertos sem lacunas e sem sobreposições com ganchos de forma que não existe nenhuma parte de algum gancho que está fora do retângulo.

Solução: Suponha que um retângulo pode ser coberto por ganchos. Vejamos quais as características de e . Um dos principais problemas de cobrirmos o tabuleiro assim é que os ganchos tem uns certos "buracos".

IMO2004Q31

Como não podemos deixar lacunas, algum gancho deve ocupar esse quadrado. De certa forma, para qualquer gancho, existe outro que cobre o quadrado unitário que fica no seu centro. As possíveis junções de duas peças em que uma cobre o centro da outra são:

IMO2004Q32

Por isso, ao invés de pensarmos em uma peça separadamente, vamos pensar nas peças aos pares. O tabuleiro total possui quadradinhos. Repare que cada um dos pares de peças possuem . Por isso, se pudermos cobrir o tabuleiro com ganchos, então .

Uma possível pergunta que vem na nossa cabeça é: se , podemos cobrir o tabuleiro com ganchos? Não! Pense em ou em é impossível cobrir o tabuleiro nesses casos. Mas observe que os casos e funcionam: basta colocarmos uma peça da forma ou uma da forma . Ou seja, algumas vezes funciona e outras não. Por isso, vale a pena dividirmos em casos. Já que precisa ser múltiplo de , vale a pena observarmos quando ou é múltiplo de ou de .

Caso 1: é múltiplo de

Observe que o caso em que for múltiplo de será totalmente análogo. Como conseguimos cobrir o tabuleiro com , em casos que conseguimos cobrir o tabuleiro com vários subtabuleiros nosso problema está resolvido. Por isso, vale a pena pensarmos no seguinte subcaso:

Caso 1.1: é múltiplo de

Se é múltiplo de e é múltiplo de , podemos dividir nosso tabuleiro em vários subtabuleiros . Como eles podem ser cobertos por ganhos, segue que o tabuleiro maior também pode.

IMO2004Q33

Caso 1.2: não é múltiplo de

Como (já que e ), segue que ou . Já que estamos no caso em que não é múltiplo de , segue que . Mas aqui neste caso . Desta maneira, . Seria legal se conseguíssemos dividir em subtabuleiros menores de forma que pudéssemos cobrí-los. Já que o número de linhas é múltiplo de , seria legal dividirmos em subtabuleiros que possam ser cobertos por ganchos.

Observe que subtabuleiros e podem sim ser cobertos por ganchos (afinal o primeiro pode ser dividido em três tabuleiros e o segundo em quatro tabuleiros ). Se supusermos tabuleiros da forma e tabuleiros da forma , teremos colunas. Quais inteiros podem ser escritos da forma para e inteiros não negativos? Já sabemos que existem inteiros tais que para todo inteiro. Mas nada garante que e são não negativos.

Já que não é múltiplo de , ele pode ser da forma ou da forma . Analisemos cada caso separadamente. Se é da forma (para ), então basta tomarmos . Já se for da forma (para ), tomemos e . Ficaram para trás os casos , e . Eles não podem ser escritos na forma com inteiros não negativos.

Desta forma, quando não for nem , podemos dividir o tabuleiro em subtabuleiros e que podem ser cobertos por ganchos, ou seja, o tabuleiro grande também pode.

E quanto ao caso em que ? Como cada par de ganchos precisa de pelo menos três linhas e três colunas, segue que não podemos ter ou . Resta analisarmos quando . Aqui também é impossível, pois as larguras possíveis das peças duplas são e .

Caso 2: nem e nem são múltiplos de

Como o produto de ambos deve ser múltiplo de , nenhum deles deve ser ímpar. Logo ambos são pares. Repare que isso pode influenciar no número de peças. De fato, existem peças. Como não pode ser múltiplo de (já que e são pares e nenhum deles pode ser múltiplo de ), segue que é um número ímpar.

Repare que

é um número ímpar. A soma de dois números ímpares só pode ser ímpar se exatamente um deles é ímpar. Vamos supor, sem perda de generalidade, que a soma das quantidades de peças duplas e seja ímpar.

Uma maneira interessante de resolvermos problemas de tabuleiros é colorirmos ele. Seria legal uma coloração em que pegasse todas as peças. Como as peças têm largura maior ou igual a , vamos pintar todas as colunas que estão em uma posição divisível por (ou seja, pintaremos as colunas ). Por isso, vale a pena separarmos as peças: as que pegam uma quantidade ímpar de quadradinhos em cada coluna chamaremos de e , enquanto as que pegam uma quantidade par de e . Cada uma das peças e cobrem três quadrados pretos, que rende uma quantidade ímpar de quadrados no total.

Mas observe que a quantidade de quadrados pretos é par. Afinal, se é a quantidade de colunas que pintamos de preto, então é a quantidade de quadrados pretos (que deve ser par, já que é par). Desta forma, a quantidade de quadrados pretos que as peças e cobrem é ímpar. Mas isso é impossível, pois cada uma das peças e cobrem uma quantidade par de quadrados pretos. Assim, este caso não nos dá solução.

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

Dado um natural e sua fatoração em primos , sua falsa derivada é definida por:

Prove que existem infinitos naturais tais que .

Solução: A definição da falsa derivada é algo que envolve bastantes produtos e potências, mas não adição ou subtração, que tem a ver com o que queremos provar. Vamos ver se encontramos alguma propriedade de que nos ajude a amenizar essa dificuldade: podemos notar que se e são primos entre si, então , ou seja, a função é multiplicativa. Mais do que isso, se nenhum dos expoentes dos primos de for maior do que 1 (chamamos esses valores de números livres de quadrados, porque não são divisíveis por nenhum quadrado perfeito maior que 1), os expoentes de serão todos zerados, e . Isso nos dá três conclusões:

  1. Se é livre de quadrados,
  2. Se é livre de quadrados e , então

Essa última conclusão nos permite modificar o problema. Se encontrarmos dois valores de consecutivos, digamos , podemos multiplicar e por números livres de quadrados e , e ainda valerá , e, se , teremos que os dois valores são consecutivos e conseguimos um par. A nossa solução, então, se estruturará da seguinte forma:

  • Parte 1: Encontrar dois valores de e de forma que
  • Parte 2: Provar que existem infinitos pares de números positivos livres de quadrados satisfazendo .

Parte 1: Mexendo um pouco com a função (não calculamos nenhum valor até agora, afinal!), podemos encontrar que e que . Ou seja:

Devemos, agora, provar que existem infinitos pares de números livres de quadrados tais que

Lembrando que isso nos permitirá colocar e e assim .

Parte 2: A primeira coisa que podemos nos lembrar ao vermos é de que isso é uma equação diofantina linear. Notando que , podemos fazer o Algoritmo de Euclides Estendido para encontrar um par qualquer que satisfaça a relação:

Restos Quocientes
-169 * 0 1
27 * 1 0
20 -7 7 1
7 1 -6 -1
6 2 19 3
1 1 -25 -4

Ou seja, é solução, portanto todos os pares da forma também funcionam. Queremos um par livre de quadrados e de números positivos.

Tomar nos dá , em que não é livre de quadrados. Tomar nos dá , em que não é livre de quadrados. Por fim, nos dá , que finalmente é um par positivo e livre de quadrados. Assim, podemos convencionar que todas as soluções que queremos são da forma . Para não precisarmos ficar escrevendo “pares com ambos os membros livres de quadrados”, vamos chamar esses pares de bons.

Como provar que há infinitos pares bons? Não parece existir uma fórmula geral, afinal, ser livre de quadrados envolve multiplicação e a fórmula que temos envolve soma. Vamos fazer o seguinte: provar que para valores de entre 0 e qualquer número, uma parte considerável desses valores gera pares bons. Por que isso prova que há infinitas soluções? Suponha que conseguimos que, para , que pelo menos dos valores de geram pares bons; podemos deixar tão grande quando quisermos e sempre teremos que pelo menos dos pares serão bons, então ao aumentar sempre geraremos pares bons novos; como podemos aumentar para sempre, há infinitos pares bons.

Primeiro, vamos notar que como os pares bons serão da forma , é interessante fatorar os números que temos: (241 é primo) e . Isso significa, dentre outras coisas, que se for múltiplo de vários quadrados, então e não serão divisíveis por nenhum deles! Porque, supondo que seja múltiplo de um , e só seriam múltiplos de também se e fossem múltiplos de , mas como os dois são livres de quadrados, isso é impossível!

Então, vamos tomar múltiplo de vários quadrados de primos, ou seja, tomar um número da forma , em que é o produto dos quadrados dos primos menores que um número (porque infelizmente não podemos tomar todos os primos nesse produto), e um número entre 1 e , o número que queremos aumentar infinitamente. Pelo que vimos, nenhum quadrado de um primo menor que dividirá os valores de , mas e os primos maiores que ou iguais a ?

Vamos ver o que queremos: temos um conjunto de elementos e queremos saber, ou ao menos estimar, quantos de seus elementos são divisíveis por um quadrado de primo , com . Como a diferença entre cada um de seus elementos consecutivos é a mesma (), há no máximo elementos que são divisíveis por , e o mesmo com o conjunto . Ou seja, há, no máximo, dos pares que não são bons (esse máximo acontece no caso em que os valores de em que e aqueles em que são todos diferentes, portanto os pares serão ).

Assim, os valores de para os quais o par não é bom (ou seja, algum divide ou ) totalizam, no máximo,

Para algum número máximo . Por que esse número máximo e quanto ele vale? Note que, à medida que pegamos valores de maiores, seus quadrados deixam de dividir valores de e (afinal, ), então há algum valor para o qual todos os quadrados dos não dividem mais nenhum valor de ou . Como , o maior valor de ou possível sendo analisado é . Assim, . Dessa forma, a quantidade de pares que não são bons é, no máximo:

Calcular essa soma é terrível, quando não impossível. Mas não precisamos calculá-la, queremos apenas provar que ela é menor que alguma coisa em função de ou . Então, podemos aplicar várias desigualdades, por exemplo, que para dizer que

Esse no índice não nos ajuda muito. Felizmente, impor um máximo no deixa o valor da soma menor, porque nos dá menos parcelas para somar, o que significa que

Ok, e como calculamos essa soma? Podemos deixá-la maior ainda (deixando o denominador menor) e fazendo uma soma telescópica, assim:

Agora, usando o truque de que

ficamos com:

Ou seja, dentre os pares, no máximo

Não são bons. Como funções afins crescem mais do que raízes quadradas, se escolhermos suficientemente grande, teremos que , e se pegarmos um valor de , teremos que , ou seja:

Em outras palavras, o número de pares que não são bons será no máximo a metade do total de pares, o que significa que os pares bons totalizarão pelo menos a metade dos pares. Como podemos aumentar o quanto quisermos, há infinitos pares bons, o que significa que há infinitos valores de tais que .

Restos que Não Mudam[]

Ao somarmos um número a um múltiplo de o seu resto na divisão por não altera. Essa ideia pode ser interessante para resolvermos alguns problemas.

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

Mostre que existe um inteiro positivo com a seguinte propriedade: para qualquer inteiro é possível particionar um cubo em cubos menores.

Solução: Em certos problemas, antes de se ter a ideia, o ideal é que você descubra várias coisas sobre o problema. Afinal quanto mais informações temos sobre algo, mais fácil fica pensar sobre ela.

Observe que sempre é possível particionar um cubo em cubos menores, para todo inteiro maior ou igual a . Além disso, se podemos particionar um cubo em menores e em menores também, então podemos particionar em . De fato, para vermos isto, vamos particionar um cubo nesta quantidade de partes. Particione primeiramente um cubo em cubos menores. Depois escolha um e particione ele em menores. A quantidade de cubos irá aumentar , ou seja, teremos cubos.

Suponha que podemos particionar um cubo em menores. Como podemos particioná-lo em , segue que também podemos dividir um cubo em menores. Vamos usar isto para atacarmos o problema de fato.

Observe que encontrarmos um número múltiplo de em que seja possível dividir o cubo nesta quantidade de cubos menores, então todo múltiplo de maior do que ele também terá esta característica. De fato, basta somarmos quantas vezes precisarmos.

Da mesma forma, se soubermos de um número com resto na divisão por em que podemos dividir o cubo nesta quantidade de cubos menores, então todo número que também deixa resto na divisão por e seja maior do que o primeiro também vai ser uma quantidade em que podemos particionar o cubo (basta somarmos ao primeiro número quantas vezes precisarmos).

Isto vale não só para restos e : também vale para e . Por isso, se pegarmos exemplos de números em que podemos dividir um cubo em cubos menores com todos os restos na divisão por , teremos resolvido o problema. Afinal, basta pegarmos o como sendo o maior deles. E todo número maior ou igual a vai satisfazer as condições do enunciado.

Observe que , e deixam restos , e , respectivamente, na divisão por . Faltam os restos e . Vamos usar o fato de que se podemos particionar em e cubos menores, então podemos fazer também com .

Notemos que, com isso, podemos particionar em cubos menores e este deixa resto na divisão por . Além disso, deixa resto , enquanto deixa resto e deixa resto . Logo, basta tomarmos .

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

Em cada casa de um tabuleiro está escrito um inteiro. A operação permitida é tomar três casas formando um L-triminó (ou seja, uma casa C e outras duas com um lado em comum com C, um na horizontal e outro na vertical) e somar ao inteiro em cada uma das três casas. Determine a condição necessária e suficiente, em função de e dos números iniciais, para que seja possível deixar todos os números iguais.

Solução: Parece chato começar mexendo com um tabuleiro . Por isso, vamos fazer alguns casos pequenos. Comecemos com um tabuleiro :

OBM2014n3q5

Existem quatro tipos de transformações: uma que soma a todos os números com exceção do , outra que soma todos os números com exceção do , outra que tem como exceção e outra que possui como exceção. Se fizermos , , e vezes a primeira, a segunda, a terceira e a quarta transformações, teremos no tabuleiros os números , , e . Será legal escolher números de forma que todas essas somas fiquem iguais. Uma possibilidade é . Neste caso, as transformações serão feitas da seguinte forma:

OBM2014n3q51


Ou seja, em qualquer tabuleiro é possível essas transformações de forma que todos os números fiquem iguais. Vamos para um tabuleiro um pouco mais: o . Podemos usar o caso para pensar nele? Sim, afinal o tabuleiro é formado por dois tabuleiros :

OBM2014q3n52

Podemos usar a mesma ideia que fizemos no caso anterior em cada um dos tabuleiros e chegar em:

OBM2014q3n53

Se , o problema está resolvido, pois todos os números do tabuleiros serão iguais. Caso contrário, podemos supor, sem perda de generalidade, que . Agora vale a pena mexermos com o tabuleiro no meio, já que temos uma oportunidade de mexermos com e ao mesmo tempo. O que podemos fazer com esse tabuleiro? Será que vale a pena deixarmos todos os números iguais? Se isso ocorresse, a gente perderia a capacidade de colocar todos os números iguais mexendo nos dois tabuleiros da esquerda e da direita.

De fato, quando usamos a técnica de deixar todos os números iguais em um tabuleiro , o número em cada tabuleiro será a soma dos números de cada tabuleiro. Para que todos os números sejam iguais, precisaríamos que a soma dos números do tabuleiro da direita fosse a mesma que a dos números do tabuleiro da esquerda. Suponha que o número das quatro casas do tabuleiro do meio fosse . Então a soma dos números do tabuleiro da esquerda seria , enquanto a soma do da direita seria . Essas somas são iguais se, e somente se, o que não necessariamente acontece.

Que tal então deixar o tabuleiro do meio da seguinte forma:

OBM2014q3n54

Para isso, vale a pena mexermos no tabuleiro central. Ao invés de fazer tipos de movimento com um L-triminó, vamos pensar em apenas dois (para ficar mais fácil de fazermos as contas):

OBM2014q3n55

Figura 1

Já que queremos que os dois se transformem no mesmo número, vale a pena pegarmos movimentos que mexam com cada um dos 's exatamente a mesma quantidade de vezes (o mesmo vale para o ). Seja o número de vezes que aplicamos o movimento da esquerda e o número de vezes que aplicamos o movimento da direita. Após esses movimentos, nosso tabuleiro ficará:

OBM2014n3q52

Mas queremos que os números destacados a seguir sejam iguais:

OBM2014n3q53

Desta forma,

Com isso, a nossa tabela se torna,

OBM2014n3q54

Para terminarmos, vale a pena aplicarmos o mesmo método que usamos na tabela tanto na tabela da direita quanto na da esquerda. Mas para isso funcionar, o resultado final nas duas tabelas deve ser o mesmo. Mas lembre-se que o número final deve ser a soma. Por isso, a soma dos números da tabela da esquerda deve ser a mesma que a da soma da tabela da direita. Por isso,

Como todas as parcelas são pares, podemos dividir os dois lados da igualdade por :

Ou seja, devemos aplicar o movimento da Figura 1 da esquerda vezes e o mesmo vale para o movimento da direita. Observe que é positivo, pois . Se aplicarmos o movimento da esquerda vezes, iremos obter:

OBM2014n3q55

Já se aplicarmos o movimento da direita vezes:

OBM2014q3n56

Observe que a soma dos números das tabelas tanto da esquerda quanto da direita são . Por isso, para finalizarmos, basta aplicarmos o mesmo método que usamos na tabela para deixar todos os números da tabela iguais a . Isso mostra que sempre podemos colocar todos os números iguais em uma tabela . O mesmo vale para uma tabela (já que uma tabela é igual à outra, mas rotacionada).

Vamos para o caso . O raciocínio aqui é parecido. Podemos ver um tabuleiro com dois tabuleiros . Em cada um deles, podemos deixar todos os números iguais.

OBM2014n3q56

Também podemos ver ele como dois tabuleiros iguais ao que já tínhamos feito aqui:

OBM2014q3q57


Já vimos que podemos fazer todos os números do tabuleiro tanto de cima quanto debaixo virarem . Por isso, também conseguimos fazer todos os números de um tabuleiro ficarem iguais.

Vamos para um tabuleiro . Ao brincarmos um pouco com ele, parece que nem sempre iremos conseguir fazer todos os números ficarem iguais. Vejamos se isso é verdade. Observe que, em cada movimento, a soma aumenta de em . Por isso, o resto da divisão da soma não se altera. Suponhamos que, no final, tenhamos todos os números iguais a . A soma final deverá ser , ou seja, um múltiplo de . Mas se a soma original for um número que não seja múltiplo de , não iremos conseguir fazer todos os números ficarem iguais.

Isso aconteceu aqui porque o número de colunas é um múltiplo de . Também aconteceria se o número de linhas fosse também. Por isso, se ou o número de linhas ou o número de colunas for múltiplo de , é necessário que a soma de todos os números seja múltiplo de . Mas e se todos os números forem múltiplos de , podemos fazer com que todos os números sejam iguais?

Vamos atacar primeiro o caso . Suponhamos que a soma de todos os números do tabuleiro seja múltiplo de . Note que ele é formado por um tabuleiro e outro :

OBM2014n3q57

Como já mexemos como esses dois casos, podemos usar isso a nosso favor. Já conseguimos que conseguimos fazer todos os números do tabuleiro virarem o mesmo (digamos ) e o mesmo vale para o tabuleiro , ou seja, todos os números podem virar .

OBM2014n3q58

Se , o problema estará resolvido. E o caso em que eles são diferentes? Podemos supor, sem perda de generalidade, que . Já que cada movimento aumenta uma unidade nos números em que atua, vamos fazer os números das casas onde tem aumentarem até chegar em , ou seja, vamos atuar no tabuleiro da direita. Observe que nele podemos fazer os seguintes movimentos:

OBM2014n3q59

Se fizermos os quatro movimentos no tabuleiro da direita, aumentaremos três unidades em cada uma das casas. Para chegarmos de para , precisaremos aumentar em cada um dos quadradinhos (observe que é positivo, pois ). Como fazer os quatro movimentos aumenta em três unidades, seria interessante se fizéssemos os quatro movimentos vezes. Mas isso só é possível se for um número inteiro, ou seja, se .

Sabemos que a soma dos números de todas as casas do tabuleiro é divisível por . Por isso, . Será que podemos usar isso para concluir que ? A primeira coisa que precisamos fazer é sumir com o . Observe que . Desta forma, . E para fazermos esse virar ? Basta notarmos que . Assim . Portanto, podemos transformar todos os números do tabuleiro em . O tabuleiro é análogo.

Vamos para o caso geral. Como parece que importa se um número é múltiplo de ou não, vamos considerar e com . Com isso, e . Podemos dividir o tabuleiro em um e vários e (isso pode acontecer, pois a quantidade de quadradinhos depois que colocamos o , ou seja , é divisível por , pois ).

OBM2014n3q510

Lembre-se: só podemos igualar todos os números de um tabuleiro se a soma dos números for divisível por . Para podermos consertar isso, podemos adicionar L-triminós nos tabuleiros de forma que a sua soma se torne divisível por . Aí você pode estar pensando: isso possivelmente vai bagunçar as peças ao redor. Certo. Mas podemos fazer isso (sem desorganizar os tabuleiros que você já mexer) até que fique na região caso ela exista.

Se ou a região não existe. Aqui a soma dos números do tabuleiro precisa ser divisível por , como já vimos. Vamos ver que se a soma a soma for divisível por , então é possível igualar todos os números. Vamos repetir o processo do parágrafo anterior até que em todos os tabuleiros e tenham todos somas iguais. Sabemos que podemos deixar todos os números os números iguais de cada um desses subtabuleiros. Mas e agora como deixar todos os números do tabuleiro iguais? Basta que em cada um dos tabuleiros apliquemos L-triminós conforme a figura a seguir:

OBM2014n3q511

E como isso nos ajuda? Cada vez que fazemos isso aumentamos uma unidade em cada um dos números do tabuleiro . Por isso, podemos fazer isso em todos os tabuleiros e de forma que todos os números do tabuleiro sejam iguais. Desta forma, se a soma dos números de um tabuleiro (em que um dos números ou é múltiplo de ) for múltiplo de , então é possível igualar todos os números (e vice-versa).

Suponha, agora, que e sejam diferentes de zero. Depois de fazermos o processo descrito no antepenúltimo parágrafo, a região cuja soma dos números não é múltipla de é a do tabuleiro . Como e valem ou cada, estamos lidando com um tabuleiro ou ou ou . Podemos igualar todos os números, independente da soma (como já vimos). Mas antes de fazermos isso, vamos igualar todos os números de cada um dos tabuleiros . Em seguida, vamos aumentar os números do tabuleiro (com L-triminós) até que a sua soma seja maior do que a de qualquer outra região e igualamos todos os números dele. Para finalizarmos, basta aumentarmos cada um dos tabuleiros até que eles fiquem com a mesma soma que o tabuleiro .

Portanto, conseguimos igualar todos os números se, e somente se, e não são divisíveis por ou a soma de todos os números é um múltiplo de .

Princípio da Casa dos Pombos[]

Você pode saber mais sobre ele aqui.

Exemplo (OBM 1998 - 3ª Fase - Níveis 2 e 3)[]

São dados números naturais maiores que e menores que tais que dois quaisquer são primos entre si. Mostre que pelo menos um desses números é primo.

Dica:
Se um número é composto, ele deve possuir algum fator primo menor do que . Quantos são os primos menores do que ?

Solução: Suponha todos os números desta lista são compostos. Então eles devem possuir algum fator primo menor que , ou seja, menor que . Porém só existem primos menores que . Já que dois números primos entre si não podem possui fatores primos em comum, segue que não podemos ter o números compostos. Portanto, algum deles é primo.

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

Esmeralda escreveu uma lista de números inteiros positivos em uma folha de papel. Renan percebeu que todos os números da lista e todas as somas de qualquer quantidade de números distintos da lista não eram divisíveis por nenhum quadrado perfeito diferente de . Qual a quantidade máxima de números na lista de Esmeralda?

Solução: Comecemos com casos pequenos. Dá para montar uma lista com números? Sim: .

Também conseguimos com três? Sim: .

Tem como a lista ter ou mais números? Suponha que existam pelo menos quatro números nessa lista, que chamaremos de e . Como é quadrado perfeito, precisamos que nenhum destes números seja múltiplo de . Então os possíveis restos destes números na divisão por são ou . Pelo Princípio da Casa dos Pombos, existem dois destes números com o mesmo resto na divisão por . Podemos supor, sem perda de generalidade, que esses números são e .

Observe que e não podem ter resto na divisão por , pois isto faria com que fosse múltiplo de . Desta forma, os restos na divisão de e por são ou . Em ambos os casos possui resto na divisão por .

Como e não podem ser múltiplos de , segue que não podem ter resto na divisão por , ou seja, os restos possíveis para estes números são ou . Em ambos os casos, deixa resto , fazendo com que múltiplo de . Absurdo.

Logo, não é possível fazer essa lista com ou mais elementos e a quantida máxima de números é .

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

Qual é a maior quantidade de inteiros positivos menores ou iguais a que podemos escolher de modo que não haja dois números cuja diferença é , ou ?

Solução: Vamos pegar e dividir em intervalos de comprimento :

Observe que existem intervalos. Vejamos que neles não é possível pegar mais do que números que satisfaçam as condições do enunciado. Vamos fazer isso para (para os outros intervalos o raciocínio é o mesmo já que o que importa são as diferenças).

Se pegarmos o número só podemos pegar , ou , mas em nenhum casos é possível três números ou mais. Já se pegarmos , só podemos pegar , ou , mas em nenhum dos casos é possível pegar três números ou mais. Idem para o caso em que o menor número do conjunto é : só poderíamos pegar ou , mas nunca os dois juntos. Se o menor número do conjunto for o outro único número possível é , mas isso só daria dois números no conjunto. Finalmente, não podemos ter , ou como menor elemento, pois aí não conseguiríamos pegar outro número. Desta forma, só é possível pegar no máximo números de satisfazendo as condições do enunciado.

Se pegássemos mais do que , pelo Princípio da Casa dos Pombos, deveríamos mais do que dois números em um intervalo e isso é um absurdo. Desta forma, a quantidade de números satisfazendo as condições do enunciado é menor ou igual a . Mas para provarmos que essa quantidade é máxima, devemos tomar uma sequência de números de modo que não haja dois números cuja diferença é , ou .

Tomemos a sequência

Nela a diferença entre dois termos consecutivos alterna entre e e nunca podemos ter diferença entre termos igual a ou (já que a diferença mínima é ). Além disso, não podemos ter termos cuja diferença é (afinal a diferença entre um termo e o antecessor do seu antecessor é sempre ). Desta forma, essa sequência sempre satisfaz as condições do enunciado. Resta provarmos que ela possui termos.

Observe que os termos das posições ímpares são . Eles começam em e aumentam de em . Como aumentou no total, segue que ocorreram aumentos. Por isso, existem termos nas posições ímpares. De forma análoga, existem termos nas posições pares. Desta forma, a sequência possui termos.

Portanto, a quantidade máxima de números que satisfazem as condições do enunciado é .

Exemplo[]

Prove que se escolhermos mais do que números do conjunto então um será múltiplo do outro.

Solução: Vamos começar com casos pequenos para entender melhor.

(i)

Se pegarmos elementos do conjunto , estaremos pegando todos eles e logo um será múltiplo do outro.

(ii)

Devemos provar que se pegarmos números do conjunto , um deles será múltiplo do outro. Observe que se pegarmos quaisquer dois números dentre , e , então um deles será múltiplo do outro. Por isso, podemos dividir o conjunto em duas partes iguais: e . Ao pegarmos três números, devemos pegar pelo menos dois do primeiro conjunto. Logo, um deverá ser múltiplo do outro.

(iii)

Vamos provar aqui que se pegarmos elementos do conjunto , um deles será múltiplo do outro. Para isso, podemos dividir em conjuntos em que quaisquer dois deles, um deles é múltiplo do outro. Aqui podemos dividir em , e . Observe que se pegarmos quatro números aqui, deveremos pegar dois do mesmo conjunto. Ou seja, é impossível pegar quatro números aqui sem que tenhamos dois do mesmo conjunto.

(iv)

O raciocínio será o mesmo se dividirmos em , , e .

Parece que sempre funciona se dividirmos em conjuntos que começamos com um número ímpar e multiplicamos os elementos por quantas vezes for preciso. Para podemos generalizar, vale a pena colocarmos um número inteiro positivo na forma para maior ou igual a zero e ímpar.

Quantos são os possíveis valores para ? Observe que ele é ímpar e deve ser menor do que . Por isso, os possíveis valores para ele são . Desta forma, existem valores possíveis para ele. Se escolhermos mais do que números do conjunto , pelo Princípio da Casa dos Pombos, existirão dois números com "o mesmo ". Ou seja, dentre os números escolhidos, existirão e tais que e . Sem perda de generalidade, podemos supor . Desta forma,

Com isso, é múltiplo de . Em outras palavras, sempre que escolhermos mais de números do conjunto, teremos um deles sendo múltiplo do outro.

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

Seja , . Encontre o maior valor de para o qual a seguinte afirmação é verdadeira: todo subconjunto de com elementos tem pelo menos subconjuntos com e é múltiplo de .

Solução: Mostraremos que o maior valor possível para é . Para isso, vamos fazer o seguinte:

  • encontrar um subconjunto de que possui subconjuntos com e múltiplo de , mas não possui subconjuntos;
  • provar que qualquer subconjunto de de elementos possui pelo menos subconjuntos com e múltiplo de .

Ao provarmos essas duas coisas, teremos mostrado que o maior valor possível para é . Vamos começar com a primeira. Tomaremos o subconjunto . Existem pelo menos pares de números em que um é divisível por outro:

Observe que em todos os casos a divisão dá . Será que existe algum par de números em que um é divisível por outro além desses? Se existisse, a divisão deveria ser maior ou igual a . Como o menor é , deveria ter um número maior ou igual a para termos uma divisão com resultado maior ou igual a . Desta forma, temos exatamente subconjuntos de da forma com e múltiplo de .

Resta mostrarmos que qualquer subconjunto de de elementos possui pelo menos subconjuntos com e múltiplo de . Seja um subconjunto qualquer de que possui elementos. Vamos dividi-lo em duas partes: e . Como possui elementos, pelo exercício anterior, sabemos que existem e em (com ) tais que . Essa é a vantagem de resolver vários exercícios ao invés de apenas conhecer muitos resultados (não que a teoria não seja importante).

Se montarmos outro conjunto retirando e colocando , encontraremos outro par, já que esse novo conjunto terá elementos. Se repetirmos o processo para teremos pares pelo menos. Desta forma, .

Pense Nos Números como Tendo Algum Módulo[]

Aqui vale a pena pensar nos números como tendo algum módulo para que as contas fiquem mais fáceis de serem trabalhadas.

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

OBM2011q1n2

Num tabuleiro escrevemos os números de a , um em cada casa. Em seguida, achamos a soma dos números de cada linha, de cada coluna e de cada diagonal e contamos o número de somas que são múltiplos de três. Por exemplo, no tabuleiro ao lado as somas (as três linhas, as três colunas e as duas diagonais) são múltiplos de .

É possível que nenhuma das somas seja um múltiplo de ? Lembre-se de que você deve justificar sua resposta.

Solução: Vamos pensar neste problema módulo , isto é, ao invés de pensarmos no número em si, vamos pensar nos seus restos na divisão por . Neste modelo, as possíveis fileiras (linhas, colunas ou diagonais) são

além de suas permutações. Com isso, em cada fileira devem haver dois números congruentes entre si (módulo ) e um diferente. Consideremos e os números e (não necessariamente nessa ordem). Analisemos cada uma das possibilidades.

OBM2011q1n21

Na possibilidade acima, a soma dos números da diagonal é congruente a módulo .

OBM2011q1n22

Quem aparece na diagonal? Observe que nas linhas faltam um , um e um . Ou seja, aparecem e na diagonal e assim a soma dos elementos da diagonal é congruente a módulo .

OBM2011q1n23

Nos outros casos, existirão uma linha ou coluna com os números congruentes a módulo .

Portanto, é impossível que nenhuma das somas é múltiplo de .

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

Uma permutação dos números do conjunto é legal se não existem dois termos consecutivos cuja soma é um múltiplo de e se os dois vizinhos de um termo qualquer não diferem por um múltiplo de . Por exemplo, é uma permutação legal do conjunto . Entretanto, não é uma permutação legal do mesmo conjunto, pois os números e são vizinhos e sua soma é um múltiplo de . Além disso, outra razão para ela não ser legal, é que os vizinhos do número , que são o e o , diferem por um múltiplo de .

a) Determine o número de permutações legais do conjunto .

b) Determine o número de permutações legais do conjunto .

Observação: Uma permutação de um conjunto é uma sequência ordenada contendo cada um de seus elementos uma única vez.

Solução: Antes de partirmos para os itens, vamos montar uma estratégia. Como as restrições sobre as permutações legais são relacionadas a múltiplos de , faz sentido reduzir módulo : isso deixará todos os elementos iguais a , ou , dependendo do seu resto numa divisão por .

A primeira regra diz que, numa permutação legal, não se pode haver uma subsequência do tipo , ou , ou seja, não pode haver s e s vizinhos um do outro, assim como não deve haver s vizinhos de s.

A segunda regra diz que permutações legais não podem ter subsequências do tipo , ou .

Agora, vamos ver como essas permutações se comportam. s podem ser seguidos de s e s, mas não pode haver uma sequência de mais de dois s por causa da segunda regra. Da mesma forma, s podem ser seguidos de s e s, mas não pode haver uma sequência de mais de dois s por causa da segunda regra. s não podem ser seguidos de s, mas serão seguidos pelo oposto do número anterior, ou seja, apenas sequências da forma e são permitidas. Então, nossas permutações legais terão sequências de um ou dois s ou s alternando, separadas por zeros. Mas, espera, não podemos ter sequências de apenas um ou um , porque assim teríamos subsequências do tipo ou , ou seja, todas as permutações possíveis seguem essa ordem:

E, como cada uma pode começar de um ponto diferente dessa sequência, ficamos com seis tipos de permutações possíveis:

Mais uma coisa antes de irmos para os itens: reduzir os números módulo acaba "tratando-os da mesma forma", ou seja, as sequências e acabam se tornando a mesma, , então é importante contar quantos números são transformados em cada resto, para depois podermos permutá-los.

a) Reduzindo módulo , , ou seja, há uma quantidade igual de cada resto. Há seis tipos de sequência possíveis (as mesmas descritas anteriormente). Para cada uma delas, temos que permutar a ordem em que aparecem cada um dos números dos restos: por exemplo, na sequência de tipo , o e o podem aparecer como ou , ou seja, há maneiras de colocar os números de resto , e o mesmo para os outros restos. Como há seis sequências possíveis, o número de permutações legais é:

b) Como é um múltiplo de , não temos que nos preocupar sobre como as sequências acabam, e teremos números de cada resto. Como há seis possibilidades de sequência, o número de permutações legais é:

Exemplo (Cone Sul 2010)[]

Pablo e Sílvia jogam em um tabuleiro . Primeiro Pablo escreve um número inteiro em cada casa. Feito isso, Sílvia repete tantas vezes quanto quiser a seguinte operação: escolher três casas que formem um L, como na figura, e somar a cada número dessas três casas. Sílvia ganha se fizer com todos os números do tabuleiro sejam múltiplos de .

Demonstre que Sílvia sempre que pode escolher um sequência de operações com as quais ela ganha o jogo.

ConeSul2010q4

Solução: Já que queremos analisar que os números sejam múltiplos de , vamos analisar o tabuleiro módulo . Neste caso, deveremos fazer com que todos os números do tabuleiro sejam .

Mas o tabuleiro é muito grande. Vamos fazer o seguinte: resolveremos o problema em um tabuleiro . E depois? Basta dividirmos o tabuleiro em tabuleiros e aplicarmos o método em cada um dos subtabuleiros.

Considere o tabuleiro a seguir, onde e são números em módulo .

ConeSul2010q41

Ao invés de começarmos zerando todos os números (módulo ), vamos descobrir como diminuir uma unidade (módulo ) em cada um. E para quê isso? Se diminuirmos uma unidade em cada quadradinho até que zerem todos, resolveremos o problema.

E comoS diminuir uma unidade em algum quadradinho? Como estamos trabalhando módulo , uma maneira é aumentar unidades em três dos números (já que isso não altera o número se analisarmos módulo ) e unidades o outro número (já que aumentar unidades módulo é o mesmo que diminuir unidade). Vejamos isto melhor na prática.

Por exemplo, vamos diminuir em uma unidade módulo . Para isto, aplicaremos vezes a jogada de Sofia com a seguinte peça

ConeSul2010q42

Em seguida, aplicamos a jogada com cada uma das outras peças. Assim e aumentarão unidades (o que faz com que eles não mudem módulo ) e aumentará somente unidades (o que equivale a diminuir uma unidade módulo ). Isto fará que com e não mudem, mas diminua unidade.

Se repetirmos o processo para todas as letras, podemos "zerar" o tabuleiro e assim Sílvia sempre pode ganhar o jogo.

Exemplo (IMO 1995)[]

Seja um primo ímpar. Quantos são os subconjuntos de elementos de tais que a soma dos seus elementos é divisível por ?

Observação: Existe outra solução deste problema que pode ser encontrada aqui.

Solução: Vamos resolver o problema para . O resultado será o mesmo: se pensarmos apenas nos restos, a quantidade de subconjuntos de que possui resto na divisão por é a mesma que a quantidade de conjuntos que satisfazem as condições do enunciado.

Devemos de alguma forma controlar a soma dos elementos dos conjuntos. Por isso, considere a soma dos elementos do conjunto . Também vale a pena controlarmos os restos da divisão por da soma dos elementos. Para isso, vale a pena encontrarmos uma transformação interessante e prestar atenção no que ela faz com a soma dos elementos de um conjunto.

Que tipo de transformação é interessante para encontrarmos números que deixam resto na divisão por ? Uma ideia é considerarmos que uma sequência que aumenta de em (com ) forma um sistema completo de resíduos (você pode ver a prova disso aqui). E sabemos que todos sistema completo de resíduos módulo possui exatamente um número divisível por . Por isso, pegar um conjunto e uma transformação e fazer pode nos ajudar a encontrar números cuja soma dos elementos é um múltiplo de .

Para definirmos uma transformação que possa cumprir isso, considere formado por todos os subconjuntos de que possuem exatamente elementos. É legal pegarmos uma transformação que leva um subconjunto de elementos em outro que também tenha elementos. Ou seja, tomaremos uma transformação .

Como estamos interessados em uma transformação que aumenta a soma dos elementos em unidades (com ), vale a pena tomarmos uma transformação que soma a cada um dos elementos do conjunto que esteja entre . Para facilitar o nosso raciocínio, vamos considerar e .

A nossa transformação pode ser entendida como uma que adiciona a todos os elementos do conjunto que estejam também em (vamos pensar nessa soma módulo ). Em outras palavras,

.

Apesar de ela aumentar unidades a soma (o que ainda não provamos de fato), existem alguns conjuntos em que ela não faz efeito. Por exemplo, . De fato, se usarmos a definição e lembrarmos que ,

Lembre-se que a soma é módulo , por isso . E quanto a ? Se usarmos a definição e lembrarmos que ,

Existe algum outro conjunto tal que não faz efeito, ou seja, tal que ? Vejamos que não. Tomemos diferente de e de . Mostremos que é diferente de .

Ao aplicarmos em , somamos a todos os elementos de que também estão em . Como estamos falando da adição módulo , se somarmos a um elemento de iremos ter um elemento dele próprio (afinal, em módulo , podemos considerar ). Se ao somarmos a um elemento de e obtivermos sempre um elemento de , isso significa que todos os elementos de também são elementos de (de fato, se isso ocorrer e pertencer a , vale que pertencem a , ou seja, não pode ocorrer). Mas e o caso em que é vazio? Aqui o que não pode ocorrer. Desta forma, deve ser diferente de se for diferente de e de .

E o que acontece com a soma dos elementos de (diferente de e de ) ao aplicarmos diversas vezes? Considere a quantidade de números de que também estão em . Quando aplicamos somamos a cada um desses elementos e a soma é módulo . Por isso,

É possível provar por indução em que

Com efeito, o caso é verdadeiro conforme a penúltima congruência. Suponha que o caso seja verdadeiro, isto é, . Então

Com isso, nos dá um sistema completo de resíduos, ou seja, restos possíveis na divisão por . Assim somente um deles é divisível por .

Melhor ainda: o conjunto é formado por uniões da forma . Para vermos isso, repare que todo elemento de pode fazer parte de algum conjunto assim (nem que seja como primeiro elemento).

Além disso, repare que

Assim e são conjuntos de elementos cuja soma dos elementos também é divisível por . Para acharmos os outros, basta encontrarmos a quantidade de conjuntos . Como eles possuem elementos e dividem em conjuntos disjuntos, segue que a quantidade de conjuntos que satisfazem as condições do enunciado é:

Mas . Com isso, a quantidade desejada será

Princípio do Elemento Extremo[]

Você pode saber mais sobre aqui.

Exemplo (IMO 2000)[]

Um mágico tem cem cartas numeradas de a . Ele as coloca dentro de três caixas, uma vermelha, uma branca e uma azul, sendo que cada caixa contem pelo menos uma carta. Um membro da audiência pega duas cartas de duas caixas diferentes e anuncia a soma dos números das duas caras. Dada essa informação, o mágico localiza a caixa da qual nenhum carta foi retirada.

De quantas maneiras diferentes o mágico pode colocar as cartas de forma que o truque funcione?

Solução: Vamos começar repensando nosso problema de outro modo (de alguma forma que nos permita dar pensamentos mais aprofundados). Suponha que , onde está na caixa de cor , está na de cor e está na de cor (onde , e são cores distintas). Podemos advinha em que caixa está a carta ?

Suponha que ela esteja na caixa de cor . Se o membro da audiência disser , então o médico deve falar que a caixa em que nenhuma carta foi retirada é a (já que está em e está em ). Só que se o membro disser , como e estão nas caixas e , respectivamente, o mágico deverá dizer que a caixa em que nenhuma carta foi retirada é . Só que nesse caso, o truque não pode funcionar, pois . Desta forma, a carta na caixa . Analogamente, ela não está na caixa . Desta forma, está na caixa .

Como essa maneira de ver o problema pode nos ajudar a extrair mais informações do problema? Conhecemos quatro bons números tais que a soma de dois deles é igual a soma dos outros dois? Isso acontece quando temos dois números consecutivos: afinal, . Mas usar essa informação depende se essas cartas estão em caixas distintas ou não. Por isso, vamos dividir o nosso problema em casos:

1º Caso: Para algum as cartas estão em caixas distintas

Como , pelo argumento que apresentamos no começo da solução, e pertencem à mesma caixa. Da mesma forma, como estão em caixas distintas e , segue que e estão na mesma caixa. Pelo mesmo raciocínio, e estão na mesma caixa e assim por diante.

E quanto às cartas com valores menores do que ? Vejamos onde está . Será que conseguimos colocar ele em uma soma com coisas que já conhecemos? Sim, observe que . Pelo mesmo argumento que já fizemos, e estão na mesma caixa.

Vamos chamar as cores das caixas que contem de , respectivamente. Por isso,

Cartas de :

Cartas de :

Cartas de :

Observe que em cada caixa, as cores aumentam de em . Por isso, possuem o mesmo resto na divisão por . Desta forma, uma das caixas contem , a outra e a terceira . Desta forma, o mágico deve definir qual das caixas é vermelha, qual é branca e qual é azul. Ele pode fazer isso de maneiras.

2º Caso: Não existem três cartas consecutivas em caixas diferentes

Vale a pena prestarmos atenção no menor cartão de cada uma das caixas. Vamos supor que a caixa que possui o seja . Considere e as menores cartas das outras duas caixas cujas cores chamaremos de e , respectivamente.

Como estamos lidando com um "menor" vale a pena sabermos qual é menor: ou . Por supor, sem perder a generalidade, que é menor do que .

Já que estamos falando sobre cartas consecutivas, vale a pena perguntar onde fica , , .

Note que não pode estar na caixa de cor (pois a menor carta de lá é e é menor do que ). Além disso, não pode estar na caixa de cor. Com efeito, é menor do que que é menor do que e a menor carta de é . Portanto, está na caixa de cor .

As cores que já sabemos podem ser combinadas em uma igualdade para encontrarmos outra? Sim: observe que

Para falarmos sobre , devemos supor que seja menor do que (caso contrário seria e isso não pode ocorrer). Pela igualdade anterior, devemos ter na cor .

Será que podemos combinar essas cartas em outra igualdade? Observe que ainda não falamos sobre , por exemplo. Além disso,

Portanto deve estar na cor . Mas isso é impossível, pois estariam em cores diferentes. Logo, não podemos ter menor do que . Mas não existem cartas maiores do que . Desta forma, , ou seja, a única carta na urna de cor é a .

IMO2000Q4

Já que vale a pena mexer com consecutivos e já sabemos sobre o , vamos falar sobre o . Repare que

Assim é da caixa de cor . Parece que a mesma ideia não funciona para falarmos sobre . Vamos por outra estratégia. Que tal eliminação? Observe que não pode pertencer à caixa de cor . Será que ele pode pertencer à de cor ? Se isso ocorrer, então

E com isso pertenceria à caixa de cor , o que é um absurdo (pois lá só temos a caixa de cor ). Desta forma, pertence à caixa de cor . Por motivos análogos, pertence à caixa de cor (afinal ). Pelo mesmo raciocínio, podemos provar que a caixa possui os cartões . Existe um modo de provarmos que isso vale em geral?

Considere um número dentre . Observe que ele não pode pertencer à caixa de cor . Suponha, por absurdo, que ele esteja na caixa de cor . Então

Então pertence à caixa de cor . Absurdo. Logo, deve pertencer à caixa de cor . Por isso, temos:

Cartas de :

Cartas de :

Cartas de :

O número de maneiras de escolhermos as cores aqui é .

Desta forma, o total de possibilidades é

Construções[]

Antes de construir uma casa, é interessante imaginar ela pronta. O mesmo acontece para objetos matemáticos.

Exemplo (IMO 1994)[]

Mostre que existe um conjunto de inteiros positivos com a seguinte propriedade: Para qualquer conjunto infinito de primos existe dois inteiros positivos e tais que cada um deles é o produto de elementos distintos de para algum .

Solução: Já que é um conjunto qualquer de primos infinitos, o conjunto deve mexer com todos os primos possíveis. Além disso, ela deve multiplicar todos os primos de forma que deixe alguns de fora (para encontrarmos ), mas que também tenha alguns dentro (para encontrarmos ). Mais ainda não precisamos de todas as quantidades de primos multiplicando já que é para algum e não para todos.

Vamos tomar o conjunto de todos os produtos de primos começando por (isto é, tomaremos o conjunto formado por todos os produtos de dois primos cujo menor é , pelo produto de três primos cujo menor é , produto de cinco primos cujo menor é e assim por diante). Em outras palavras os elementos serão da forma onde são primos. E por que começar com ? Para termos alguns números fora e outros dentro do conjunto. Assim

Mostremos que esse conjunto satisfaz as condições do enunciado. De fato, para qualquer conjunto infinito de primos (onde ), podemos tomar

Observe que está em pois é o produto de primos e começa com . Porém não está em , pois apesar de ser o produto de primos, ele não começa com .

Lugares Para Estudar[]

Vídeos[]

Bibliografia[]

Advertisement