Re: [obm-l] Tres Problemas Russos

["Cláudio \(Prática\)" <claudio@xxxxxxxxxxxxxxxxxxxxxxx>]

>
> PROBLEMA 3) Existe um número impar de soldados em um exercício. A
distância
> entre dois quaisquer soldados é diferente da distancia entre quaisquer
dois
> outros. Cada soldado vigia o soldado que lhe esta mais próximo. Prove que
ao
> menos um soldado não está sendo vigiado.
>

Vamos chamar os soldados de 1, 2, ..., 2n+1.

Indução sobre n:

n = 1 (ou seja, existem 2*1 + 1 = 3 soldados):
Suponhamos s.p.d.g. que a menor distância entre dois soldados quaisquer seja
aquela entre os soldados 2 e 3. Então, o soldado mais próximo de 2 é o 3 e o
mais próximo de 3 é o 2. Assim, 2 vigia 3, 3 vigia 2 e ninguém vigia o
soldado 1. Logo, o resultado vale para n = 1.

Hipótese de Indução:
Dados 2(n-1) + 1= 2n-1 soldados (n >= 2) nas condições do enunciado, existe
um soldado que não está sendo vigiado.

Consideremos o caso de 2n+1 soldados nas condições do enunciado.
Suponhamos s.p.d.g. que a menor distância entre dois soldados seja aquela
entre os soldados 2n e 2n+1.
Então, o soldado mais próximo de 2n é o 2n+1 e o soldado mais próximo de
2n+1 é o 2n, ou seja 2n vigia 2n+1 e 2n+1 vigia 2n.

Se nenhum outro soldado vigia o soldado 2n ou o soldado 2n+1, então,
excluindo estes dois soldados do conjunto de soldados, obtemos um
subconjunto com 2n-1 soldados nas condições do enunciado. Nesse caso, a H.I.
garante a existência de um soldado não vigiado.

Por outro lado, se algum outro soldado vigia o soldado 2n ou o 2n+1, então
um destes dois é vigiado por pelo menos dois soldados. Como cada soldado
vigia exatamente um outro soldado, deve haver um soldado que não é vigiado
por ninguém.


Um abraço,
Claudio.

=========================================================================
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>
=========================================================================