Olimpíadas ⇒ (INMO) Combinatória
Moderador: [ Moderadores TTB ]
-
- Última visita: 31-12-69
Nov 2021
04
15:50
(INMO) Combinatória
Mostre que o número de subconjuntos de 3 elementos {a, b, c} de {1, 2, ... 63} com a+b+c < 95 é menor do que o número com a+b+c > 95
-
- Mensagens: 408
- Registrado em: Qua 18 Nov, 2009 20:24
- Última visita: 15-08-22
Nov 2021
05
08:36
Re: (INMO) Combinatória
Vamos fazer uma tentativa de justificativa aqui.
A menor soma é do subconjunto {1,2,3}, que vale 6, e a maior soma é do subconjunto {61,62,63}, que vale 186.
Ou seja, todos os valores entre 6 e 186 serão somas possíveis de 1 ou mais subconjuntos.
Mas podemos relacionar sempre um subconjunto de soma pequena com um subconjunto de soma grande:
Digamos que a+b+c = x. Podemos pegar os valores (64-a,64-b,64-c), cuja soma será 192-(a+b+c) = 192-x.
Para toda soma x, temos uma soma 192-x de valores "espelhados", ou seja, se existem [tex3]N_x[/tex3] subconjuntos cuja soma é x, temos certeza de que existem exatamente [tex3]N_x[/tex3] subconjuntos cuja soma será 192-x.
Se quiser tabelar
Soma/ [tex3]N_x[/tex3]
6 / [tex3]N_6[/tex3]
7 / [tex3]N_7[/tex3]
8 / [tex3]N_8[/tex3]
...
94 / [tex3]N_{94}[/tex3]
95 / [tex3]N_{95}[/tex3]
96 / [tex3]N_{96}[/tex3]
97 / [tex3]N_{97}=N_{95}[/tex3]
98 / [tex3]N_{98}=N_{94}[/tex3]
...
184 / [tex3]N_{186}=N_8[/tex3]
185 / [tex3]N_{187}=N_7[/tex3]
186 / [tex3]N_{186}=N_6[/tex3]
Ou seja, da soma 6 até a soma 94, temos sempre um correspondente indo da soma 186 até a soma 98. O subconjunto de soma 95 tem a mesma quantidade de trios que o subconjunto de soma 97 e o subconjunto de soma 96 é o único que não tem correspondente, ele é o próprio correspondente.
Isso significa que existem [tex3]N_{96}+N_{97}[/tex3] subconjuntos com soma maior que 95 a mais do que subconjuntos com soma menor que 95.
A menor soma é do subconjunto {1,2,3}, que vale 6, e a maior soma é do subconjunto {61,62,63}, que vale 186.
Ou seja, todos os valores entre 6 e 186 serão somas possíveis de 1 ou mais subconjuntos.
Mas podemos relacionar sempre um subconjunto de soma pequena com um subconjunto de soma grande:
Digamos que a+b+c = x. Podemos pegar os valores (64-a,64-b,64-c), cuja soma será 192-(a+b+c) = 192-x.
Para toda soma x, temos uma soma 192-x de valores "espelhados", ou seja, se existem [tex3]N_x[/tex3] subconjuntos cuja soma é x, temos certeza de que existem exatamente [tex3]N_x[/tex3] subconjuntos cuja soma será 192-x.
Se quiser tabelar
Soma/ [tex3]N_x[/tex3]
6 / [tex3]N_6[/tex3]
7 / [tex3]N_7[/tex3]
8 / [tex3]N_8[/tex3]
...
94 / [tex3]N_{94}[/tex3]
95 / [tex3]N_{95}[/tex3]
96 / [tex3]N_{96}[/tex3]
97 / [tex3]N_{97}=N_{95}[/tex3]
98 / [tex3]N_{98}=N_{94}[/tex3]
...
184 / [tex3]N_{186}=N_8[/tex3]
185 / [tex3]N_{187}=N_7[/tex3]
186 / [tex3]N_{186}=N_6[/tex3]
Ou seja, da soma 6 até a soma 94, temos sempre um correspondente indo da soma 186 até a soma 98. O subconjunto de soma 95 tem a mesma quantidade de trios que o subconjunto de soma 97 e o subconjunto de soma 96 é o único que não tem correspondente, ele é o próprio correspondente.
Isso significa que existem [tex3]N_{96}+N_{97}[/tex3] subconjuntos com soma maior que 95 a mais do que subconjuntos com soma menor que 95.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 0 Respostas
- 159 Exibições
-
Última msg por paiva
-
- 0 Respostas
- 564 Exibições
-
Última msg por paiva
-
- 1 Respostas
- 2089 Exibições
-
Última msg por Fibonacci13
-
- 0 Respostas
- 333 Exibições
-
Última msg por Gabi123