Número 3 Setembro 2006

• O LEMA DA PERPENDICULAR •
Bruno Holanda

Muitas vezes nos deparamos com problemas que pedem

para mostrar que dois segmentos são perpendiculares, ou
que um ângulo dado é reto. Neste artigo vamos falar sobre
um lema pouco conhecido, mas de muita utilidade nesse
tipo de problema.

Lema 1 (da Perpendicular). Dados dois segmentos AB e

CD, temos que AB⊥CD ⇔ AC 2 + BD2 = AD2 + BC 2 .

Você pode provar esse lema de várias maneiras: Usando Figura 1: IMO 1985
vetores, Teorema de Pitágoras ou geometria analı́tica. Es-
colha seu método favorito e tente prová-lo!
e ∠N CP são todos iguais. Usando potência de ponto,
Exemplo 1 (USAMO 1997). Seja ABC um triângulo. De- temos:
senhe triângulos isósceles DBC, AEC, ABF externos ao
triângulo ABC, com bases sobre seus lados. Prove que as BM · BP = BN · BC = (BO + r)(BO − r) = BO2 − r2 ,
retas perpendiculares a EF, F D, DE passando por A, B, C,
respectivamente, são concorrentes. onde r denota o raio do cı́rculo centrado em O. De modo
análogo:
Prova. Seja P o ponto de encontro das perpendiculares
passando por A e B. Desse modo, temos que: P M · P B = P N · P K = (P O + r)(P O − r) = P O2 − r2 .

P E 2 + AF 2 = P F 2 + AE 2 , Com isso,

P F 2 + BD2 = P D2 + BF 2 P O2 − BO2 = BP (P M − BM ) = P M 2 − BM 2 .

Somando essas duas equações, substituindo CE = AE, Pelo lema da perpendicular, o resultado segue de imediato.
BF = AF , BD = CD e fazendo os cancelamentos
possı́veis, obtemos
Exercı́cio 1 (Bielorússia 2000). Seja P o ponto de encon-
P E 2 + CD2 = P D2 + CE 2 , tro das diagonais AC e BD de um quadrilátero convexo
ABCD, com AB = AC = BD. Se O 6= I são respecti-
relação que pelo lema é equivalente a P C⊥DE. Assim, fica vamente o circuncentro e o incentro do triângulo ABP ,
claro que as três perpendiculares são concorrentes. prove que OI⊥CD.

Exemplo 2 (IMO 1985). Uma circunferência de centro O Exercı́cio 2 (Rússia 1995). ABCD é um quadrilátero tal
passa pelos vértices A e C do triângulo ABC, e corta que AB = AD e B̂ = D̂ = 90◦ . Os pontos F e E são es-
os segmentos AB e BC nos pontos K e N , respectiva- colhidos em BC e DC, respectivamente tais que DF ⊥AE.
mente. Os circuncı́rculos dos triângulos ABC e KBN Prove que AF ⊥BE.
intercectam-se novamente em M . Prove que OM B é um
ângulo reto. Referências
Prova. Antes de tudo: vamos desenhar a figura! [1] Carlos Y. Shine. Geometria com Contas. Eureka 17
Observe que as retas AC, KN, BM concorrem no centro (2003), 17-35.
radical P dos três cı́rculos. Agora, note que o quadrilátero
P M N C é cı́clico, já que os ângulos ∠BM N , ∠AKP [2] Kiran S. Kedlaya. Notes on Euclidean Geometry.

[Link]/sigma 1 [Link]@[Link]
 Exercı́cio 4. Existem 21 pontos sobre um cı́rculo. Prove
