A maior rede de estudos do Brasil

Grátis
109 pág.
Lógica e Demonstraçoes

Pré-visualização | Página 46 de 50

um tabuleiro obtido pela retirada do quadrado superior esquerdo e do inferior 
direito de um tabuleiro standard, mostrado na Figura 5?
Solução: Um tabuleiro obtido pela retirada de dois quadrados de um tabuleiro standard contém 64 
− 2 = 62 quadrados. Como 62 é par, não podemos dizer imediatamente que não existe essa situação, 
como fizemos no Exemplo 19, em que demonstramos que não existia um ladrilhamento de um ta-
buleiro com um quadrado removido. Procurar construir um ladrilhamento desse tabuleiro através da 
colocação de sucessivos dominós pode ser uma primeira tentativa, como o leitor pode experimentar. 
No entanto, mesmo depois de muitas tentativas, não conseguimos encontrar essa solução. Como 
nossos esforços não resultaram em uma solução, somos levados a conjecturar que não existe essa 
solução.
Figura 2 O Tabuleiro Standard. Figura 3 
Dois Dominós.
Exemplos
Extras
Tentamos	então	demonstrar	que	não	existe	ladrilhamento,	mostrando	que	alcançamos	uma	situa-
ção sem saída toda vez que colocamos sucessivamente dominós no tabuleiro. Para construir essa 
demonstração,	devemos	considerar	todos	os	possíveis	casos	que	aparecem	como	se	estivéssemos	
passando	por	todas	as	escolhas	possíveis	na	colocação	de	sucessivos	dominós.	Por	exemplo,	temos	
duas	escolhas	para	cobrir	o	quadrado	na	segunda	coluna	da	primeira	linha,	próximo	ao	quadrado	
removido do canto esquerdo superior. Podemos cobri-lo com um dominó na horizontal ou na verti-
cal.	Cada	uma	das	 escolhas	nos	 leva	 a	muitas	 escolhas,	 e	 assim	 sucessivamente.	Não	demorará	
muito	para	ver	que	esse	não	é	um	plano	interessante	para	uma	pessoa,	embora	um	computador	possa	
ser	usado	para	completar	essa	demonstração	por	exaustão.	(O	Exercício	21	pede	para	fornecer	uma	
demonstração	de	que	um	tabuleiro	4	por	4	com	cantos	opostos	excluídos	não	pode	ser	ladrilhado.)	
Precisamos de um outro método. Talvez exista uma maneira mais fácil de demonstrar que 
não existe essa solução para um tabuleiro standard com dois cantos opostos removidos. Como em 
muitas	demonstrações,	alguma	observação	pode	ajudar.	Vamos	colorir	os	quadrados	desse	tabu-
leiro	usando	branco	e	preto	alternadamente,	como	na	Figura	2.	Observe	que	um	dominó	cobre	
sempre	um	quadrado	branco	e	um	preto.	Agora	note	que	esse	tabuleiro	tem	um	número	diferente	
de quadrados brancos e pretos. Podemos usar essa observação para mostrar por contradição que 
um tabuleiro standard com cantos opostos removidos não pode ser ladrilhado usando dominós. 
Agora	apresentamos	essa	demonstração.
Demonstração: Suponha que usemos dominós para ladrilhar um tabuleiro standard com cantos 
opostos	removidos.	Note	que	o	tabuleiro	standard	com	cantos	opostos	removidos	contém	64	−	2	
= 62 quadrados. O ladrilhamento usará 62/2 = 31 dominós. Note que cada dominó cobre um 
quadrado	branco	e	um	preto.	Conseqüentemente,	o	ladrilhamento	cobre	31	quadrados	brancos	e	
31	pretos.	No	entanto,	quando	removemos	dois	cantos	opostos,	32	dos	quadrados	restantes	são	
brancos e 30 são pretos ou 32 pretos e 30 brancos. Isso contradiz o fato assumido de que podemos 
usar	dominós	para	cobrir	esse	tabuleiro,	completando	a	demonstração.	 ◄
Podemos	usar	outros	 tipos	de	peças	além	de	dominós	para	 ladrilhar.	Em	vez	de	dominós,	
podemos estudar ladrilhamentos que usam peças construídas a partir de quadrados congruentes 
que são conectados pelos seus lados. Essas peças são os chamados poliominós,	termo	cunhado	
em	1953	pelo	matemático	Solomon	Golomb,	 autor	 de	um	 livro	de	 entretenimento	 sobre	 eles	
[Go94]. Vamos considerar dois poliominós com o mesmo número de quadrados que podemos 
rotacionar	e/ou	deslizar	para	obter	outro	poliominó.	Por	exemplo,	existem	dois	tipos	de	triominós	
(veja	a	Figura	6),	que	são	poliominós	feitos	com	três	quadrados	conectados	pelos	seus	lados.	Um	
FIGURA 4 Ladrilhando um Tabuleiro 
Standard.
FIGURA 5 O Tabuleiro Standard sem os 
Dois Cantos Opostos.
FIGURA 6 Um 
Triominó à Direita e 
Um Triominó Reto.
1-99 1.7 Métodos de Demonstração e Estratégia 99
100	 	1	/	Os	Fundamentos:	Lógica	e	Demonstrações	 1-100
tipo	de	triominó,	o triominó reto,	tem	três	quadrados	conectados	horizontalmente,	o	outro	tipo,	
o triominó à direita,	lembra	uma	letra	L,	e	pode	ser	rotacionado	e/ou	deslocado, se necessário. 
Podemos	estudar	esses	ladrilhamentos	de	tabuleiros	por	triominós	retos	agora;	e	vamos	estudar	
os ladrilhamentos por triominós à direita na Seção 4.1.
EXEMPLO 21 Podemos usar triominós retos para ladrilhar um tabuleiro standard?
Solução: O tabuleiro standard contém 64 quadrados e cada triominó cobre três quadrados. Con-
seqüentemente,	se	triominós	ladrilham	um	tabuleiro,	o	número	de	quadrados	do	tabuleiro	deve	
ser	múltiplo	de	3.	Como	64	não	é	um	múltiplo	de	3,	triominós	não	podem	ser	usados	para	cobrir	
um tabuleiro 8 por 8. ◄
No	Exemplo	22,	consideraremos	o	problema	de	ladrilhar	um	tabuleiro	standard	sem	um	can-
to com triominós retos.
EXEMPLO 22 Podemos usar triominós retos para cobrir um tabuleiro standard sem um de seus cantos? Um tabu-
leiro		8	por	8	com	um	canto	removido	tem	64	−	1	= 63 quadrados. Qualquer possibilidade de cobrir 
com triominós retos usará 63/3 =	21	triominós.	No	entanto,	quando	tentamos,	não	conseguimos	
encontrar uma solução. Uma demonstração por exaustão não parece promissora. Podemos adaptar 
nossa demonstração do Exemplo 20 para demonstrar que esse ladrilhamento não existe?
Solução: Vamos colorir os quadrados desse tabuleiro em uma tentativa de adaptar a demonstração 
por	contradição	que	demos	no	Exemplo	20,	da	impossibilidade	de	ladrilhar,	usando	dominós	para	
cobrir um tabuleiro com cantos opostos removidos. Como estamos usando triominós retos em vez 
de	dominós,	vamos	colorir	os	quadrados	usando	três	cores	em	vez	de	duas,	como	mostra	a	Figura	
7.	Note	que	existem	21	quadrados	cinza,	21	pretos	e	22	brancos	nessa	coloração.	Depois,	faremos	
uma	observação	crucial	que,	quando	o	triominó	cobre	três	quadrados	do	tabuleiro,	ele	cobre	um	
quadrado	cinza,	um	preto	e	um	branco.	Depois,	note	que	cada	uma	das	três	cores	aparece	em	algum	
canto	do	tabuleiro.	Em	seguida,	sem	perda	de	generalidade,	podemos	assumir	que	o	quadrado	reti-
rado	é	cinza.	Portanto,	assumimos	que	sobram	20	quadrados	cinza,	21	pretos	e	22	brancos.	
Se	conseguíssemos	ladrilhar	usando	triominós	retos,	então	deveríamos	usar	63/3	= 21 trio-
minós.	E	esses	deveriam	cobrir	21	quadrados	cinza,	21	brancos	e	21	pretos.	Isso	contradiz	o	fato	
de	que	esse	tabuleiro	contém	20	quadrados	cinza,	21	pretos	e	22	brancos.	Portanto,	não	podemos	
cobrir esse tabuleiro usando triominós retos. ◄
O Papel dos Problemas Abertos
Muitos avanços em matemática têm sido feitos por pessoas que tentam resolver famosos proble-
mas	não	resolvidos.	Nos	últimos	20	anos,	muitos	problemas	foram	finalmente	resolvidos,	como	
a demonstração da conjectura de teoria dos números feita há mais de 300 anos. Essa conjectura 
diz a verdade da sentença conhecida como O Último Teorema de Fermat.
TEOREMA 1 ÚLTIMO TEOREMA DE FERMAT A	equação
 x n + y n = z n
não tem solução para x,	y e z inteiros com xyz  0 sempre que n for um inteiro com n > 2.
Lembre-se: A equação x2 + y2 = z2	tem	infinitas	soluções	inteiras	x,	y e z;	essas	soluções	são	
chamadas de triplas pitagóricas e correspondem aos comprimentos dos três lados de triângulos 
retos com comprimentos inteiros. Veja o Exercício 30.
Esse	problema	tem	uma	história	fascinante.	No	século	XVII,	Fermat	escreveu	na	margem	da	
cópia dos trabalhos de Diofanto que ele tinha uma “maravilhosa demonstração” de que não exis-
tiam soluções inteiras de xn + yn = zn quando n é um inteiro maior que 2 com xyz 	0.	No	entanto,	
ele	nunca	publicou	uma	demonstração	(Fermat	não	publicou	quase	nada),	e	nenhuma	demonstra-
ção foi encontrada nos papéis que deixou quando morreu. Matemáticos procuraram uma demons-
tração	 por	 três	 séculos	 sem	 sucesso,	 embora	 muita	 gente	 estivesse

Crie agora seu perfil grátis para visualizar sem restrições.