Divisores Comuns na OBMEP: Como Preencher Grafos com Números
Você recebe um conjunto de círculos conectados por segmentos e a instrução: preencha cada círculo com um número diferente, de forma que dois círculos ligados tenham sempre um divisor em comum maior do que 1.
Parece simples. Até você tentar resolver sem uma estratégia.
O truque está na fatoração em primos. Dois números têm um divisor em comum maior do que 1 se e somente se compartilham pelo menos um fator primo. Isso transforma a questão de “encontrar números compatíveis” em “identificar quais primos servem de ponte entre os números disponíveis”.
A Condição de Conexão
Dois números a e b podem ser colocados em círculos adjacentes se, e somente se:
MDC(a, b) > 1
ou equivalentemente: a e b compartilham pelo menos um fator primo em comum.
Exemplos:
- 8 e 12 podem ser adjacentes: 8 = 2³, 12 = 2² × 3. Compartilham o fator 2. MDC = 4 > 1. ✓
- 9 e 15 podem ser adjacentes: 9 = 3², 15 = 3 × 5. Compartilham o fator 3. MDC = 3 > 1. ✓
- 7 e 10 não podem ser adjacentes: 7 é primo, 10 = 2 × 5. Nenhum fator em comum. MDC = 1. ✗
A Estratégia: Comece Pelos Mais Difíceis
A armadilha clássica é começar pelos números “fáceis” (como 2, 4, 6) porque eles se conectam com muita coisa. O problema é que no final você empacota os números “difíceis” sem lugar para ir.
A regra: comece pelos números com menos possibilidades de conexão.
Quais são os mais difíceis? Os números primos — eles só podem ser adjacentes a múltiplos de si mesmos. Dentro de um conjunto limitado, as opções são poucas.
Por exemplo, dentro dos números de 2 a 12:
- O 5: só pode ser adjacente ao 10 (único múltiplo de 5 no conjunto)
- O 7: não tem nenhum múltiplo no conjunto 2–12 (o próximo seria 14)
- O 11: não tem nenhum múltiplo no conjunto 2–12 (o próximo seria 22)
Essa análise já revela muito antes de você mover um único número.
Exemplo Resolvido: Preenchendo Círculos com 2 a 12
Questão (OBMEP 2024, 1ª Fase, Nível 1, Questão 4 — adaptada):
Preencha 9 círculos dispostos em uma configuração específica com os números de 2 a 12, onde o maior número (12) deve aparecer numa posição determinada. Números em círculos adjacentes devem ter MDC > 1.
1. Fatorize os candidatos
| Número | Fatoração | Conecta-se facilmente com… |
|---|---|---|
| 2 | 2 | 4, 6, 8, 10, 12 |
| 3 | 3 | 6, 9, 12 |
| 4 | 2² | 2, 6, 8, 10, 12 |
| 5 | 5 | 10 |
| 6 | 2 × 3 | 2, 3, 4, 8, 9, 10, 12 |
| 7 | 7 | (nenhum no conjunto) |
| 8 | 2³ | 2, 4, 6, 10, 12 |
| 9 | 3² | 3, 6, 12 |
| 10 | 2 × 5 | 2, 4, 5, 6, 8, 12 |
| 11 | 11 | (nenhum no conjunto) |
| 12 | 2² × 3 | 2, 3, 4, 6, 8, 9, 10 |
2. Identifique os casos críticos
O 5 só pode ser adjacente ao 10. Portanto, o 5 deve ficar em uma posição que toque apenas o 10 — ou seja, em uma posição de grau 1 (que toca só um outro círculo) adjacente ao 10.
O 7 não tem conexão possível com nenhum outro número no conjunto. Isso significa que ele não pode ser usado sem causar uma violação — mas a questão exige usar todos de 2 a 12 (11 números, dos quais usamos 9… espera, de 2 a 12 são 11 números).
3. Determine quais números podem ser eliminados
Você precisa eliminar 2 dos 11 números. Lembre-se: o 12 está fixo. Os eliminados devem ser números que não causam problemas ao serem retirados.
O 7 é impossível de conectar (sem múltiplos no conjunto) — elimine-o. O 11 é impossível de conectar (sem múltiplos no conjunto) — elimine-o.
Com 7 e 11 eliminados, sobram: 2, 3, 4, 5, 6, 8, 9, 10, 12. Todos têm pelo menos uma conexão possível.
4. Preencha a partir dos mais restritos
- O 5 fica adjacente apenas ao 10 — posicione o 5 em um extremo ligado ao 10.
- O 9 conecta com 3, 6, 12 — posicione-o adjacente a um desses.
- O 3 conecta com 6, 9, 12 — flexível, mas pouco.
- O 2 conecta com quase tudo — deixe-o para o centro ou posições de alto grau.
Uma configuração válida para o grafo da questão coloca os números da seguinte forma: 5–10–2–(4, 8, 12)–(3, 6, 9), onde os traços indicam adjacência e os parênteses indicam o subgrafo conectado pelo fator 2 ou 3.
A Parte C: Por Que é Impossível Usar 1 a 11
Questão: explique por que é impossível preencher 9 círculos com números de 1 a 11 (sem o 12).
De 1 a 11 são 11 números para 9 posições — você elimina 2.
O número 1 não pode ser adjacente a ninguém: MDC(1, n) = 1 sempre. Elimine o 1 obrigatoriamente.
Agora você tem 10 números (2 a 11) para 9 posições — elimina 1 mais.
O problema: dois números não têm nenhuma conexão com os demais nesse conjunto:
- 7: sem múltiplos em {2, 3, 4, 5, 6, 8, 9, 10, 11}
- 11: sem múltiplos em {2, 3, 4, 5, 6, 7, 8, 9, 10}
Para usar os 9 números restantes (depois de eliminar 1), você precisa eliminar um dos dois: 7 ou 11. Mas se elimina o 7, você é forçado a usar o 11 — que não tem conexão. Se elimina o 11, você é forçado a usar o 7 — que não tem conexão. Não há saída.
O Que Isso Tem a Ver com a OBMEP
Questões de preenchimento de grafos com números aparecem na OBMEP porque combinam múltiplas habilidades:
- Fatoração em primos: para identificar conexões possíveis
- Raciocínio combinatório: para contar e eliminar possibilidades sistematicamente
- Demonstração de impossibilidade: para provar que certas configurações não existem
A habilidade mais importante aqui é a análise de casos extremos: identificar os números mais restritos e começar por eles. Estudantes que começam pelos fáceis acabam travados. Estudantes que identificam o 5 (conecta só ao 10), o 7 e o 11 (não conectam a nada) logo de início já sabem onde cada número pode e não pode ir.
Conclusão
Para resolver questões de preenchimento de grafos com divisores comuns:
- Fatorize todos os números disponíveis — primos primeiro
- Identifique as restrições mais severas: números primos sem múltiplos no conjunto são “ilhas” — eles ou ficam em posições isoladas ou são eliminados
- Comece a preencher pelos mais restritos — o que tem menos conexões vai primeiro
- Para provar impossibilidade: identifique quais números são ilhas e mostre que o conjunto de ilhas é grande demais para o número de eliminações permitidas
O fato de o 7 não ter nenhum múltiplo em {2, …, 11} e de o 11 também não ter é o núcleo da demonstração de impossibilidade — e é exatamente o tipo de raciocínio que a banca da OBMEP está avaliando.
Fonte: RESOLUÇÃO 2ª FASE OBMEP 2024 — NÍVEL 1 (QUESTÃO 4) — Canal Só o mi (@soomi_hokage)