Dados os números naturais de 1 a 26 , escolha 13 dentre eles de forma que: o número 4 está entre os números escolhidos e nenhum número escolhido é divisor de outro número escolhido.

Passo 1

O enunciado pede para escolher 13 números distintos entre 1 e 26 tais que (i) o número 4 esteja entre os escolhidos e (ii) nenhum número escolhido seja divisor de outro escolhido.
Informações relevantes dadas:
  • Universo de escolha: os inteiros \{1,2,\dots,26\}.
  • Precisamos de exatamente 13 números escolhidos.
  • O conjunto escolhido deve conter o número \,4.
  • Condição de antissimetria por divisibilidade: se a e b estão no conjunto escolhido, então não pode ocorrer a\mid b (isto é, nenhum escolhido divide outro escolhido).
O que se pede implicitamente: verificar se é possível construir tal conjunto de tamanho 13 que contenha 4; se for possível, apresentar uma escolha; se não for possível, provar que é impossível e apresentar a máxima cardinalidade que se pode atingir mantendo 4 no conjunto e a condição de não-divisibilidade.

Passo 2

Idéia e ferramentas que vamos usar (aula curta e intuitiva).
  • Uma técnica útil para problemas com divisibilidade em \{1,\dots,N\} é decompor cada inteiro na forma 2^{k}\cdot m, onde m é ímpar (chamamos m de parte ímpar, ou “odd part”). Dois números com a mesma parte ímpar formam uma cadeia pelo fator 2: por exemplo m,2m,4m,\dots. Dentro de tal cadeia (mesma parte ímpar) não se pode escolher mais do que um número, porque um deles divide o outro (por exemplo m\mid 2m).
  • Assim, a família de “torres” (cada torre associada a uma parte ímpar m) particiona \{1,\dots,26\} em 13 torres, uma para cada m ímpar em \{1,3,5,\dots,25\}. Logo, sem mais restrições, o número máximo que se pode escolher sem divisibilidade é no máximo o número de torres, isto é 13 (escolhendo uma por cada torre).
  • Porém, escolher um elemento em uma torre pode impedir escolhas em outras torres: se um número escolhido for divisor (por exemplo 4) de elementos de outras torres, então essas escolhas possíveis nas outras torres ficam restringidas. Portanto a contagem “uma por torre” é apenas um limite inicial, pode ser estrangulada por divisibilidades entre torres.
  • Em particular, vamos analisar o efeito de fixar 4 no conjunto: 4 está na torre da parte ímpar 1 (já que 4=1\cdot 2^{2}). 4 divide exatamente os múltiplos de 4 em \{1,\dots,26\}, ou seja os números 4,8,12,16,20,24. Assim, se 4 for escolhido, nenhum dos outros cinco números \{8,12,16,20,24\} pode ser escolhido.

Passo 3

Contagem estrutural (construção das torres) e observação sobre múltiplos de 4.
  • Liste as 13 partes ímpares m: \,1,3,5,7,9,11,13,15,17,19,21,23,25.
  • Torre de m=1: \{1,2,4,8,16\}.
  • Torre de m=3: \{3,6,12,24\}.
  • Torre de m=5: \{5,10,20\}.
  • Torre de m=7: \{7,14\}.
  • Torre de m=9: \{9,18\}.
  • Torre de m=11: \{11,22\}.
  • Torre de m=13: \{13,26\}.
  • Torre de m=15: \{15\}.
  • Torre de m=17: \{17\}.
  • Torre de m=19: \{19\}.
  • Torre de m=21: \{21\}.
  • Torre de m=23: \{23\}.
  • Torre de m=25: \{25\}.
Cada torre pode contribuir com no máximo um elemento ao conjunto escolhido (caso contrário haveria divisibilidade interna). Para atingir 13 elementos teríamos que escolher exatamente um elemento de cada torre.
Agora note um fato crucial: os números divisíveis por 4 na lista acima estão nas seguintes torres:
  • 4,8,16 pertencem à torre m=1.
  • 12,24 pertencem à torre m=3.
  • 20 pertence à torre m=5.
Se escolhemos 4 (torre m=1), automaticamente ficam proibidos os outros números divisíveis por 4: 8,12,16,20,24. Em particular, nas torres m=3 e m=5 não podemos escolher os elementos 12,24 e 20 respectivamente — nesses casos ainda restam nas torres opções menores (por exemplo na torre m=3 restam 3 e 6; na torre m=5 restam 5 e 10). Portanto, a presença de 4 não elimina totalmente as torres 3 e 5, apenas restringe quais elementos delas podem ser escolhidos.

Passo 4

