Bem, pela interpretacao abaixo, que parece razoavel, o problema e' achar uma solucao de k(k+1)/2-r(r+1)/2=0 (mod n) com 1<=r<k e k minimo. Temos que k(k+1)/2-r(r+1)/2=(k-r)(k+r+1)/2. Queremos entao achar dois numeros (k-r e k+r+1) com paridades distintas, cuja diferenca e' pelo menos 3, cujo produto e' multiplo de 2n e cuja soma seja minima. Nesse caso seu produto sera' igual a 2n (senao podemos cortar fatores deles para que seu produto seja 2n fazendo a sua soma diminuir - temos so' que cuidar do caso em que ao cortar esses fatores obtemos dois fatores com diferenca 1, e nesse caso o produto poderia ser igual a 4n no caso otimo - por causa dessas coisas seria mais natural comecar com k=0...), e a maior potencia de 2 que divide 2n dividira' um deles. Devemos escolher uma tal fatoracao de 2n (ou de 4n) de modo que os fatores sejam os mais proximos possiveis. E' claro que a forma da solucao otima depende de n. Se n=2^u, por exemplo, teremos k=2^u e r=2^u-1 ( esse e' o unico caso, alem de n=3, em que k=n), e se n > 3 e' um primo impar, devemos ter k=(n+1)/2 e r=(n-3)/2.Por outro lado, se n=(u+2)(u-1)/2 entao k=u e r=1; esse e' o caso em que k=(sqrt(9+8n)-1)/2 e' o menor possivel comparado com n. Abracos, Gugu
Obs: Se n=36=8.9/2, o produto no caso otimo (16.9=144) e' 4n, e nao 2n (nesse caso o melhor que podemos conseguir com produto igual a 2n com diferenca pelo menos 3 entre os fatores, dado que os fatores devem ter paridade diferente e' 24.3=72, 24+3=27 > 25=16+9). Nesse caso, portanto, k=12 e r=3. Esses fenomenos so podem ocorrer quando n e' da forma k(k+1)/2 (e nem sempre ocorrem nesses casos). > >Claudio, > >Acho ki o problema inicial nao e so saber que o processo para, mas como = >determinar em qual valor de k o processo pararia para a given N. > >Estou meio ki stuck, quem sabe vc pode me ajudar... vou tentar explicar = >minhas observacoes ate agora com alguns exemplos: > >para N=3D6 >1 2 3 4 5 6 >1 2 4 3 -> para quando k =3D 5 ocupa a celula 3 > >para N=3D8 >1 2 3 4 5 6 7 8 >1 4 2 7 6 3 5 -> para quando k =3D 8 ocupa a celula 4 > >para N=3D11 >1 2 3 4 5 6 7 8 9 10 11 >1 2 5 3 4 -> para quando k =3D 6 ocupa a celula 10 > > >ficha k sempre ocupa a celula R onde=20 >R =3D (1+2+...+k) mod N ou a celula N se R=3D0 ( basta mudar o label da >celula N para 0 ) > > >o processo acaba quando celula R ja esta ocupada, ou seja >existe um a < k para o qual (1+2+...+a) mod N =3D R > >outras observacoes (talvez obvias ): > >Sum(1,k) - Sum(1,a) =3D xN onde x >=3D 1 > >Sum(1,k) > N > >Eu tenho ki ralar, entao paro por aki... a minha pergunta e: >Sera possivel, escrever k em funcao de N? > >-Auggy > > > >----- Original Message -----=20 >From: "Cl=E1udio (Pr=E1tica)" <[EMAIL PROTECTED]> >To: <[EMAIL PROTECTED]> >Sent: Friday, March 28, 2003 8:31 AM >Subject: Re: [obm-l] Numero redondo > > > >Oi, JP: > >De qualquer forma, com um no. finito N de c=E9lulas (contando-se mod N, = >ou, >equivalentemente, com as c=E9lulas em torno de um c=EDrculo como disse o = >Gugu), >o processo p=E1ra qualquer que seja k, pois pelo princ=EDpio das casas = >de >pombos, depois de no m=E1ximo N passos haver=E1 necessariamente uma = >c=E9lula com >duas fichas. > >Um abra=E7o, >Claudio. > >----- Original Message ----- >From: "Cl=E1udio (Pr=E1tica)" <[EMAIL PROTECTED]> >To: <[EMAIL PROTECTED]> >Sent: Thursday, March 27, 2003 5:36 PM >Subject: Re: [obm-l] Numero redondo > > >> Quantas c=E9lulas ou compartimentos existem? Se for um n=FAmero = >infinito, >ent=E3o >> n=E3o p=E1ra nunca. Se for um n=FAmero finito (digamos N), ent=E3o = >qual a regra? >> Volta ao in=EDcio mod N? >> >> Outra d=FAvida: voc=EA coloca a ficha 1 na c=E9lula 1. A=ED, se voc=EA = >saltar 1 >> c=E9lula, ir=E1 colocar a ficha 2 na c=E9lula 3. T=E1 certo isso? >> >> ----- Original Message ----- >> From: <[EMAIL PROTECTED]> >> To: <[EMAIL PROTECTED]> >> Sent: Thursday, March 27, 2003 4:31 PM >> Subject: [obm-l] Numero redondo >> >> >> > Turma,tenho uma questao que esta me matando!!!Temos uma sequencia de >> fichas >> > que devemos colocar em celulas assim:coloca a FICHA 1 NUM espa=E7o,e >> indutivamente >> > ao se colocar a ficha k em seu compartimento,saltamos k = >compartimentos e >> > passamos a colocar a ficha k+1 na proxima celula.O processo para = >quando >> > algum compartimento contiver duas fichas.Para quais k o processo = >para? >> > >> > TEA WITH ME THAT I BOOK YOUR FACE >> > >> > >> > ------------------------------------------ >> > Use o melhor sistema de busca da Internet >> > Radar UOL - http://www.radaruol.com.br >> > >> > >> > >> > >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D >> > Instru=E7=F5es para entrar na lista, sair da lista e usar a lista em >> > http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html >> > O administrador desta lista =E9 <[EMAIL PROTECTED]> >> > >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D >> >> = >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D >> Instru=E7=F5es para entrar na lista, sair da lista e usar a lista em >> http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html >> O administrador desta lista =E9 <[EMAIL PROTECTED]> >> = >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D >Instru=E7=F5es para entrar na lista, sair da lista e usar a lista em >http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html >O administrador desta lista =E9 <[EMAIL PROTECTED]> >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D > > >------=_NextPart_000_00B2_01C2F522.05C11BB0 >Content-Type: text/html; > charset="iso-8859-1" >Content-Transfer-Encoding: quoted-printable > ><!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"> ><HTML><HEAD> ><META http-equiv=3DContent-Type content=3D"text/html; = >charset=3Diso-8859-1"> ><META content=3D"MSHTML 5.50.4807.2300" name=3DGENERATOR> ><STYLE></STYLE> ></HEAD> ><BODY> ><DIV><FONT face=3DCourier size=3D2>Claudio,</FONT></DIV> ><DIV><FONT face=3DCourier size=3D2></FONT> </DIV> ><DIV><FONT face=3DCourier size=3D2>Acho ki o problema inicial nao e so = >saber que o=20 >processo para, mas como determinar em qual valor de k o processo pararia = >para a=20 >given N.</FONT></DIV> ><DIV><FONT face=3DCourier size=3D2></FONT> </DIV> ><DIV><FONT face=3DCourier size=3D2>Estou meio ki stuck, quem sabe vc = >pode me=20 >ajudar... vou tentar explicar minhas observacoes ate agora com alguns=20 >exemplos:</FONT></DIV> ><DIV><FONT face=3DCourier size=3D2></FONT> </DIV> ><DIV><FONT face=3DCourier size=3D2>para N=3D6</FONT></DIV> ><DIV><FONT face=3DCourier size=3D2>1 2 3 4 5 6</FONT></DIV> ><DIV><FONT face=3DCourier size=3D2>1 2 4 3 = >-> para=20 >quando k =3D 5 ocupa a celula 3</FONT></DIV> ><DIV><FONT face=3DCourier size=3D2></FONT> </DIV> ><DIV><FONT face=3DCourier size=3D2> ><DIV><FONT face=3DCourier size=3D2>para N=3D8</FONT></DIV> ><DIV><FONT face=3DCourier size=3D2>1 2 3 4 5 6 7 8</FONT></DIV> ><DIV><FONT face=3DCourier size=3D2>1 4 2 7 6 = >3 5 =20 >-> para quando k =3D 8 ocupa a celula 4</FONT></DIV> ><DIV> </DIV> ><DIV> ><DIV><FONT face=3DCourier size=3D2>para N=3D11</FONT></DIV> ><DIV><FONT face=3DCourier size=3D2>1 2 3 4 5 6 7 8 9 10 11</FONT></DIV> ><DIV><FONT face=3DCourier size=3D2>1 2 5 =20 >3 4  = >; ->=20 >para quando k =3D 6 ocupa a celula 10</FONT></DIV> ><DIV> </DIV> ><DIV> </DIV> ><DIV>ficha k sempre ocupa a celula R onde </DIV> ><DIV>R =3D (1+2+...+k) mod N ou a celula N se R=3D0 ( basta mudar o = >label da</DIV> ><DIV>celula N para 0 )</DIV> ><DIV> </DIV> ><DIV> </DIV> ><DIV>o processo acaba quando celula R ja esta ocupada, ou seja</DIV> ><DIV>existe um a < k para o qual (1+2+...+a) mod N =3D R</DIV> ><DIV> </DIV> ><DIV>outras observacoes (talvez obvias ):</DIV> ><DIV> </DIV> ><DIV>Sum(1,k) - Sum(1,a) =3D xN onde x >=3D 1</DIV> ><DIV> </DIV> ><DIV>Sum(1,k) > N</DIV> ><DIV> </DIV> ><DIV>Eu tenho ki ralar, entao paro por aki... a minha pergunta e:</DIV> ><DIV>Sera possivel, escrever k em funcao de N?</DIV> ><DIV> </DIV> ><DIV>-Auggy</DIV> ><DIV> </DIV></DIV></FONT></DIV> ><DIV><FONT face=3DCourier size=3D2></FONT> </DIV> ><DIV><FONT face=3DCourier size=3D2></FONT> </DIV> ><DIV><FONT face=3DCourier size=3D2>----- Original Message ----- </FONT> ><DIV><FONT face=3DCourier size=3D2>From: "Cl=E1udio (Pr=E1tica)" = ><</FONT><A=20 >href=3D"mailto:[EMAIL PROTECTED]"><FONT face=3DCourier=20 >size=3D2>[EMAIL PROTECTED]</FONT></A><FONT face=3DCourier=20 >size=3D2>></FONT></DIV> ><DIV><FONT face=3DCourier size=3D2>To: <</FONT><A=20 >href=3D"mailto:[EMAIL PROTECTED]"><FONT face=3DCourier=20 >size=3D2>[EMAIL PROTECTED]</FONT></A><FONT face=3DCourier=20 >size=3D2>></FONT></DIV> ><DIV><FONT face=3DCourier size=3D2>Sent: Friday, March 28, 2003 8:31 = >AM</FONT></DIV> ><DIV><FONT face=3DCourier size=3D2>Subject: Re: [obm-l] Numero=20 >redondo</FONT></DIV></DIV> ><DIV><FONT face=3DCourier><BR><FONT = >size=3D2></FONT></FONT></DIV><BR><FONT=20 >face=3DCourier size=3D2>Oi, JP:<BR><BR>De qualquer forma, com um no. = >finito N de=20 >c=E9lulas (contando-se mod N, ou,<BR>equivalentemente, com as c=E9lulas = >em torno de=20 >um c=EDrculo como disse o Gugu),<BR>o processo p=E1ra qualquer que seja = >k, pois pelo=20 >princ=EDpio das casas de<BR>pombos, depois de no m=E1ximo N passos = >haver=E1=20 >necessariamente uma c=E9lula com<BR>duas fichas.<BR><BR>Um=20 >abra=E7o,<BR>Claudio.<BR><BR>----- Original Message -----<BR>From: = >"Cl=E1udio=20 >(Pr=E1tica)" <</FONT><A = >href=3D"mailto:[EMAIL PROTECTED]"><FONT=20 >face=3DCourier size=3D2>[EMAIL PROTECTED]</FONT></A><FONT = >face=3DCourier=20 >size=3D2>><BR>To: <</FONT><A = >href=3D"mailto:[EMAIL PROTECTED]"><FONT=20 >face=3DCourier size=3D2>[EMAIL PROTECTED]</FONT></A><FONT = >face=3DCourier=20 >size=3D2>><BR>Sent: Thursday, March 27, 2003 5:36 PM<BR>Subject: Re: = >[obm-l]=20 >Numero redondo<BR><BR><BR>> Quantas c=E9lulas ou compartimentos = >existem? Se for=20 >um n=FAmero infinito,<BR>ent=E3o<BR>> n=E3o p=E1ra nunca. Se for um = >n=FAmero finito=20 >(digamos N), ent=E3o qual a regra?<BR>> Volta ao in=EDcio mod = >N?<BR>><BR>>=20 >Outra d=FAvida: voc=EA coloca a ficha 1 na c=E9lula 1. A=ED, se voc=EA = >saltar 1<BR>>=20 >c=E9lula, ir=E1 colocar a ficha 2 na c=E9lula 3. T=E1 certo = >isso?<BR>><BR>> -----=20 >Original Message -----<BR>> From: <</FONT><A=20 >href=3D"mailto:[EMAIL PROTECTED]"><FONT face=3DCourier=20 >size=3D2>[EMAIL PROTECTED]</FONT></A><FONT = >face=3DCourier=20 >size=3D2>><BR>> To: <</FONT><A = >href=3D"mailto:[EMAIL PROTECTED]"><FONT=20 >face=3DCourier size=3D2>[EMAIL PROTECTED]</FONT></A><FONT = >face=3DCourier=20 >size=3D2>><BR>> Sent: Thursday, March 27, 2003 4:31 PM<BR>> = >Subject:=20 >[obm-l] Numero redondo<BR>><BR>><BR>> > Turma,tenho uma = >questao que=20 >esta me matando!!!Temos uma sequencia de<BR>> fichas<BR>> > que = >devemos=20 >colocar em celulas assim:coloca a FICHA 1 NUM espa=E7o,e<BR>>=20 >indutivamente<BR>> > ao se colocar a ficha k em seu = >compartimento,saltamos=20 >k compartimentos e<BR>> > passamos a colocar a ficha k+1 na = >proxima=20 >celula.O processo para quando<BR>> > algum compartimento contiver = >duas=20 >fichas.Para quais k o processo para?<BR>> ><BR>> > TEA WITH = >ME THAT=20 >I BOOK YOUR FACE<BR>> ><BR>> ><BR>> >=20 >------------------------------------------<BR>> > Use o melhor = >sistema de=20 >busca da Internet<BR>> > Radar UOL - </FONT><A=20 >href=3D"http://www.radaruol.com.br"><FONT face=3DCourier=20 >size=3D2>http://www.radaruol.com.br</FONT></A><BR><FONT face=3DCourier = >size=3D2>>=20 >><BR>> ><BR>> ><BR>>=20 >><BR>=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D<BR>>=20 >> Instru=E7=F5es para entrar na lista, sair da lista e usar a lista = >em<BR>>=20 >> </FONT><A = >href=3D"http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html"><FONT=20 >face=3DCourier=20 >size=3D2>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html</FONT></A><B= >R><FONT=20 >face=3DCourier size=3D2>> > O administrador desta lista =E9 = ><</FONT><A=20 >href=3D"mailto:[EMAIL PROTECTED]"><FONT face=3DCourier=20 >size=3D2>[EMAIL PROTECTED]</FONT></A><FONT face=3DCourier = >size=3D2>><BR>>=20 >><BR>=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D<BR>><BR>>=20 >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<BR>= >>=20 >Instru=E7=F5es para entrar na lista, sair da lista e usar a lista = >em<BR>>=20 ></FONT><A = >href=3D"http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html"><FONT=20 >face=3DCourier=20 >size=3D2>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html</FONT></A><B= >R><FONT=20 >face=3DCourier size=3D2>> O administrador desta lista =E9 = ><</FONT><A=20 >href=3D"mailto:[EMAIL PROTECTED]"><FONT face=3DCourier=20 >size=3D2>[EMAIL PROTECTED]</FONT></A><FONT face=3DCourier = >size=3D2>><BR>>=20 >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D<BR>= ><BR>=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= ><BR>Instru=E7=F5es=20 >para entrar na lista, sair da lista e usar a lista em<BR></FONT><A=20 >href=3D"http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html"><FONT = >face=3DCourier=20 >size=3D2>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html</FONT></A><B= >R><FONT=20 >face=3DCourier size=3D2>O administrador desta lista =E9 <</FONT><A=20 >href=3D"mailto:[EMAIL PROTECTED]"><FONT face=3DCourier=20 >size=3D2>[EMAIL PROTECTED]</FONT></A><FONT face=3DCourier=20 >size=3D2>><BR>=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D= >=3D=3D=3D=3D<BR></FONT></BODY></HTML> > >------=_NextPart_000_00B2_01C2F522.05C11BB0-- > > >========================================================================= >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 >O administrador desta lista é <[EMAIL PROTECTED]> >========================================================================= ========================================================================= 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 O administrador desta lista é <[EMAIL PROTECTED]> =========================================================================