• O TEOREMA DE TÚRAN • que existem pelo menos 100 arcos definidos por esses 21
Samuel Barbosa pontos, cujas medidas em graus são menores ou iguais a
120◦ . (Dica: trace uma aresta entre A e B se ∠AOB >
120◦ )
Neste artigo iremos explorar um resultado devido a Paul Exercı́cio 5 (Hungria-Israel). Prove que se o número de
Túran (1910-1976) (cf. [4]), que é considerado um dos pre- arestas de um grafo G é maior ou igual a n2 /4 + 2 então
cursores da teorial extremal dos grafos. Vamos começar G contém dois triângulos com exatamente um vértice em
falando de um caso particular. Se adicionarmos suces- comum.
sivamente arestas em um grafo de n vértices, em algum
momento iremos formar algum “triângulo”. Qual seria o Exercı́cio 6. Seja G um grafo com 10 vértices e 26 arestas.
máximo de arestas que poderı́amos traçar em nosso grafo Mostre que G deve ter pelo menos 5 triângulos.
para evitar isso?
Chamaremos de Kp , ou p−clique, um grafo completo
Teorema 2. Um grafo de n vértices G que possui mais que de p
vértices (i.e., um grafo com p vértices, onde todas
⌊n2 /4⌋ arestas possui um “triângulo”. as p2 arestas possı́veis estão traçadas). Então triângulos
são 3−cliques, e queremos estender o resultado acima para
p−cliques. Suponha que n = t(p − 1) + r, 1 ≤ r ≤ p − 1.
Divida os n vértices do grafo G em p − 1 subconjuntos
S1 , S2 , . . . , Sp−1 , com r deles de cardinalidade t + 1 e p −
1 − r de cardinalidade t. Em cada Si não iremos traçar
nenhuma aresta interna, mas todo vértice de Si será ligado
a todo vértice de Sj se i 6= j. Ao todo traçamos n2 −


t+1 t



2 r − 2 (p − 1 − r) aretas. Substituindo t = (n −
r)/(p − 1) obtemos:

n2 (p − 2) r(p − 1 − r)
− = M (n; p)
Prova. Suponhamos que G não possui triângulo. Seja A o 2(p − 1) 2(p − 1)
vértice de G com o maior grau, k digamos. Claramente os arestas. Veja que nosso grafo não contém um Kp .
k vértices que estão ligados a A não podem estar ligados
entre si. Assim todas as arestas que não contém o vértice Teorema 3 (Turán,1941). Se um grafo de n vértices contém
A devem conter pelo menos um vértice dos outros n−k −1 mais que M (n, p) arestas, então ele contém um Kp como
que não estão ligados a A. Como cada um desses n − k − 1 subgrafo.
vértices tem grau no máximo k, então G possui no máximo
Prova. Faremos uma prova por indução sobre t. Para t
=
k + k(n − k − 1) = n2 /4 − (n/2 − k)2 ≤ n2 /4 arestas. 0 o resultado é imediato, uma vez que M (n, p) = n2 e
Exite uma história curiosa sobre este teorema . Reza a n < p. Considere agora um grafo G com n vértices, sem
lenda que o grande matemático húngaro Paul Erdös per- um Kp e com o número máximo de arestas. Claramente G
guntou para o joven Lois Posá a demonstação do teorema contém um subgrafo Kp−1 , digamos H, pois caso contrário
acima. Posá tinha 12 anos e conseguiu uma demonstração poderı́amos adicionar mais uma aresta a G e não terı́amos
em menos de 6 horas! Vejamos algumas aplicações simples um Kp . Cada um dos vértices restantes está ligado a no
de nosso resultado: máximo p − 2 vértices de H. Por outro lado, os n − p +
1 vértices restantes não contêm um Kp como subgrafo.
Exercı́cio 3 (Rússia). Em um torneio nacional de futebol Como n − p + 1 = (t − 1)(p − 1) + r, nós podemos aplicar
participam 20 equipes. Qual é o número mı́nimo de par- a hipótese de indução a este conjunto de pontos. Então, o
tidas que deve ter o torneio para que, dentre quaisquer três número de arestas de G é no máximo
equipes, haja duas que joguem entre si?  
p−1
Prova. Represente cada time por um vértice e trace uma M (n − p + 1, p) + (n − p + 1)(p − 2) + = M (n, p).
aresta entre dois times se eles não jogam entre si. Não 2
podemos ter um triângulo, logo o número de arestas
2
traçadas é menor

