Qual é o menor inteiro positivo n para o qual qualquer subconjunto de n elementos de {1,2,3,…,20} contém dois números cuja diferença é 8?
a) 2 b)8 c)12 d) 13 e) 15
A resposta é 13 mas por quê?
Soluções para a tarefa
Resposta:
R: 13
Explicação passo-a-passo:
Considere as sequências (1, 9, 17); (2, 10, 18); (3, 11, 19); (4, 12, 20); (5, 13); (6, 14); (7, 15) e (8, 16) cuja diferença entre dois elementos seguidos é 8. Escolhendo-se um elemento de uma dessas sequências e outro elemento de outra dessas sequências a diferença entre eles nunca será 8. Das quatro primeiros podemos tomar no máximo 2 elementos cuja diferença não é 8 (por exemplo 1 e 17 ou 2 e 18) e dos demais no máximo 1. Logo o número máximo de elementos que se pode escolher entre 1 e 20 de modo a não haver dois números cuja diferença é 8 é 4 × 2 + 4 × 1 = 12. Por exemplo o conjunto {1, 17, 2, 18, 3, 19, 4, 20, 5, 6, 7, 8}. Assim, o menor valor de n para que qualquer subconjunto com n elementos contenha dois números cuja diferença é 8, é 13.