> > 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 é <[EMAIL PROTECTED]> =========================================================================