Questão 6 (Nível 3) da 2ª fase da OBMEP 2017

Question

Joana retira bolas, sem reposição, de uma caixa com 2017 bolas numeradas de 1 a 2017.

Ilustração de uma garota retirando bolas coloridas e numeradas de dentro de uma caixa cheia de bolas

a) Qual é a quantidade mínima de bolas que ela deve retirar para garantir que em pelo menos uma delas haja um número múltiplo de 3?

b) Qual é a quantidade mínima de bolas que ela deve retirar para garantir que existam duas bolas com a soma de seus números igual a um múltiplo de 3?

c) Qual é a quantidade mínima de bolas que ela deve retirar para garantir que existam duas bolas de modo que a soma de seus números seja um múltiplo de 3 e sua diferença seja um múltiplo de 2?

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

Questão 6 (Nível 3) da 2ª fase da OBMEP 2017

Nível 3 · Matemática: Princípio fundamental da contagem

Joana retira bolas, sem reposição, de uma caixa com 2017 bolas numeradas de 1 a 2017.

Ilustração de uma garota retirando bolas coloridas e numeradas de dentro de uma caixa cheia de bolas

a) Qual é a quantidade mínima de bolas que ela deve retirar para garantir que em pelo menos uma delas haja um número múltiplo de 3?

b) Qual é a quantidade mínima de bolas que ela deve retirar para garantir que existam duas bolas com a soma de seus números igual a um múltiplo de 3?

c) Qual é a quantidade mínima de bolas que ela deve retirar para garantir que existam duas bolas de modo que a soma de seus números seja um múltiplo de 3 e sua diferença seja um múltiplo de 2?

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

a)

Podemos separar as bolas em três conjuntos: as que deixam resto 0, 1 ou 2, na divisão por 3. Vamos chamar esses conjuntos de A, B e C, respectivamente.

Como 2017 = 3 \times 672 + 1, A tem 672 elementos, B tem 673 e C tem 672.

Podemos analisar o "pior cenário", isto é, procurar o número máximo de bolas em que nenhuma bola retirada possui número múltiplo de 3. Se pegarmos todas as bolas dos conjuntos B e C, um total de 1345 bolas, não teremos nenhum múltiplo de 3. A próxima bola, portanto, necessariamente será do grupo A, que é o grupo dos múltiplos de 3. Assim, se pegarmos 1346 bolas teremos de pegar uma do grupo A, necessariamente. Portanto, o mínimo de bolas que devem ser retiradas é 1346.

b)

Para que a soma dos números das bolas seja um múltiplo de 3, temos as seguintes possibilidades:

duas bolas do grupo A;
uma bola do grupo B e uma bola do grupo C.

Qual o número máximo de bolas que podemos pegar de tal forma que a soma de duas quaisquer não seja um múltiplo de 3? O pior cenário é: pegar uma bola do conjunto A e todas do conjunto B (que tem mais bolas que o grupo C). Então, o total é 1 + 673 = 674. Se pegarmos 675 bolas, necessariamente a soma de duas delas será um múltiplo de 3. De fato, note que, para quaisquer 675 bolas que pegarmos, se duas estiverem no conjunto A, então elas formam um par cuja soma de seus números é igual a um múltiplo de 3. Se apenas uma estiver no conjunto A ou nenhuma das duas estiver em A, pelo menos 674 bolas estarão em B U C. Como o B tem 673 elementos, temos que ter pelo menos uma do conjunto B e uma do conjunto C e, novamente, a soma dos números nessas bolas será um múltiplo de 3.

Portanto, neste caso, a quantidade mínima de bolas é 675.

c)

Desta vez vamos separar as bolas em conjuntos de acordo com o resto da divisão do número delas por 6. Isso basta porque se m e n são números inteiros, como m + n = m - n + 2n e 2n é um número par, m - n e m + n ou são ambos pares ou são ambos ímpares. Portanto, basta Joana buscar a quantidade mínima de bolas que devem ser retiradas para garantir que a soma dos números escritos em duas delas seja simultaneamente um múltiplo de 2 e 3, ou seja, um múltiplo de 6.

