ELEMENTOS: 018-A Resolução do Círculo Redutor

Descreverei a seguir a minha versão da solução do problema do Círculo Redutor .

Problema: Imagine que peguemos $[;n;]$ pessoas e as coloquemos em círculo, numerando-as de $[;1;]$ a $[;n;]$ no sentido horário. Você é o número $[;1;]$ . Cabe a você contar até $[;10;]$ , 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 $[;M;]$ da pessoa devemos começar o processo da contagem de forma que a última a sobrar seja a de número $[;1;]$ ?

RESOLUÇÃO

CONSIDERAÇÕES INICIAIS

Definição 1: Círculo Maior - é o círculo com $[;n;]$ 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 $[;1;]$ a $[;n-1;]$ começando da pessoa sempre fixa de número $[;1;]$ ( a única que não recebe nova numeração );

Definição 3: $[;f(n)=M\geq1;]$ é o número da pessoa do Círculo Maior que se iniciou a contagem;

Definição 4: $[;e>1;]$ é o número da pessoa do Círculo Maior onde terminou a contagem, ou seja, $[;e;]$ é o número a ser eliminado neste círculo;

Definição 5: $[;f(n-1)=m\geq1;]$ é o número da pessoa do Círculo Menor que se iniciou a contagem;

Definição 6: $[;[u]_k=u;]$ , se $[;u \neq 1;]$
$[;[u]_k=k;]$ , se $[;u=1;]$ ;

Definição 7: $[;R(u/k)=;]$ o resto da divisão de $[;u;]$ por $[;k;]$ , se $[;u>0;]$ ;
$[;R(u/k)=;]$ o resto da divisão de $[;u;]$ por $[;k;]$ acrescido de $[;+k;]$ , se $[;u \leq 0;]$ .

SOBRE ELIMINAÇÃO E RENUMERAÇÃO

Temos dois casos a considerar:

Primeiro caso: $[;e\neq n;]$ .

Trecho do Círculo Maior, com $[;n;]$ pessoas e número $[;e\neq n;]$ para eliminar:

e-1, e, e+1,...,n

Trecho do Círculo Menor, com $[;n-1;]$ pessoas com número $[;e;]$ 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 $[;e;]$ . Logo, $[;f(n-1)=m=e;]$ , para $[;e\neq n;]$ .

Segundo caso: $[;e=n;]$ .

Trecho do Círculo Maior, com $[;n;]$ pessoas e número $[;e=n;]$ para eliminar:

e-1, e=n, 1

Trecho do Círculo Menor, com $[;n-1;]$ pessoas com número $[;e;]$ eliminado. Observe que abaixo não é necessário renumeração porque $[;n=e;]$ .

n-1, eliminado, 1

Então, no Círculo Menor, começa-se a contagem a partir de $[;1;]$ . Logo, $[;f(n-1)=m=1;]$ , para $[;e=n;]$ .

Então a relação do $[;f(n-1);]$ do Círculo Menor com o $[;e;]$ do Círculo Maior é ( ver definição 6 ) $[;e=[f(n-1)]_n;]$ .

RELAÇÃO ENTRE O INÍCIO E O FINAL DE CONTAGEM INICIAL

A contagem para eliminação é de $[;10;]$ em $[;10;]$ . Começando por $[;M;]$ no Círculo Maior, a contagem horária percorre mais $[;9;]$ pessoas posteriores à $[;M;]$ . Assim ( $[;1<e\leq n;]$ ),

$[;e=M+9;]$ , se $[;M+9 \leq n;]$

$[;e=M+9-\alpha n;]$ se $[;M+9>n;]$

O abatimento de $[;\alpha n;]$ na segunda igualdade as vezes é necessária porque, como estamos somando números em um círculo de $[;1;]$ a $[;n;]$ , se $[;M+9>n;]$ , temos que enquadrar este resultado na primeira volta horária positiva do Círculo Maior. Pode-se provar que ( ver definição 7 ) $[;e=R[(M+9)/n];]$ .

Exemplos: para $[;M=16;]$ , de $[;n=40;]$ temos $[;e=R[(16+9)/40]=R[25/40]=25;]$
para $[;M=34;]$ , de $[;n=40;]$ temos $[;e=R[(34+9)/40]=R[43/40]=3;]$

