Olimpíadas(INMO) Combinatória

Aqui devem ser postados problemas Olímpicos. Informe a olimpíada e o ano no título do tópico. Exemplo: (OBM - 2008).

Moderador: [ Moderadores TTB ]

Autor do Tópico
Deleted User 23699
6 - Doutor
Última visita: 31-12-69
Nov 2021 04 15:50

(INMO) Combinatória

Mensagem não lida por Deleted User 23699 »

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




Avatar do usuário
AlexandreHDK
3 - Destaque
Mensagens: 408
Registrado em: Qua 18 Nov, 2009 20:24
Última visita: 15-08-22
Nov 2021 05 08:36

Re: (INMO) Combinatória

Mensagem não lida por AlexandreHDK »

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.




Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Olimpíadas”