Re: [obm-l] Questões da OBM

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

Oi,

O problema 3 tem uma solução bem bonita (não é minha,
eu vi não me lembro onde): imagine que há 100*101/2 =
5050 cordas, cada uma amarrando cada par de pedras.
Então, para Esmeralda separar uma pilha de a+b pedras
em uma pilha de a pedras e outra de b pedras, ela deve
cortar ab cordas! Como no final devemos ter pedras
soltas, devemos cortar todas as cordas, de modo que a
soma pedida é igual à quantidade de cordas, que é
5050.

No problema 2, item a, suponha por absurdo que
apareçam 2,0,0,4 nessa ordem. Então, voltando a
seqüência obtemos 2,2,0,0,4; 6,2,2,0,0,4... e só
obtemos números pares, absurdo, pois começamos com
1,2,3,4.

O item b é mais interessante: a seqüência é periódica
(assim como qualquer recursão linear homogênea). Para
ver isso, use casa dos pombos: considere todas as 10^4
quádruplas (a,b,c,d) de algarismos. Agora pense nas
quádruplas (x,y,z,w) de quatro termos consecutivos da
seqüência dada. Após pelo menos 10^4 + 1 termos,
alguma quádrupla (x,y,z,w) vai se repetir, e a
seqüência vai "ciclar" a partir daí.

Infelizmente, (x,y,z,w) não é necessariamente
(1,2,3,4). O que fazer então? Considere o começo da
seqüência mais uma quantidade grande de ciclos (o
suficiente para que seja o dobro do tamanho do começo
da seqüência sem ciclos). Se você voltar a seqüência
(assim como no item a) de dois pontos diferentes, o
fim do primeiro ciclo e o fim do pedaço considerado da
seqüência, vai obter os mesmos dígitos. Entre eles,
vai aparecer 1,2,3,4 no começo se voltar do primeiro
ponto e a mesma coisa, 1,2,3,4, se voltar do segundo
ponto. Assim, 1,2,3,4 aparece de novo na seqüência.

[]'s
Shine

--- Marcelo Salhab Brogliato <msbrogli@xxxxxxxxx>
wrote:

> Olá Barola,
> 
> ainda estou tentando resolver.. mas não consegui...
> achei a questão MUITO interessante...
> e espero que o item B seja falso.. é um indicio de
> que a sequencia nao eh
> periodica..
> resta sabermos se ela nao fica periodica apos um
> tempo... por exemplo:
> aparecendo um segundo 9, 4, 8, 7.. entende?
> entao, poderiamos utiliza-la, por exemplo, para a
> geracao de numeros
> aleatorios...
> uma outra questao interessante é: qual a
> distribuicao de probabilidades
> dessa sequencia?
> como a sequencia esta limitada entre 0 e 9, se
> contarmos qtos 0
> aparecerem... dps qtos 1 aparecem.. e
> assim por diante... e fizermos n->inf, essas
> quantidades seriam iguais?!
> 
> estou tentando.. se eu conseguir mando alguma
> coisa..
> mas estou realmente "sem ideias"...
> 
> junto contigo, fico no aguardo da solucao de alguem
> da lista!
> 
> abraços,
> Salhab
> 
> 
> 
> 
> On 10/24/07, barola@xxxxxxxxxxxxxxxx <
> barola@xxxxxxxxxxxxxxxx> wrote:
> >
> >  Oi gente! Alguém pode resolver estas? São da 3ª
> fase da OBM, mas pelo
> > visto o site não disponibiliza o gabarito.
> >
> >
> >
> > *PROBLEMA 2*
> >
> > A seqüência de algarismos
> >
> > 1, 2, 3, 4, 0, 9, 6, 9, 4, 8, 7, ?
> >
> >
> >
> > é construída da seguinte maneira: cada elemento, a
> partir do quinto, é
> > igual ao último algarismo da soma dos quatro
> anteriores.
> >
> > a) Os algarismos 2, 0, 0, 4, juntos e nesta ordem,
> aparecem na seqüência?
> >
> > b) Os algarismos iniciais 1, 2, 3, 4, juntos e
> nesta ordem, aparecem
> > novamente na seqüência?
> >
> >
> >
> >
> >
> > *PROBLEMA 3*
> >
> > Esmeralda tem uma pilha com 100 pedras. Ela divide
> essa pilha em duas novas pilhas e em seguida
> multiplica as
> >
> > quantidades de pedras nessas duas novas pilhas e
> escreve o produto em um quadro. Ela então escolhe
> uma pilha
> >
> > com mais de uma pedra e repete esse procedimento:
> a pilha é dividida em duas, as quantidades de pedras
> nessas
> >
> > duas pilhas são multiplicadas e o produto escrito
> no quadro. Esta operação é realizada até se obter
> apenas pilhas
> >
> > com 1 pedra cada. Quais são os possíveis valores
> da soma de todos os produtos escritos no quadro?
> >
> >
> >
> > Desde já, agradeço.
> >
> > Bárbaral Nedel.
> >
> >
> 


__________________________________________________
Do You Yahoo!?
Tired of spam?  Yahoo! Mail has the best spam protection around 
http://mail.yahoo.com 
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================