(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
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. Logo10\binom{n}{6}.
Somando os três casos obtemos a identidade combinatória (válida para todo n):
\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.)
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):
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.