Problema: Imagine que peguemos
pessoas e as coloquemos em círculo,
numerando-as de
a
no sentido horário. Você é o número
. Cabe a
você contar até
, sempre no sentido horário, começando de qualquer
uma das pessoas, e aquele no qual a contagem terminar, é eliminado do
jogo. A contagem reinicia a partir da próxima pessoa depois ( sentido horário ) do vizinho
eliminado. Sucessivamente, vão sendo eliminados os integrantes. O último a
sobrar não é eliminado e ganha um prêmio. É possível criar uma fórmula ou regra que permita descobrir por qual número
da pessoa devemos começar o processo da contagem de forma que a última a sobrar seja a de número
?
RESOLUÇÃO
CONSIDERAÇÕES INICIAIS
CONSIDERAÇÕES INICIAIS
Definição 1: Círculo Maior - é o círculo com
pessoas;
Definição 2: Círculo Menor - é o círculo imediatamente formado após a eliminação da primeira pessoa. As pessoas do círculo menor são renumeradas no sentido horário de
a
começando da pessoa sempre fixa de número
( a única que não recebe nova numeração );
Definição 3:
é o número da pessoa do Círculo Maior que se iniciou a contagem;
Definição 4:
é o número da pessoa do Círculo Maior onde terminou a contagem, ou seja,
é o número a ser eliminado neste círculo;
Definição 4:
Definição 5:
é o número da pessoa do Círculo Menor que se iniciou a contagem;
Definição 6:
, se ![u \neq 1 [;u \neq 1;]](http://thewe.net/tex/u%20%5Cneq%201)
, se
;
Definição 7:
o resto da divisão de
por
, se
;
o resto da divisão de
por
acrescido de
, se
.
Definição 6:
Definição 7:
SOBRE ELIMINAÇÃO E RENUMERAÇÃO
Temos dois casos a considerar:
Primeiro caso:
.
Trecho do Círculo Maior, com
pessoas e número
para eliminar:
e-1, e, e+1,...,n
Trecho do Círculo Menor, com
pessoas com número
eliminado e números posteriores renumerados:
e-1, eliminado, e,...,n-1
Então, no Círculo Menor, começa-se a contagem a partir de
. Logo,
, para
.
Segundo caso:
.
Trecho do Círculo Maior, com
pessoas e número
para eliminar:
e-1, e=n, 1
Trecho do Círculo Menor, com
pessoas com número
eliminado. Observe que abaixo não é necessário renumeração porque
.
n-1, eliminado, 1
Então, no Círculo Menor, começa-se a contagem a partir de
. Logo,
, para
.
Então a relação do
do Círculo Menor com o
do Círculo Maior é ( ver definição 6 )
.
Então a relação do
RELAÇÃO ENTRE O INÍCIO E O FINAL DE CONTAGEM INICIAL
A contagem para eliminação é de
em
. Começando por
no Círculo Maior, a contagem horária percorre mais
pessoas posteriores à
. Assim (
),
O abatimento de
na segunda igualdade as vezes é necessária porque, como estamos somando números em um círculo de
a
, se
, temos que enquadrar este resultado na primeira volta horária positiva do Círculo Maior. Pode-se provar que ( ver definição 7 )
.
Exemplos: para
, de
temos ![e=R[(16+9)/40]=R[25/40]=25 [;e=R[(16+9)/40]=R[25/40]=25;]](http://thewe.net/tex/e=R[%2816+9%29/40]=R[25/40]=25)
para
, de
temos ![e=R[(34+9)/40]=R[43/40]=3 [;e=R[(34+9)/40]=R[43/40]=3;]](http://thewe.net/tex/e=R[%2834+9%29/40]=R[43/40]=3)
para
Entretanto, veremos que na dedução da regra para
, é necessário saber por qual pessoa de número
iniciou-se uma contagem isolada de
por intermédio do número
da eliminada. Então temos que ter
em função de
. Mas na relação
pode ocorrer a situação
e, da mesma forma, temos que enquadrar este resultado na primeira volta horária positiva do Círculo Maior. Neste caso, usa-se novamente a função da definição 7, pois
.
Exemplos: para
, de
temos ![M=R[(3-9)/7]=R[(-6)/7]=-6(<0)+7=1 [;M=R[(3-9)/7]=R[(-6)/7]=-6(<0)+7=1;]](http://thewe.net/tex/M=R[%283-9%29/7]=R[%28-6%29/7]=-6%28%3C0%29+7=1)
para
, de
temos ![M=R[(2-9)/7]=R[(-7)/7]=0(=0)+7=7 [;M=R[(2-9)/7]=R[(-7)/7]=0(=0)+7=7;]](http://thewe.net/tex/M=R[%282-9%29/7]=R[%28-7%29/7]=0%28=0%29+7=7)
Exemplos: para
para
VALORES INICIAIS DE
para
e ![n=2 [;n=2;]](http://thewe.net/tex/n=2)
Sendo
a quantidade de pessoas, se
( e esta única pessoa de numeração
) então o problema está resolvido e não é necessário fazer contagem nenhuma. Convenciona-se que
;
Se
, para a contagem de
começando pelo número
ela terminará em número par, ou seja, o
será o eliminado. Portanto
.
FÓRMULA RECURSIVA PARA
com ![n\geq 3 [;n\geq 3;]](http://thewe.net/tex/n%5Cgeq%203)
Para
( Círculo maior ) temos que chegar na situação de
( de Círculo Menor) quando
após a pessoa do Círculo Maior ser eliminada. Como foi dito na parte final da seção ELIMINAÇÃO E RENUMERAÇÃO,
...a relação do
do Círculo Menor com o
do Círculo Maior é ( ver definição 6 ) é
Assim,
e isto quer dizer que no Círculo Maior a pessoa eliminada será a de número
, de forma que se inicie a contagem no Círculo Menor (
) na pessoa de número
, que como sabemos é vantajoso.
Agora, no Círculo Maior o que nos interessa é
, o início da contagem. Como vimos na seção RELAÇÃO ENTRE O INÍCIO E O FINAL DE CONTAGEM INICIAL, temos
Portanto, em um círculo com
pessoas, deve-se começar a contar da pessoa de número
, de forma que ao final das eliminações reste a pessoa de número
.
Como vimos, a relação entre o Círculo Menor (![n-1 [;n-1;]](http://thewe.net/tex/n-1)
) e o Círculo Maior (
) permitiu-nos saber qual número da pessoa se inicia a contagem no maior, sabendo do número da pessoa de início no menor. Transferindo essa definição de Círculo Menor
Círculo Maior para as quantidades respectivas de pessoas
,
,...,
, podemos fazer uma fórmula recursiva para
, com
.
Substituindo ( 1 ) em ( 2 ):
Exemplo: Calcular
sabendo que
.
Resolução:
Fonte das outras imagens: http://br.freepik.com/fotos-gratis
Olá, Aloísio Teixeira!!!!
ResponderExcluirBom dia!!!!
A sua postagem, para mim, são daquelas que eu mais gosto, pois são obras diferenciadas das demais, devido à engenhosidade empregada na solução do(s) problema(s)!!!! Dizendo assim, até parece que eu não dou importância às demais postagens, não é isso!!! Todas tem o seu lado interessante, seja quanto ao assunto abordada, formas demonstrativas, qualidades editoriais gráficas e etc. Mas, se tem tudo isso, por exemplo, essa sua postagem aqui e se vê que o autor apresenta um novo método resolutivo, é aí, que eu digo que, parto para aquela preferência individual, de eleger tal artigo como "diferenciado" !!!!
Parabéns, pelo seu artigo "diferenciado, amigo Aloísio!!!! Muito poder de criatividade você colocou aqui e vai fazer sucesso, não só por disso, como também, por sempre agregar valor ao que escreve para o seu blog (mais um dos bons blogs) aplicando aquelas outras qualidades de que falei anteriormente.
Tem alguma ideia, para uma aplicação afora aquela de ser a solução para o problema da enumeração de pessoas no círculo redutor? Na mecânica, biologia, indústria de brinquedos (jogo do... "resta um", xadrez, RPG?), etc.
Estou aproveitando esse período do carnaval, para avançar na minha pesquisa sobre a formação dos "quadrados mágicos" de lados ímpares, pois me pareceu serem os mais.. "fáceis" de serem estudados e também, eu e o Kleber Kilhian estamos trabalhando na postagem para apresentarmos s solução daquela postagem que fizemos conjuntamente, com o título... "Desafio: Tecnologia Extraterrestre" e que até agora, ninguém atinou com uma solução!!!!!
Tudo de bom e vamos... que vamos!!!! Até breve!!!!
Um abraço!!!!!
Olá, Francisco Valdir!
ExcluirObrigado pelas palavras positivas.
Sobre a utilização do método do círculo para resolver outras questões de outras disciplinas ou para fins práticos não cheguei a pensar nada a respeito.
Uma vez, há muito tempo, vi em uma Biblioteca de Fortaleza, um livro muito antigo que tratava apenas da confecção de quadrados mágicos. Hoje me arrependo de não ter tirado uma xerox do mesmo.
Vou dar uma estudada, com carinho, na postagem "Desafio:Tecnologia Extraterrestre" sua e do Kleber.
Obrigado mais uma vez e até a próxima!