Programa de Iniciaç~
ao Cientı́fica 2012
Orientador: Prof. Cláudio T. Cristino
Grupo 1, Módulo 1
Primeira Lista de Exercı́cios -- 05/04/2013
Paridade
Exemplo 1: Você pode encontrar cinco números ı́mpares cuja soma seja 100?
Sol.: (Esta é uma prova por “absurdo”. Primeiro supomos que a pergunta seja respondida com SIM,
e mostramos que seria uma absurdo, portanto a resposta é NÃO). Suponha que existam tais 5
ı́mpares com soma 100, digamos a, b, c, d, e. Por enquanto, vamos considerá-los todos positivos.
Primeiramente devemos considerar o seguinte Lema1
Lema 1. Para números inteiros, temos que:
(i) A soma de dois números pares é par.
(ii) A soma de dois números ı́mpares é par.
(iii) A soma de dois números, sendo um par e o outro ı́mpar é ı́mpar.
Prova. Note que podemos escrever um número par como 2k, em que k é um inteiro (ou seja,
todo número par tem como fator o número 2) e que um número ı́mpar por ser escrito como
2k + 1, k inteiro (ou seja, o resto da divisão de um número ı́mpar por 2 é sempre igual a 1).
Logo,
(i) a = 2k1 e b = 2k2 pares, então a + b = 2k1 + 2k2 = 2(k1 + k2 ), par.
(ii) c = 2k1 + 1 e d = 2k2 + 1 ı́mpares, então c + d = 2k1 + 1 + 2k2 + 1 = 2k1 + 2k2 + 2 =
2(k1 + k2 + 1), par.
(iii) a = 2k1 e d = 2k2 + 1 pares, então a + d = 2k1 + 2k2 + 1 = 2(k1 + k2 ) + 1, ı́mpar.
Observe que temos as mesmas “regras” para a subtração!
1 Lemas
são proposições cuja veracidade implicam na prova de outras proposições.
1
PIC/OBMEP
Grupo 1 – Recife
Voltemos ao problema do Exemplo 1. Temos que (usando o Lema 1):
par
a + b + c + d + e = 100
⇒
z }| {
(a + b) +c + d + e = 100
⇒
z
}|
{
par
par
z }| { z }| {
(a + b) + (c + d) +e = 100
par
par
par
z }| { z }| {
(a + b) + (c + d) +e = 100
ı́mpar
}|
{
z
par
z
}|
{
par
par
par
z }| { z }| {
z}|{
(a + b) + (c + d) +e = 100 →|←
O último sı́mbolo, →|←significa que houve uma “contradição”, um “absurdo”. Logo não existem
cinco números ı́mpares cuja soma seja 100. Você deve notar que a suposição de positividade
dos números não altera a conclusão.
♣
Exemplo 2: Existem dois números pares consecutivos?
Sol.: Não! Dois números consecutivos podem ser escritos como x e x + 1. Logo, se x é par, x = 2k
para algum k inteiro e x + 1 = 2k + 1, que é ı́mpar. Também, se x é ı́mpar, x = 2k + 1, para
algum k e x + 1 = 2k + 1 + 1 = 2k + 2 = 2(k + 1), que é par. Assim, não existem dois número
consecutivos que sejam pares (nem ı́mpares).
♣
Exemplo 3: É possı́vel trocar uma nota de 25 rublos2 em dez notas com valores 1, 3 ou 5 rublos?
Sol.: Note que devemos usar uma quantidade par de número ı́mpares cuja soma seja ı́mpar. Pelo
Lema 1 isso não é possı́vel. Portanto, a resposta é NÃO.
♣
Exemplo 4: Os números de 1 a 10 estão escritos um uma linha. Pode-se colocar os sinais “+” e “−” entre
eles de modo que o valor da expressão resultante é igual a zero?
Sol.: O que queremos é escrever uma lista com número de 1 a 10 intercalados com sinais, por exemplo:
+ 1
−
2 +
3 +
4 +
5 −
6
+ 7
− 8
+ 9
−
10
(que obviamente não resulta em zero). Vamos fazer a seguinte “tentativa”: agrupando todos os
número ı́mpares da lista de um lado e todos os número pares de outro temos:
par
ı́mpar
}|
{ z }| {
z
(5 ı́mpares) ± (5 pares)= ı́mpar
Logo a soma/subtração dos dois grupos não pode ser zero. Agora,
par
ı́mpar
z
}|
{ z
}|
{
(4 ı́mpares + 1 par) ± (4 pares + 1 ı́mpar)= ı́mpar,
2 Moeda
da Rússia.
2
PIC/OBMEP
Grupo 1 – Recife
ou,
ı́mpar
par
z
}|
{ z
}|
{
(3 ı́mpares + 2 pares) ± (3 pares + 2 ı́mpares)= ı́mpar,
ou,
par
ı́mpar
z
}|
{ z
}|
{
(2 ı́mpares + 3 pares) ± (3 pares + 2 ı́mpares)= ı́mpar.
Assim todos os caso analisados impossibilitam a soma zero.
Exemplo 5: Mostre que 1 + 2 + 3 + · · · + n =
♣
n(n+ 1)
.
2
Sol.: Vamos dividir a solução em duas partes. Primeiramente, vamos supor que n é par. Logo
podemos repartir os n número em duas colunas da seguinte forma:
1
2
3
..
.
n
n−1
n − 2 somando cada linha ⇒
..
.
1+n
2+n−1
3+n−2
..
.
=n+1
=n+1
=n+1
..
.
n
2
n
2
n
2
=n+1
+1
+
n
2
+1
n
(n + 1), o que mostra o resultado para n par. Para n ı́mpar temos
2
uma ligeira diferença, a primeira coluna terá um número a mais:
como há
n
2
somas, o total é:
1
2
3
..
.
n−1
2
n+1
2
como há
n−1
2
n
n−1
n−2
somando cada linha ⇒
..
.
n+3
2
1+n
2+n−1
3+n−2
..
.
=n+1
=n+1
=n+1
..
.
n−1
n+3
2 + 2
n+1
2
=n+1
= n+1
2
somas n + 1, o total contando contado com a última linha é:
n+1
n
n−1
(n + 1) +
= (n + 1),
2
2
2
mostrando que o resultado também é válido para n ı́mpar.
♣
Exemplo 6: Um tabuleiro 5 × 5 pode ser coberto por dominós 1 × 2 (ou 2 × 1)?
Sol.: Na Figura 1 temos uma tentativa de solução para o problema proposto. Observe que ela nos
indica que possivelmente não haja uma forma de se cobrir o tabuleiro com os dominós!
Sistema posicional de numeração
Exemplo 7: Retire 10 dı́gitos do número 1234512345123451234512345 de modo que o número remanescente
seja o maior possı́vel. E para formar o menor número, como deverı́amos proceder?
Sol. A primeira observação é que retirando-se 10 dı́gitos, o número que ficará será o maior se a
primeira casa à esquerda for a maior possı́vel, seguida da segunda casa da esquerda a maior
possı́vel, etc. Logo devemos tira os primeiros quatro dı́gitos, obtendo: 512345123451234512345,
3
PIC/OBMEP
Grupo 1 – Recife
Figura 1:
depois tiramos do segundo ao quinto dı́gitos, o que resulta no número: 55123451234512345
(lembre-se, atá agora tiramos 8 dı́gitos), como somente podemos retira mais dois dı́gitos, temos
o maior número como: 553451234512345.
3
Agora para produzirmos o menor número adotamos a estratégia inversa, devemos retirar dı́gitos
deixando os menores dı́gitos à esquerda possı́vel: 111231234512345.
♣
Exemplo 8: Joãozinho coleciona números naturais cujo algarismo das unidades é a soma dos outros algarismos. Por exemplo, ele colecionou 10023, pois 1 + 0 + 0 + 2 = 3.
(a) Na coleção de Joãozinho há um número que tem 4 algarismos e cujo algarismo da unidade
é 1. Que número é esse?
Sol.: Como o número possui 4 algarismos, o algarismo correspondente à milhar não pode ser zero.
Como a soma dos algarismos da milhar, centena e dezena tem que ser 1 a única solução é
1001.
♣
(b) Qual é o maior número sem o algarismo 0 que pode aparecer na coleção?
Sol.: Bem, primeiramente devemos fazer a cada das unidade a maior possı́vel, ou seja, igual a 9.
Os números sem o algarismo 0 na coleção de Joãozinho, com a casa das unidades igual a 9
e sendo o maior na casa mais à esquerda são:
99
819
7119
61119
511119
4111119
31111119
211111119
1111111119
Logo 1.111.111.119 (um bilhão, cento e onze milhões, cento e onze mil, cento e dezenove) é
o maior número sem o algarismo 0 que pode aparecer na coleção.
3O
♣
número 553.451.234.512.345 é lido como quinhentos e cinquenta e três trilhões, quatrocentos e cinquenta e um bilhões,
duzentos e trinta e quatro milhões, quinhentos e doze mil, trezentos e quarenta e cinco .
,
4
PIC/OBMEP
Grupo 1 – Recife
(c) Qual é o maior número sem algarismos repetidos?
Sol.: Novamente, vamos colocar o algarismo correspondente às unidade como 9, e termos uma
maior possibilidade de partições. Como podemos particionar 9 de modo que o algarismo
mais à esquerda seja o maior possı́vel e não haja algarismos repetidos? O número procurado
é 62109.
♣
Exemplo 9: Para obter o resumo de um número de até 9 algarismos, deve-se escrever quantos são seus algarismos, depois quantos são seus algarismos ı́mpares e, finalmente, quantos são seus algarismos
pares. Por exemplo, o número 9103405 tem 7 algarismos, sendo 4 ı́mpares e 3 pares, logo seu
resumo é 743.
(a) Encontre um número cujo resumo seja 523.
Sol.: devemos escrever um número com 5 algarismos, sendo 2 ı́mpares e 3 pares. Por exemplo,
22211, 22233, 22255, 22277, 24615, . . .
♣
(b) Encontre um número que seja igual a seu próprio resumo.
Sol.: Bem como o resumo tem 3 algarismos, o número procurado tem 3 algarismos e o resumo
começa com 3. Agora temos que ter 2 ı́mpares e 1 par, ou 1 ı́mpar e dois pares. Testando
a primeira possibilidade, o resumo seria 321 que é igual ao número original 321 (em outras
palavras, 321 tem resumo 321). O número 312 tem 3 dı́gitos, sendo dois ı́mpares e um par,
logo seu resumo é 321, que é diferente no número original. Logo o único número procurado
é 321.
♣
(c) Para qualquer número de até 9 algarismos, podemos calcular o resumo do resumo de seu
resumo. Mostre que esse procedimento leva sempre a um mesmo resultado, qualquer que
seja o número inicial.
Sol.: Suponha inicialmente que o número original tenha uma quantidade ı́mpar de algarismos.
Assim seu resumo é, digamos, abc, com a ı́mpar. Como a = b + c, b é ı́mpar e c é par (Lema
1) ou b é par e c ı́mpar. Nos dois casos o resumo do resumo é 321, que tem resumo 321 (item
anterior). Agora suponha que o número original tenha uma quantidade par de algarismos.
Então seu resumo inicia-se com um algarismo par, que pode ser particionado como soma de
dois números pares, cujo resumo é 303, ou como soma de dois ı́mpares, cujo resumo é 321.
No primeiro caso, o resumo de 303 é 321 (autoresumo) e no segundo novamente teremos
como resumo 321.
♣
Sistema posicional de numeração em outras bases
Exemplo 10: Escrever os números 62 e 125 como somas de potências de 2. Representar estas somas de modo
análogo ao que é feito na base 10.
5
PIC/OBMEP
Grupo 1 – Recife
Sol.: Primeiramente, vamos lembrar como representamos um número na base usual de 10. Por exemplo:
13452 = 1 × 10000 + 3 × 1000 + 4 × 100 + 5 × 10 + 2 × 1 .
| {z }
| {z } | {z } | {z } | {z }
dezena de milhar
milhar
centena
dezena
unidade
Também podemos escrever o número como potências (explı́citas) de 10:
13450 = 1 × 104 + 2 × 103 + 4 × 102 + 5 × 101 + 2 × 100 .
Agora, vamos listas as potências 2r , r = 0, 1, 2, . . .. Listando as primeiras potências:
20 = 1
21 = 2
22 = 4
23 = 8
24 = 16
25 = 32
26 = 64 27 = 128 28 = 256 29 = 512 210 = 1024
···
Note que se quisermos, por exemplo, escrever o número 608 como potências de 2, necessariamente
precisaremos de 29 , mas não precisaremos de 210 . Vamos ao exercı́cio:
62 = x0 20 + x1 21 + x2 22 + x3 23 + x4 24 + x5 25 com xi = 0 ou 1.
Começando da esquerda para a direita (devemos “preencher” o 62 com a maior potência de 2
possı́vel), neste caso, começamos com com x5 = 1 e,
=32
z }| {
62 = x0 2 + x1 2 + x2 2 + x3 2 + x4 2 + 1 × 25
0
1
2
3
4
62 − 32 = x0 20 + x1 21 + x2 22 + x3 23 + x4 24
=16
z }| {
30 = x0 2 + x1 2 + x2 2 + x3 2 + 1 × 24
0
1
2
3
30 − 16 = x0 20 + x1 21 + x2 22 + x3 23
=8
z }| {
14 = x0 20 + x1 21 + x2 22 + 1 × 23
14 − 8 = x0 20 + x1 21 + x2 22
=4
z }| {
6 = x0 2 + x1 2 + 1 × 22
0
1
6 − 4 = x0 20 + x1 21
=2
z }| {
2 = x0 20 + 1 × 21
2 − 2 = x0 20
0 = x0 20 ⇔ x0 = 0.
Assim,
62 = 0 × 20 + 1 × 21 + 1 × 22 + 1 × 23 + 1 × 24 + 1 × 25 + 0 × 26 + 0 × 27 + 0 × · · ·
= 1 × 25 + 1 × 24 + 1 × 23 + 1 × 22 + 1 × 21 + 0 × 20
Como para o sistema decimal, escrevemos os coeficientes de menor potência à direita. Logo
62 = (111110)2
6
PIC/OBMEP
Grupo 1 – Recife
(os “zeros” à esquerda não são necessários na representação, daı́ a expressão fulano é um zero à
esquerda, ou seja, fulano não “serve pra nada”!)
E o número 125? Diretamente,
6
5
3
2
1
0
125 = 1| ×
+ 1 × 2}4 + |1 ×
{z2} + |1 × 2 {z
{z2} + |1 ×
{z2} + |1 ×
{z2} + |1 ×
{z2}
=64
=32
=16
=8
=4
=1
Observe que na base 2 número pares terminam com 0 e número ı́mpares terminam com 1.
♣
Exemplo 11: Usando potência de 3 escreva os números 62 e 125.
Sol.: Da mesma forma que no Exemplo anterior, primeiramente vamos dar uma “olhada” nas potências
de 3:
30 = 1
31 = 3
32 = 9
33 = 27
34 = 51
35 = 243
36 = 729 37 = 2187 38 = 6561 39 = 19683 310 = 50049
···
Vamos ao exercı́cio:
62 = x0 30 + x1 31 + x2 32 + x3 33 + x4 34 com xi = 0, 1 ou 2.
= x0 30 + x1 31 + x2 32 + x3 33 + 1 × 34
62 − 51 = x0 30 + x1 31 + 1 × 32 + 0 × 33
11 − 9 = 2 × 30 + 0 × 31 .
Logo,
62 = 2 × 30 + 0 × 31 + 1 × 32 + 0 × 33 + 1 × 34 + 0 × 35 + 0 × 36 + 0 × 37 + 0 × · · ·
= 1 × 34 + 0 × 33 + 1 × 32 + 0 × 31 + 2 × 30 ,
e,
62 = (10102)3 .
♣
Exemplo 12: O número (101101)2 é par ou ı́mpar? E o número (202012)3 é par ou ı́mpar? Determine um
critério par saber quando um número escrito na base 2 seja par. Estude também a paridade de
números escritos na base 3.
Sol.: Como dito antes, para toda potência de 2 há (obviamente) um fator 2, com exceção da potência
20 (que é igual a 1). Neste caso um número na base 2 que for par tem o algarismo mais à direita
igual a zero, se for ı́mpar, este algarismo deve ser 1. Logo, (01101)2 é ı́mpar.
Agora, veja no Exemplo 11 que toda potência de 3 é ı́mpar. Logo um número na base 3 será
ı́mpar se a tiver uma quantidade ı́mpar de potências todas multiplicadas por 1 (naturalmente).
Assim para o número (202012)3 temos uma única potência multiplicada por 1 e, portanto, este
número é ı́mpar.
♣
7
Exemplo 13: Ao entrar numa sala você se depara com a seguinte operação do quadro:
+
16
6
25
Você pergunta a seu professor se esta conta está correta ele olha e diz: “sim, mas para os número
escritos numa base especial”. Que base é essa?
Sol.: Seja b a base procurada. Então (16)b = 1 × b1 + 6 × b0 , (6)b = 6 × b0 e (25)b = 2 × b1 + 5 × b0 .
Assim,
(1 × b1 + 6 × b0 ) + (6 × b0 ) = (2 × b1 + 5 × b0 )
1 × b1 + (6 + 6) × b0 = 2 × b1 + 5 × b0
1 × b1 + 12 × b0 = 2 × b1 + 5 × b0
(12 − 5) × b0 = (2 − 1)b1 , mas b0 = 1
7×1=b ∴
b = 7.
A base na qual foi escritos os números é 7, ou seja (16)7 + (6)7 = (25)7 .
8
♣