ou igual a ⌊20 /4⌋ = 100. Então temos
20
pelo menos 2 − 100 = 90 arestas não traçadas, ou seja, Exercı́cio 7. Será que a cota estabelida por Turán é real-
devemos ter pelo menos 90 jogos. Para construir um e- mente boa? Use a demonstração anterior para mostrar que
xemplo com 90 jogos, divida os dois times em
dois grupos o número máximo de arestas em um grafo de n vértices
de 10 e em cada grupo realize todos os 10 = 45 jogos sem Kp é atingido apenas em configurações como a que
2
possı́veis. antecede a demonstração do teorema.

[Link]/sigma 2 [Link]@[Link]
Exercı́cio 8 (IMO 2003). Seja A um subconjunto de 101 1. Existe um K4 azul. Observe o conjunto formado pelo
elementos do conjunto S = {1, 2, . . . , 1000000}. Prove que K4 e por cada um dos outros 5 vértices. Como de-
existem números t1 , t2 , . . . , t100 em S tais que os conjuntos vemos ter pelo menos duas arestas pretas entre eles,
cada um dos outros 5 vértices deve estar ligado a pelo
Aj = {x + tj | x ∈ A}, j = 1, 2, . . . , 100 menos 2 vértices do K4 . Assim teremos pelo menos
2 × 5 = 10 arestas pretas.
são disjuntos dois a dois.
Prova. Associe a cada elemento de S um vértice. Uma 2. Não existe um K4 azul. Pelo teorema de Turán, e-
aresta entre os vértices i e j é traçada se se os conjuntos xistem no máximo 27 arestas azuis. Como
a soma
A+i e A+j são disjuntos onde A+k := {x+k|x ∈ A}. Uma do número de arestas de ambas as cores é 92 = 36,
aresta liga dois elementos de S cujo módulo da diferença devemos ter pelo menos 9 arestas pretas.
não é igual a nenhum dos números |ai − aj | onde A =
{a1 , a2 , . . . , a101 }. Veja que #{|ai − aj |} ≤ 101 × 100/2. Basta mostrarmos um exemplo com 9 arestas. Veja que
Assim cada vértice x tem grau pelo menos 106 − 101 × 100. três triângulos disjuntos formados por arestas pretas sat-
Veja que nosso problema termina se encontrarmos um K100 isfazem o enunciado.
em nosso grafo. Temos pelo menos 106 (106 − 101 × 100)/2
arestas e M (106 , 100) = (98×1012 )/(2×99)−98/(2×99) <
Exercı́cio 13 (USA, TST 2002). Seja n um inteiro pos-
106 (106 − 101 × 100)/2. Pelo teorema de Turán nosso grafo
itivo e seja S um conjunto de 2n+1 elementos. Seja
contém um K100 .
f uma função do conjunto de subconjuntos de dois
elementos de S em {0, 1, . . . , 2n−1 − 1}. Assuma
Exercı́cio 9 (China 2005). Para n pessoas, é conhecido que: que, para quaisquer elementos x, y, z de S, um den-
tre f ({x, y}), f ({y, z}), f ({z, x}) é igual à soma dos out-
a) entre quaisquer três pessoas existem duas que se co- ros dois. Mostre que existem a, b, c em S tais que
nhecem, e f ({a, b}), f ({b, c}), f ({c, a}) são todos iguais a 0.
b) entre quaisquer quatro pessoas existem duas que se des- Exercı́cio 14. Sejam x1 , x2 , . . . , xn números reais distintos.
conhecem. Prove que #{(i, j)|1 < |xi − xj | < 2} ≤ n2 /4
Encontre o valor máximo de n. Assuma que a relação
Prova. Para cada número xi associe um vértice. Trace
de conhecimento é simétrica.
uma aresta entre i e j se |xi − xj | ∈ (1, 2). Veja que não
Exercı́cio 10 (Polônia 1997). Dados quaisquer n pontos so- podemos ter um K3 . Então #{(i, j)|1 < |xi − xj | < 2} ≤
n2 n2 /4
bre um cı́rculo unitário, mostre que no máximo seg-
3
mentos
√ ligando pares de pontos tem comprimento maior
que 2. (Dica: trace uma aresta Exercı́cio 15 (USAMO 1995). Suponha que em uma certa
√ entre dois pontos se o sociedade cada par de pessoas pode ser classificada como
segmento entre eles é maior que 2. Use a desgualdade de
Ptolomeu para mostrar que não pode existir um K4 ). amigável ou hostil. Membros de pares amigáveis são
chamados de amigos e membros de pares hostis são chama-
Exercı́cio 11 (OBM 2005). Temos quatro baterias car- dos de adversários. Suponha que a sociedade tenha n pes-
regadas, quatro baterias descarregadas e um rádio que soas, q pares amigáveis e que pelo menos um par em qual-
necessita de duas baterias carregadas para funcionar. quer conjunto de três pessoas é hostil. Prove que existe pelo
Supondo que não sabemos quais baterias estão carregadas menos um membro da sociedade cujos adversários contêm,
e quais estão descarregadas, determine o menor número ao todo, não mais que q(1 − 4q/n2 ) pares de amigos.
de tentativas suficiente para garantirmos que o rádio fun-
cione. Uma tentativa consiste em colocar duas das baterias Exercı́cio 16. Mostre que se um grafo com n vértices não
no rádio e verificar se ele, então, funciona. contém um subgrafo completo com k vértices (k ≥ 2) então
contém pelo menos ⌈n/(k − 1)⌉ vértices de grau menor ou
Exercı́cio 12 (Japão 1997). Seja G um grafo com 9
igual a ⌊(k − 2)n/(k − 1)⌋.
vértices. Suponha que, dados quaisquer 5 vértices de G,
existem pelo menos duas arestas com ambas as extremi-
Exercı́cio 17. Um conjunto M contém 1001 pessoas e é
dades dentre esses 5 vértices. Qual é o menor número
tal que cada subconjunto de 11 pessoas contém pelo menos
possı́vel de arestas em G?
dois indivı́duos que se conhecem. Mostre que existem
Prova. Vamos pintar as arestas de nosso grafo de preto e pelo menos 101 pessoas onde cada uma delas conhece pelo
as arestas não traçadas de azul. Vamos dividir o problema menos 100 pessoas em M . (Dica: Use o exercı́cio anterior
em dois casos: no grafo complementar)

