Essa viagem é possível? (Análise combinatória) [resolvida]
10 set 2013, 04:34
Existem 5 carros e 20 pessoas para viajar. A viajem será feita em 5 etapas com cada carro contendo 4 pessoas. Em cada etapa as pessoas devem mudar de carro de uma forma que nenhuma pessoa repita o carro e sempre viaje com pessoas diferentes. Isso é possível? Se sim de um exemplo.
Re: Essa viagem é possível? (Análise combinatória)
10 set 2013, 18:55
Olá gabrielxes
Sim, é possível. Não fiz as contas a quantas possibilidades existem para tal distribuição).
Já encontrei um exemplo, mas em vez de te mostrar, vou dar-te o exemplo para 6 pessoas, 3 carros (2 pessoas/carro, e 3 viagens/carro:
Cada pessoa viaja em cada carro uma só vez, pelo que deve rodar para o próximo carro (p.e. sequencialmente) sem repetir o carro, e sem encontrar anteriores companheiros de viagem. Etiquetando os passageiros {1,2,3,4,5,6}, escolhemos para a primeira viagem a distribuição pelos carros, sem perda de generalidade. Escolho p.e. Carro I {1,2}, Carro II {3,4}, Carro III {5,6}. Nas seguintes viagens, os {1} e {2} já não voltarão ao Carro I, devem ocupar cada um, um carro diferente, e devem permutar a cada viagem sem repetir o carro. Assim, podemos construir o exemplo:
_____________Viagem
Carro \(\begin{bmatrix} &I&II&III\\ I&1,2&3,6&4,5\\ II&3,4&1,5&2,6\\ III&5,6&2,4&1,3 \end{bmatrix}\)
É de observar-se o seguinte: se chamarmos n, c, v respectivamente aos números de pessoas, pessoas/carro, viagens, o problema que colocaste só é possível quando n/c<v, pois se fosse n/c=v, pelo menos num carro haveria uma presença repetida ou o reencontro de 2 pessoas, o que por hipótese não é admissível. Tenta resolver o problema que colocaste. Se não conseguires arranjar um exemplo, diz. Bom estudo
Sim, é possível. Não fiz as contas a quantas possibilidades existem para tal distribuição).
Já encontrei um exemplo, mas em vez de te mostrar, vou dar-te o exemplo para 6 pessoas, 3 carros (2 pessoas/carro, e 3 viagens/carro:
Cada pessoa viaja em cada carro uma só vez, pelo que deve rodar para o próximo carro (p.e. sequencialmente) sem repetir o carro, e sem encontrar anteriores companheiros de viagem. Etiquetando os passageiros {1,2,3,4,5,6}, escolhemos para a primeira viagem a distribuição pelos carros, sem perda de generalidade. Escolho p.e. Carro I {1,2}, Carro II {3,4}, Carro III {5,6}. Nas seguintes viagens, os {1} e {2} já não voltarão ao Carro I, devem ocupar cada um, um carro diferente, e devem permutar a cada viagem sem repetir o carro. Assim, podemos construir o exemplo:
_____________Viagem
Carro \(\begin{bmatrix} &I&II&III\\ I&1,2&3,6&4,5\\ II&3,4&1,5&2,6\\ III&5,6&2,4&1,3 \end{bmatrix}\)
É de observar-se o seguinte: se chamarmos n, c, v respectivamente aos números de pessoas, pessoas/carro, viagens, o problema que colocaste só é possível quando n/c<v, pois se fosse n/c=v, pelo menos num carro haveria uma presença repetida ou o reencontro de 2 pessoas, o que por hipótese não é admissível. Tenta resolver o problema que colocaste. Se não conseguires arranjar um exemplo, diz. Bom estudo
Re: Essa viagem é possível? (Análise combinatória)
10 set 2013, 19:12
Dou-te ainda outro exemplo:
n=12; c=4; v=4
_____________Viagem
Carro\(\begin{bmatrix} &I&II&III&IV\\ I&1,2,3&4,7,10&6,9,12&5,8,11\\ II&4,5,6&1,8,11&3,7,10&2,9,12\\ III&7,8,9&2,5,12&1,4,11&3,6,10\\ IV&10,11,12&3,6,9&2,5,8&1,4,7 \end{bmatrix}\)
n=12; c=4; v=4
_____________Viagem
Carro\(\begin{bmatrix} &I&II&III&IV\\ I&1,2,3&4,7,10&6,9,12&5,8,11\\ II&4,5,6&1,8,11&3,7,10&2,9,12\\ III&7,8,9&2,5,12&1,4,11&3,6,10\\ IV&10,11,12&3,6,9&2,5,8&1,4,7 \end{bmatrix}\)