FANDOM


É interessante procurarmos, no problema, coisas que não variam.

Exemplo (Cone Sul)Editar

Em uma mesa está uma pilha com T discos que de forma incremental deve ser convertida em pilhas com três discos cada. Cada passo consiste em selecionar uma pilha removendo um dos seus discos. E então a pilha que sobrou é separada em duas pilhas. Existe uma sequência de passos que pode realizar este processo?


(a) T=1000

(b) T=2001

Solução:

Considere n e m o números discos e o de pilhas, no começo, respectivamente. Vamos entender o que cada movimento faz com o número de pilhas e de discos.

O número de discos diminui em 1 unidade (pois tiramos um disco) e o número de pilhas aumenta 1 unidade (pois transformamos uma pilha em duas). Desta forma, a soma das quantidades de pilhas e discos é sempre a mesma (encontramos nossa invariante). Esta soma deve ser a mesma do começo, ou seja, m+n.

(a) Na primeira rodada, n=T=1000 e m=1. Logo, m+n=1001.

Vamos pensar, agora, na última rodada. Nela haverão apenas pilhas com três discos, ou seja, o número de discos deve ser o triplo do número de pilhas. Assim, a soma do número de pilhas com o de discos de ser um múltiplo de 4.

Mas como essa soma é sempre a mesma, segue que, 1001 é um múltiplo de 4. Absurdo. Logo, é impossível realizar este processo.

(b) Análogo.

Interferência de bloqueador de anúncios detectada!


A Wikia é um site grátis que ganha dinheiro com publicidade. Nós temos uma experiência modificada para leitores usando bloqueadores de anúncios

A Wikia não é acessível se você fez outras modificações. Remova o bloqueador de anúncios personalizado para que a página carregue como esperado.