Olimpíadas

Mensagem não lidapor **HHHoppe** » Sex 22 Set, 2017 17:43

Sete pessoas estão esperando, em fila, para entrar em uma sala onde sentarão em sete cadeiras arrumadas em linha, uma do lado da outra. As pessoas entrarão e, enquanto for possível, irão sentar-se isoladas, isto é, em uma cadeira cujas cadeiras vizinhas (à esquerda e à direita ou só de um dos lados caso seja uma cadeira de uma das pontas) estejam ambas vazias. De quantas maneiras distintas as pessoas podem se distribuir pelas cadeiras?

Dica: considere em separado o caso em que a quarta pessoa a entrar na sala encontra uma cadeira isolada para sentar-se e os casos em
que ela não encontra.

Não entendi muito bem o problema... Se as 7 pessoas vão sempre se sentar, não importa se as primeiras vão procurar se sentar em cadeiras com as vizinhas vazias, as possibilidades ainda seriam [tex3]7![/tex3] , que é a permutação delas nas cadeiras. Ou eu estou vacilando e realmente faz diferença? Ao meu ver, o fato das 3 ou 4 primeiras pessoas se sentarem em posições não adjacentes não elimina a possibilidade de nenhuma ordenação das pessoas nessas 7 cadeiras.

Mensagem não lidapor **HHHoppe** » Sex 22 Set, 2017 22:03

Faz diferença sim, pois há uma redução nas possibilidades para as pessoas que entrarão na sala logo após a primeira sentar-se.
Depois que as primeiras 4 (ou 3, dependendo do caso) sentarem-se, então pode sim ser feita uma simples permutação com o resto das pessoas.

Minha dúvida é justamente a respeito das possibilidades do terceiro ou até quarto indíviduo que entra na sala. Não sei como contabilizar as suas possibilidades, pois o anterior pode ter sentado em diversas posições.
Por exemplo, o primeiro e o segundo podem entrar, tendo assim: _ _ P1 _ _ P2 _ => somente uma possibilidade para o terceiro.
Ou podem entrar: P1 _ _ _ _ _ P2 => tendo três possibilidades para o terceiro.
Ou também: P1_ _ P3 _ _ _ => duas possibilidades para o terceiro

O número de possibilidades é bastante menor que 7!, ao meu ver.

Eu ainda não consigo ver essa diferença pelo seguinte motivo:
Considere o caso que as quatro pessoas sentam no início separadas. Isso só é possível se tivermos a configuração [tex3]P_{a} \_ P_{b} \_ P_{c} \_ P_{d} [/tex3]
Pra essas quatro pessoas sentarem, temos [tex3]7*6*5*4[/tex3] maneiras, porque a ordem que elas sentam importa.

Ah pera, acho que entendi, as pessoas sempre entram na mesma ordem, é isso? Porque só seria 7*6*5*4 se elas pudessem entrar em qualquer ordem, mas se elas só entrarem na mesma ordem, só temos 4*3*2*1 possibilidades com as quatro primeiras pessoas que sempre entram. Agora sim, eu tinha começado a resolver antes e tinha caído num absurdo que esse caso já dava as 7! possibilidades, mas agora faz sentido. Vou tentar resolver e entender sua dúvida.

Olha, quanto a sua dúvida, eu acho melhor atacarmos o problema da maneira que eu tinha em mente: ir direto pra quatro sentados separados ou três, e pensar neles como conjuntos disjuntos. Isso vai ser melhor que colocar três pessoas e então verificar se dá pra colocar uma quarta e quais são as condições para tal. Divida direto nesses dois casos:

Primeiro: quatro pessoas se sentaram e portanto temos p_p_p_p
Pra colocar essas quatro pessoas, temos [tex3]4![/tex3] possibilidades pois é a permutação das quatro primeiras que entram. As últimas três escolherão seu lugar aleatoriamente, portanto [tex3]3![/tex3] para elas. Assim, esse caso rende [tex3]4!.3!=144[/tex3] possibilidades.

