(Competição de Matemática Harvery Mudd do Caltech inverno de 2022 - adaptada) O maior divisor primo da expressão \sum_{n=3}^{30}\left(\begin{array}{c}n \\\\ 3 \\\\ 2\end{array}\right) é igual a:
a) 29
b) 31
c) 173
d) 383
e) 431

Passo 1

O enunciado pede: determinar o maior divisor primo da soma
\sum_{n=3}^{30}\left(\begin{array}{c}n \\\\ 3 \\\\ 2\end{array}\right).
Informações dadas e interpretações que vou usar (sem pedir nada a mais):
  • A notação \left(\begin{array}{c}n \\\\ 3 \\\\ 2\end{array}\right) será interpretada como o binomial aninhado \displaystyle \binom{\binom{n}{3}}{2}, ou seja, escolher 2 entre as \binom{n}{3} tripletas distintas. (Essa interpretação é natural para essa notação.)
  • O somatório vai de n=3 até n=30.
  • A tarefa final é escolher, entre as alternativas dadas, qual é o maior primo que divide essa soma.

Passo 2

Vamos compreender \displaystyle \binom{\binom{n}{3}}{2} de uma forma combinatória mais explícita: é o número de pares não-ordenados de subconjuntos de tamanho 3 de um conjunto com n elementos. Vou contar esses pares segundo o tamanho da interseção das duas triplas (isso ajuda a expressar a quantidade em termos simples).
Casos possíveis para duas triplas distintas A,B\subseteq\{1,\dots,n\} com |A|=|B|=3:
  • Interseção de tamanho 2 (as triplas compartilham exatamente dois elementos). Contagem: escolher os 2 elementos comuns: \displaystyle \binom{n}{2}. Escolher os dois elementos restantes (um para cada triple) entre os n-2 restantes, como um par não-ordenado: \displaystyle \binom{n-2}{2}. Logo número de pares com interseção 2 é \binom{n}{2}\binom{n-2}{2}.
  • Interseção de tamanho 1. Contagem: escolher o elemento comum: \displaystyle \binom{n}{1}=n. Escolher os outros 4 elementos distintos que completarão as duas triplas entre os n-1 restantes: \displaystyle \binom{n-1}{4}. Depois, desses 4 elementos temos que dividi-los em dois pares (cada par se junta ao elemento comum para formar uma triple); o número de partições de 4 elementos em dois pares não-ordenados é 3. Logo o total para interseção 1 é 3n\binom{n-1}{4}.
  • Interseção de tamanho 0 (as triplas são disjuntas). Contagem: escolher 6 elementos que formarão a união: \displaystyle \binom{n}{6}. Particioná-los em dois subconjuntos de tamanho 3 sem ordem entre os dois conjuntos: \dfrac{1}{2}\binom{6}{3}=10. Logo 10\binom{n}{6}.
Somando os três casos obtemos a identidade combinatória (válida para todo n):
\binom{\binom{n}{3}}{2}= \binom{n}{2}\binom{n-2}{2} + 3n\binom{n-1}{4} + 10\binom{n}{6}.

Passo 3

Agora vou simplificar cada termo em combinações padrão \binom{n}{k}.
  1. Para o primeiro termo:
\binom{n}{2}\binom{n-2}{2} = \frac{n(n-1)(n-2)(n-3)}{4} =6\binom{n}{4},
porque \displaystyle \binom{n}{4}=\frac{n(n-1)(n-2)(n-3)}{24} e 24/4=6.
  1. Para o segundo termo note que \displaystyle \binom{n}{5}=\frac{n}{5}\binom{n-1}{4}. Então
3n\binom{n-1}{4}=3n\cdot\frac{5}{n}\binom{n}{5}=15\binom{n}{5}.
  1. O terceiro termo já está em forma de binomial:
10\binom{n}{6}.
Portanto obtemos a expressão limpa
\binom{\binom{n}{3}}{2}=6\binom{n}{4}+15\binom{n}{5}+10\binom{n}{6}.

Passo 4

Agora somamos para n=3 até 30:
S=\sum_{n=3}^{30}\binom{\binom{n}{3}}{2} =6\sum_{n=3}^{30}\binom{n}{4}+15\sum_{n=3}^{30}\binom{n}{5}+10\sum_{n=3}^{30}\binom{n}{6}.
Uso a identidade do “bastão de hóquei” (hockey-stick): para inteiros r e N\ge r,
\sum_{n=r}^{N}\binom{n}{r}=\binom{N+1}{r+1}.
Aplicando com N=30:
\sum_{n=3}^{30}\binom{n}{4}=\binom{31}{5},\qquad \sum_{n=3}^{30}\binom{n}{5}=\binom{31}{6},\qquad \sum_{n=3}^{30}\binom{n}{6}=\binom{31}{7}.
Logo
S=6\binom{31}{5}+15\binom{31}{6}+10\binom{31}{7}.

Passo 5

Calculo numérico dos binomiais (passo a passo, sem pular etapas):
  1. \displaystyle \binom{31}{5}=\frac{31\cdot30\cdot29\cdot28\cdot27}{5!}=\frac{31\cdot30\cdot29\cdot28\cdot27}{120}=169911.
  2. \displaystyle \binom{31}{6}=\binom{31}{5}\cdot\frac{31-5}{6}=169911\cdot\frac{26}{6}=169911\cdot\frac{13}{3}=736281. (Aqui usei que 169911 é divisível por 3.)
  3. \displaystyle \binom{31}{7}=\binom{31}{6}\cdot\frac{31-6}{7}=736281\cdot\frac{25}{7}=2629575.
Agora multiplico pelos coeficientes:
6\binom{31}{5}=6\cdot169911=1019466,
15\binom{31}{6}=15\cdot736281=11044215,
10\binom{31}{7}=10\cdot2629575=26295750.
Somando:
S=1019466+11044215+26295750=38359431.

Passo 6

Agora fatoro S para identificar seus fatores primos relevantes. Primeiro observo uma propriedade prática sobre binomiais com número primo p=31: para 1\le k\le p-1 vale \displaystyle \binom{p}{k}\equiv 0\pmod p. Em particular \binom{31}{5},\binom{31}{6},\binom{31}{7} são múltiplos de 31. Assim S é múltiplo de 31.
Dividindo:
\frac{S}{31}=\frac{38359431}{31}=1237401.
Agora fatoro 1237401. Testando divisibilidade por 431 (uma das opções):
431\cdot 2871 = 431\cdot(2000+800+70+1)=862000+344800+30170+431=1237401,
portanto 1237401=431\cdot2871. Logo
S=31\cdot431\cdot2871.
Por fim fatoro 2871:
2871=3\cdot957=3\cdot3\cdot319=9\cdot319=9\cdot 11\cdot29.
Logo fatoração completa (com os primos encontrados) é
S=31\cdot431\cdot3^2\cdot11\cdot29.

Passo 7

Conclusão sobre o maior divisor primo entre as alternativas: os fatores primos de S são 3,11,29,31,431. Dentre as opções dadas (29,31,173,383,431), o maior primo que divide S é \;431.

Resposta

e) 431

Exercícios relacionados