Chamemos os conjuntos dos números que deixam resto 0, 1, 2, 3, 4 e 5 na divisão por 6, respectivamente, por P, Q, R, S, T e U. Esses conjuntos têm 336, 337, 336, 336, 336 e 336 elementos, respectivamente.

Queremos saber qual é o menor número de bolas que Joana deve pegar para assegurar que a soma de duas delas seja divisível por 3 e que a sua diferença seja divisível por 2. É fácil ver que essas condições são satisfeitas apenas nos seguintes casos:

Caso 1. Duas bolas do conjunto P (resto 0 por 6),
Caso 2. Uma bola do conjunto Q (resto 1 por 6) e uma bola do conjunto U (resto 5 por 6),
Caso 3. Uma bola do conjunto R (resto 2 por 6) e uma bola do conjunto T (resto 4 por 6),
Caso 4. Duas bolas do conjunto S (resto 3 por 6).

O pior cenário é o seguinte: pegar 1 bola do conjunto P, 337 bolas do conjunto Q (este conjunto é o que possui uma maior quantidade de elementos), 336 bolas do conjunto R, e uma bola do conjunto S. Com certeza, se Joana fizer essas escolhas, pegando um total de 1 + 337 + 336 + 1 = 675 bolas, ela não obterá duas bolas cuja soma de seus números é múltipla de 3 e a diferença múltipla de 2. Entretanto, se ela pegar uma bola a mais, certamente entre as 676 bolas aparecerão duas com números que, somados, dão um múltiplo de 3 e cuja diferença é par. De fato, selecionemos duas bolas dentre as 676 e analisemos as possibilidades:

As duas bolas estão no conjunto P. Neste caso, os números são ambos múltiplos de 6 e as exigências do enunciado estão satisfeitas (Caso 1 descrito acima).
As duas bolas estão no conjunto S. Neste caso, os números em ambas as bolas são múltiplos de 3 e, novamente, elas cumprem as exigências do enunciado (Caso 4 descrito acima).
Não existem duas bolas em P, nem duas bolas em S. Neste caso, em Q U R U T U U estão pelo menos 676 - 1 - 1 = 674 elementos. Considerando as uniões Q U U e R U T, pelo menos uma delas deve possuir 337 ou mais elementos, pois, caso contrário, existiriam no máximo 336 + 336 = 672 elementos nessas duas uniões. Vamos analisar separadamente cada caso:
- Suponha que R U T possua 337 elementos ou mais; então, devem existir bolas escolhidas nos dois elementos da união, uma delas em R e outra em T, pois ambos os conjuntos possuem menos do que 337 elementos. Escolhendo uma bola em R e outra em T, os números escritos nelas deixam restos 2 e 4, respectivamente, quando divididos por 6. Este par satisfaz as exigências do enunciado (Caso 3 descrito acima).
- Suponha que R U T possua menos do que 337 elementos; então Q U U deve possuir pelo menos 674 - 336 = 338 elementos. Deste modo, deve sempre existir um par de bolas, uma delas em Q e outra em U, pois Q e U possuem menos do que 337 elementos. Este par assim escolhido cumpre as exigências do enunciado, posto que uma bola em Q possui número que deixa resto 1 quando dividido por 6 e uma bola em U tem número que deixa resto 5, quando dividido por 6 (Caso 2 descrito acima).

Em qualquer uma das duas situações anteriores, será formado um par que satisfaz as propriedades descritas no enunciado e, portanto, o mínimo de bolas que Joana deve retirar é 676.

Outra solução:

Temos três conjuntos disjuntos de números inteiros positivos:

A_0 = \{x\ /\ 1 \le x \le 2017\ ,\ x \equiv 0 \bmod 3\}

A_1 = \{x\ /\ 1 \le x \le 2017\ ,\ x \equiv 1 \bmod 3\}

A_2 = \{x\ /\ 1 \le x \le 2017\ ,\ x \equiv 2 \bmod 3\}

