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

Question

Pedro deve preencher um tabuleiro retangular 9 \times 2018 com os números do conjunto \{1,2,\dots, 2018\} usando cada número do conjunto exatamente 9 vezes. Além disso, a diferença entre dois números numa mesma coluna não pode ser maior do que 3.

Parte de uma grade quadriculada com 9 linhas horizontais e 11 colunas completas visíveis, aberta no lado direito.

a) Qual é o maior número que pode aparecer em uma coluna que contém um número 1?

b) Determine o número máximo de colunas que podem conter números iguais a 1.

c) Além de preencher o tabuleiro, Pedro deve escrever embaixo de cada coluna o valor da soma dos números dessa coluna. Explique por que, independentemente do preenchimento de Pedro, pelo menos uma dessas somas vai ser menor do que 25.

Answer 1

PRÁTICA COM QUESTÕES OFICIAIS

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

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

Pedro deve preencher um tabuleiro retangular 9 \times 2018 com os números do conjunto \{1,2,\dots, 2018\} usando cada número do conjunto exatamente 9 vezes. Além disso, a diferença entre dois números numa mesma coluna não pode ser maior do que 3.

Parte de uma grade quadriculada com 9 linhas horizontais e 11 colunas completas visíveis, aberta no lado direito.

a) Qual é o maior número que pode aparecer em uma coluna que contém um número 1?

b) Determine o número máximo de colunas que podem conter números iguais a 1.

c) Além de preencher o tabuleiro, Pedro deve escrever embaixo de cada coluna o valor da soma dos números dessa coluna. Explique por que, independentemente do preenchimento de Pedro, pelo menos uma dessas somas vai ser menor do que 25.

Reportar erro na questão

Resolução comentada

Solução oficial da OBMEP

a) Como a diferença entre dois números em uma mesma coluna não pode ser maior que 3, o maior número que pode aparecer em uma coluna com o 1 é 1 + 3 = 4.

b) As colunas que contém 1 só podem ter os números do conjunto \{1,2,3,4\}. Como Pedro só pode usar 4 \times 9 = 36 números (nove repetições de cada um dos números 1, 2, 3 e 4), o número de colunas que podem conter o número 1 é, no máximo, \frac{36}{9} = 4.

Observe que esse número pode ser atingido, por exemplo, colocando-se nas 4 primeiras colunas os seguintes conjuntos de números:

\begin{aligned} C_1 &= \{1,1,1,2,2,2,2,3,3\} \\ C_2 &= \{1,1,2,2,2,2,3,3,4\} \\ C_3 &= \{1,1,2,3,3,3,3,4,4\} \\ C_4 &= \{1,1,3,4,4,4,4,4,4\} \end{aligned}

e as nove casas das demais colunas C_i, com i > 4, podem ser preenchidas com números todos iguais a i.

c) Seja k a quantidade de colunas com o número 1. Vamos dividir a análise em casos:

i) Se k = 1, todos os números 1 estão em uma mesma coluna e assim a soma dos números dela é 9. Nenhuma outra coluna pode ter soma menor. Portanto, a soma dos números dessa coluna formada por 1´s apenas é menor do que 25.

ii) Se k = 2, uma das duas colunas terá pelo menos 5 números 1´s. Mesmo que os números restantes dessa coluna sejam todos 4´s, a soma dos números nessa coluna é, no máximo, igual a 5 \cdot 1 + 4 \cdot 4 = 21. Portanto, nesse caso também, a soma dos números dessa coluna com cinco 1´s é menor do que 25.

iii) Se k = 3, a soma dos números nessas três colunas é no máximo 9 \cdot 1 + 9 \cdot 3 + 9 \cdot 4 = 72, pois devemos utilizar nove 1´s e maximizar as casas faltantes com os maiores números permissíveis que podem acompanhar o 1, ou seja, com números 3 ou 4. Pelo menos uma das três colunas terá como soma de seus elementos um número menor do que ou igual a 72/3 = 24. Portanto, nesse caso também, há uma coluna cuja soma é menor do que 25.

