Olimpíadas(China) Combinatória com Grafos Tópico resolvido

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
Out 2021 18 18:22

(China) Combinatória com Grafos

Mensagem não lida por Deleted User 23699 »

Oito cantores participam de um festival de música onde m músicas são cantadas. Cada música é cantda por 4 cantores e cada par de cantores canta junto um mesmo número de músicas. Determine o menor valor possível de m.
Resposta

14.
No livro do Rufino "Técnicas em Olimpíadas de Matemática", ele não usa grafos: prefere fazer uma solução incompreensível.
Eu gostaria de ver algo por Grafos, pois ideias semelhantes já cairam no IME.




Autor do Tópico
Deleted User 25040
6 - Doutor
Última visita: 31-12-69
Out 2021 18 19:13

Re: (China) Combinatória com Grafos

Mensagem não lida por Deleted User 25040 »

vamos contar agora o número de triplas da forma (cantor, cantor, música) onde a música é cantada pelos dois cantores
há m maneira de escolher a música e depois há 4 escolhe 2 maneiras de escolher os cantores então número de triplas é [tex3]6m[/tex3]
que é também [tex3]\binom{8}{2}x[/tex3] onde x é o número de músicas dessa frase : " cada par de cantores canta junto um mesmo número de músicas.", aqui eu escolhi os cantores primeiro e depois uma música em comum entre eles
[tex3]{8\choose 2}x=6m[/tex3]
[tex3]14x=3m[/tex3]
o menor valor de m que gera um inteiro x é m = 14 e x = 3
(agora eu não tenho certeza se preciso mostrar que existe uma configuração com tais valores, ele mostrou?)
(não usei nada de grafo mas espero que esteja mais claro do que a do livro)

Última edição: Deleted User 25040 (Ter 19 Out, 2021 12:05). Total de 3 vezes.



Autor do Tópico
Deleted User 23699
6 - Doutor
Última visita: 31-12-69
Out 2021 19 08:24

Re: (China) Combinatória com Grafos

Mensagem não lida por Deleted User 23699 »

Ficou mais claro sim.
Número de pares x Número de músicas cantadas por cada par = Número de pares em um grupo de 4 x Número de músicas

Vou marcar a solução, mas deixo aberto para alguma solução por grafo.




Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg
  • Nova mensagem (China) Polinômios
    por Deleted User 23699 » » em Olimpíadas
    0 Respostas
    614 Exibições
    Última msg por Deleted User 23699
  • Nova mensagem (China) Polinômios
    por Deleted User 23699 » » em Olimpíadas
    0 Respostas
    616 Exibições
    Última msg por Deleted User 23699
  • Nova mensagem (China) Polinômios
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    694 Exibições
    Última msg por Ittalo25
  • Nova mensagem (China) Polinômios
    por Deleted User 23699 » » em Olimpíadas
    1 Respostas
    690 Exibições
    Última msg por Ittalo25
  • Nova mensagem (China) Funções compostas
    por SkyWalker17 » » em Ensino Superior
    1 Respostas
    561 Exibições
    Última msg por Gaussiano

Voltar para “Olimpíadas”