Segundo: três pessoas se sentaram, e aqui temos várias distribuições.
Não sei se você já estudou os lemas de Kaplanksy. Eles servem justamente para distribuir coisas sem que elas fiquem adjancetes. O primeiro lema cuida do caso linear com cadeiras, o segundo cuida do caso circular com mesas por exemplo (onde o último elemento deve ser visto como adjacente do primeiro). A ideia do primeiro lema é bastante simples. Considere as três pessoas que devemos colocar nas 7 cadeiras:
[tex3]n_1 /P_1/n_2/P_2/n_3/P_3/n_4[/tex3]
Entenda os P's como as pessoas sentadas e [tex3]n_a[/tex3] o número de cadeiras entre/do lado delas. Queremos necessariamente [tex3]n_2,n_3\geq 1[/tex3] para que elas estejam separadas. Além disso, [tex3]n_1+n_2+n_3+n_4=4[/tex3] , pois é o número de cadeiras restantes. Não sei quão fácil é pra você ver que o problema em questão é análogo a calcular o número de soluções de [tex3]n_1+n_2+n_3+n_4=4[/tex3] com a imposição [tex3]n_2,n_3 \geq 1[/tex3] . A restrição dada pode ser facilmente driblada impondo [tex3]n_2'=n_2+1[/tex3] e [tex3]n_3'=n_3+1[/tex3] , de modo que temos [tex3]n_1+n_2'+n_3'+n_4=2[/tex3] , com as variáveis apenas não negativas. A solução disso é dada por [tex3]C_{4+2-1}^{4-1}[/tex3] . É uma combinação de [tex3]a+b-1[/tex3] elementos tomados [tex3]a-1[/tex3] , onde a é o número de variáveis e b é o valor depois do sinal de igual. Isso dá [tex3]C_{5}^3=10[/tex3] possibilidades para as três primeiras pessoas sentarem. Mas ainda precisamos permutar elas entre si, portanto [tex3]10*3!=60[/tex3] possibilidades
Só que aqui contamos as seguintes possibilidades indesejadas:
A_A_A_ _
_ _A_A_A
A _ _ _ A_A
A_A_ _ _A
Que dão um total de 24 casos indesejados, pois temos essas 4 possibilidades vezes a permutação das pessoas entre si, então [tex3]4*3!=24[/tex3]
Esses casos são indesejados porque a quarta pessoa sempre vai sentar no espaço vazio não adjacente e vai acabar configurando o primeiro caso que já estudamos.
Então sobra [tex3]36[/tex3] casos em que estamos interessados.
As últimas quatro pessoas vão sentar aleatoriamente, então [tex3]4![/tex3] para elas. Ao todo. [tex3]36*4!=864[/tex3]

Somando as duas, [tex3]864+144=1008[/tex3]

Acho que é isso. Sou meio ruim em combinatória, então qualquer coisa mais tarde relendo direitinho eu acho algum erro. Ou se você perceber algo também, dá um toque.

EDIT: Faltou eu colocar um caso

Olá.

Fiz da seguinte forma.

Considerando o caso em que a quarta pessoa entra da sala e não encontra uma cadeira isolada:
Há 3 posições isoladas dentre as 7, então o numero de maneiras distintas em que as 7 pessoas podem sentar-se é
[tex3]C_1 = \frac{7!}{3!4!} = 35[/tex3]
Sobrando neste caso, 4 espaços não isolados, neste caso usa-se permutação para as 4 pessoas restantes: [tex3]C_2 = 4! = 24[/tex3]

Para este primeiro caso, o numero de maneiras distintas é: [tex3]C_1 \times C_2 = 35\times 24 = 840 maneiras[/tex3]

Para o caso em que a quarta pessoa entra e encontra uma vaga isolada, deve-se estar atento as repetições, pois pode haver a mesma combinação de pessoas para os dois casos.

Para o caso em que a quarta pessoa encontra uma vaga isolada: Considere a primeira vaga, há sete maneiras de 7 pessoas se sentarem. Agora considere a mesma vaga para caso onde a quarta pessoa não encontra uma posição isolada o número de maneiras para a primeira posição cai para 3 ( pois há repetição, nesta vaga (para o primeiro caso) há 7 maneiras de 7 pessoas se sentarem, e no segundo caso, apenas 3 (pois 4 já estão sentadas isoladamente)). Fazendo isso para a primeira, terceira, quinta e sétima posição temos mais 12 maneiras distintas.
Por exemplo:
A_B_C_D ->A quarta pessoa entra na sala e encontra uma vaga isolada
_A_B_C_ -> A quarta pessoa entrará e não encontrará uma vaga isolada
Na primeira posição para os dois casos
A_B_C_D -> Das combinações possíveis esta posição podem sentar as pessoas A, B, C, D, E, F, G.
_A_B_C_ -> Das combinações possíveis esta posição podem sentar apenas 3 pessoas (A,B,C ou A,E,F ... etc) , primeiro que 3 pessoas entram e sentam nas vagas isoladas, sobrando apenas 4 pessoas para entrar e assumir as vagas não isoladas, segundo que como não pode haver repetições, por exemplo, se anteriormente na primeira posição podem sentar (A, B, C, D, E, F, G) e neste caso podem sentar (A,B,C,E) então eliminando as repetições (D, F, G) 3 maneiras distintas serão adicionadas. Para este caso, a primeira, terceira, quinta e sétima posição, temos 3 + 3 + 3 + 3 = 12 maneiras distintas.

