(PUTNAM) Determine o número de triplas ordenadas (????1,????2,????3) de conjuntos tais que: I. ????1 ∪ ????2 ∪ ????3 = {1,2,3,4,5,6,7,8,9,10}, e II. ????1 ∩ ????2...

Este é um problema clássico de contagem. Podemos resolvê-lo usando o Princípio da Inclusão-Exclusão (PIE). Primeiro, vamos contar o número de triplas ordenadas de conjuntos que satisfazem apenas a condição I. Para cada elemento de {1,2,3,4,5,6,7,8,9,10}, temos três opções: ele pode estar em ????1, ????2 ou ????3. Portanto, o número total de triplas ordenadas de conjuntos que satisfazem apenas a condição I é 3^10. Agora, vamos subtrair o número de triplas ordenadas de conjuntos que violam a condição II. Existem 10 escolhas para o elemento que estará em todos os três conjuntos. Depois disso, temos 2^10 escolhas para os outros elementos, pois cada um pode estar em qualquer um dos dois conjuntos restantes. Portanto, o número de triplas ordenadas de conjuntos que violam a condição II é 10 * 2^10. No entanto, subtraímos demais, pois algumas triplas ordenadas de conjuntos violam a condição II mais de uma vez. Precisamos adicionar de volta o número de triplas ordenadas de conjuntos que violam a condição II duas vezes. Existem 10 escolhas para o primeiro elemento que estará em todos os três conjuntos e 9 escolhas para o segundo elemento que estará em todos os três conjuntos (já que não podemos escolher o mesmo elemento duas vezes). Depois disso, temos 2^8 escolhas para os outros elementos, pois cada um pode estar em qualquer um dos dois conjuntos restantes. Portanto, o número de triplas ordenadas de conjuntos que violam a condição II duas vezes é 10 * 9 * 2^8. No entanto, adicionamos demais, pois algumas triplas ordenadas de conjuntos violam a condição II três vezes. Precisamos subtrair o número de triplas ordenadas de conjuntos que violam a condição II três vezes. Existem 10 escolhas para o elemento que estará em todos os três conjuntos. Depois disso, temos 2^6 escolhas para os outros elementos, pois cada um pode estar em qualquer um dos dois conjuntos restantes. Portanto, o número de triplas ordenadas de conjuntos que violam a condição II três vezes é 10 * 2^6. Agora, podemos usar o PIE para obter o número total de triplas ordenadas de conjuntos que satisfazem ambas as condições. Temos: Número total = N(I) - N(II) + N(III) Número total = 3^10 - 10 * 2^10 + 10 * 9 * 2^8 - 10 * 2^6 Número total = 59049 - 102400 + 23040 - 640 Número total = 48149 Portanto, a resposta é 2^2 * 7 * 685.