1. (Polônia) Determine o número de subconjuntos de \{1,2,3, \ldots, 2 n\} em que a equação x+y=2 n+1 não possua solução.

Passo 1

Vou primeiro deixar claro o que o problema pede e o que nos é dado.
  • O conjunto dado é \{1,2,3,\ldots,2n\}.
  • A equação considerada é x+y=2n+1.
  • A pergunta é: “Quantos subconjuntos de \{1,2,\ldots,2n\} existem tais que a equação x+y=2n+1 não tenha solução com x e y pertencendo ao subconjunto?”
    Em outras palavras: contar os subconjuntos que não contêm nenhum par de elementos cuja soma seja 2n+1.

Passo 2

Observação estrutural (formando pares): cada inteiro k em \{1,\dots,2n\} tem um único companheiro 2n+1-k tal que
k+(2n+1-k)=2n+1.
Portanto os elementos se agrupam em n pares disjuntos:
(1,2n),(2,2n-1),(3,2n-2),\ldots,(n,n+1).
Esses pares são todos disjuntos (não se sobrepõem) e cobrem todo o conjunto \{1,\ldots,2n\}.

Passo 3

Entendimento da restrição: para que a equação x+y=2n+1 não tenha solução dentro de um subconjunto, esse subconjunto não pode conter, para nenhum desses pares, os dois elementos ao mesmo tempo. Ou seja, em cada par (i,2n+1-i) devemos evitar escolher os dois elementos juntos.
Agora, para cada par temos exatamente três opções possíveis ao construir um subconjunto que respeite a restrição:
  1. não escolher nenhum dos dois elementos do par;
  2. escolher apenas o primeiro elemento do par;
  3. escolher apenas o segundo elemento do par.
Essas três opções cobrem todas as escolhas permitidas por par e excluem a escolha proibida (escolher os dois).

Passo 4

Independência entre pares e princípio multiplicativo: como os pares são disjuntos, a escolha feita em um par não afeta as escolhas nos outros pares. Pelo princípio multiplicativo (se um processo é composto por decisões independentes com a escolhas, b escolhas, etc., o total é o produto), o número total de subconjuntos válidos é o produto do número de opções em cada par.
Como há n pares e cada par oferece 3 opções, o total de subconjuntos que satisfazem a condição é
3\cdot 3\cdot\cdots\cdot 3 = 3^{n},
com n fatores.

Passo 5

Cheque rápido com exemplos pequenos para ganhar intuição:
  • Para n=1: conjunto \{1,2\}. Pares: (1,2). Subconjuntos permitidos: \varnothing,\{1\},\{2\} — são 3=3^1.
  • Para n=2: conjunto \{1,2,3,4\}. Pares: (1,4),(2,3). Cada par tem 3 opções, total 3^2=9. Dá para listar se quiser, confirma a fórmula.

Resposta

3^{n}

Exercícios relacionados