Água para todos

[Sergio Alvarez]

Problema. 2n pontos são dados no plano, três a três não colineares. Exatamente n desses pontos são fazendas: F1,...,Fn. Os n pontos restantes são poços: W1,...,Wn. O programa Água Para Todos pretende ligar cada fazenda a algum poço através de um caminho retilíneo. Mostre que é possível estabelecer uma correspondência biunívoca entre fazendas e poços de modo que os caminhos ligando cada fazenda ao seu poço correspondente não se intersectem.

Esse problema retirado do livro Problem-Solving Strategies, de Arthur Engel (Springer-Verlag).

[Sergio Alvarez]

Dica. Olhe para os extremos.

Extremo de quê? Máximo ou mínimo?

Se você não adivinhar, talvez eu conte...

2009/11/9 Sergio Alvarez <sergi...@gmail.com>

[Sergio Alvarez]

Dica  (versão extendida). Há apenas um número finito de bijeções entre o conjunto das fazendas e o conjunto dos poços. E cada uma dessas correspondências biunívocas determina um sistema de caminhos retilíneos ligando cada fazenda ao seu poço correspondente. Considere o sistema de caminhos cujo comprimento total seja mínimo.

E aí, o que você faz com isso?

A equipe de planejamento do programa Água para Todos conta com a sua resposta.

Obs. O programa Água para Todos a que eu me refiro neste problema é fictício. Qualquer semelhança com a vida real é mera coincidência.

2009/11/11 Sergio Alvarez <sergi...@gmail.com>

[Cristiano Santos Benjamin]

Seja f a bijeção tal que o comprimento total dos caminhos seja o
mínimo. Vamos supor que exista uma fazenda f1 ligada a um poço p1 e
uma fazenda f2 ligada a um poço p2 tal que os caminhos se intersectam
e vamos chamar esse ponto de intersecção de t. repare que a soma
desses dois caminhos é igual f1 a t + t a p1 + f2 a t + t a p2. note
que há doi triangulos nessa sistema. O triangulo formado pelos pontos
f1, t e p2 e o triangulo formado pelos pontos f2, t e p1. Agora
considere um novo sistema onde f1 está ligado a p2 e f2 está ligado a
p1. observe que o caminho de f1 a p2 é menor que a soma dos outros
dois lados do triangulo f1 a t + t a p2 e também o caminho de f2 a p1
é menor que a soma dos outros dois lados do triangulo f2 a t + t a p1.
Logo a soma desses novos caminhos é menor do que a soma dos caminhos
anteriores e não existe intersecções entre os caminhos. Concluímos que
considerando f como a bijeção cuja soma dos caminhos seja mínima, não
haverá intersecções entre os caminhos. Note também que a existencia
desses triangulos vem do fato de que quaiquer tres pontos desse plano
não são colineares entre si. Logo esse novo ponto t e os pontos f1 e
p2 não são colineares e da mesma forma acontece com os pontos t, f2 e
p1.