wmutex

Ok, doucement. Sa zicem ca S este setul de numere cautat. Desi problema nu enunta, probabil ca numerele pot fi adunate o singura data. Si iarasi, desi problema nu specifica, probabil ca nu e nevoie intotdeauna de 2 numere care sa fie adunate: unul singur poate fi suficient (altfel nu pot gasi 2 numere intre 1 si 1000000000 care adunate sa dea 1).

In grupul de numere S trebuie sa fie 1 (in caz ca cineva spune 1, nu pot aduna alte 2 numere care sa dea 1); daca notez cu "c" relatia de incluziune, atunci:

{1} c S


La fel, 2 trebuie sa fie in S, din aceleasi motive pentru care 1 trebuie sa fie in S:

{1, 2} c S


Cu numerele {1, 2} pot "forma" doar numerele {1, 2, 3}, deci 4 trebuie sa fie in S:

{1, 2, 4} c S


Cu numerele {1, 2, 4} pot "forma" doar numerele {1, 2, 3, 4, 5, 6, 7}, deci 8 trebuie sa fie in S:

{1, 2, 4, 8} c S

. . .

In general, cu numerele {1, 2, 2^2, 2^3, ..., 2^k} se pot forma toate numerele de la 1 la 2^(k+1) - 1. Chestia asta e "de baza" in baza 2. :-)

In cazul nostru, cu 30 de puteri "consecutive" ale lui 2 (k=29) se pot forma toate numerele de la 1 la 2^30-1 = 1073741823 (asta include toate numerele de la 1 la 1000000000).

Fara demonstatie de data asta (dar pot da exemple pentru oricine se indoieste si ofera un challenge), conditia suplimentara ca suma numerelor sa fie 1000000000 se poate obtine utilizand setul de numere:

S = {1, 2, 2^2, 2^3, ..., 2^28, 2^29 - 73741823}

Powhentall

DAP, am uitat sa spun ca nu se poate aduna mai mult de odata.Scuzati-ma ,ma grabeam sa merg la scoala.

catanedelcu

Ne vom folosi de reprezentarea binara a numerelor zecimale

Un miliard, in binar, este asa :

11101 11001 10101 10010 10000 00000

adica o insiruire de 30 de biti.

de aici, observam ca orice numar intre 1 si 111...1111 cu 30 de biti 1  se poate scrie ca o suma de maximum 30
de numere cu 1 pe prima pozitie si 0 pe celelalte pozitii .  exemplu

1100100011000100   =   51396  =

1000000000000000+       32768 +
 100000000000000+       16384 +
       100000000000+         2048 +
               10000000+           128 +  
                 1000000+             64 +
                         100 =              4 =
_____________________________
1100100011000100          51396

de aici deducem ca alegand cele 30 de numere cerute astfel :

1,10,100,1000,.....,1000000000...000(29 de zerouri)    (suntem in baza 2)

putem "compune" orice numar intre 1 si 111..111  (30 de-al de 1)

trecand acum in baza 10, numerele noastre vor fi evident:

2^0,   2^1,   2^2, ...   ,2^29

cu care putem sa scriem orice numar intre 1 si un miliard prin mecanismul din exemplu.

wmutex

Am uitat sa spun: solutia nu e unica. Daca cineva vrea sa incerce sa caute o solutie generala, poate pleca de la ideea ca numerele care sunt adunate pentru a da numarul cautat sunt, de fapt, submultimi ale setului cautat de numere S.

Daca notez cu U{S} multimea submultimilor lui S, atunci o solutie este de fapt o functie surjectiva Sum care aduna elementele submultimilor si da rezultate in {1, ..., 1000000000}:

Sum : U{S} ---> {1, ..., 1000000000}

Evident ca numarul de submultimi nevide ale unei multimi de 30 de elemente (adica nr. de elemente ale lui U{S}) este 2^30-1 = 1073741823, care este mai mare decat numarul de elemente-rezultat (1000000000). Rezulta ca trebuie ca, din 1073741823 de submultimi, 73741823 dintre ele trebuie sa aiba suma elementelor egala cu a unei alte submultimi din restul de 1000000000. Am capul prea plin de bere ca sa ma gandesc la asta, dar cred ca numarul de solutii posibile e urias, ceva de genul 2^73741823, sau ceva pe-acolo.

Eu ma las pagubas. :D