Para o caso em que a quarta pessoa não encontra uma vaga isolada: Considere a segunda posição, há 7 maneiras distintas de 7 pessoas se sentarem, mas no caso da quarta pessoa encontrar uma vaga isolada nesta mesma posição (segunda), o número de maneiras distintas cai para 4. Fazendo isso para a segunda, quarta e sexta posição temos 12 maneiras distintas.
Por exemplo:
A_B_C_D ->A quarta pessoa entra na sala e encontra uma vaga isolada
_A_B_C_ -> A quarta pessoa entrará e não encontrará uma vaga isolada
O mesmo raciocínio anterior é aplicado para a segunda, quarta e sexta posição, só que neste caso haverá 4 maneiras distintas adicionais (eliminando as repetições), 4 + 4 + 4 = 12 .

ASsim, o número de maneiras distintas é
[tex3]C = 840 + 12 + 12 = 864[/tex3]

Poderia detalhar melhor esse "Há 3 posições isoladas dentre as 7, então o numero de maneiras distintas em que as 7 pessoas podem sentar-se é [tex3]\frac{7!}{3!4!}[/tex3] "?
Acho que isso não engloba todas posições isoladas.

undefinied3 escreveu: ↑
Sex 22 Set, 2017 22:44
Poderia detalhar melhor esse "Há 3 posições isoladas dentre as 7, então o numero de maneiras distintas em que as 7 pessoas podem sentar-se é [tex3]\frac{7!}{3!4!}[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]\frac{7!}{3!4!}[/tex3]

"?
Acho que isso não engloba todas posições isoladas.

Considerei a disposição das vagas da seguinte forma; _ X _ X _ X_
Em que "X" são as vagas isoladas dado que 3 pessoas entraram na sala.
Pelo que entendi da questão, quando cada pessoa entra ela procura uma vaga isolada das demais, então o máximo de pessoas que podem entrar e ocupar todas as vagas de forma isolada umas das outras é 3. Por isso, fiz considerando esta disposição.

O
[tex3]\frac{7!}{3!4!}[/tex3] é devido as primeiras 3 pessoas entrarem e ocuparem as vagas de forma isolada. As demais ocupariam as vagas não isoladas.

Ainda não consegui enxergar totalmente a ideia da sua resolução, rippertoru. E também não vi como a minha está errada (acho que está errada pois encontrei outros gabaritos dizendoque a resposta é 864 mesmo). Minha dúvida quanto a sua resolução foi na maneira que você quebrou os casos. No post acima você disse que "x são as vagas isoladas dado que 3 pessoas entraram na sala", mas só constaram 3 X, quando deveria ter 4 ainda. Você quis dizer que X são as posições que elas sentaram?

O meu raciocínio foi notar que tem 10 possibilidades de três pessoas se sentarem nas 7 cadeiras de modo que elas não fiquem adjacentes. São elas:
PcPcccP
PcPccPc
PcPcPcc
PccPccP
PccPcPc
PcccPcP
cPccPcP
cPcPccP
cPcPcPc
ccPcPcP
Dessas 10, 4 são tais que a quarta pessoa pode se sentar também isolada (c são as cadeiras e P as pessoas). Daí, pra esses 4 casos, temos:
[tex3]4*3![/tex3] -> os 4 casos e a permutação das três pessoas
[tex3]*1[/tex3] -> a 4 pessoa senta num lugar fixo que já está determinado
[tex3]*3![/tex3] -> permutação das outras 3 pessoas que se sentaram aleatoriamente
Totallizando [tex3]4*3!*3!=144[/tex3]
Os outros 6 casos, resta só as outras quatro pessoas sentarem aleatoriamente, já que não tem mais lugar isolado. Então fica [tex3]6*3!*4!=864[/tex3] , 6 casos, 3! pra permutar os três que sentaram, 4! pra permutar os 4! que vão sentar.
Que no total daria [tex3]1008[/tex3] . Não consigo enxergar nenhuma contagem dupla que foi feita...

Eu havia chegado no mesmo raciocínio que você, undefinied3.
Também não compreendi a falha de tal método.

Olimpíadas ⇒ Análise Combinatória - OPM Tópico resolvido

Análise Combinatória - OPM

Re: Análise Combinatória - OPM

Re: Análise Combinatória - OPM

Re: Análise Combinatória - OPM

Re: Análise Combinatória - OPM

Re: Análise Combinatória - OPM

Re: Análise Combinatória - OPM

Re: Análise Combinatória - OPM

Re: Análise Combinatória - OPM

Re: Análise Combinatória - OPM

Olimpíadas ⇒ Análise Combinatória - OPM Tópico resolvido

Entrar • Registrar