Question

Dados 11 números naturais diferentes, nenhum maior que 20, prove que podemos escolher dois deles tais que um divide o outro.

Answer 1

Olá GFerraz.


Dados 11 números naturais diferentes, nenhum maior que 20, prove que podemos escolher dois deles tais que um divide o outro.

________________________________

Para esse problema iremos considerar a pior das hipóteses.

Sabendo que o maior número possível entre esses 11 distintos, seria o número 20. Então se eu pegar qualquer número que seja maior que a metade de 20, ou seja, 10, então o múltiplo desse número ultrapassaria o 20 (que é o maior número possível).

Por exemplo, pegando o 11, que é o número mais próximo da metade de 20, seu múltiplo mais próximo seria o 22, se pegássemos o 12, o múltiplo mais próximo seria o 24. 

Portanto, se pegarmos qualquer número no intervalo [11, 20], não existirá nenhum múltiplo desse número menor que 20.

Então vamos definir 9 desses números no intervalo [11, 20]. Agora a questão será verificar se é possível escolher um número no intervalo [1, 10], que não tenha um múltiplo no intervalo [11, 20].

Pegando o menor desse número o 1, teríamos que qualquer número no intervalo [11, 20], seria divisível por ele (já que qualquer número é divisível por 1). Pegando o maior número nesse intervalo, o 10, seu menor múltiplo seria o 20.

Ou seja, se o maior e o menor múltiplo do intervalo [1, 10], será um número menor ou igual a 20 (o maior número possível), então se escolhermos um número qualquer no intervalo [1, 10], teremos seu um múltiplo garantindo no intervalo [11, 20].

Portanto, é possível escolher 2 números menores do que 20, tais que um divida o outro.


Dúvidas? comente.

Answer 2

Explicação passo-a-passo:

Pelo princípio das casas de pombo, se você precisar colocar N + 1 ou mais pombos em N casas, então alguma casa terá dois ou mais pombos.

• Casas:

- {1, 2, 4, 8, 16}

- {3, 6, 12}

- {5, 10, 20}

- {7, 14}

- {9, 18}

- {11}

- {13}

- {15}

- {17}

- {19}

Na pior das hipóteses, escolheríamos os primos 11, 13, 15, 17 e 19 primeiramente. Porém, quaisquer que sejam os dois próximos números escolhidos, um deles dividirá o outro.

- {1, 2, 4, 8, 16}

- {3, 6, 12}

- {5, 10, 20}

- {7, 14}

- {9, 18}

Isso acontece porque temos 11 pombos e 10 casas, logo, alguma casa terá 2 ou mais pombos.