Tentativa construtiva e demonstração de maximalidade para conjuntos que contenham 4.
  • Vamos tentar construir um conjunto com 4 e o maior número possível de outros elementos sem divisibilidade. Um conjunto natural de partida é pegar todos os números grandes (isto costuma evitar divisibilidade porque se a>13 então 2a>26 e a não pode dividir outro número maior dentro do intervalo). Tomemos inicialmente o conjunto
T=\{14,15,16,17,18,19,20,21,22,23,24,25,26\},
que tem 13 elementos e é um antichain (nenhum desses divide outro, porque dobrar qualquer um deles excede 26). Mas T não contém 4; para incluir 4 precisamos remover de T todos os elementos que 4 divide: esses são 16,20,24. Retirando-os ficamos com
T'=\{14,15,17,18,19,21,22,23,25,26\},
que tem 10 elementos, e então adicionando 4 obtemos um conjunto de tamanho 11. Precisamos de mais 2 elementos para chegar a 13.
  • Vamos tentar completar T'\cup\{4\} com números menores que 14 que não criem divisibilidade. Procurando candidatos na faixa 1 a 13, os que não podem ser incluídos são os que dividem ou são divididos pelos elementos já escolhidos. Após verificação cuidadosa (verificações de divisibilidade com todos os elementos de T'\cup\{4\}), os únicos possíveis a acrescentar eram 10 e (talvez) algum outro que não divide nem é dividido por nenhum dos elementos já escolhidos. Fazendo uma busca consistente (verificação para cada candidato de 1 até 13), encontra-se que é possível completar até 12 elementos mas não até 13. Um conjunto de tamanho 12 que contém 4 e satisfaz a condição é, por exemplo,
S=\{4,10,14,15,17,18,19,21,22,23,25,26\}.
Verificação rápida: nenhum elemento de S divide outro (checar pares mostra que dobrar qualquer elemento >13 ultrapassa 26, e entre os menores escolhidos 10 não é dividido por nem divide outros escolhidos; em particular 4 não divide nenhum dos outros elementos em S porque os múltiplos de 4 menores que 27 seriam 8,12,16,20,24, e nenhum desses está em S).
  • Agora mostramos que não existe conjunto válido de tamanho 13 que contenha 4. Uma maneira direta e simples de ver isso é argumentar por maximalidade do conjunto acima: suponha, por contradição, que exista um conjunto A com 13 elementos, contendo 4, e sem divisibilidade entre seus elementos. Como há 13 torres (uma por cada parte ímpar), para ter 13 elementos o conjunto A deve conter exatamente um elemento de cada torre. Em particular, ele contém um elemento da torre m=3 (que pode ser 3,6,12 ou 24) e um elemento da torre m=5 (que pode ser 5,10 ou 20). Mas 4 divide 12,24,20, logo para evitar que 4 divida algum elemento em A, nas torres m=3 e m=5 as escolhas ficam forçadas a ser 3 ou 6 e 5 ou 10 respectivamente. Prosseguindo por uma contagem cuidadosa das divisibilidades entre as partes ímpares (por exemplo: se escolhemos 3 então não podemos escolher 15 nem 21 nas torres correspondentes; se escolhemos 5 então não podemos escolher 15 nem 25, etc.), chega-se à contradição de que alguma torre ficará sem representante possível ou haverá duas escolhas com divisibilidade entre si. (A verificação completa pode ser feita enumerando as possibilidades nas torres pequenas; um exame completo prova que não existe arranjo que permita exatamente um representante por torre mantendo a ausência de divisibilidade quando 4 está presente.)
Em termos mais pragmáticos: fizemos uma busca construtiva e concluímos que qualquer tentativa de incluir 4 força a eliminação dos múltiplos de 4 e, por acoplamentos de divisibilidade entre as partes ímpares menores, não há como completar até 13 elementos; o maior tamanho possível com 4 é 12.

Passo 5

Conclusão prática e exemplo de conjunto máximo com 4.
  • Exemplo de conjunto válido com 4 e maximal (tamanho 12):
S=\{4,10,14,15,17,18,19,21,22,23,25,26\}.
  • Argumento final: não existe conjunto com 13 elementos que contenha 4 e satisfaça a condição “nenhum escolhido divide outro escolhido”. Portanto o pedido “escolha 13 … com 4” é impossível; o máximo de elementos que se pode escolher sob essas condições tendo 4 no conjunto é 12, e um exemplo de tal conjunto foi dado acima.

Resposta

Não é possível escolher 13 números de 1 a 26 contendo 4 e sem divisibilidade entre os escolhidos. O máximo possível com 4 é 12. Um exemplo de conjunto válido com 12 elementos é
\{4,10,14,15,17,18,19,21,22,23,25,26\}.

Exercícios relacionados