[obm-l] Moedas em caixas

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

Title: Moedas em caixas

Oi, Alexandre:

Eu achei esse problema das moedas em caixas mais interessante do que o do no. de solucoes da equacao, onde a matematica "legal" acaba no momento em que voce estabelece a relacao entre o no. de solucoes de uma equacao e os coeficientes de um certo polinomio associado aquela equacao. Depois eh soh braco (ou de preferencia, transistor).

O das moedas eh uma aplicacao bem legal da representacao binaria de numeros naturais.

No caso de 10 caixas e 1000 moedas, a k-esima caixa tem que ter 2^(k-1) moedas, para k = 1, 2, ..., 9.  Total das 9 primeiras caixas = 1 + 2 + 4 + ... + 128 + 256 = 511 moedas.
A 10a. caixa contera as 489 moedas restantes.

Usando as 9 primeiras caixas, voce consegue pegar qualquer numero de moedas entre 1 e 511 (inclusive) - pra ver isso basta reparar que qualquer numero tem uma (unica) representacao binaria (ou seja, como soma de potencias de 2).

Pra pegar 512 ou mais moedas, voce usa a 10. caixa e depois uma combinacao das 9 primeiras que contenha de 1 a 511 moedas. Por exemplo, 836 = 489 + 256 + 64 + 16 + 8 + 2 + 1 = 489 + 2^(9-1) + 2^(7-1) + 2^(5-1) + 2^(4-1) + 2^(2-1) + 2^(1-1) ==> pra pegar 836 moedas voce vai usar as caixas 1, 2, 4, 5, 7, 9 e 10.

O problema geral eh o seguinte:
1) Prove que com caixas contendo 1, 2, 4, ..., 2^(n-1) moedas, voce consegue pegar um numero qualquer de moedas entre 1 e 2^n - 1 (inclusive).
2) Prove que essa eh a unica forma de distribuir 2^n - 1 moedas por n caixas em que isso eh possivel.

Um abraco,
Claudio.


on 10.08.03 00:26, Alexandre Daibert at alexandredaibert2@ig.com.br wrote:

> Não, isto não caiu em vestibular nenhum, eu cheguei nisto no meio de um problema, q eh o seguinte:
> Tendo 10 caixas e 1000 moedas, colocar as caixas nas moedas de modo q qualquer quantidade de 1 a 1000 moedas possam ser pegas de modo a não abrir nenhuma caixa. Se não me engano este problema eh do homem q calculava. tem uma solução mais usual para ele q eh ir colocando 1, 2, 4, 8, ... moedas em cada caixa, e no fim as q sobrarem colocar na última caixa. 
>
> *** De uma checada nas contas: 1+2+4+8+...+256 = 511 ==> sobram 489 moedas.
> Esse 23 deve vir do fato de que 2^10 - 1 = 1023 e de que existem apenas 1000 moedas, ou seja, faltam 23 moedas pra completar uma eventual 11a. caixa, que conteria 2^9 = 512 moedas (489+23=512).
>
> Sobram 23 moedas, mas elas não precisam ser colocadas necessariamente apenas na última caixa. Se vc pensar em cima do problema vc chega q o número de soluções do problema é o número de soluções inteiras não negativas da equação: 16a + 8b + 4c + 2d + e = 23. Claro q isto vai além do q se esperava q a pessoa fizesse no problema. Cheguei a este resultado e quis, por curiosidade, saber como calcular o número de soluções deste tipo de equação, visto q o cálculo no braço seria muito trabalhoso. Pensei q houvesse alguma solução por análise combinatória deste problema, porém mais avançada q a resolução clássica da equação a + b + c + d = 10 por exemplo. Mas pelo que eu entendi, este tipo de problema, pelo q vimos ateh aki, mesmo com problemas menores, ou vc calcula todas as soluções no braço mesmo ou joga em um computador. Não há método matemático q seja pouco trabalhoso. Mas mesmo assim gostaria de agradecer imensamente ao colega, pois as suas explicações contribuiram muito para mim.  :-) 
>
> Se alguém quiser a minha resolução deste problema das caixas e como eu cheguei a isso, depois me dê um toque q colocarei minha resolução aki com paciência
>
> Alexandre Daibert