Jump to content
Warrior

[Desafio] Fracções

Recommended Posts

Warrior

No outro dia deparei-me com um problema interessante e decidi partilhar. Não é propriamente fácil mas como tem motivação histórica achei curioso.

Há muitos desafios que nos pedem para recuperarmos fracções tendo por base a sua representação decimal.

A verdade é que a divisão de dois números A e B pode dar origem a uma dízima infinita com um período que pode ir no máximo até B. Por exemplo 1/7 = 0,142857 142857 142857... Recuperar 1/7 tendo este período já foi colocado como desafio no forum várias vezes (por exemplo aqui).

Algo que menos pessoas sabem é que, tendo o resultado de uma fracção A/B, é possível recuperar eficientemente A e B se descobrirmos os primeiros NA+NB+1 dígitos. Ou seja, se nos disserem que o dividendo tem NA dígitos e o divisor NB, então podemos recuperar a fracção inicial muito rapidamente. No caso do 1/7, bastam-nos os 3 dígitos 142.

O desafio é esse mesmo. Como recuperar A e B conhecendo só parte da representação decimal?

Portanto eu pergunto, qual é a fracção A/B, com A e B de 5 dígitos cada, cuja representação decimal inicia com este número "16764004988"? Que método é que pode ser usado para o descobrir, sem recorrer ao computador?

Contexto: ZAPMAIL

Antes do Fax se ter difundido, a FedEx procurou instalar um serviço de entrega de correspondência mais rápido para as empresas. Os documentos eram digitalizados nos correios e enviados pela rede para outra estação FedEx que os imprimia e entregava no destinatário no mesmo dia. As empresas conseguiam entregar os documentos mais rapidamente e a FedEx poupava somas significativas ao reduzir a frota de transportes. (Este sistema foi descontinuado com elevados prejuízos quando poucos anos mais tarde o Fax se espalhou e as empresas não estavam dispostas a pagar para um serviço que tinham gratuito)

Uma das primeiras preocupações foi a forma como poderiam encriptar os documentos pela rede. A proposta foi terem os dois terminais a escolherem dois números co-primos A e B, obterem a divisão A/B e com o seu resultado em binário fazerem XORs no documento, encriptando-o. Na outra extremidade, e conhecendo-se o mesmo A e B, a operação podia ser revertida aplicando exactamente o mesmo processo.

Infelizmente os documentos por vezes continham espaços em branco consecutivos, sendo possível recuperar uma parte do resultado da divisão. Mais tarde se demonstrou que com B números consecutivos se conseguia quebrar a encriptação e este método foi abandonado.

Edited by Warrior
  • Vote 1

Share this post


Link to post
Share on other sites
Warrior

Oh, nunca mais me lembrei de colocar aqui a solução..

Vou ver se arranjo um tempo para escrevê-la.

Share this post


Link to post
Share on other sites
Pedro Ribeiro I

Bem, hoje em química descobri como achar o B, falta-me o A. Sem computador :) só fiz para números com um dígito, não sei como funciona com mais dígitos. Vou continuar a ver e depois digo algo. Obrigado pelo desafio Warrior

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.