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

[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.

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]6m[/tex3]

que é também [tex3]\binom{8}{2}x[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[tex3]{8\choose 2}x=6m[/tex3]

[tex3]14x=3m[/tex3]

Código: Selecionar tudoSHIFT+Click na eq = ZOOM

[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)

[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.