[Link]/sigma 3 [Link]@[Link]
Referências
[1] J.H. van Lint, R. M. Wilson. A Course in Combina-
torics. (1992), 29-34.
estaria no cı́rculo. De modo análogo, o 29 também
[2] Edward Lozansky, Cecil Rousseau. Winning Solu-
deve estar no cı́rculo. Agora, para provar que 29 é o
tions. (1996), 205-213.
mı́nimo basta construir o exemplo.
[3] Ioan Tomescu. Problems in Combinatorics and Graph
Theory. (1985), 45-46. ⋆⋆⋆
[4] Paul Turán. An extremal problem in graph theory.
A8. Dados a e b reais, mostre que existem infinitos irra-
Mat. Fiz. Lapok 41 (1941), 435-452.
cionais x no intervalo (a, b) com x3 racional.
(Solução de Diego Marques Ferreira)
Lema: O conjunto
 
• FÓRUM DE PROBLEMAΣ • p
S= | p, q ∈ Z e p ≡ q ≡ 1 (mod 2)
2q

é denso em R, pois para qualquer intervalo (a, b)

Esta é apenas a terceira vez que fazemos a coluna Fórum existe n ı́mpar tal que (2na, 2nb) contém um inteiro
de Problemas na Sigma, e já estamos muito felizes com o m
m ı́mpar, ou seja, ∈ (a, b). Considere o intervalo
crescente número de soluções enviadas. Porém, devido ao 2n
3 3
nosso pequeno espaço, deixaremos para publicar as demais (a , b ). Pelo lema acima, existem infinitos números
p
soluções em um próximo número. da forma ∈ (a3 , b3 ). Então existem infinitos x da
2q
p
r
Soluções forma 3 ∈ (a, b), tal que x3 ∈ Q mas x 6∈ Q.
2q
I3. Resolva a equação
√ √ (Solução de Paulo Sérgio e Pedro Paulo)
√ √
1− 2+ 3 x+ y Seja d = b − a o comprimento do intervalo (a, b). E-
√ √ = 1
1+ 2− 3 2 xistem infinitos primos p tais que p > 3 . Com isso,
√ √ d
onde x, y ∈ Z. b 3 p − a 3 p > 1, e podemos garantir que existe um
√ √ n n
(Solução de Gelly Whesley Silva Neves) inteiro n ∈ (a 3 p, b 3 p). Logo, √
3 p
∈ (a, b), √
3 p
6∈ Q
√ √ √ √ √ √ n3
1− 2+ 3 2 −2 + 2 + 6 pois 3 p 6∈ Q e ∈ Q.
√ √ ×√ = √ √ p
1+ 2− 3 2 2+ 2− 6
⋆⋆⋆
√ √ √ √ √ √
−2 + 2 + 6 2 2 + 2 + 2 3 2+ 6 A9. Encontre todos os polinômios P (x) ∈ R[x] tais que se
√ √ × √ √ = .
2+ 2− 6 2 2+2+2 3 2 P (a) ∈ Z, então a ∈ Z.
Então (x, y) = (2, 6) é solução. (Solução de Paulo Sérgio e Pedro Paulo)
Dado um inteiro a ∈ Z, se |P (a + 1) − P (a)| > 1
⋆⋆⋆
então, pelo teorema do valor intermediário, existe um
inteiro x no intervalo de extremos P (a) e P (a + 1)
I10. Ao redor de um cı́rculo são escritos os números de 1 a tal que x = P (y) para algum y ∈ (a, a + 1). Isto
N , uma única vez cada, de tal forma que dois inteiros é uma contradição pois y 6∈ Z. Seja Q(x) = P (x +
adjacentes têm pelo menos um dı́gito em comum em 1) − P (x). Se Q não é um polinômio constante então
suas representações decimais. Ache o menor N > 2 limx→∞ |Q(x)| = +∞ e assim existiria a ∈ Z tal que
para qual isso é possı́vel. |P (a + 1) − P (a)| > 1. Portanto, Q é constante e
(Solução de João Lucas Camelo) igual a c, digamos, de modo que o teorema do valor
O problema sugere que o menor inteiro seja pelo médio garante a existência de dx ∈ (x, x + 1) tal que
menos 3. Porém, ao lado do número 3, devemos colo- c = P (x + 1) − P (x) = P ′ (d). Então P ′ (x) − c é um
car dois números com dı́gitos 3. Fica claro que deve- polinômio com infinitas raı́zes, donde identicamente
mos usar o 13 e o 23. Mas deste jeito, o 9 também nulo. Logo, P tem grau no máximo 1. Analisando as

