.Problema de Gincana: Provas para uma gincana

Problema

---

A Equipe responsável pela Gincana dos Clubes elaborou três provas, cada uma delas composta por 10 atividades diferentes.
Se cada prova deve conter exatamente sete atividades que não aparecem em nenhuma das outras duas provas, qual o número máximo de atividades distintas que poderiam ter sido utilizadas na Gincana?

Solução

---

Como cada prova deve conter exatamente [tex]7[/tex] atividades que não aparecem em nenhuma das outras, então foram utilizadas [tex]7\times3=21[/tex] atividades únicas.
Para completar as 30 atividades, foram necessárias 9 atividades. Cada uma destas foi utilizada, pelo menos, em duas provas, uma vez que as atividades únicas já foram contadas.
Se para a primeira prova foram utilizadas [tex]3[/tex] atividades adicionais, [tex]E_1, \, E_2, \, E_3[/tex], então essa prova ficou com a seguinte configuração:
PROVA 1: [tex]A_1 \, \, \, A_2 \, \, \, A_3 \, \, \, A_4 \, \, \, A_5 \, \, \, A_6 \, \, \, A_7 \, \, \, E_1 \, \, \, E_2 \, \, \, E_3[/tex].
As atividades [tex]E_1, \, E_2, \, E_3[/tex] não são únicas e, portanto, devem ser utilizadas em, pelo menos, mais uma prova prova. Como queremos prever o número máximo de atividades que poderiam ter sido utilizadas na Gincana, vamos supor, sem perda de generalidade, que a prova 2 contém E1 e E2 e uma quarta atividade adicional: E4. Com isso, passaríamos a ter a seguinte situação:
PROVA 1: [tex]E_1 \, \, \, E_2 \, \, \, E_3[/tex];
PROVA 2: [tex]E_1 \, \, \, E_2 \, \, \, E_4[/tex].
Mas [tex]E_3[/tex] e [tex]E_4[/tex] não poderiam ser utilizadas apenas uma vez; logo, necessariamente, essas atividades deveriam ser utilizadas na terceira prova e, assim, passaríamos a ter a seguinte situação com relação às nove atividades adicionais:
PROVA 1: [tex]E_1 \, \, \, E_2 \, \, \, E_3[/tex];
PROVA 2: [tex]E_1 \, \, \, E_2 \, \, \, E_4[/tex];
PROVA 3: [tex]E_3 \, \, \, E_4 \, \, \, ?[/tex].
Poderíamos ter uma quinta atividade adicional?
A resposta é não, pois se tivéssemos uma quinta atividade, digamos [tex]E_5[/tex], então [tex]E_5[/tex] deveria ser utilizada em mais uma prova. Mas isso é impossível já que as adicionais [tex]E_1, \, E_2, \, E_3, \, E_4[/tex] não podem ser substituídas por [tex]E_5[/tex] sob pena de serem utilizadas uma única vez.
Assim, deve haver no máximo 4 atividades adicionais para a composição das três provas e, portanto, a terceira questão adicional da prova 3 poderá ser ou [tex]E_1[/tex] ou [tex]E_2[/tex].
Dessa forma, poderão ser utilizadas, no máximo, [tex]21+4=25[/tex] atividades na Gincana.
Vejamos uma possível distribuição dessas [tex]25[/tex] atividades:
PROVA 1: [tex]A_1 \, \, \, A_2 \, \, \, A_3 \, \, \, A_4 \, \, \, A_5 \, \, \, A_6 \, \, \, A_7 \, \, \, E_1 \, \, \, E_2 \, \, \, E_3[/tex];
PROVA 2: [tex]B_1 \, \, \, B_2 \, \, \, B_3 \, \, \, B_4 \, \, \, B_5 \, \, \, B_6 \, \, \, B_7 \, \, \, E_1 \, \, \, E_2 \, \, \, E_4[/tex];
PROVA 3: [tex]C_1 \, \, \, C_2 \, \, \, C_3 \, \, \, C_4 \, \, \, C_5 \, \, \, C_6 \, \, \, C_7 \, \, \, E_1 \, \, \, E_3 \, \, \, E_4[/tex].

---

Solução elaborada pelos Moderadores do Blog.