Um exemplo deste caso é o preenchimento cujas cinco primeiras colunas têm o seguinte aspecto:

\begin{aligned} C_1 &= \{1,1,1,3,3,3,4,4,4\} \\ C_2 &= \{1,1,1,3,3,3,4,4,4\} \\ C_3 &= \{1,1,1,3,3,3,4,4,4\} \\ C_4 &= \{2,2,2,2,2,2,2,5,5\} \\ C_5 &= \{2,2,5,5,5,5,5,5,5\} \end{aligned}

e as nove casas das demais colunas C_i, com i > 5, podem ser preenchidas com números todos iguais a i. Isto mostra que 25 é a melhor limitação que podemos encontrar em preenchimentos gerais da tabela.

iv) Se k = 4, a soma dos números nessas quatro colunas é 9 \cdot 1 + 9 \cdot 2 + 9 \cdot 3 + 9 \cdot 4 = 90. Pelo menos uma delas terá como soma de seus elementos um número menor do que ou igual a 90/4 = 22{,}5. Portanto, nesse último caso, há uma coluna cuja soma é menor do que 25.

Ver como a OBMEP publicou

Publicada pela banca.

Resolução comentada

a) Se uma coluna tem o número 1, todos os outros números dela diferem de 1 em no máximo 3. Logo, todos são no máximo 1+3=4. O 4 pode aparecer, por exemplo na coluna 1,1,1,1,1,1,1,1,4, em que a diferença entre 4 e 1 é 3.

O maior número possível é 4.

b) Pelo item (a), toda coluna que contém um 1 só tem números de \{1,2,3,4\}. Esses quatro números aparecem, ao todo, 4\cdot 9=36 vezes no tabuleiro. Cada coluna tem 9 casas. Se k colunas têm um 1, elas ocupam 9k casas, todas preenchidas com 1, 2, 3 ou 4. Então 9k\le 36, ou seja, k\le 4.

O valor 4 é atingido. Basta usar 4 colunas, cada uma com 1, assim:

Coluna A: três 1, dois 2, dois 3, dois 4.
Coluna B: dois 1, três 2, dois 3, dois 4.
Coluna C: dois 1, dois 2, três 3, dois 4.
Coluna D: dois 1, dois 2, dois 3, três 4.

Cada número de 1 a 4 aparece 9 vezes e a diferença dentro de cada coluna é no máximo 3. As demais colunas se preenchem com 5, 6, 7, … de modo análogo (por exemplo, cada número repetido 9 vezes numa coluna).

O máximo é 4 colunas.

c) Seja k o número de colunas que contêm algum 1. Pelo item (b), 1\le k\le 4. Essas k colunas têm 9k casas, só com números de 1 a 4, e contêm os nove 1 do tabuleiro. Vamos limitar a soma dessas k colunas. Além dos nove 1, as outras 9k-9 casas recebem no máximo os maiores valores disponíveis (cada valor aparece só 9 vezes: nove 4, depois nove 3, ...).

k=1: soma =9, média 9.
k=2: soma \le 9\cdot1+9\cdot4=45, média \le 22{,}5.
k=3: soma \le 9\cdot1+9\cdot4+9\cdot3=72, média \le 24.
k=4: usa todos os 1, 2, 3 e 4, soma =9(1+2+3+4)=90, média =22{,}5.

Em todos os casos a média das somas dessas k colunas é menor que 25. Se todas as somas fossem \ge 25, a média também seria \ge 25, o que é um absurdo. Portanto, alguma coluna tem soma menor que 25.

Pelo menos uma das colunas com um 1 tem soma menor que 25, qualquer que seja o preenchimento.

Assuntos: Princípio fundamental da contagem, Lógica e raciocínio lógico.

Reportar erro na resolução

Ver como caiu na prova

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

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