Re: [obm-l] Problema de pilhas
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 x1x2...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-mm+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.
Re: [obm-l] Problema de pilhas
k(1+(k-1)r+1)/2=900 rk^2+k(2-r)-1800=0 delta=(2-r)^2+r7200 r=2 o menor r k=30 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.
Re: [obm-l] Problema de pilhas
k=1 450,450 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.
[obm-l] Problema de pilhas
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.
