Problema a fost propusa de Vasile Trofin, care a primit punctajul aferent acesteia (10 puncte). Multumim pentru propunere!

Soluţii corecte: George Teseleanu, Zoltan Szabo, Ionel-Vasile Pit-Rada, Viorel Manta, Stefan Gatachiu, Nicu Scutaru.

 

George Teseleanu:

n=1 -> (1) -> r(1) = 1

n=2 -> (2), (1,1) -> r(2) = 2

n=3 -> (3), (1,2), (1,1,1), (2,1) -> r(2) = 4

Presupunem ca pentru i > n avem s(i) = 2^(i-1). Atunci pe n il putem scrie ca n, 1+(n-1), 2+(n-2),...., (n-1)+1. Folosind pasul de inductie pentru n-1,...,1 obtinem s(n) = 1 + s(n-1) + s(n-2) +...+ s(1) = 1 + 2^(n-2) + 2^(n-3) +...+ 1 = 1 + 2^(n-1) - 1 = 2^(n-1).

 

Zoltan Szabo:

Este vorba despre partiționarea numerelor naturale în numere nenule în toate modurile posibile.

Rezolvare 1:

Dacă notăm cu P(N) numărul partiționărilor lui n, atunci observăm că există următoarea formulă recursivă:

P(0)=1 ( numărul 0 prin definiție se poate partiționa într-un singur fel)

P(1)=1 (numărul 1 se poate partiționa doar ca 1)

P(2) = P(0) + P(1) = 2 (2 se poate partiționa ca 2+... (numărul partițiiilor lui 0),   și ca 1+... (numărul partițiilor lui 1))

P(3)=P(0)+P(1)+P(2) = 4 (3 se poate partiționa ca 3+... (numărul partițiilor lui 0), 2+... (numărul partițiilor lui 1) , 1+... (numărul partițiilor lui 2) )

Observăm că este adevărată formula recursivă:

P(N)=P(0)+P(1)+...+P(n-2)+P(N-1)

Primii N-1 termeni din dreapta corespund relației P(N-1)=P(0)+P(1)+...+P(N-2)

Înlocuind în ecuație obținem:

P(N)=2*P(N-1)

Dezvoltăm termenii în mod repetat până ce ajungem la parametrul 1:

P(N)=2*P(N-1)=2²*P(N-2)=2³*P(N-3)=...=2^N-1*P(1)=2^N-1

Deci numărul de moduri de reprezentare a lui N ca sumă de numere naturale nenule este 2^N-1.

Rezolvare 2:

Vom considera un numerele naturale reprezentate în baza binară pe N biți.

De exemplu, toate numerele binare cu 3 biți sunt (100, 101, 110, 111)

Pentru fiecare număr binar în parte vom asocia fiecărui bit de 1 numărul natural egal cu 1+numărul de biți de 0 din secvența ce îl succede imediat, astfel obținem următoarele șiruri de numere:

(100) == {3} (1+2 de 0)

(101)=={2, 1}

(110)=={1, 2}

(111)={1,1,1}

Observăm că fiecare mulțime corespunzătoare unui număr are suma elementelor egală cu numărul de biți, toate cazurile sunt distincte, iat alte cazuri nu pot exista.

Pentru cazul general, mulțimea numerelor binare cu N biți, dintre care cel mai semnificativ bit are valoarea 1, are 2^N-1 elemente, fiecărui termen îi corespnde o descompunere distinctă așa cum am definit mai sus, deci am demonstrat astfel că numărul de moduri de reprezentare a lui N ca sumă de numere naturale nenule este 2^N-1.