Aritmética Elementar: MDC, cap. 10 - questão 70

Cinquenta bolas, numeradas de 2 a 51, devem ser colocadas em x caixas, de modo que o máximo divisor comum dos números de duas bolas quaisquer de uma caixa não seja o número correspon- dente a uma bola desta caixa. O menor valor possível de x é:


Gab.: 5

Primeiro podemos observar que as bolas com números 2,4,8,16,32  não podem estar numa mesma caixa. Isso significa que devem haver pelo menos 5 caixas. Daí vc pode exibir explicitamente. A ideia por trás é justamente pensar nas potencias que aparecem na fatoração do número.

Digamos então que as caixas são A,B,C,D,E.

Na caixa A, colocamos todos os números primos.

Na caixa B, colocamos todos os números cuja fatoração em fatores primos há exatamente dois primos (possivelmente iguais). Ou seja, aqui entram os números como 4 =2.2, 6 = 2.3, 15 = 3.5, 9 = 3.3, etc. Repare que o mdc entre dois números dessa caixa ou é 1 ou é um número primo. Ou seja, o mdc ou é 1 ou está na caixa A.

Na caixa C, colocamos todos os números cuja fatoração aparecem exatamente 3 primos (que podem ser iguais). Aqui entram os números 8 = 2.2.2, 12 = 2.2.3, 30 = 2.3.5, etc.  O mdc entre dois numeros dessa caixa ou é 1, ou um numero primo ou um número da caixa B.

Na caixa D, analogamente, colocamos numeros cuja fatoração aparecem exatamente 4 primos. E na caixa E a mesma coisa, com 5 primos.

Pra concluir o problema basta verificar que todos os números entre 2 e 51 estão em alguma caixa. Isso é verdade, pois 2⁶ = 64 é maior que 51. Isso mostra que é possível fazer a divisão com 5 caixas.