Intr-un parlament fiecare membru are cel mult 3 inamici politici. Sa se arate ca parlamentul poate fi divizat in doua camere astfel ca fiecare membru sa fie in aceasi camera cu cel mult un inamic al sau.

Vom da demonstratia prin inductie matematica dupa numarul n al parlamentarilor.

Pentru n=2, proprietatea este evident adevarata.

Presupunand proprietatea adevarata pentru k parlamentari, vom demonstra ca ea ramane valabila si pentru k+1 parlamentari.

Intr-adevar, conform ipotezei de inductie, k parlamentari pot fi divizati in doua camere cu respectarea conditiei din problema. Cel de-al k+1 - lea parlamentar, avand cel mult 3 inamici, rezulta ca cel putin in una din cele doua camere nu va exista mai mult de 1 inamic al sau (altfel el ar avea cel putin 2+2=4 inamici).

Plasand acest al k+1 - lea parlamentar in aceasta camera, conditia problemei va fi astfel respectata pentru toti cei k+1 parlamentari.

Demonstratia este astfel incheiata.

Solutia aceasta nu merge si iata de ce:

Fie Ion cel de-al k+1 parlamentar. Il punem in camera unde mai exista un inamic al lui (pe care-l cheama Gheorghe) si intr-adevar in acea camera Ion nu are decat un inamic. Dar in acea camera Gheorghe poate avea deja un inamic. Cand l-am pus pe Ion are deja 2.

[Citat] Solutia aceasta nu merge si iata de ce: Fie Ion cel de-al k+1 parlamentar. Il punem in camera unde mai exista un inamic al lui (pe care-l cheama Gheorghe) si intr-adevar in acea camera Ion nu are decat un inamic. Dar in acea camera Gheorghe poate avea deja un inamic. Cand l-am pus pe Ion are deja 2.

Just!
Eroarea mea este impardonabila (poate numai de ora foarte tarzie la care s-a produs)! Atentie, ora afisata pe site nu este ora reala (a Romaniei), ci cu 10 ore in urma (probabil serverul pro-didactica se afla in SUA).

Este adevarat ca ora de pe site nu este cea a Romaniei. Serverul pe care lucreaza pro-didactica.ro se afla in SUA. Suntem inca in faza [beta] asa ca mai avem inca asemenea corecturi de facut. Multumim ca ne aduceti aminte

In alta ordine de idei, suntem bucurosi ca avem utilizatori ce ne viziteaza la asemenea ore