Seja
um conjunto finito. Como devemos particionar
em dois subconjuntos não vazios
de modo que o produto cartesiano
tenha o número máximo de elementos?
Passo 1
O enunciado pede uma partição de um conjunto finito
de modo a maximizar o número de elementos do produto cartesiano
, sujeita a
O conteúdo aqui é otimização discreta: dado
, queremos escolher cardinais
e
que maximizem o produto das cardinais.
Passo 2
Denotemos
e seja
Como
, temos
. O número de elementos de
é
com
inteiro em
.
Passo 3
A função
é uma parábola voltada para baixo (coeficiente de
negativo). No caso contínuo, sua raiz derivada anula-se em
Em inteiros, o máximo ocorre nos valores de
mais próximos de
, ou seja
Passo 4
Para
par temos
e o máximo é único em
. Para
ímpar,
e
, ambos geram o mesmo valor
Logo o produto cartesiano é maximizado quando os subconjuntos têm cardinais o mais “equilibrados” possível.
Resposta
Escolher
e
de modo que
isto é, particionar
em dois blocos cujas cardinais diferem no máximo por 1.