Uma maneira que satisfaz as condições do enunciado é com 30 pilhas:
1,3,5,7,9,...,59
Ao dividir qualquer pilha em duas, tem que aparecer um ímpar menor, então
haverá repetição.
Agora temos que mostrar que não há maneira mais eficiente que esta...
Suponha, por contradição, que você conseguiu uma partição com menos pilhas,
digamos x1<x2<...<xn onde n<=29. Considere as desigualdades:
x1<=3
x2<=5
x3<=7
...
xn<=(2n+1)
Se todas elas valerem, então a soma dos xi é <=3+5+7+...+59=899, absurdo.
Então alguma delas tem que ser falsa. Seja m um índice onde a desigualdade
quebra, isto é, estou supondo:
xm>(2m+1)
Mas existem pelo menos m maneiras de quebrar a pilha xm:
1+(xm-1),2+(xm-2),...,m+(xm-m). Note que xm-m>m+1, então realmente todas
essas maneiras são válidas. Portanto, tem que haver uma pilha de tamanho em
{1,xm-1}, outra em {2,xm-2}, etc. Mas você só tinha m-1 pilhas menores que
xm! Então haverá uma maneira de quebrar a pilha xm em dois pedaços menores
distintos que não estão presentes!
Assim, mostramos que não há maneira de distribuir as pedras em 29 pilhas
(ou menos), e portanto a maneira mais eficiente possível tem 30 pilhas.
Abraço,
Ralph
P.S.: Note-se que até onde sabemos poderia haver OUTRAS maneiras com 30
pilhas, não provamos que aquela maneira é única.
2014-11-02 14:08 GMT-02:00 Mariana Groff <bigolingroff.mari...@gmail.com>:
> Boa Tarde,
> Alguém poderia, por favor, me auxiliar neste problema?
>
> Devemos distribuir 900 pedras em k pilhas, de modo que sejam satisfeitas
> as condições a seguir:
> (i) todas as pilhas têm quantidades distintas de pedras;
> (ii) se dividirmos uma das pilhas em duas pilhas não vazias, as k+1 pilhas
> resultantes não mais terão quantidades distintas de pedras.
> Ache o menor valor possível de k.
>
> Obrigada,
> Mariana
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
--
Esta mensagem foi verificada pelo sistema de antiv�rus e
acredita-se estar livre de perigo.
