Olimpíadas ⇒ (Cone Sul 1998) Combinatória

[Deleted User 24758]

Em Terra Brasilis existem n casas onde vivem n duendes, cada um em uma casa. Existem estradas de mão única de tal modo que:

• cada estrada liga duas casas;

• em cada casa começa exatamente uma estrada;

• em cada casa termina exatamente uma estrada.

Todos os dias, a partir do dia 1, cada duende sai da casa onde está e chega à casa vizinha. Uma lenda de Terra Brasilis diz que, quando todos os duendes regressarem à posição original, o mundo acabará.

(a) Demonstre que o mundo acabará.
(b) Se n=98, demonstre que é possível que os duendes construam e orientem as estradas de modo que o mundo não se acabe antes de 300.000 anos.

[leozitz]

me parece que o grafo disso são varios ciclos direcionados, vou começar pelo item b)
se a gente conseguisse inteiros positivos com mmc maior que 300000*366 o problema estaria resolvido, a gente poderia construir circulos onde cada cidade aponta para o proximo no sentido horario e eles iriam volta a posição inicial em cada ciclio apos o número de casas no ciclo
3+5+7+11+13+17+19+23 = 98
3*5*7*11*13*17*19*23 é maior que 300000 anos, considerando um ano de 366 dias (geralmente tem 365 mas mesmo que sempre acontece o pior caso de ter 366 não importaria)

depois tento resolver o item a), parece mais difícil