segunda-feira, 29 de junho de 2009

O general e o Teorema Chinês dos Restos

Na antiguidade, os generais chineses costumavam contar suas tropas perdidas após a guerra da seguinte forma: ordenavam que as tropas formassem várias colunas com um determinado tamanho e depois contavam quantas sobravam, e faziam isto para vários tamanhos diferentes [1].


Por exemplo, um general chinês possuia 1200 tropas antes da guerra. Após a guerra, ele alinhou as tropas de 5 em 5 de forma que sobraram 3 tropas. Quando alinhou de 6 em 6, também sobraram 3 tropas. Quando alinhou de 7 em 7, sobrou 1 tropa. E quando alinhou de 11 em 11, não sobrou nenhuma tropa. Quantas tropas o general tinha?

Para resolver este problema, é necessário saber lidar com congruências. Além disso, vamos utilizar uma poderosa arma em Teoria dos Números, chamada de Teorema Chinês dos Restos. De fato, o problema apresentado acima é uma aplicação direta deste teorema.

Basta então um pequeno esforço para interpretar o problema. Quando o general alinha suas tropas, formando colunas de tamanho n, ele está realizando uma divisão do número de tropas por n, e depois verificando seu resto.

Observe que, na prática, contar o resto é muito mais fácil que contar o número total, ou o quociente. Aliás, quem conhece um pouco de Teoria dos Números, sabe que raramente estamos interessados no quociente, o resto é o que importa.


O teorema



Não vou apresentar uma prova do Teorema Chinês dos Restos aqui. Simplesmente vou enunciá-lo (e exibir a forma geral de sua solução) para que possamos ir direto ao objetivo do artigo. Existem várias provas desse teorema e elas podem ser achadas na internet ou em livros.

Teorema Chinês dos restos : Sejam inteiros positivos e primos entre si. O sistema de congruências




tem solução única , onde , e é tal que (ou seja, é o inverso multiplicativo de módulo ).


Solução





Primeiramente, vamos organizar as informações do enunciado de forma matemática. Se x é o número de tropas restantes, temos:



Como 5, 6, 7 e 11 são primos entre si, basta aplicar o Teorema Chinês dos Restos. Para isso, vamos usar a "fórmula" mencionada anteriormente. Temos que:









Para calcular os é simples. Vou deduzir o primeiro deles, os outros irei omitir por serem análogos.

é tal que

Mas 462 deixa resto 2 quando dividido por 5, isto quer dizer que , substituindo acima temos que



Que número multiplicamos por 2 que o resto é 1 quando dividido por 5? é 3. Pois (na pior das hipóteses, só teríamos de testar 5-1=4 casos).

Então .

Repetindo o processo, temos



.

Pronto, agora basta jogar tudo na fórmula:







Portanto

que é equivalente a para todo q natural.

Mas queremos x maior que e menor que , o que implica que .

Isto significa que podemos comunicar ao general que lhe sobraram 1023 tropas após o combate [2].

Espero que tenha gostado... não o general, você.




Notas:


[1] Não consegui averiguar a veracidade deste fato. Como vi este problema originalmente num livro de matemática, pode ser que seja apenas fruto da imaginação de algum matemático. Contudo, acho bem plausível que um método como este (ou parecido) possa ter sido usado pelos chineses antigamente, visto que o teorema aplicado para a resolução do problema já era conhecido por eles. Se alguém souber se é verdade ou não, me avise!

[2] Note que o general organizou as tropas módulo 5, módulo 6, módulo 7 e módulo 11. Você consegue dizer se ele poderia ter organizado as tropas de outra forma? Além disso, note que M = 2310 é maior que 1200. Por que precisamos que M fosse maior que 1200?

Imagens de miniaturas legais que eu queria ganhar de presente retiradas de http://wargames.spyz.org.

Obs.: Post feito em homenagem ao Anônimo.




20 comentários:

Gabriel Martins disse...

Po oq esse general tava fazendo perdendo seu tempo liderando uma tropa?
O cara devia é estudar matemática uhahuauha

Anônimo disse...

Valeu pelo post em minha homenagem, rsrs.

Gostei bastante deste post... eu já havia estudado o teorema chinês dos restos mas não tinha visto ainda uma aplicação tão genuína deste teorema.

Valeu!!!

Anônimo disse...

Ótimo artigo.