[Link]/sigma 4 [Link]@[Link]
 possı́bilidades encontramos que os únicos polinômios Problemas Avançados
satisfazendo as condições do problema são: P (x) =
x + b, com b ∈ Z e P (x) = c, com c 6∈ Z. A14. Seja I : Rn → Rn uma isometria (i.e., uma aplicação
que preserva a distância Euclidiana) sem pontos fixos.
⋆⋆⋆ Prove que I mantém uma reta fixa.
(Proposto por Tiago Caúla)
A12. Seja ABC um triângulo acutângulo escaleno cujo
ortocentro é H. M é o ponto médio do segmento BC. A15. Dado um cı́rculo Γ, uma reta d é traçada não inter-
N é o ponto onde se intersectam o segmento AM e sectando Γ. M e N são dois pontos variando em d,
a circunrefência determinada por B, C e H. Mostre de tal forma que o cı́rculo de diâmetro M N seja tan-
que HN ⊥AM . gente externamente a Γ. Prove que existe um ponto
P no plano tal que ∀M, N , o ∠M P N é constante.
(Solução de Claudio Arconcher ) (Proposto por Rafael Sampaio Rezende)
Vamos usar o seguinte lema: seja P o simétrico
A16. Mostre que não existem pares de inteiros positivos
do A em relação ao circuncentro O do △ABC.
(x, y) satisfazendo 3y 2 = x4 + x.
Então BHCP é um paralelogramo. Pelo lema, os
triângulos BHC e BP C são congruentes. Sejam A17. Seja n ≥ 2 um inteiro. Um grupo de pessoas é dito
R′ e R respectivamente os raios dos circuncı́rculos n − apertado se, para qualquer pessoa no grupo, é
dos triângulos ABC e BHC. O Teorema dos possı́vel encontrar n outras pessoas que se conhecem
Senos aplicado aos triângulos △BHC e △ABC nos mutuamente. Encontre o maior valor possı́vel de N tal
dá 2R′ = BC/ sen (BAC) = BC/ sen (BP C) = que todo grupo n−apertado de N pessoas contém um
BC/ sen (BHC) = 2R. Então o circuncı́rculo Γ1 de grupo de n + 1 pessoas que se conhecem mutuamente.
centro W do triângulo △BHC é congrunte ao cir-
cuncı́rculo Γ2 do triângulo △ABC. Como AH = OW A18. Dado um número natural k maior que 1, prove que é
(pelo teorema de Euler) e ambos são perpendiculares a impossı́vel colocar os números 1, 2, ..., k2 em um tabu-
−−→ leiro k × k de forma que todas as somas dos números
BC, Γ1 é a transladada de Γ2 pelo vetor AH. Sendo Q
escritos em cada linha e coluna sejam potências de 2.
a imagem de P pela translação, AHQP é um paralel-
ogramo. Como M é ponto médio de HP , devido ao A19. Seja G um grupo tal que todo elemento x, x 6= 1,
lema, M é ponto médio de AQ e consequentemente tem ordem p.
N ∈ AQ. Por fim, HQ é diâmetro de Γ1 , pois é im-
agem do diâmetro AP de Γ2 , logo HN ⊥AM . a) Mostre que p é um número primo.
b) Mostre que se qualquer subconjunto de p2 − 1
⋆⋆⋆ elementos de G contém p elementos que comutam
um com o outro, então G é um grupo abeliano.
Problemas Iniciantes
I11. Prove que o número 8n −3n −6n +1 é sempre múltiplo Também recebemos soluções corretas:
10 para todo n ∈ N.
(Proposto por Gelly Whesley Silva Neves) Pedro Paulo e Paulo Sérgio A11
Rafael Rezende A11
I12. Seja RST U V pentágono regular. Construa um Prof. Lev Birbrair A9
triângulo eqüilátero P RS com P no interior do Tiago Caúla A9
pentágono. Ache a medida do ângulo ∠P T V .
I13. Mostre como colocar 16 peças brancas e 16 peças
pretas em um tabuleiro de xadrez (8 × 8) de modo Editores Resposáveis:
que, para toda peça, o número de peças brancas que Antônio Caminha Muniz Neto
são suas vizinhas é igual ao número de peças pretas Francisco Bruno L. Holanda
que também são suas vizinhas. (Duas peças são ditas Samuel Barbosa Feitosa
vizinhas se as casas que elas ocupam possuem pelo
menos um vértice em comum.) As soluções para os problemas dos arti-
gos e do fórum podem ser enviadas para o
I14. Os números 1, 2, 3, ..., 1000 são escritos no quadro. e-mail [Link]@[Link] ou direta-
Dois jogadores apagam alternadamente um dos mente pelo o correio para:
números da lista até que só restem dois números. Se Bruno Holanda
a soma desses números for divisı́vel por 3, o primeiro Rua Neudélia Monte 440
jogador vence, caso contrário vence o segundo. Quem 60833-420 Fortaleza-CE
tem a estratégia vencedora?

[Link]/sigma 5 [Link]@[Link]