4
Representa»c~
ao posicional de inteiros
Habitualmente os n¶umeros inteiros positivos s~ao representados no sistema (posicional)
decimal. Na representa»c~ao de um inteiro positivo no sistema decimal, os d¶³gitos ou
algarismos representam m¶
ultiplos de pot^encias de 10, base do sistema. Esses m¶ultiplos de
pot^encias de 10, quando somados, determinam o n¶
umero. Por exemplo, ao escrevermos
27 065 estamos representando a quantidade
2 ¢ 104 + 7 ¢ 103 + 0 ¢ 102 + 6 ¢ 101 + 5 ¢ 100
A raz~ao hist¶orica para a ado»c~ao da base 10 na representa»c~ao dos inteiros ¶e provavelmente
o fato de termos dez dedos em nossas m~aos. Algumas civiliza»co~es antigas usaram bases
diferentes, como os Babil^onios, que usavam a base 60 (sistema sexagesimal ). Uma
heran»ca cultural que temos dos Babil^onios est¶a no sistema sexagesimal da contagem de
minutos e segundos. J¶a os computadores eletr^onicos usam a base 2 (sistema bin¶ario)
para representar os inteiros internamente, nos circuitos el¶etricos, e a base 8 (sistema
octal ) ou a base 16 (sistema hexadecimal ) para representar os inteiros externamente,
nos dispositivos de visualiza»c~ao.
Uma calculadora cient¶³¯ca, como a encontrada em modernos computadores, realiza
c¶alculos e exibe resultados nos sistemas decimal, hexadecimal, octal e bin¶ario. Quando
o leitor adquirir familiaridade com esses quatro sistemas, poder¶a conferir seus c¶alculos,
propostos nos exerc¶³cios, em uma dessas calculadoras.
Como veremos a seguir, qualquer inteiro positivo maior do que 1 pode ser usado
como base na representa»c~ao dos inteiros. A representa»c~ao de inteiros de que estamos
tratando ¶e chamada representa»c~ao posicional, uma vez que a posi»c~ao de cada d¶³gito ¶e
relevante na representa»c~ao do n¶umero.
Teorema 4.1 Seja b > 1 um inteiro positivo ¯xado. Ent~ao qualquer inteiro positivo n
pode ser escrito, de maneira u¶nica, na forma
n = ak ¢ bk + ak¡1 ¢ bk¡1 + ¢ ¢ ¢ + a2 ¢ b2 + a1 ¢ b + a0
na qual os coe¯cientes aj , para j = 0; 1; : : : ; k, s~ao elementos do conjunto de d¶³gitos
f0; 1; : : : ; b ¡ 1g, e ak 6
=0.
27
28
~o posicional de inteiros
Representac
»a
Demonstra»c~ao. Para obter a representa»c~ao (ou expans~ao) de n, na base b, constru¶³mos
uma seqÄu^encia ¯nita de divis~oes euclidianas por b, cujos restos constituir~ao a seqÄu^encia
de d¶³gitos a0 ; : : : ; ak .
Primeiro dividimos n por b, e obtemos
n = bq0 + a0 ; 0 · a0 < b:
Se q0 > 0 ent~ao dividimos q0 por b, obtendo
q0 = bq1 + a1 ; 0 · a1 < b:
Se q1 > 0, continuamos o processo, obtendo
q1 = bq2 + a2 ; 0 · a2 < b
q2 = bq3 + a3 ; 0 · a3 < b
..
.
qk¡1 = bqk + ak ; 0 · ak < b
(q2 > 0)
(q3 > 0)
(qk¡1 > 0)
at¶e encontrarmos o primeiro quociente qk = 0.
A garantia de que o processo termina est¶a no fato de que a seqÄu^encia n > q0 >
q1 > q2 > ¢ ¢ ¢ , ¶e uma seqÄ
u^encia estritamente decrescente de inteiros n~ao negativos,
terminando portanto em algum qk = 0 (n~ao existe uma seqÄu^encia in¯nita e decrescente
de inteiros positivos).
Substituindo sucessivamente q0 ; q1 ; : : : ; qk¡1 na equa»c~ao n = bq0 + a0 obtemos
n = bq0 + a0
= b(bq1 + a1 ) + a0
= q1 b2 + a1 b + a0
= (bq2 + a2 )b2 + a1 b + a0
= b3 q2 + a2 b2 + a1 b + a0
..
.
= (bqk + ak )bk + ak¡1 bk¡1 + ¢ ¢ ¢ + a2 b2 + a1 b + a0
= ak bk + ak¡1 bk¡1 + ¢ ¢ ¢ + a2 b2 + a1 b + a0
Para demonstrarmos a unicidade da expans~ao de n na base b, vamos supor que
existem duas expans~oes distintas,
n = ak bk + ak¡1 bk¡1 + ¢ ¢ ¢ + a2 b2 + a1 b + a0
n = Ak bk + Ak¡1 bk¡1 + ¢ ¢ ¢ + A2 b2 + A1 b + A0
com os coe¯cientes aj e Aj , para j = 0; 1; : : : ; k, tomados no conjunto de d¶³gitos
f0; 1; : : : ; b ¡ 1g.
~o posicional de inteiros
Representac
»a
29
Note que, em princ¶³pio, as duas expans~oes n~ao precisam conter o mesmo numero
k + 1 de termos. Isto ¶e facilmente contornado somando parcelas com coe¯cientes nulos
para for»car a igualdade no n¶umero de coe¯cientes dos dois somat¶orios. Subtraindo o
segundo somat¶orio do primeiro, termo a termo, obtemos
(ak ¡ Ak )bk + ¢ ¢ ¢ + (a2 ¡ A2 )b2 + (a1 ¡ A1 )b + (a0 ¡ A0 ) = 0
Seja j 2 f0; 1; 2; : : : ; kg o primeiro inteiro tal que aj 6
= Aj . Note que tal j existe
quando as duas representa»c~oes s~ao realmente distintas.
A igualdade anterior tem ent~ao a forma
(ak ¡ Ak )bk + (ak¡1 ¡ Ak¡1 )bk¡1 + ¢ ¢ ¢ + (aj+1 ¡ Aj+1 )bj+1 + (aj ¡ Aj )bj = 0
e podemos ent~ao escrever
¤
£
bj (ak ¡ Ak )bk¡j + ¢ ¢ ¢ + (aj+1 ¡ Aj+1 )b + (aj ¡ Aj ) = 0
ou, equivalentemente,
£
¤
Aj ¡ aj = b (ak ¡ Ak )bk¡j¡1 + ¢ ¢ ¢ + (aj+1 ¡ Aj+1 ) :
Nestas condi»co~es b j (Aj ¡ aj ).
Por outro lado, como 0 · aj < b e 0 · Aj < b, segue que ¡b < Aj ¡ aj < b.
ultiplo de b no intervalo ¡b < Aj ¡ aj < b, isto ¶e,
Assim Aj ¡ aj ¶e o u¶nico m¶
Aj ¡ aj = 0.
Chegamos ent~ao a uma contradi»c~ao, j¶a que estamos sob a hip¶otese de que aj 6
= Aj .
Alternativamente, podemos demonstrar a exist^encia da expans~ao de n, na base
b, por indu»c~ao sobre n, usando o segundo princ¶³pio de indu»c~ao ¯nita, analogamente ao
procedimento usado na demonstra»c~ao do teorema 2.6, cap¶³tulo 1.
Um caso particularmente interessante do teorema 4.1 ocorre quando b = 2, conforme enunciado a seguir.
Corol¶
ario 4.1 Qualquer inteiro positivo pode ser representado, de maneira ¶unica, como
uma soma de pot^encias de dois, distintas entre si.
Demonstra»c~ao. Seja n um inteiro positivo. Segue do teorema 4.1, quando b = 2, que n
tem a forma
n = ak ¢ 2k + ak¡1 ¢ 2k¡1 + ¢ ¢ ¢ + a2 ¢ 22 + a1 ¢ 21 + a0 ¢ 20
com cada d¶³gito aj igual a 0 ou 1, sendo os d¶³gitos aj determinados de maneira u¶nica.
Logo n pode ser representado, de maneira ¶unica, como uma soma de pot^encias de dois,
distintas entre si.
30
~o posicional de inteiros
Representac
»a
Na representa»c~ao descrita no teorema 4.1, b ¶e chamado de base da representa»c~ao.
Expans~oes decimais (b = 10), bin¶arias (b = 2), hexadecimais (b = 16) ou octais (b = 8)
s~ao as mais usadas. Os coe¯cientes aj s~ao chamados de d¶³gitos da representa»c~ao. D¶³gitos
bin¶arios tamb¶em s~ao chamados de bits (binary digits).
Para distinguir representa»c~oes de inteiros em diferentes bases, ¶e h¶abito usar a
nota»c~ao
(ak ak¡1 : : : a2 a1 a0 )b
para representar
ak bk + ak¡1 bk¡1 + ¢ ¢ ¢ + a2 b2 + a1 b + a0
Tamb¶em escrevemos abc : : : rsb em lugar de (abc : : : rs)b .
Assim, por exemplo, (2102)3 ou 21023 signi¯ca 2 ¢ 33 + 1 ¢ 32 + 0 ¢ 31 + 2 ¢ 30 , que
¶e, no nosso sistema decimal, 2 ¢ 27 + 1 ¢ 9 + 2 = 65.
Como de h¶abito, ¯ca subententida a base dez quando n~ao ¯zermos men»c~ao µa base
na qual o inteiro est¶a representado. Assim, 2307 ¶e o mesmo que 230710 ou (2307)10 ,
sendo o inteiro 2 ¢ 103 + 3 ¢ 102 + 7.
P
Observa»c~
ao 4.1 Se n = ak ¢ bk + ak¡1 ¢ bk¡1 + ¢ ¢ ¢ + a2 ¢ b2 + a1 ¢ b + a0 = kn=0 an bn ,
tal como no enunciado do teorema 4.1, este somat¶orio ¶e a sua expans~ao na base b,
enquanto que a nota»c~ao simb¶olica (ak ak¡1 : : : a2 a1 a0 )b ¶e a sua representa»c~ao na base
b. No entanto, os termos expans~ao e representa»c~ao, neste contexto, podem ser usados
como sin^onimos.
Note que a demonstra»c~ao do teorema 4.1 fornece um m¶etodo para encontrar a representa»c~ao na base b de um inteiro qualquer n. N¶os simplesmente aplicamos o algoritmo da
divis~ao sucessivamente sempre com o mesmo divisor b, come»cando com o dividendo n,
tomando sempre, como novo dividendo, o u¶ltimo quociente obtido, e parando quando o
quociente se anular. A leitura dos restos, do u¶ltimo para o primeiro, fornece os d¶³gitos
da representa»c~ao procurada.
Exemplo 4.1 Para encontrar a representa»c~ao na base 2 do inteiro 2006 basta fazer
sucessivas divis~oes euclidianas por 2, tal como abaixo:
2006
2
0 1003
62 2
0 31
1003
1
31 2
1 15
2
501
501 2
1 250
15 2
1 7
250
0
7
1
2
3
2
125
3 2
1 1
125 2
1 62
1
1
2
0
31
~o posicional de inteiros
Representac
»a
Das divis~oes acima, temos:
2006
1003
501
250
125
62
31
15
7
3
1
=
=
=
=
=
=
=
=
=
=
=
2 ¢ 1003
2 ¢ 501
2 ¢ 250
2 ¢ 125
2 ¢ 62
2 ¢ 31
2 ¢ 15
2¢7
2¢3
2¢1
2¢0
+
+
+
+
+
+
+
+
+
+
+
0
1
1
0
1
0
1
1
1
1
1
Para obter a representa»c~ao de 200610 na base 2, anotamos ordenadamente os restos das
divis~oes euclidianas efetuadas, iniciando no u¶ltimo e terminando no primeiro, isto ¶e,
(2006)10 = (11111010110)2
Internamente, computadores representam n¶umeros em circuitos el¶etricos usando
uma s¶erie de chaves que possuem dois estados: \ligada" (passando corrente el¶etrica)
e \desligada" (n~ao passando corrente el¶etrica). Chaves ligadas representam o d¶³gito
bin¶ario 1 e chaves desligadas representam o d¶³gito bin¶ario 0. J¶a em seus dispositivos
visuais, os computadores representam n¶
umeros usando a base hexadecimal, atrav¶es dos
d¶³gitos hexadecimais 0, 1, 2, 3, 4, 5 ,6 ,7, 8, 9, A, B, C, D, E e F . As letras A, B, C,
D, E e F representam os d¶³gitos correspondentes a 10 ,11, 12, 13, 14 e 15 no sistema
decimal.
Por exemplo, para converter (B013CE)16 para a base decimal escrevemos
(B013CE)16 = B ¢ 165 + 0 ¢ 164 + 1 ¢ 163 + 3 ¢ 162 + C ¢ 16 + E
= 11 ¢ 165 + 0 ¢ 164 + 1 ¢ 163 + 3 ¢ 162 + 12 ¢ 16 + 14
= (11539406)10
A convers~ao hexadecimal-bin¶ario ¶e feita atrav¶es da convers~ao dos d¶³gitos hexadecimais em blocos de 4 d¶³gitos bin¶arios, conforme mostra a tabela 4.1.
Exemplo 4.2 Para converter (B6AF )16 em bin¶ario basta colocar, em seqÄ
u^encia, os
respectivos blocos de d¶³gitos bin¶arios de cada um dos d¶³gitos hexadecimais 2, F , B e 3.
Assim
(46AF )16 = (0100
|{z} 0110
|{z} 1010
|{z} 1111
|{z})2 = (0100011010101111)2 = (100011010101111)2
B
6
A
F
~o posicional de inteiros
Representac
»a
32
Tabela 4.1. Convers~ao de d¶³gitos hexadecimais para o sistema bin¶ario.
d¶³gito
hexadecimal
0
1
2
3
4
5
6
7
8
9
A
B
C
D
E
F
d¶³gitos
bin¶arios
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
N~ao justi¯caremos este procedimento no seu caso geral. Mostraremos por¶em, passo a
passo, a convers~ao de (46AF )16 para a forma (0100011010101111)2 .
(46AF )16 = 4 ¢ 163 + 6 ¢ 162 + A ¢ 16 + F
= (0100)2 ¢ 163 + (0110)2 ¢ 162 + (1010)2 ¢ 16 + (1111)2
= (0100)2 ¢ 212 + (0110)2 ¢ 28 + (1010)2 ¢ 24 + (1111)2
= (0100)2 ¢ (1 0000 0000 0000)2 + (0110)2 ¢ (1 0000 0000)2 + (1010)2 ¢ (1 0000)2 + (1111)2
= (0100 0000 0000 0000)2 + (0110 0000 0000)2 + (1010 0000)2 + (1111)2
= (0100 0110 1010 1111)2 = (100011010101111)2
Exemplo 4.3 Para converter (10110011111000)2 em hexadecimal basta converter, da
direita para a esquerda, os blocos de digitos bin¶arios em hexadecimal. Assim
(10110011111000)2 = (0010 1100 1111 1000)2 = (2CF 8)16
Esquema an¶alogo ao da convers~ao bin¶ario-hexadecimal tamb¶em se aplica quando
uma das bases ¶e uma pot^encia da outra.
~o posicional de inteiros
Representac
»a
4.1
33
Exerc¶³cios
1. Seja n um inteiro positivo, e seja n = (as as¡1 : : : a1 a0 )10 sua representa»c~ao decimal posicional, isto ¶e,
n = as 10s + as¡1 10s¡1 + ¢ ¢ ¢ + a1 10 + a0
sendo as ; as¡1 ; : : : ; a0 \algarismos" tomados no conjunto f0; 1; : : : ; 8; 9g.
Demonstre os seguintes resultados:
(a) n ¶e divis¶³vel por 2 se e somente se a0 , o d¶³gito das unidades, ¶e par.
(b) n ¶e divis¶³vel por 3 se e somente se a soma dos d¶³gitos de n, as + as¡1 + ¢ ¢ ¢ +
a1 + a0 ¶e divis¶³vel por 3.
Sugest~ao. Repare primeiramente que 10¡1 = 9, 102 ¡1 = 99, 103 ¡1 = 999,
etc. Escreva
n = as 10s + as¡1 10s¡1 + ¢ ¢ ¢ + a1 10 + a0
= as (10s ¡ 1) + as + as¡1 (10s¡1 ¡ 1) + as¡1 + ¢ ¢ ¢ + a1 (10 ¡ 1) + a1 + a0
= 9m + (as + as¡1 + ¢ ¢ ¢ + a1 + a0 )
(c) n ¶e divis¶³vel por 5 se e somente se a0 , o d¶³gito das unidades, ¶e 0 ou 5.
(d) n ¶e divis¶³vel por 9 se e somente se a soma dos d¶³gitos de n, as + as¡1 + ¢ ¢ ¢ +
a1 + a0 , ¶e divis¶³vel por 9. Sugest~ao. A mesma sugest~ao dada para o item b.
(e) n ¶e divis¶³vel por 11 se e somente se a soma alternada de seus d¶³gitos, a0 ¡
a1 + a2 ¡ ¢ ¢ ¢ + (¡1)s as , ¶e divis¶³vel por 11.
Sugest~ao. Mostre primeiramente que, se m ¶e par ent~ao 10m ¡ 1 ¶e multiplo
de 11, e se m ¶e ¶³mpar 10m + 1 ¶e m¶
ultiplo de 11.
2. Determinar todos os inteiros positivos, m¶ultiplos de 5 que, escritos em base 10,
s~ao de 3 algarismos cuja soma ¶e 19. Resposta. 595, 685, 775, 865, e 955.
3. Demonstre que o quadrado de um inteiro positivo ¶e da forma 4k ou 4k + 1,
sendo k inteiro. Usando este fato, demonstre que nenhum inteiro da seqÄu^encia
11; 111; 1111; 11111; : : : ¶e um quadrado perfeito.
4. Determine um inteiro de quatro algarismos, que somado µa soma de seus algarismos
resulta 2603. Resposta. 2584.
5. Demonstre que o quadrado de um inteiro ¶e da forma 5k ou 5k § 1. Com quais
algarismos pode terminar um quadrado perfeito?
6. (a) Converta 1995 da nota»c~ao decimal µa nota»c~ao em base 7. Resposta. 55507 .
(b) Converta 61047 µa nota»c~ao decimal. Resposta. 2111.
(c) Converta 74898 da nota»c~ao decimal µa nota»c~ao em base 8. Resposta. 2222228 .
~o posicional de inteiros
Representac
»a
34
(d) Converta 5666578 µa nota»c~ao decimal. Resposta. 191919.
(e) Converta 101010102 e 111111112 µa nota»c~ao decimal. Resposta. 170 e 255,
respectivamente.
(f) Converta 1500 e 819 ao sistema bin¶ario.
Resposta. 101110111002 e 11001100112 , respectivamente.
(g) Converta 10110110111101112 e 11000101111001112 ao sistema hexadecimal
(base 16). Resposta. B6F 716 e C5E716 , respectivamente.
(h) Converta 5BABA16 , 45F E16 e 9A0B16 ao sistema bin¶ario.
Resposta. 10110111010101110102 , 1000101111111102 , e
10011010000010112 , respectivamente.
7. Imagine que voc^e viajou para um planeta, onde os habitantes usam o sistema de
numera»c~ao posicional de base 5. Construa tabuadas nesse sistema, para a adi»c~ao
e para a multiplica»c~ao.
Realize as seguintes contas, sem converter os n¶umeros para o sistema decimal,
como se voc^e estivesse que explic¶a-las a seus alunos nesse planeta.
(a) 12343215 + 20301045 . Resposta. 33144305 .
(b) 44342015 ¡ 4344215 . Resposta. 3442305 .
(c) 12345 ¢ 30025 . Resposta. 43200235 .
(d) 143215 ¥ 3345
(divis~ao euclidiana). Resposta. quociente 225 e resto 3135 .
8. Nos itens abaixo, imite o procedimento usado no exerc¶³cio anterior, isto ¶e, fa»ca os
c¶alculos aritm¶eticos imitando os algoritmos que voc^e aprendeu na escola b¶asica,
da aritm¶etica do sistema decimal. Realize as opera»co~es sem converter os n¶umeros
dados para o sistema decimal.
(a) Calcule, dando solu»co~es no sistema em que os inteiros est~ao representados:
i.
ii.
iii.
iv.
v.
vi.
1010110112 + 11001010112 . Resposta. 100100001102 .
101010101111012 + 111011010110112 . Resposta. 1100110000110002 .
11110010112 ¡ 1001011112 Resposta. 10100111002 .
11011011002 ¡ 1011101012
101112 ¢ 110012 . Resposta. 10001111112 .
1101112 ¢ 10110112 . Resposta. 10011100011012 .
(b) Encontre o quociente e o resto
i. quando 1100101112 ¶e dividido por 11012 .
Resposta. q = 111112 , r = 1002 .
ii. quando 1101001112 ¶e dividido por 111012 .
Resposta. q = 1110, r = 10001.
(c) Calcule
i. ABAF ADA16 + AB0BADA16 . Resposta. 156BB5B416 .
~o posicional de inteiros
Representac
»a
35
ii. F ADA16 ¡ CAF E16 . Resposta. 2F DC16 .
iii. CACA16 ¢ B0A16 . Resposta. 8BE99E416 .
Sugest~ao. Fa»ca primeiramente uma tabuada de todas as multiplica»co~es
b¶asicas envolvidas: C £ B = 84, A £ B = 6E, etc.
9. (a) Demonstre que todo inteiro ¶e de uma das formas: 3k ou 3k ¡ 1 ou 3k + 1,
com k inteiro.
(b) Demonstre ent~ao que cada inteiro positivo n pode ser representado na forma
tern¶aria balanceada, ou seja, pode ser representado na forma
n = an ¢ 3n + an¡1 ¢ 3n¡1 + ¢ ¢ ¢ + a1 ¢ 3 + a0
com ai = 0 ou §1, para cada ¶³ndice i.
(c) Um farmac^eutico tem apenas pesos de 1g, 3g, 9g, 27g, 81g, e uma balan»ca
de dois pratos (os pesos podem ser colocados em ambos os pratos). Mostre
que ele pode pesar qualquer objeto com at¶e 121g.
10. Mostre que qualquer peso n~ao excedendo 2k ¡ 1 gramas pode ser medido usando
pesos de 1, 2, 22 , : : : , 2k¡1 gramas, em uma balan»ca de dois pratos, os pesos
sendo colocados num u¶nico prato da balan»ca.
11. Decifre a seguinte brincadeira de adivinha»c~ao.
O m¶agico (adivinho) pede a uma pessoa que pense em um n¶
umero de 10 a 100.
O m¶agico executa ent~ao os seguintes passos:
1. Pergunta µa pessoa se o n¶umero pensado ¶e par ou ¶³mpar. Ouvida a resposta,
se for par, pede µa pessoa que divida o n¶
umero por 2. Se for ¶³mpar, pede µa pessoa
que subtraia 1 e que ent~ao divida o resultado por 2.
2. Pergunta ent~ao se o novo resultado, assim obtido, ¶e par ou ¶³mpar.
3. O procedimento continua com cada novo resultado. Isto ¶e, o m¶agico pergunta
se o n¶umero resultante ¶e par ou ¶³mpar e, ouvida a resposta, pede µa pessoa para
repetir o procedimento descrito no item 1. O m¶agico pede µa pessoa para avis¶alo quando o resultado tornar-se igual a 1, quando ent~ao os c¶alculos da pessoa
terminam.
O m¶agico vai fazendo anota»co~es enquanto a pessoa lhe passa as informa»co~es
solicitadas e, quando ¶e informado de que o resultado ¶e igual a 1, ele revela imediatamente µa pessoa o n¶umero pensado por ela.
Qual ¶e o procedimento adotado pelo m¶agico em suas anota»co~es ?
12. Explique como converter representa»c~oes de inteiros na base 3 para a base 9 e
vice-versa.
13. Mostre que se n = (ak ak¡1 : : : a1 a0 )b ent~ao o quociente e o resto, da divis~ao de
n por bj s~ao, respectivamente, q = (ak ak¡1 : : : aj )b e r = (aj¡1 : : : a1 a0 )b .
36
~o posicional de inteiros
Representac
»a
14. Se n = (ak ak¡1 : : : a1 a0 )b ent~ao qual ¶e a representa»c~ao de bm n na base b ?
15. Uma expans~ao de Cantor para um inteiro positivo n ¶e uma soma da forma
n = am m! + am¡1 (m ¡ 1)! + ¢ ¢ ¢ + a2 ¢ 2! + a1 ¢ 1!
sendo cada aj um inteiro, com 0 · aj · j.
(a) Encontre a expans~ao de Cantor para 14, 56 e 384. Sugest~ao. Se encontrar
di¯culdade, veja o algoritmo apresentado no item abaixo.
(b) Mostre que qualquer inteiro positivo tem uma expans~ao de Cantor.
Sugest~ao. Seja n um inteiro positivo. Inicialmente, divida n por 2, obtendo
quociente q1 e resto r1 . Divida ent~ao q1 por 3, obtendo quociente q2 e
resto r2 . Divida ent~ao q2 por 4, obtendo quociente q3 e resto r3 . Prossiga
iterativamente. Para cada j, j ¸ 2, ao dividir qj¡2 por j, obtemos quociente
qj¡1 e resto rj¡1 . Como q1 > q2 > q3 > ¢ ¢ ¢ ¶e uma seqÄ
u^encia decrescente
de inteiros n~ao negativos, se n ¸ 3, existir¶a um inteiro m tal que qm 6
=0e
qm+1 = 0 (se n · 2, teremos simplesmente n = 1! ou n = 2!). Coletando
as divis~oes euclidianas realizadas, mostre ent~ao que
n = r1 + r2 ¢ 2! + r3 ¢ 3! + ¢ ¢ ¢ + rm ¢ m!
(c) Mostre que a escolha dos coe¯cientes a0 ; : : : ; am , na expans~ao de Cantor de
um inteiro positivo, ¶e u¶nica.
Sugest~ao. Suponha que um inteiro positivo a tenha duas expans~oes de Cantor
n
m
X
X
distintas, digamos a =
ak ¢ k! =
bk ¢ k!. Podemos escrever a =
s
X
ak ¢ k! =
s
X
k=1
k=1
k=1
k=1
k=1
k=1
bk ¢ k!, completando com coe¯cientes nulos o somat¶orio que
tiver menos termos.
Sendo diferentes as duas expans~oes, existir¶a um ¶³ndice `, o maior poss¶³vel,
tal que a` 6
= b` . Teremos ent~ao
s
s
X
X
X̀
X̀
ak ¢ k! ¡
bk ¢ k! =
ak ¢ k! ¡
bk ¢ k! = 0.
k=1
k=1
Da¶³, (a` ¡ b` )`! = (b`¡1 ¡ a`¡1 )(` ¡ 1)! + ¢ ¢ ¢ + (b2 ¡ a2 )2! + (b1 ¡ a1 ).
Explique ent~ao porqu^e
ja` ¡ b` j`! · (` ¡ 1)(` ¡ 1)! + ¢ ¢ ¢ + 2 ¢ 2! + 1! e, fazendo uso da f¶ormula
apresentada no exerc¶³cio 2f, p¶agina 16, cap¶³tulo 1, mostre que a` = b` .
16. O Jogo chin^es NIM ¶e jogado em duplas como segue. Inicialmente v¶arios palitos
est~ao dispostos em v¶arias ¯leiras. Cada movimento consiste em retirar um ou
mais palitos de apenas uma das ¯leiras. Vence o jogo aquele que retirar o u¶ltimo
palito em sua jogada. Uma posi»c~ao ganhadora ¶e uma con¯gura»c~ao de palitos
tal que, se voc^e deix¶a-la para seu oponente, voc^e poder¶a continuar jogando de
~o posicional de inteiros
Representac
»a
37
modo a ganhar, n~ao importa quais sejam as futuras jogadas de seu oponente. Por
exemplo, se voc^e deixar somente dois palitos, cada um em uma ¯leira, voc^e est¶a
em uma posi»c~ao ganhadora, pois seu oponente ir¶a tirar um dos palitos e voc^e ir¶a
tirar o u¶ltimo palito.
(a) Mostre que a con¯gura»c~ao de duas ¯leiras, com dois palitos cada, ¶e uma
posi»c~ao ganhadora.
(b) Para cada arranjo de palitos em ¯leiras, podemos escrever o n¶umero de palitos
em cada ¯leira no sistema bin¶ario, e dispor esses n¶umeros em uma coluna,
alinhando seus d¶³gitos em colunas, acrescentando zeros quando necess¶ario.
Por exemplo, se a con¯gura»c~ao de palitos ¶e de tr^es ¯leiras, sendo elas de 10,
8 e 3 palitos, escrevemos
10 = 1 0 1 0
8 = 1 0 0 0
7 = 0 1 1 1
Mostre que uma posi»c~ao ¶e ganhadora se o n¶umero de 1's em cada coluna ¶e
par, e ¶e perdedora se o n¶
umero de 1's em alguma das colunas ¶e impar. Por
exemplo, se tivermos tr^es ¯leiras com 10, 8 e 7 palitos, como acima, temos
uma posi»c~ao perdedora.
Sugest~ao. Mostre que
(a) a retirada de palitos, de qualquer ¯leira, a partir de uma posi»c~ao ganhadora, produz uma posi»c~ao perdedora;
(b) a partir de uma posi»c~ao perdedora, existe uma retirada de palitos, de
uma das ¯leiras, que produz uma posi»cao ganhadora. Considere a ¯leira com
maior n¶umero de palitos. Mostre que ¶e poss¶³vel subtrair um n¶umero de palitos
dessa ¯leira de modo a alterar d¶³gitos previamente escolhidos (transformando
os 0's escolhidos em 1's e vice-versa).