Question

Considere o conjunto $M = {1, 2, . . . , 1000000}$ e seu subconjunto A formado por todos os inteiros positivos da forma $m^2+k^3$ com m e k também inteiros positivos. Quem têm mais elementos: A ou M\A

Answer 1

Resolvi essa utilizando um raciocínio puramente combinatório. O exercício nos fornece o conjunto M = {1, 2, 3, ... , 1000000} e um outro conjunto A constituído por todos os inteiros positivos de M, gerados a partir da expressão algébrica m² + k³, para m e k inteiros positivos. Devido ao fato de m e k serem números naturais, a primeira parcela m² da referida soma é um quadrado perfeito e, pelo mesmo motivo, a segunda parcela k³ será um cubo perfeito. Portanto, para resolver o exercício, precisamos primeiro calcular ou ter uma estimativa do total de somas possíveis que pertencem a M e atendem ao formato m² + k³. Equivalentemente, tentaremos encontrar o número máximo de elementos de A. Vimos acima que A foi definido a partir de M, ou melhor dizendo, o conjunto A é formado apenas pelos elementos de M que resultem da adição entre um "quadrado" e um "cubo". Em razão disso, dizemos que A é um subconjunto próprio de M (escrevendo A ⊂ M). Como podemos ver, existem 1000 (mil) quadrados perfeitos no conjunto M, que são eles:

$\sf{1^2\ =\ 1}\\ \sf{2^2\ =\ 4}\\ \sf{3^2\ =\ 9}\\ \sf{4^2\ =\ 16}\\\\ \vdots\quad\ \ \,\vdots\quad\ \ \, \vdots \\\\ \sf{998^2\ =\ 996004}\\ \sf{999^2\ =\ 998001}\\ \sf{1000^2\ =\ 1000000}$

Do mesmo modo, podemos concluir que o número de cubos perfeitos existentes nesse mesmo conjunto é de apenas 100, sendo eles os seguintes:

$\sf{1^3\ =\ 1}\\ \sf{2^3\ =\ 8}\\ \sf{3^3\ =\ 27}\\ \sf{4^3\ =\ 64}\\\\ \vdots\quad\ \ \,\vdots\quad\ \ \, \vdots \\\\ \sf{98^3\ =\ 941192}\\ \sf{99^3\ =\ 970299}\\ \sf{100^3\ =\ 1000000}$

Sendo assim, por intermédio do Princípio Multiplicativo da Análise Combinatória, depreende-se a existência de 1000 x 100 = 100000 (cem mil) somas satisfazendo a condição imposta anteriormente, e este resultado, a princípio, é o número máximo de elementos de A. Repare agora que a cardinalidade (número de elementos) de A (representada por # A) não pode ser 100000, ao passo que neste valor estão incluídas somas repetidas (ex.: 3² + 2³ = 4² + 1³ = 17) e até mesmo aquelas maiores que 1000000 (ex.: 1000² + 100³ = 2000000). Em vista disso, é verdade que # A < 100000 e, por este motivo, a quantidade de elementos da diferença (na ordem de escrita) entre os conjuntos M e A (denotada por # M \ A) é maior que # A, ou seja, # M \ A > # A. Isso se dá porque # M = 1000000, # A < 100000 e A ⊂ M; equivalendo, portanto, à dupla desigualdade # M \ A > 900000 > # A.

Resposta: o conjunto M \ A.