[obm-l] problema 3 nivel 3

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxxxxxxxxx>]

Oi.

Esta é uma solução alternatica para o problema 3 nível 3
(percorrendo as casas de um retangulo quadriculado sempre
se faz um U em algum momento). Escrevi para mandar para o Gugu
e acho que pode interessar a vocês.

Em um disco quadriculado, sejam
 F o número de faces,
Ai arestas internas
Ab arestas no bordo
Vi vértices no interior
Vb vértices no bordo
Ax arestas cortadas pelo nosso caminho.

Claramente Ab = Vb.
Por Euler
V - A + F = Vi - Ai + F = 2

Contando arestas interiores pelas duas pontas temos
2Ai = 4Vi + Vb - 4
pois por um argumento de curvatura o número de arestas interiores
que tocam o bordo é Vb - 4.

Analogamente
2F - 2 = 2Ax <= 2Vi + Vb - 4 = 2Ai - 2Vi

Mas esta desigualdade por Euler é uma igualdade.
Assim toda aresta interior que toca o bordo o que forma um circuito
(exceto so o disco for uma fileira única de quadrados) e desconecta
o caminho.

[]s, N.

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
O administrador desta lista é <nicolau@mat.puc-rio.br>
=========================================================================