Ensino MédioAnálise combinatória Rufino Tópico resolvido

Problemas sobre assuntos estudados no Ensino Médio devem ser postados aqui. Se o problema for de Vestibular, poste-o no fórum Pré-Vestibular

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
robsonslf
iniciante
Mensagens: 3
Registrado em: Seg 17 Jun, 2019 10:17
Última visita: 02-08-19
Jun 2019 17 10:27

Análise combinatória Rufino

Mensagem não lida por robsonslf »

Determine o número de maneiras de escolher 5 números dentre os primeiros 18 inteiros positivos de modo que a mínima diferença entre quaisquer dois números escolhidos seja 2.
Resposta

C14,5 = 2002




Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 5112
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 22-01-22
Jun 2019 17 15:22

Re: Análise combinatória Rufino

Mensagem não lida por csmarcelo »

Não faço ideia de como chegar na fórmula que leva ao gabarito, mas resolvi de outra forma.

A ideia é, ao invés de nos importarmos com os números escolhidos, darmos atenção aos espaços na lista de números (quantidade de números entre os escolhidos) resultantes dessas escolhas.

Com isso em mente, basta trabalharmos a fórmula que calcula o número de soluções inteiras e não-negativas de uma equação linear.

Esse trabalho envolve três casos:

1) Existem 4 espaços na lista

[tex3]\underline{n_1}\ \underbrace{\underline{}\ \underline{}\ \underline{}}_{a+1}\ \underline{n_2}\ \underbrace{\underline{}}_{b+1}\ \underline{n_3}\ \underbrace{\underline{}\ \underline{}\ \underline{}\ \underline{}\ \underline{}\ \underline{}}_{c+1}\ \underline{n_4}\ \underbrace{\underline{}\ \underline{}\ \underline{}}_{d+1}\ \underline{n_5}[/tex3]

Na ilustração acima, as posições de [tex3]n_1[/tex3] e [tex3]n_5[/tex3] são fixas, ou seja [tex3]n_1=1[/tex3] e [tex3]n_5=18[/tex3] , enquanto as dos demais são arbitrárias, apenas respeitando a diferença mínima.

[tex3]a+1[/tex3] significa a quantidade de números entre [tex3]n_1[/tex3] e [tex3]n_2[/tex3] e, de forma análoga, o mesmo raciocínio vale para as demais expressões.

Temos que [tex3]a+1+b+1+c+1+d+1=13[/tex3] e, portanto [tex3]a+b+c+d=9[/tex3] .

O número de soluções inteiras e não-negativas dessa equação é [tex3]C^{9+4-1}_9=220[/tex3] .

2) Existem 5 espaços na lista

[tex3]\underbrace{\underline{}}_{a+1}\ \underline{n_1}\ \underbrace{\underline{}\ \underline{}\ \underline{}}_{b+1}\ \underline{n_2}\ \underbrace{\underline{}}_{c+1}\ \underline{n_3}\ \underbrace{\underline{}\ \underline{}\ \underline{}\ \underline{}\ \underline{}}_{d+1}\ \underline{n_4}\ \underbrace{\underline{}\ \underline{}\ \underline{}}_{e+1}\ \underline{n_5}[/tex3]

Na ilustração acima, a posição de [tex3]n_5[/tex3] é fixas, enquanto as dos demais são arbitrárias, apenas respeitando a diferença mínima e o espaço minimo de uma casa antes de [tex3]n_1[/tex3] .

Temos que [tex3]a+1+b+1+c+1+d+1+e+1=13[/tex3] e, portanto [tex3]a+b+c+d+e=8[/tex3] .

O número de soluções inteiras e não-negativas dessa equação é [tex3]C^{8+5-1}_8=495[/tex3] .

Repare, no entanto, que temos uma variação desse caso, que é quando [tex3]n_1[/tex3] é fixo no início da lista e existe um espaço de pelo menos uma casa depois de [tex3]n_5[/tex3] .

Logo, no total, temos que [tex3]2\cdot495=990[/tex3] soluções.

3) Existem 6 espaços na lista

[tex3]\underbrace{\underline{}}_{a+1}\ \underline{n_1}\ \underbrace{\underline{}\ \underline{}\ \underline{}}_{b+1}\ \underline{n_2}\ \underbrace{\underline{}}_{c+1}\ \underline{n_3}\ \underbrace{\underline{}\ \underline{}\ \underline{}}_{d+1}\ \underline{n_4}\ \underbrace{\underline{}\ \underline{}\ \underline{}}_{e+1}\ \underline{n_5}\ \underbrace{\underline{}\ \underline{}}_{f+1}[/tex3]

Aqui, todas as posições são arbitrárias, apenas respeitando a diferença mínima e o espaço minimo de uma casa antes de [tex3]n_1[/tex3] e de depois de [tex3]n_5[/tex3] .

Temos que [tex3]a+1+b+1+c+1+d+1+e+1+f+1=13[/tex3] e, portanto [tex3]a+b+c+d+e+f=7[/tex3] .

O número de soluções inteiras e não-negativas dessa equação é [tex3]C^{7+6-1}_7=792[/tex3] .

Somando todos os casos, chegamos nas 2002 maneiras de escolher os 5 números de acordo com o enunciado.

