Mostre que dentre 4 números quaisquer existem 2 números cuja diferença é divisível por 3

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