Apresenta de maneira simples a aplicação do Teorema Chinês dos Restos.

Este tipo de trabalho mostra a face positiva da net de distribuir informação e conhecimento.

Parabens.

Tiago J. Fonseca disse...

Obrigado. ;-)

Simone disse...

Nossa achei super divertida a maneira de explicar o Teorema do resto Chinês...

Tiago J. Fonseca disse...

Obrigado! ;-)

Anônimo disse...

Anonimato em alta. :P
É...Cultura(de verdade), a gente vê por aqui.

Anônimo disse...

zzzz

Anônimo disse...

Então não tem um a aplicação dentro da propria matematica pura. Sempre escuto falar que este é um importante teorema da teoria dos números mas nunca vi nenhuma aplicação a não ser estas sem utilidade. O tempo que o general leva pra alinhar de 4 maneiras diferentes eu teria contado o número de tropas, e até ele terminar de fazer suas anotaçoes e depois resolver o problema eu teria chegado no infinito e voltado.

Tiago J. Fonseca disse...

Olá! Acho que seria interessante você ler isso http://en.wikipedia.org/wiki/Chinese_remainder_theorem#Applications

Anônimo disse...

Beleza, não tinha conseguido entender a demonstração.essa linha de pensamento (ilustrativo ) é muito válida para o conhecimento da matamática. Parabens...

inesprada disse...

mt bom;))

Anônimo disse...

Muito bom, meus parabéns! Você enunciou o teorema de forma clara e depois mostrou uma aplicação, resolvendo passo a passo. Falta um pouco disso na maioria das explicações que vejo na internet.

Obrigado!

Anônimo disse...

Muito bom, meus parabéns! Você enunciou o teorema de forma clara e depois mostrou uma aplicação, resolvendo passo a passo. Falta um pouco disso na maioria das explicações que vejo na internet.

Obrigado!

Anônimo disse...

Oi eu sou Ilvécio Ramos
Estou fazendo licenciatura em matemática e gostaria de saber se se pode utilizar os ideais primos para demonstrar o teorema do reto chinês
da-me um exemplo por favor

Tiago J. Fonseca disse...

Olá, Ilvécio!

Sim, a generalização deste teorema pra outros anéis se dá por ideais (não preciam ser primos). Se A é um anel comutativo e I e J são ideais, dizemos que I e J são coprimos se I+J=A=(1) (esta soma é a soma de ideais). Por exemplo, se n e m são dois inteiros, os ideais (n) e (m) são coprimos se (n)+(m)=(1), ou seja, se e somente se existem inteiros a e b tais que na+mb=1. Então esta definição generaliza a noção de coprimos.

Nesta noção de ideais, o teorema chinês se traduz da seguinte maneira:

Se I e J são coprimos, então

A/I.J = A/I x A/J

Onde o "igual" denota "isomorfo", "I.J" denota o produto de ideais e o "x" é o produto cartesiano dos dois aneis. Pode parecer estranho, mas se você trocar A por Z e I e J por ideais gerados por inteiros, então você recupera o Teorema Chinês dos Restos clássico.

O livro de Álgebra do Arnaldo Garcia e Yves Lequain demonstra o teorema chinês dos restos com ideais para o caso A=Z. Para o caso em que A é um anel comutativo qualquer, o Lang deve ter (ele tem tudo). Este teorema é melhor apreciado em Álgebra Comutativa, então qualquer livro deste assunto também prova este teorema no caso geral.

Neto disse...

Nossa, achei fantástico, finalmente entendi esse teorema, mas fiquei com uma dúvida depois de pensar um pouco: Como é que o general alinhou 1200 tropas de 11 em 11 e não sobrou nenhuma? E também com esse mesmo raciocínio, alinhando de 6 em 6 e de 5 em 5 não poderiam sobrar tropas!! Ou não é bem assim? Fiquei confuso nesta parte!!

Tiago J. Fonseca disse...

Olá Neto! É o seguinte: 1200 tropas era o número de tropas que o general tinha ANTES de ir para a guerra. Ele não alinhou 1200 tropas, ele alinhou as 1023 tropas restantes.

Anônimo disse...

Obrigado! Ótimo artigo! Me ajudou muito!

Italo Luiz disse...

...a porcaria do Dr. de merda aqui na UNB explicou e deduziu e ninguém entendeu nada. Agora com um exemplo quase infantil tudo se esclarece. Valeu!!!