Questão 2. Suponha que o governo decida construir o menor número possível de pontes de forma a garantir que, utilizando as pontes, seja possível ir de bicicleta de qualquer ilha para qualquer outra ilha atravessando exatamente uma das pontes. Nesse caso, qual o menor número de pontes que o governo deve construir?
Passo 1
O enunciado pede o menor número de pontes que o governo deve construir de modo que, usando apenas as pontes, seja possível ir de bicicleta de qualquer ilha para qualquer outra ilha atravessando exatamente uma das pontes. Vou introduzir uma notação simples para ficar claro o que se tem:
- Seja
o número de ilhas (assumimos inteiro, ). - A exigência “ir de qualquer ilha para qualquer outra atravessando exatamente uma das pontes” significa que, para quaisquer duas ilhas distintas, deve existir uma ponte que as ligue diretamente.
O enunciado pede então: qual é o menor número de pontes necessário em função de
?
Passo 2
Modelagem do problema (ideia-chave, explicada devagar). Pense nas ilhas como vértices de um grafo e em cada ponte como uma aresta que liga dois vértices. Uma ponte que liga a ilha
à ilha
permite ir de
para
atravessando exatamente uma ponte. Assim, a exigência do enunciado diz que entre quaisquer dois vértices distintos deve haver uma aresta. Um grafo com essa propriedade é conhecido como grafo completo.
Passo 3
O que significa “aresta entre quaisquer dois vértices”? Significa que precisamos uma aresta para cada par não-ordenado de ilhas distintas. Cada ponte conecta exatamente duas ilhas, logo corresponde a exatamente um par não-ordenado
com
. Portanto o problema se reduz a contar quantos pares não-ordenados distintos de ilhas existem.
Passo 4
Contagem dos pares (a parte combinatória, explicada passo a passo). Para formar um par ordenado de ilhas podemos escolher a primeira ilha de
maneiras e a segunda de
maneiras, totalizando
pares ordenados. Mas uma ponte entre
e
não distingue a ordem: o par
e o par
representam a mesma ponte. Logo cada ponte foi contado duas vezes em
. Para obter o número de pares não-ordenados, dividimos por
. Assim obtemos a fórmula
Passo 5
Verificação por exemplos pequenos (pra sentir a ideia).
- Se
, há ponte — faz sentido: uma única ponte liga as duas ilhas. - Se
, há pontes — cada par de ilhas tem sua ponte direta.
Esses exemplos mostram que a fórmula dá resultados plausíveis.
Passo 6
Argumento de minimalidade (por que não se pode ter menos). A exigência pede que todo par de ilhas distintas seja ligado diretamente por uma ponte. Como cada ponte pode ligar no máximo um par não-ordenado de ilhas (isto é, duas ilhas específicas), é necessário ter pelo menos tantas pontes quanto pares não-ordenados de ilhas. Portanto nenhum esquema com menos de
pontes satisfaz o enunciado. Por outro lado, construir exatamente uma ponte para cada par de ilhas (o grafo completo) cumpre a exigência. Logo esse número é atingível e é o mínimo.
Passo 7
Observações finais e casos degenerados. Para
ou
não há pares de ilhas distintas, então a fórmula também dá
pontes, o que faz sentido.