1. Em um torneio no qual cada participante enfrenta todos os demais uma única vez, são jogadas 780 partidas. Quantos são os participantes?
  2. Sejam I_{m}=\{1,2, \ldots, m\} e I_{n}=\{1,2, \ldots, n\}, \operatorname{com} m \leqslant n. Quantas são as funções f: I_{m} \rightarrow I_{n} estritamente crescentes?
  3. Um homem tem 5 amigas e 7 amigos. Sua esposa tem 7 amigas e 5 amigos. De quantos modos eles podem convidar 6 amigas e 6 amigos, se cada um deve convidar 6 pessoas?

Passo 1

Vou rescrever claramente o que cada item pede e quais dados são fornecidos, para não nos perder no enunciado.
  • Item 6: Em um torneio em que cada participante enfrenta todos os outros exatamente uma vez, foram jogadas 780 partidas. Pergunta: quantos participantes havia no torneio?
  • Item 7: Definem-se I_{m}=\{1,2,\ldots,m\} e I_{n}=\{1,2,\ldots,n\} com m\le n. Pergunta: quantas são as funções f:I_{m}\to I_{n} que são estritamente crescentes?
  • Item 8: O homem tem 5 amigas e 7 amigos. A esposa tem 7 amigas e 5 amigos. Eles vão convidar, juntos, 6 amigas e 6 amigos, e cada um (o homem e a esposa) deve convidar exatamente 6 pessoas (cada convite é feito só entre as amizades próprias). Pergunta: de quantos modos isso pode ser feito?
    Observação importante (assumida aqui porque o enunciado não contradiz): as listas de amigos da mulher e do homem são pessoas distintas (não há interseção entre as listas), e a ordem dos convidados não importa (conta-se apenas quem foi convidado).

Passo 2

Resolver o item 6 — entendimento do modelo combinatório e fórmula básica.
  • Em um torneio onde cada par de participantes joga exatamente uma partida, cada partida corresponde a um par não ordenado de participantes. O número total de partidas é, portanto, o número de maneiras de escolher 2 participantes dentre n.
  • A fórmula para o número de pares (combinações de 2) de um conjunto com n elementos é
\binom{n}{2}=\frac{n(n-1)}{2}.
  • O enunciado diz que esse número é 780, então temos a equação
\frac{n(n-1)}{2}=780.
Nosso objetivo é resolver essa equação para n.

Passo 3

Resolver a equação do item 6 passo a passo (álgebra elementar).
  • Multiplico ambos os lados por 2 para eliminar o denominador:
n(n-1)=1560.
  • Desenvolvendo, obtemos a equação quadrática
n^{2}-n-1560=0.
  • Para resolver uma quadrática n^{2}-n-1560=0 uso a fórmula de Bhaskara (fórmula quadrática). O discriminante é
\Delta = (-1)^{2}-4\cdot 1\cdot(-1560)=1+6240=6241.
  • Calculo a raiz quadrada de \Delta. Observando números, 79^{2}=6241, então \sqrt{\Delta}=79.
  • As raízes são
n=\frac{1\pm 79}{2}.
  • A raiz negativa \frac{1-79}{2}=-39 não faz sentido para número de participantes. Assim, tomo
n=\frac{1+79}{2}=\frac{80}{2}=40.
  • Conclusão: havia 40 participantes.

Passo 4

Resolver o item 7 — ideia combinatória por trás de funções estritamente crescentes.
  • Uma função f:I_{m}\to I_{n} é estritamente crescente quando, sempre que i<j em I_{m}, temos f(i)<f(j) em I_{n}.
  • Isso implica que os valores \{f(1),f(2),\ldots,f(m)\} são m elementos distintos de I_{n} e, além disso, a ordem desses valores é determinada (ordenados em ordem crescente devem corresponder a f(1),f(2),\ldots,f(m)).
  • Portanto, dar uma função estritamente crescente é o mesmo que escolher um subconjunto de m elementos de I_{n}; depois de escolhido o subconjunto, não há liberdade adicional: ordenar esse subconjunto em ordem crescente dá os valores f(1),\ldots,f(m).
  • O número de formas de escolher m elementos de um conjunto com n elementos é o coeficiente binomial
\binom{n}{m}.
  • Logo, o número de funções estritamente crescentes f:I_{m}\to I_{n} é \binom{n}{m}.

Passo 5

