C14,5 = 2002
Ensino Médio ⇒ Análise combinatória Rufino Tópico resolvido
Moderador: [ Moderadores TTB ]
Jun 2019
17
10:27
Análise combinatória Rufino
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.
C14,5 = 2002
Resposta
C14,5 = 2002
Jun 2019
17
15:22
Re: Análise combinatória Rufino
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.
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.
-
- Mensagens: 2693
- Registrado em: Qui 16 Ago, 2018 19:15
- Última visita: 21-02-24
- Localização: Fortaleza/CE
Jun 2019
17
15:25
Re: Análise combinatória Rufino
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.
"Como sou pouco e sei pouco, faço o pouco que me cabe me dando por inteiro."
Jun 2019
17
15:59
Re: Análise combinatória Rufino
Ótima solução, gostei dessa ideia de aplicar isso de encontrar as soluções inteiras em cada caso. Obrigado.
Jun 2019
18
08:28
Re: Análise combinatória Rufino
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.
-
- Mensagens: 2693
- Registrado em: Qui 16 Ago, 2018 19:15
- Última visita: 21-02-24
- Localização: Fortaleza/CE
Jun 2019
18
12:36
Re: Análise combinatória Rufino
Ahhh, agr entendi melhor. A diferença não tem que ser dois, mas no mínimo dois. Valeu!
"Como sou pouco e sei pouco, faço o pouco que me cabe me dando por inteiro."
-
- Mensagens: 2693
- Registrado em: Qui 16 Ago, 2018 19:15
- Última visita: 21-02-24
- Localização: Fortaleza/CE
Jul 2019
08
10:48
Re: Análise combinatória Rufino
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.
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.
"Como sou pouco e sei pouco, faço o pouco que me cabe me dando por inteiro."
Jul 2019
08
10:59
Re: Análise combinatória Rufino
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".
E a matemática é cheia dessas semelhanças e coincidências "bizarras".
Jul 2019
08
11:05
Re: Análise combinatória Rufino
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.
-
- Mensagens: 2693
- Registrado em: Qui 16 Ago, 2018 19:15
- Última visita: 21-02-24
- Localização: Fortaleza/CE
Jul 2019
08
11:18
Re: Análise combinatória Rufino
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.
Eu prefiro que você marque como solução sua resposta. Até pq ela foi colocada primeiro.
"Como sou pouco e sei pouco, faço o pouco que me cabe me dando por inteiro."
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg