Re: [obm-l] desafio !

["Paulo Santa Rita" <p_ssr@xxxxxxxxxxx>]

Ola Wander e demais colegas
desta lista ... OBM-L,

Como CADA HOMEM PARTICIPA DE DUAS PATRULHAS  e CADA DUAS PATRULHAS TEM 
EXATAMENTE UM HOMEM EM COMUM podemos caracterizar univocamente um homem 
atraves de uma combinacao de duas patrulhas, isto e, existe uma aplicacao 
biunivoca entre as combinacoes de duas patrulhas e o conjunto dos homens :

TOTAL DE HOMENS = BINOM(11,2) = 55

Esses homens serao distribuidos por 11 patrulhas. Seja N o numero de homens 
por patrulha. Entao 11N e o total de homens, contados duas vezes, isto e :

11*N = 2*55  => N=10

Assim, cada patrulha tera 10 homens.

Talvez seja interessante perguntar se ha uma forma rapida de se visualizar 
como sera feita a distribuicao dos homens nas patrulhas. Sim, ha e e 
simples. Basta observar a primeira parte do raciocinio :

Seja H={H1, H2, ..., H55} o conjunto de homens e P={Conjunto de todas as 
combinacoes de 11 patrulhas, tomadas 2 a 2 }. Qualquer bijecao
D : H -> P sera uma distribuicao valida, que atendera as exigencias de 
simetria do problema.

Para uma visualizacao melhor, basta observar que todo Conjunto de 
combinacoes de um conjunto ordenado pode ser distribuido em forma de 
triangulo. No nosso caso, se P1, P2,...,P11 forem as patrulhas :

{P10,P11}
{P9,P10},{P9,P11}
{P8,P9},{P8,P10},{P8,P11}
...
{P1,P2},{P1,P3},{P1,P4},...,{P1,P11}

Basta agora associar a cada conjunto de duas patrulhas um homem. Isso e uma 
forma de visualizar as coisas.

Esse problema enseja outros, de alguma forma relacionados ...

Suponha que o comandante, dispondo de um numero fixo (efetivo) de soldados, 
precisasse montar a cada semana um conjuntos de patrulhas, de forma que :

1) Todas as patrulhas tenham o mesmo numero de soldados
2) Nenhum soldaodo do efetivo fique, em nenhuma semana, sem estar alocado a 
uma patrulha
3) Em qualquer instante, duas patrulhas quaisquer nao tenham nenhum soldado 
em comum ( patrulhas disjuntas )
4) Em qualquer semana seguinte, quaisquer dois soldados que ja tenham 
servidos juntos em uma mesma patrulha nao poderam ficar juntos novamente.
5) Ao fim das semanas de patrulhamento quaisquer dois soldados( do efetivo ) 
tenham servido juntos em alguma patrulha.

Como ajudar o comandante ? Existe um algoritmo para tanto ? Qualquer numero 
inicial de soldados serve ? Senao, Qual o numero de efetivos que sempre 
serve ?

Um abraco
Paulo Santa Rita
2,1927,041102









>----- Original Message ----- From: Wander  <mailto:wander29br@hotmail.com> 
>Junior To: obm-l@mat.puc-rio.br <mailto:obm-l@mat.puc-rio.br>  Sent: 
>Sunday, November 03, 2002 2:09 PM
>Subject: [obm-l] desafio !
>
>Dúvida:
>
>Um comandante de companhia convocou voluntários para a constituição de 11
>patrulhas. Todas elas são formadas pelo mesmo número de homens. Cada homem
>participa de exatamente duas patrulhas. Cada duas patrulhas tem somente um
>homem em comum. Determine o múmero de voluntários e integrantes de uma
>patrulha.
>
>
>Agradeço desde já.
>Wander


_________________________________________________________________
MSN Messenger: converse com os seus amigos online. 
http://messenger.msn.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
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================