Dar um pequeno exemplo ilustrativo para fixar a ideia do item 7 (pra tornar didático).
  • Ex.: se m=2 e n=4, então I_{2}=\{1,2\} e I_{4}=\{1,2,3,4\}. As funções estritamente crescentes correspondem a escolher 2 valores distintos e ordenados para f(1)<f(2). As escolhas possíveis de conjunto de imagem são \{1,2\},\{1,3\},\{1,4\},\{2,3\},\{2,4\},\{3,4\}, ou seja \binom{4}{2}=6 possibilidades. Isso coincide com a enumeração direta.

Passo 6

Resolver o item 8 — modelagem por casos e regra do produto.
  • Cada um (homem e esposa) deve convidar exatamente 6 pessoas das suas respectivas listas. O homem tem 5 amigas (mulheres) e 7 amigos (homens). A esposa tem 7 amigas e 5 amigos.
  • Queremos que, no total (somando convites do homem e da esposa), sejam convidados 6 amigas e 6 amigos.
  • Denotemos por a o número de amigas que o homem convida. Então o homem convida a mulheres e 6-a homens (pois convida 6 pessoas no total). A esposa, então, deve convidar 6-a mulheres (porque o total de mulheres convidadas deve ser 6) e, portanto, 6-(6-a)=a homens.
  • Restrições de disponibilidade: a deve satisfazer 0\le a\le 5 (pois o homem tem só 5 amigas) e a esposa precisa convidar 6-a mulheres, com 0\le 6-a\le 7 (o que dá -1\le a\le 6, trivialmente satisfeito para a=0,\dots,5). Portanto a pode ser 0,1,2,3,4,5 (se a=6 o homem precisaria convidar 6 amigas mas ele só tem 5).
  • Para um valor fixo de a, calculamos o número de maneiras multiplicando escolhas independentes:
    • O homem escolhe a amigas dentre 5: \binom{5}{a}.
    • O homem escolhe 6-a amigos dentre 7: \binom{7}{6-a}.
    • A esposa escolhe 6-a amigas dentre 7: \binom{7}{6-a}.
    • A esposa escolhe a amigos dentre 5: \binom{5}{a}.
  • Pela regra do produto, para esse a fixo o número de formas é
\binom{5}{a}\binom{7}{6-a}\binom{7}{6-a}\binom{5}{a}=\biggl[\binom{5}{a}\biggr]^{2}\biggl[\binom{7}{6-a}\biggr]^{2}.
  • Como a pode variar pelos valores 0,1,2,3,4,5, somamos sobre esses casos (princípio da soma) para obter o total:
\text{Total}=\sum_{a=0}^{5}\biggl[\binom{5}{a}\biggr]^{2}\biggl[\binom{7}{6-a}\biggr]^{2}.

Passo 7

Calcular explicitamente a soma do item 8, mostrando as combinações e produtos.
  • Primeiro, anoto os coeficientes binomiais relevantes:
    • \binom{5}{0}=1,\\ \binom{5}{1}=5,\\ \binom{5}{2}=10,\\ \binom{5}{3}=10,\\ \binom{5}{4}=5,\\ \binom{5}{5}=1.
    • Para \binom{7}{6-a}, quando a=0,1,2,3,4,5 temos respectivamente:
      • a=0:\\ \binom{7}{6}=7
      • a=1:\\ \binom{7}{5}=21
      • a=2:\\ \binom{7}{4}=35
      • a=3:\\ \binom{7}{3}=35
      • a=4:\\ \binom{7}{2}=21
      • a=5:\\ \binom{7}{1}=7
  • Agora calculo cada termo \bigl[\binom{5}{a}\bigr]^{2}\bigl[\binom{7}{6-a}\bigr]^{2}:
    • a=0:\\ (1)^{2}\cdot(7)^{2}=49.
    • a=1:\\ (5)^{2}\cdot(21)^{2}=25\cdot441=11025.
    • a=2:\\ (10)^{2}\cdot(35)^{2}=100\cdot1225=122500.
    • a=3:\\ (10)^{2}\cdot(35)^{2}=122500 (mesmo que a=2).
    • a=4:\\ (5)^{2}\cdot(21)^{2}=11025 (mesmo que a=1).
    • a=5:\\ (1)^{2}\cdot(7)^{2}=49 (mesmo que a=0).

Passo 8

Somar os termos do item 8 e concluir.
  • Somando:
49+11025+122500+122500+11025+49.
  • Agrupando termos iguais: 49+49=98, 11025+11025=22050, 122500+122500=245000.
  • Soma total 98+22050+245000=267148.
  • Portanto, existem 267148 modos de convidar 6 amigas e 6 amigos, com cada pessoa convidando 6 pessoas das suas listas (e assumindo listas distintas).

Resposta

40
\displaystyle \binom{n}{m}
267148

Exercícios relacionados