Eu fiz essa prova! Eu acho.... Observe o seguinte: os números 2, 4, 8, 16 e 32 devem estar em caixas distintas, pois senão a condição do mdc não seria satisfeita. Então temos um total de caixas maior ou igual a 5. Agora basta mostrar um exemplo com 5 caixas. Acho que colocando os números 2^i, 2^i + 1, ..., 2^(i+1) - 1 na caixa i dá certo. Quer dizer: Caixa 1 -> 2, 3; Caixa 2 -> 4, 5, 6, 7; Caixa 3 -> 8 a 15; Caixa 4 -> 16 a 31; Caixa 5 -> 32 a 51. De fato, se a, b estão na mesma caixa, por exemplo na 3, e d=mdc(a, b) , então d|(b-a) < 8, de modo que d não está nessa caixa. Em geral, se a, b pertencem à caixa i, então d <= b-a < 2^i => d não pertence à caixa i.
Até mais, Yuri -- Mensagem original -- >Olá! Meus Amigos! Sou muito grato as elucidações e valiosas informações >enviadas, pois não suspeitava da complexidade do probleminha clássico que > >enviei recentemente à lista. Também gostei do improviso da receita de biscoito > >e aproveitando o clima amigável, gostaria que atendessem ao pedido da Renata > >sobre a resolução do tal "problema esquisito" proposto na Olimpíada Cearense. > >Agora, sem querer abusar da boa vontade dos nobres colegas, vejam outro que > >caiu em nossa singela Olimpíada. OBRIGADO! > >Cinquenta bolas, numeradas de 2 a 51, devem ser colocadas em caixas, de modo > >que o máximo divisor comum dos números de duas bolas quaisquer de uma caixa >não >seja o número correspondente a uma bola desta caixa. Encontre o número mínimo > >de caixas necessárias para guardar todas as bolas. Justifique sua resposta. > >Bom Final de Semana! > > > >________________________________________________ >WebMail UNIFOR - http://www.unifor.br >========================================================================= >Instruções para entrar na lista, sair da lista e usar a lista em >http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html >========================================================================= > []'s, Yuri ICQ: 64992515 ------------------------------------------ Use o melhor sistema de busca da Internet Radar UOL - http://www.radaruol.com.br ========================================================================= Instruções para entrar na lista, sair da lista e usar a lista em http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html =========================================================================