Prévia do material em texto
Resolução de Problemas
Lista 02
Divisibilidade
1. Prove que se n é ı́mpar
(a) n2 − 1 é diviśıvel por 8;
(b) n3 − n é diviśıvel por 24;
(c) n2 + (n+ 2)2 + (n+ 4)2 + 1 é diviśıvel por 12.
2. Três números primos p, q e r, maiores que 3, formam uma progressão
aritmética, ou seja, q = p+ d e r = p+2d. Prove que d é diviśıvel por 6.1
3. Mostre que 311 − 3 é diviśıvel por 112.
4. Um robô possui dois botões, permitindo que a cada momento ele suba a
degraus ou desça b degraus de uma escada com infinitos degraus. Sabendo
que o robô está no ińıcio da escada, pergunta-se:
(a) Se a = 12 e b = 3, é posśıvel que o robô visite todos os degraus após
uma sucessão desses movimentos?
(b) Mostre que se a e b são primos entre si, o robô consegue visitar todos
os degraus.
5. Encontre o resto que deixa
(a) 2001 · 2002 · 2003 · 2004 + 20052 quando é dividido por 7;
(b) 2100 quando é dividido por 3;
(c)
(
1237156 + 34
)28
quando é dividido por 111.
6. Encontrar o último d́ıgito dos números
(a) 19892005;
(b) 777777 + 250;
(c) 1 + 22 + 32 + · · ·+ 20052.
7. Verifique que
111 . . . 1︸ ︷︷ ︸
2012 uns
= 222 . . . 2︸ ︷︷ ︸
1006 dois
+(333 . . . 3︸ ︷︷ ︸
1006 três
)2.
1Foi demonstrado em 2004 pelos Matemáticos B. Green e T. Tao que existem progressões
aritméticas de tamanho arbitrariamente grande formadas somente por primos. A prova pode
ser encontrada em www.arxiv.org.
8. Demonstre que o número 1 000 . . . 00︸ ︷︷ ︸
2012 zeros
1 é composto.
9. Considere o polinômio p(n) = amn
m+am−1n
m−1+ · · ·+a0 de grau m ≥ 1
com coeficientes inteiros e n ∈ N. Prove que p(n) é um número composto
para infinitos valores de n.2
10. Prove que se (x0, y0) é uma solução da equação diofantina linear ax−by =
1, então a área do triângulo cujos vértices são (0, 0), (b, a) e (x0, y0) é
1/2.
11. Ao entrar numa sala, João se depara com 100 interruptores e 100 lâmpadas,
numerados de 1 a 100. O interruptor n acende somente a lâmpada n, para
cada valor de n = 1, 2, . . . , 100. De ińıcio, todas as 100 lâmpadas estão
apagadas. João aperta todos os interruptores múltiplos de 2. A seguir,
aperta todos os múltiplos de 3, e assim sucessivamente, até o único inter-
ruptor múltiplo de 100. Ao final deste procedimento, pergunta-se:
(a) Quais lâmpadas estão apagadas?
(b) Quantas lâmpadas acenderam exatamente 4 vezes?
(c) Qual é o número da lâmpada que mais acendeu?
2Sugestão: Use o fato de que existe a ∈ N tal que α = |p(a)| > 1 e mostre que α divide a
p(αk + a), para todo k ∈ Z.
Prinćıpio das Casas dos Pombos
12. Seja C um conjunto formado por cinco pontos de coordenadas inteiras no
plano. Prove que o ponto médio de algum dos segmentos com extremos
em C tem também coordenadas inteiras.
13. 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.
14. Prove que se N é ı́mpar então para qualquer bijeção
p : IN → IN
do conjunto IN = {1, 2, . . . , N} o produto P (p) = (1−p(1))(2−p(2)) · · · (N−
p(N)) é necessariamente par.3
15. 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 ćırculo de
raio 1 que contém pelo menos 13 dos 25 pontos dados.
16. Marquemos todos os centros dos 64 quadradinhos de um tabuleiro de
xadrez de 8× 8. É posśı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?
17. Prove que existem duas potências de 3 cuja diferença é diviśıvel por 2012.
18. Mostre que entre nove números que não possuem divisores primos maiores
que cinco, existem dois cujo produto é um quadrado.
19. Um disco fechado de raio um contém sete pontos, cujas distâncias entre
quaisquer dois deles é maior ou igual a um. Prove que o centro do disco é
um destes pontos.
20. Seja a um número irracional. Prove que existem infinitos números racio-
nais r = p/q tais que |a− r| < 1/q2.
21. Suponha que cada ponto do reticulado4 plano é pintado de vermelho ou azul.
Mostre que existe algum retângulo com vértices no reticulado e todos da mesma
cor.
22. Um certo livreiro vende pelo menos um livro por dia. Sabendo que o livreiro
vendeu 463 livros durante 305 dias consecutivos, mostre que em algum peŕıodo
de dias consecutivos o livreiro vendeu exatamente 144 livros.
3Dica: O produto de vários fatores é par se, e somente se, um dos fatores é par.
4Reticulado refere-se ao conjunto dos pontos do plano com coordenadas inteiras