Enunciado
No parlamento de Sikinia, cada parlamentario ten, como moito, 3 inimigos. Probar que os parlamentarios se poden separar en dous grupos, conseguindo que cada un deles teña, como moito, un inimigo no seu grupo.
Resolución
Pista
Considerar o número de inimigos que cada parlamentario ten no seu grupo. Como variaría de camiño ao noso reparto ideal?
Solución
Comezamos separando aos parlamentarios en dous grupos. Sexa o o número de inimigos que cada parlamentario ten no seu grupo. Agora supoñemos que o parlamentario ten, polo menos, 2 inimigos no seu grupo. Tendo como moito 1 inimigo no grupo contrario. Se cambia de grupo, o valor de decrecerá. Se volvemos a facer o mesmo con outros parlamentarios, o valor de seguirá diminuíndo, pero non pode diminuír eternamente, así que nalgún punto, chegará ao seu mínimo absoluto. Nota: Neste caso, o invariante é o decrecemento monótono de . E o feito de que non existe ningunha sucesión estrictamente decrecente de enteiros positivos é o que acaba garantizando que se chega á división en grupos esperada.
Dúbidas & Comentarios
Nesta sección pódesnos deixar as túas dúbidas e comentarios a cerca do problema anterior. Non teñas teima en preguntar, estamos aí para botar unha man!