Última edição: csmarcelo (Seg 17 Jun, 2019 15:30). Total de 2 vezes.



Avatar do usuário
MateusQqMD
5 - Mestre
Mensagens: 2687
Registrado em: Qui 16 Ago, 2018 19:15
Última visita: 17-01-22
Localização: Fortaleza
Jun 2019 17 15:25

Re: Análise combinatória Rufino

Mensagem não lida por MateusQqMD »

Eu não consigo interpretar esse problema. Para mim, em qualquer conjunto com cinco números sempre haverá diferença diferente de dois. Mais tarde leio sua solução, Marcelo.


"Make us to choose the harder right instead of the easier wrong and never to be content with a half truth when the whole truth can be won."

Avatar do usuário
Autor do Tópico
robsonslf
iniciante
Mensagens: 3
Registrado em: Seg 17 Jun, 2019 10:17
Última visita: 02-08-19
Jun 2019 17 15:59

Re: Análise combinatória Rufino

Mensagem não lida por robsonslf »

Ótima solução, gostei dessa ideia de aplicar isso de encontrar as soluções inteiras em cada caso. Obrigado.



Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 5112
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 22-01-22
Jun 2019 18 08:28

Re: Análise combinatória Rufino

Mensagem não lida por csmarcelo »

MateusQqMD, acho que você interpretou como sendo suficiente que apenas um par qualquer dos números escolhidos possua módulo da diferença maior ou igual a 2, quando, na verdade, isso deve ser verdadeiro para todos os possíveis pares.



Avatar do usuário
MateusQqMD
5 - Mestre
Mensagens: 2687
Registrado em: Qui 16 Ago, 2018 19:15
Última visita: 17-01-22
Localização: Fortaleza
Jun 2019 18 12:36

Re: Análise combinatória Rufino

Mensagem não lida por MateusQqMD »

Ahhh, agr entendi melhor. A diferença não tem que ser dois, mas no mínimo dois. Valeu!


"Make us to choose the harder right instead of the easier wrong and never to be content with a half truth when the whole truth can be won."

Avatar do usuário
MateusQqMD
5 - Mestre
Mensagens: 2687
Registrado em: Qui 16 Ago, 2018 19:15
Última visita: 17-01-22
Localização: Fortaleza
Jul 2019 08 10:48

Re: Análise combinatória Rufino

Mensagem não lida por MateusQqMD »

Outra solução:

Pelo Primeiro Lema de Kaplansky, podemos escolher [tex3]5[/tex3] números dentre os primeiros [tex3]18[/tex3] inteiros positivos sem que haja números consecutivos de [tex3]f(18,5) = C_{18-5+1}^5 = 2002[/tex3] modos.


"Make us to choose the harder right instead of the easier wrong and never to be content with a half truth when the whole truth can be won."

Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 5112
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 22-01-22
Jul 2019 08 10:59

Re: Análise combinatória Rufino

Mensagem não lida por csmarcelo »

Muito doido que seja semelhante à fórmula do número de soluções inteiras e não-negativas.

E a matemática é cheia dessas semelhanças e coincidências "bizarras".



Avatar do usuário
csmarcelo
6 - Doutor
Mensagens: 5112
Registrado em: Sex 22 Jun, 2012 22:03
Última visita: 22-01-22
Jul 2019 08 11:05

Re: Análise combinatória Rufino

Mensagem não lida por csmarcelo »

Não sei como não pensei nisso... basta uma pequena mudança no caso 3. E eu já resolvi tantos exercícios nesses moldes... :?
Última edição: csmarcelo (Seg 08 Jul, 2019 11:09). Total de 1 vez.



Avatar do usuário
MateusQqMD
5 - Mestre
Mensagens: 2687
Registrado em: Qui 16 Ago, 2018 19:15
Última visita: 17-01-22
Localização: Fortaleza
Jul 2019 08 11:18

Re: Análise combinatória Rufino

Mensagem não lida por MateusQqMD »

Pois é. Eu acabei abrindo um livro de combinatória hj e sem querer apareceu isso na minha frente. Qnd li lembrei dessa questão hahaa

Eu prefiro que você marque como solução sua resposta. Até pq ela foi colocada primeiro.



"Make us to choose the harder right instead of the easier wrong and never to be content with a half truth when the whole truth can be won."

Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg
  • Nova mensagem Análise Combinatória (Rufino)
    por Hollo » » em Ensino Médio
    5 Respostas
    151 Exibições
    Última msg por csmarcelo
  • Nova mensagem Combinatória (Rufino)
    por Zhadnyy » » em IME / ITA
    2 Respostas
    595 Exibições
    Última msg por MateusQqMD
  • Nova mensagem Combinatória (Rufino)
    por Zhadnyy » » em IME / ITA
    3 Respostas
    779 Exibições
    Última msg por Zhadnyy
  • Nova mensagem (Rufino) Combinatória
    por Zhadnyy » » em Ensino Médio
    1 Respostas
    349 Exibições
    Última msg por A13235378
  • Nova mensagem (Rufino) Combinatória
    por Zhadnyy » » em Ensino Médio
    1 Respostas
    344 Exibições
    Última msg por A13235378

Voltar para “Ensino Médio”