Fie A o multime de n+1 numere naturale cuprinse intre 1 si 2n. Demonstrati ca exista in A doua numere diferite a si b astfel ca a sa-l divida pe b.

Inductie dupa n.

Ipoteza de inductie: "In orice multime de n+1 numere naturale cuprinse intre 1 si 2n exista doua numere diferite a si b astfel ca a sa-l divida pe b."

Vom demonstra ca : "In orice multime A de n+2 numere naturale cuprinse intre 1 si 2n+2 exista doua numere diferite a si b astfel ca a sa-l divida pe b."

Avem doua cazuri:
I. Exista n+1 numere din A cuprinse intre 1 si 2n.
Atunci, conform ipotezei de inductie rezulta concluzia.

II. A=B reunit cu {2n+1,2n+2}, unde B contine n numere cuprinse intre 1 si 2n.

Daca n+1 apartine lui B - atunci n+1,2n+2 apartin lui A si n+1 divide 2n+2, deci concluzia este asigurata.

Daca n+1 nu apartine lui B, atunci multimea B reunit cu {n+1} este formata din n+1 numere cuprinse intre 1 si 2n, si atunci, conform ipotezei de inductie rezulta ca exista in B reunit cu {n+1} numerele diferite a si b astfel ca a|b.

Exista trei subcazuri:
1) a,b diferite de n+1; In acest caz a,b apartin multimii A, deci are loc concluzia problemei.
2) a|n+1; Atunci a|2n+2, si iarasi concluzia problemei este demonstrata.
3) n+1|b, imposibil, caci b<=2n.

Cu aceasta, rezolvarea problemei este incheiata.

Solutie corecta! Iata si o alta solutie:

Scriem orice numar natural k sub forma

Cele n+1 numere au ca posibile parti impare 1,3,5,...,2n-1. Deci exista doua din ele care au aceasi parte impara. Cel mai mic dintre ele il divide atunci pe celalalt.

Solutia data de Pitagora este evident, mai frumoasa, mai scurta, si prezinta si avantajul de a putea fi inteleasa si de elevii de gimnaziu.

Sa remarcam insa ca solutia propusa de mine, desi mai lunga, este mai usor de intrevazut, si se realizeaza pas cu pas (ideea de a folosi metoda inductiei este fireasca, deoarece propozitia de demonstrat depinde de un numar oarecare natural, n).