Grátis 74 pág.
- Denunciar
Pré-visualização | Página 10 de 11
distam mais que √ 2/2. Solução. Vamos dividir o quadrado em quatro quadradinhos de lado 1/2, como mostra a �gura. Logo, pelo PCP pelo menos dois deles de- 1 • •• • • vem estar no mesmo quadradinho, uma vez que temos 4 quadradinhos e 5 pontos. Logo, como a maior distância num quadrado é a diagonal, o Teorema de Pitágoras nos garante que a distância desses dois pontos é no máximo √ 2/2, como queríamos mostrar. Exemplo 4.16. Na região delimitada por um triângulo equilátero de lado 4 são marcados 10 pontos no interior deste. Prove que existe ao menos um par destes pontos cuja distância entre eles não é maior que√ 3. Solução. Dividimos o triângulo equilátero de lado 4 em 16 triângulos equiláteros menores de lado 1, conforme a Figura 4.3. Agora pintamos os triângulos nas cores branco e cinza de maneira que dois triângulos vizinhos, isto é, com um lado comum, são pintados de cores diferentes. Se tivéssemos dois pontos no mesmo triângulo a distância máxima possível entre eles seria 1 e o problema estaria resol- vido. Se tivéssemos pontos em triângulos vizinhos, a maior distância possível entre eles seria √ 3 e também isto resolveria o problema. Se não tivéssemos nenhum dos casos anteriores, não seria difícil ver que 4.5 Miscelânea 153 A B C D E • • • • • • • •• • Figura 4.3: O triângulo DBE é equilátero de lado 3 os 10 pontos deveriam estar situados sobre os 10 triângulos brancos, contendo cada triângulo exatamente um ponto. Dividindo o triângulo DBE em 4 triângulos congruentes de lado 3/2 pelo PCP temos que pelo menos dois dos 6 pontos contidos em DBE estão num destes 4 triângulos, logo a distância entre eles não é maior que 3/2 < √ 3. Com isto terminamos nossa prova. 4.5 Miscelânea Os problemas que apresentamos a seguir usam o PCP combinado com outras idéias que são muito empregadas nas suas soluções. Exemplo 4.17. Em cada quadradinho de um tabuleiro 3×3 é colocado um dos números: -1, 0 ou 1. Prove que entre todas as somas das linhas, colunas e diagonais do tabuleiro há duas que são iguais. Por exemplo, no tabuleiro abaixo a soma da segunda linha é 2, que coincide com a soma da terceira coluna. 154 4 O Princípio da Casa dos Pombos -1 -1 1 1 0 1 0 -1 0 Solução. Seja S = a1 + a2 + a3, onde cada a1, a2 e a3 podem tomar valores: −1, 0 e 1. Então, temos 7 valores possíveis para S (casas), que são: −3,−2,−1, 0, 1, 2, 3. O tabuleiro 3×3 tem 3 linhas, 3 colunas e 2 diagonais, portanto, ao somarmos os elementos de cada uma das linhas, colunas e diagonais, obteremos 8 números (pombos). Como existem somente 7 valores possíveis para estes números, pelo PCP pelo menos dois deles devem ser iguais. Exemplo 4.18. Dado qualquer conjunto A formado por 10 números naturais escolhidos entre 1 e 99, inclusos, demonstre que existem dois subconjuntos disjuntos e não vazios de A tal que a soma dos seus res- pectivos elementos é igual. Solução: É conhecido que A tem 210 − 1 = 1.023 subconjuntos não- vazios diferentes. A soma dos elementos de cada um deles dá uma quantidade menor do que 1.000, pois o subconjunto com no máximo 10 elementos de maior soma possível é o formado por 90, 91, . . . , 99, e nesse caso 90+ 91+ · · ·+99 = 945. Agora consideramos os pombos como sendo os 1.023 subconjuntos distintos de A e as casas como sendo as somas possíveis dos elementos de cada um dos conjuntos. Logo, como o número de conjuntos é maior que o número de somas possíveis, devem existir dois conjuntos B e C de A, de tal modo que a soma dos elementos de B é igual à soma dos elementos de C. Se B 4.5 Miscelânea 155 e C são disjuntos, acabou a prova. Se não, considere D = B −B ∩ C e E = C − B ∩ C. Logo, os conjuntos D e E são disjuntos e a soma dos seus elementos é a mesma, pois retiramos de ambos a mesma quantidade. Exemplo 4.19. Qual é o maior número de quadradinhos de um ta- buleiro de 8 × 8 que podem ser pintados de preto, de forma tal que qualquer arranjo de três quadradinhos, como mostra a Figura 4.4, te- nha pelo menos um dos quadradinhos não pintado de preto? Figura 4.4: Tridominós Solução. Primeiramente, pintamos o tabuleiro de 8×8 como um tabu- leiro de jogar xadrez, ou seja, 32 quadradinhos pintados de branco e 32 quadradinhos pintados de preto (ver Figura 4.5). Figura 4.5: Tabuleiro de xadrez 156 4 O Princípio da Casa dos Pombos Notemos que uma vez pintado o tabuleiro desta forma é satisfeita a exigência do problema, pois nunca temos 2 quadradinhos vizinhos (quadradinhos com um lado comum) pintados de preto. Mostraremos agora que se pintamos 33 quadradinhos de preto en- tão a condição exigida no problema falha. De fato, se dividimos o tabuleiro em 16 quadrados de 2 × 2 (casas) e pintamos 33 quadra- dinhos de preto (pombos); então, como 33 = 16 · 2 + 1, pela versão geral do PCP um dos 16 quadrados de 2× 2 contém 3 quadradinhos pintados de preto. Portanto, este último contém um arranjo como na Figura 4.4 completamente pintado de preto. Resumindo, o número máximo de quadradinhos que podemos pin- tar de preto é 32. Exemplo 4.20. Dados sete números reais arbitrários, demonstre que existem dois deles, digamos x e y, tais que 0 ≤ x− y 1+ xy ≤ 1√ 3 Solução. Primeiramente observamos que a expressão x−y 1+xy nos faz pen- sar na fórmula tan(α− β) = tanα− tan β 1 + tanα tan β . (4.2) Sejam x1, x2, · · · , x7 os sete números selecionados arbitrariamente. Lembramos que a função tangente é uma bijeção entre o intervalo (−π 2 , π 2 ) e os números reais R, logo para cada xi, 1 ≤ i ≤ 7, existe um αi ∈ (−π2 , π2 ) tal que tan(αi) = xi. Dividimos o intervalo (−π2 , π2 ) em seis subintervalos de comprimento π 6 , como mostra o desenho a seguir. Pelo PCP dois dos números αi pertencem ao mesmo subintervalo. Denotemos os mesmos por αi1 e αi2 e suponhamos, sem perda de 4.6 Exercícios 157 αi1 αi2 −π 2 π 2π 6 generalidade, que αi1 ≤ αi2 . Então vale 0 ≤ αi2 − αi1 ≤ π 6 . Usando o fato de que a tangente é uma função crescente e a fórmula (4.2) temos que tan(0) ≤ tan(αi2 − αi1) ≤ tan( π 6 ). Equivalentemente, 0 ≤ xi2 − xi1 1 + xi2xi1 ≤ 1√ 3 . 4.6 Exercícios 1. Seja C um conjunto formado por cinco pontos de coordenadas inteiras no plano. Prove que o ponto médio de algum dos seg- mentos com extremos em C tem também coordenadas inteiras. 2. O conjunto dos dígitos 1, 2, ..., 9 é dividido em três grupos. Prove que o produto dos números de algum dos grupos deve ser maior que 71. 3. Prove que se N é ímpar então para qualquer bijeção p : IN → IN 158 4 O Princípio da Casa dos Pombos do conjunto IN = {1, 2, . . . , N} o produto P (p) = (1−p(1))(2− p(2)) · · · (N − p(N)) é necessariamente par. (Dica: O produto de vários fatores é par se, e somente se, um dos fatores é par.) 4. Dado um conjunto de 25 pontos no plano tais que entre quaisquer 3 deles existe um par com distância menor que 1. Prove que existe um círculo de raio 1 que contém pelo menos 13 dos 25 pontos dados. 5. Prove que entre quaisquer 5 pontos escolhidos dentro de um triângulo equilátero de lado 1 sempre existe um par deles cuja distância não é maior que 0,5. 6. Marquemos todos os centros dos 64 quadradinhos de um ta- buleiro de xadrez de 8× 8. É possível cortar o tabuleiro com 13 linhas retas que não passem pelos pontos marcados e de forma tal que cada pedaço de recorte do tabuleiro tenha no máximo um ponto marcado? 7. Prove que existem duas potências de 3 cuja diferença é divisível por 1.997. 8. São escolhidos 6 números quaisquer pertencentes ao conjunto A = {1, 2, 3, . . . , 10}. Prove que existem dois desses seis números cuja soma é ímpar. 9. Seja x um número real arbitrário. Prove que entre os números x, 2x, 3x, . . . , 101x 4.6 Exercícios 159 existe um tal que sua diferença com certo número inteiro é menor 0,011. 10. Mostre que entre nove números que não possuem divisores pri- mos maiores que cinco, existem dois cujo produto é um qua- drado. 11. Um disco fechado de raio um contém sete pontos, cujas distân- cias entre quaisquer dois deles