Seja A um conjunto finito. Como devemos particionar A em dois subconjuntos não vazios
A=M1 cup M2, com M1 cap M2=emptyset
de modo que o produto cartesiano M1 times M2 tenha o número máximo de elementos?

Passo 1

O enunciado pede uma partição de um conjunto finito A de modo a maximizar o número de elementos do produto cartesiano M1times M2, sujeita a
A = M1cup M2, M1cap M2=emptyset, M1neqemptyset,;M2neqemptyset
O conteúdo aqui é otimização discreta: dado lvert Arvert = n, queremos escolher cardinais lvert M1rvert e lvert M2rvert que maximizem o produto das cardinais.

Passo 2

Denotemos n=lvert Arvert e seja
k = lvert M1rvert
Como M2=Asetminus M1, temos lvert M2rvert = n-k. O número de elementos de M1times M2 é
f(k)=lvert M1times M2rvert = k,(n-k),
com k inteiro em 1,2,dots,n-1.

Passo 3

A função f(k)=kn - k^2 é uma parábola voltada para baixo (coeficiente de k^2 negativo). No caso contínuo, sua raiz derivada anula-se em
f'(k)=n-2k=0Longrightarrow k=n2
Em inteiros, o máximo ocorre nos valores de k mais próximos de n/2, ou seja
k = llfloor tfracn2rrfloor ou k = llceil tfracn2rrceil

Passo 4

Para n par temos lfloor n/2rfloor=lceil n/2rceil=n/2 e o máximo é único em k=n/2. Para n ímpar, lfloor n/2rfloor=(n-1)/2 e lceil n/2rceil=(n+1)/2, ambos geram o mesmo valor
fl(lfloor n/2rfloorr) =llfloortfracn2rrfloorllceiltfracn2rrceil =n^2-14
Logo o produto cartesiano é maximizado quando os subconjuntos têm cardinais o mais “equilibrados” possível.

Resposta

Escolher M1 e M2 de modo que
lvert M1rvert = llfloor tfraclvert Arvert2rrfloor e lvert M2rvert = llceil tfraclvert Arvert2rrceil,
isto é, particionar A em dois blocos cujas cardinais diferem no máximo por 1.

Exercícios relacionados