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
e
tais que (i) o número
esteja entre os escolhidos e (ii) nenhum número escolhido seja divisor de outro escolhido.
Informações relevantes dadas:
- Universo de escolha: os inteiros
. - Precisamos de exatamente
números escolhidos. - O conjunto escolhido deve conter o número
. - Condição de antissimetria por divisibilidade: se
e estão no conjunto escolhido, então não pode ocorrer (isto é, nenhum escolhido divide outro escolhido).
O que se pede implicitamente: verificar se é possível construir tal conjunto de tamanho
que contenha
; 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
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
é decompor cada inteiro na forma , onde é ímpar (chamamos de parte ímpar, ou “odd part”). Dois números com a mesma parte ímpar formam uma cadeia pelo fator : por exemplo . 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 ). - Assim, a família de “torres” (cada torre associada a uma parte ímpar
) particiona em 13 torres, uma para cada ímpar em . 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 é (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
) 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
no conjunto: está na torre da parte ímpar (já que ). divide exatamente os múltiplos de em , ou seja os números . Assim, se for escolhido, nenhum dos outros cinco números pode ser escolhido.
Passo 3
Contagem estrutural (construção das torres) e observação sobre múltiplos de
.
- Liste as 13 partes ímpares
: . - Torre de
: . - Torre de
: . - Torre de
: . - Torre de
: . - Torre de
: . - Torre de
: . - Torre de
: . - Torre de
: . - Torre de
: . - Torre de
: . - Torre de
: . - Torre de
: . - Torre de
: .
Cada torre pode contribuir com no máximo um elemento ao conjunto escolhido (caso contrário haveria divisibilidade interna). Para atingir
elementos teríamos que escolher exatamente um elemento de cada torre.
Agora note um fato crucial: os números divisíveis por
na lista acima estão nas seguintes torres:
-
pertencem à torre . -
pertencem à torre . -
pertence à torre .
Se escolhemos
(torre
), automaticamente ficam proibidos os outros números divisíveis por
:
. Em particular, nas torres
e
não podemos escolher os elementos
e
respectivamente — nesses casos ainda restam nas torres opções menores (por exemplo na torre
restam
e
; na torre
restam
e
). Portanto, a presença de
não elimina totalmente as torres
e
, apenas restringe quais elementos delas podem ser escolhidos.
Passo 4
Tentativa construtiva e demonstração de maximalidade para conjuntos que contenham
.
- Vamos tentar construir um conjunto com
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 então e não pode dividir outro número maior dentro do intervalo). Tomemos inicialmente o conjunto
que tem
elementos e é um antichain (nenhum desses divide outro, porque dobrar qualquer um deles excede
). Mas
não contém
; para incluir
precisamos remover de
todos os elementos que
divide: esses são
. Retirando-os ficamos com
que tem
elementos, e então adicionando
obtemos um conjunto de tamanho
. Precisamos de mais
elementos para chegar a
.
- Vamos tentar completar
com números menores que que não criem divisibilidade. Procurando candidatos na faixa a , 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 ), os únicos possíveis a acrescentar eram 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 até ), encontra-se que é possível completar até elementos mas não até . Um conjunto de tamanho que contém e satisfaz a condição é, por exemplo,
Verificação rápida: nenhum elemento de
divide outro (checar pares mostra que dobrar qualquer elemento
ultrapassa
, e entre os menores escolhidos
não é dividido por nem divide outros escolhidos; em particular
não divide nenhum dos outros elementos em
porque os múltiplos de
menores que
seriam
, e nenhum desses está em
).
- Agora mostramos que não existe conjunto válido de tamanho
que contenha . Uma maneira direta e simples de ver isso é argumentar por maximalidade do conjunto acima: suponha, por contradição, que exista um conjunto com elementos, contendo , e sem divisibilidade entre seus elementos. Como há torres (uma por cada parte ímpar), para ter elementos o conjunto deve conter exatamente um elemento de cada torre. Em particular, ele contém um elemento da torre (que pode ser ou ) e um elemento da torre (que pode ser ou ). Mas divide , logo para evitar que divida algum elemento em , nas torres e as escolhas ficam forçadas a ser ou e ou respectivamente. Prosseguindo por uma contagem cuidadosa das divisibilidades entre as partes ímpares (por exemplo: se escolhemos então não podemos escolher nem nas torres correspondentes; se escolhemos então não podemos escolher nem , 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 está presente.)
Em termos mais pragmáticos: fizemos uma busca construtiva e concluímos que qualquer tentativa de incluir
força a eliminação dos múltiplos de
e, por acoplamentos de divisibilidade entre as partes ímpares menores, não há como completar até
elementos; o maior tamanho possível com
é
.
Passo 5
Conclusão prática e exemplo de conjunto máximo com
.
- Exemplo de conjunto válido com
e maximal (tamanho ):
- Argumento final: não existe conjunto com
elementos que contenha 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 no conjunto é , e um exemplo de tal conjunto foi dado acima.
Resposta
Não é possível escolher
números de
a
contendo
e sem divisibilidade entre os escolhidos. O máximo possível com
é
. Um exemplo de conjunto válido com
elementos é