Entretanto, veremos que na dedução da regra para $[;f(n);]$ , é necessário saber por qual pessoa de número $[;M;]$ iniciou-se uma contagem isolada de $[;10;]$ por intermédio do número $[;e;]$ da eliminada. Então temos que ter $[;M;]$ em função de $[;e;]$ . Mas na relação $[;M=e-9;]$ pode ocorrer a situação $[;M\leq0;]$ 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 $[;M=R[(e-9)/n)];]$ .

Exemplos: para $[;e=3;]$ , de $[;n=7;]$ temos $[;M=R[(3-9)/7]=R[(-6)/7]=-6(<0)+7=1;]$
para $[;e=2;]$ , de $[;n=7;]$ temos $[;M=R[(2-9)/7]=R[(-7)/7]=0(=0)+7=7;]$

VALORES INICIAIS DE $[;f(n);]$ para $[;n=1;]$ e $[;n=2;]$

Sendo $[;n;]$ a quantidade de pessoas, se $[;n=1;]$ ( e esta única pessoa de numeração $[;1;]$ ) então o problema está resolvido e não é necessário fazer contagem nenhuma. Convenciona-se que $[;f(1)=0;]$ ;

Se $[;n=2;]$ , para a contagem de $[;10;]$ começando pelo número $[;1;]$ ela terminará em número par, ou seja, o $[;2;]$ será o eliminado. Portanto $[;f(2)=1;]$ .

FÓRMULA RECURSIVA PARA $[;f(n);]$ com $[;n\geq 3;]$

Para $[;n=3;]$ ( Círculo maior ) temos que chegar na situação de $[;n=2;]$ ( de Círculo Menor) quando $[;f(n-1)=f(3-1)=f(2)=1;]$ 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 $[;f(n-1);]$ do Círculo Menor com o $[;e;]$ do Círculo Maior é ( ver definição 6 ) é

$[;e=[f(n-1)]_n;]$ ( 1 )

Assim, $[;e=[f(3-1)]_3=[f(2)]_3=[1]_3=3;]$ e isto quer dizer que no Círculo Maior a pessoa eliminada será a de número $[;3;]$ , de forma que se inicie a contagem no Círculo Menor ( $[;n=2;]$ ) na pessoa de número $[;1;]$ , que como sabemos é vantajoso.

Agora, no Círculo Maior o que nos interessa é $[;f(3)=M;]$ , o início da contagem. Como vimos na seção RELAÇÃO ENTRE O INÍCIO E O FINAL DE CONTAGEM INICIAL, temos

$[;M=R[(e-9)/n)];]$ ( 2 )

$[;f(n);]$ $[;=R[(3-9)/3]=R[-6/3]=0(=0)+3=3;]$

Portanto, em um círculo com $[;n=3;]$ pessoas, deve-se começar a contar da pessoa de número $[;f(n)=f(3)=3;]$ , de forma que ao final das eliminações reste a pessoa de número $[;1;]$ .

Como vimos, a relação entre o Círculo Menor ( $[;n-1;]$ $[;=2;]$ ) e o Círculo Maior ( $[;n=3;]$ ) 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 $[;\rightarrow;]$ Círculo Maior para as quantidades respectivas de pessoas $[;3;]$ $[;\rightarrow;]$ $[;4;]$ , $[;4;]$ $[;\rightarrow;]$ $[;5;]$ ,..., $[;n;]$ $[;\rightarrow;]$ $[;n+1;]$ , podemos fazer uma fórmula recursiva para $[;f(n);]$ , com $[;n \geq 3;]$ .

Substituindo ( 1 ) em ( 2 ):

$[;f(n)=M=R \left{\frac{[f(n-1)]_n-9 }{n}\right};]$

Exemplo: Calcular $[;f(12);]$ sabendo que $[;f(11)=6;]$ .

Resolução: $[;f(12)=R \left{\frac{[f(11)]_{12}-9 }{12}\right}=R \left{\frac{6-9}{12}\right}=R \left{\frac{-3}{12}\right}=-3+12=9;]$

Link relacionados: O Círculo Redutor e a Conjectura de Hunasses
O Problema de Josefo

Fonte das outras imagens: http://br.freepik.com/fotos-gratis

2 comentários:

Francisco Valdir19 de fevereiro de 2012 às 09:47
Olá, Aloísio Teixeira!!!!

Bom 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!!!!!
ResponderExcluir
Respostas

Adicionar comentário

Páginas

domingo, 19 de fevereiro de 2012

018-A Resolução do Círculo Redutor

2 comentários:

V.O