O número de elementos de A_1 é 673, já os conjuntos A_0 e A_2 possuem 672 elementos.

Começamos com o conjunto com maior número de elementos, A_1. Escolhemos todos os ímpares contidos em A_1 e formamos um conjunto B_1 com 337 inteiros (com certeza a soma de quaisquer dois deles não é múltiplo de 3).

Escolhemos, a seguir, todos os pares contidos em A_2 e formamos um conjunto B_2 com 336 inteiros (com certeza a soma de quaisquer dois deles não é múltiplo de 3).

A soma de um elemento de B_1 com um elemento de B_2 é múltipla de 3, porém, sua diferença não é par.

Escolhemos, agora, dois elementos de A_0, um par e um ímpar e denotamos o conjunto formado por esses dois elementos por B_0. Temos que a união \text{B}_0\text{ U }\text{B}_1\text{ U }\text{B}_2 é um conjunto em que quaisquer dois elementos x e y são tais que x + y ou não é múltiplo de 3 ou x - y não é par e, para qualquer outro elemento a do conjunto diferença (\text{A}_0\text{ U }\text{A}_1\text{ U }\text{A}_2) - (\text{B}_0\text{ U }\text{B}_1\text{ U }\text{B}_2), existe um elemento b de \text{B}_0\text{ U }\text{B}_1\text{ U }\text{B}_2 tal que

a + b \equiv 0 \bmod 3

a - b \equiv 0 \bmod 2

Portanto, a quantidade mínima de bolas que Joana deve retirar é 337 + 336 + 2 + 1 = 676.

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

Primeiro, a contagem. Como 2017 = 3\cdot 672 + 1, entre 1 e 2017 há 672 múltiplos de 3, 673 números com resto 1 (1, 4, ..., 2017) e 672 números com resto 2.

a) O pior caso é Joana retirar todos os números que não são múltiplos de 3 antes de pegar um múltiplo. Há 673 + 672 = 1345 desses números. Com 1345 bolas ainda é possível não haver múltiplo de 3. Na bola seguinte ele aparece obrigatoriamente.

1345 + 1 = 1346.

b) A soma de dois números é múltiplo de 3 quando os restos na divisão por 3 são (0,0) ou (1,2).

Para evitar isso, Joana pode ter no máximo uma bola com resto 0. Das bolas com resto 1 ou 2, só pode ter de um desses tipos, e o maior grupo é o de resto 1, com 673 bolas.

O máximo sem uma soma múltipla de 3 é 1 + 673 = 674 bolas. Com mais uma bola, a soma aparece.

674 + 1 = 675.

c) Dois números com diferença par têm a mesma paridade. Então a soma é par e múltipla de 3, ou seja, múltipla de 6. Olhamos os restos na divisão por 6. Os pares de restos que dão soma múltipla de 6 são (0,0), (3,3), (1,5) e (2,4).

Contagem: 2017 = 6\cdot 336 + 1. O resto 1 aparece 337 vezes, e cada um dos restos 0, 2, 3, 4, 5 aparece 336 vezes.

Para evitar o par desejado, Joana pode ter:

no máximo 1 bola de resto 0;
no máximo 1 bola de resto 3;
bolas só de resto 1 ou só de resto 5, e o melhor é o resto 1, com 337;
bolas só de resto 2 ou só de resto 4, com 336.

Conferindo as combinações entre restos 0, 3, 1 e 2: 0+3 dá 3, mas os números têm paridades diferentes. 1+2 dá 3, também com paridades diferentes. As demais somas não são múltiplas de 3.

O máximo sem o par é 1 + 1 + 337 + 336 = 675. Com mais uma bola, o par existe.

675 + 1 = 676.

Assuntos: Princípio fundamental da contagem, Divisibilidade, MMC e MDC.

Reportar erro na resolução

Ver como caiu na prova

Questão 6 no caderno Nível 3 da 2ª fase da OBMEP 2017

Fonte: OBMEP 2ª fase 2017 · Nível 3. Prova oficial ↗