problema interesanta

[ralucast]

Am o problema interesanta pe care nu o pot rezolva. Ma poate ajuta cineva?

Avem o functie f(n) care calculeaza de cate ori apare cifra 2 de la 1 la n.
De exemplu: f(2)=1, f(12)=2 (pana la 12, cifra 2 apare de 2 ori)
Intrebarea este : care este primul numar n pentru care f(n) = n ?


Ms!

[Zeus]

Fa un program intr-un limbaj cunoscut de tine... si-ti da rezultatul!

[ralucast]

as fi avut nevoie de o rezolvare strict matematica..

[Integrator]

Am o problema interesanta pe care nu o pot rezolva. Ma poate ajuta cineva?

Avem o functie f(n) care calculeaza de cate ori apare cifra 2 de la 1 la n.
De exemplu: f(2)=1, f(12)=2 (pana la 12, cifra 2 apare de 2 ori)
Intrebarea este : care este primul numar n pentru care f(n) = n ?


Ms!

De unde este aceasta problema?

[ralucast]

problema initiala a fost asta:
http://projecteuler.net/index.php?secti ... ems&id=156

dar profesorul meu mi-a modificat cerinta si conditiile.
folosind un algoritm C++, am ajuns la concluzia ca solutia se afla intre 240 000 000 si 238 000 000 (algoritmul e destul de subred).

[ex-admin]

Cateva idei ce ar putea fi utile:

1. functia este crescatoare (nu strict)

2. f(10^k)=k * 10^(k-1) - Avand in vedere ca este ora 2 noaptea, va rog sa verificati daca am dreptate cu aceasta egalitate.

3. folosind relatia anterioara gasim ca f(10^10)=10^10, deci am gasit un numar cu proprietatea ceruta dar oare, este cel mai mic?

[Integrator]

Cateva idei ce ar putea fi utile:

1. functia este crescatoare (nu strict)

2. f(10^k)=k * 10^(k-1) - Avand in vedere ca este ora 2 noaptea, va rog sa verificati daca am dreptate cu aceasta egalitate.

3. folosind relatia anterioara gasim ca f(10^10)=10^10, deci am gasit un numar cu proprietatea ceruta dar oare, este cel mai mic?

1. Cum demonstram ca functia este crescatoare si pe ce interval anume?
2. Pentru nu se verifica relatia deoarece .
3. Cam greu de numarat cati de 2 sunt.......

[Zeus]

1. Functia intr-adevar e crescatoare cum a zis domnu` admin (nu strict).
2. Din cate vad eu e adevarata f(100)=20 cred ca nu l-ai numarat pe 22 de 2 ori Integrator.
3. Cred ca exista si un numar mai mic.
Ma apuc de demonstratie!

[Zeus]

\rm{f(10^k)=k*10^{k-1}... f(2*10^k)=2*k*10^{k-1}+1.\\
f(c*10^k)=10^k+c*k*10^{k-1} cu 2<c<10.\\
Se observa ca functia f e 'aditiva' adica\\f(c_{0}+c_{1}*10^1+...+c_{m}*10^m)=f(c_{0})+f(c_{1}*10^1)+...+f(c_{m}*10^m).\\ Avand relatiile astea incepem sa cautam pe f(x)=x.
f(10^{10})=10^{10}\\=> Tb sa cautam numere mai mici ca 10^{10}.
f(10^9)=9*10^8<10^9. f(2*10^9)=18*10^8+1<20*10^8\\
f(3*10^9)=10^9+27*10^8>3*10^9.=>m=9 c_{9}=2.\\
Si acuma ce tb sa faci din aproape in aproape ai asha :\\ f(c_{8}*10^8+2*10^9)<c_{8}*10^8+2*10^9 si\\f((c_{8}+1)*10^8+2*10^9)>(c_{8}+1)*10^8+2*10^9. Afli c_{8} (0<=c_{8}<=8)\\ ptr care se indeplinesc cele 2 conditii. Iar apoi afli c-urile... pana ajungi\\ la gasirea intregului numar. Sper ca ai inteles procedeul si\\ nu ma chinui sa-ti fac toate calculele. \\
Dupa ce faci calculele incerci sa-l gasesti pe m.\\ (ptr ca poate fi si mai mic de 9) Succes la calcule.
[/tex]

[Integrator]

1.
2. Din cate vad eu e adevarata f(100)=20 cred ca nu l-ai numarat pe 22 de 2 ori Integrator.
Ma apuc de demonstratie!

Asa este!Am fost neatent!

[Zeus]

n=242463827.
P.S. Atentie! Cand unul din coeficienti e 2 la termeni se adauga f(ce ramane fara ce-i in fata lui 2 inclusiv 2)+(ce ramane fara ce-i in fata lui 2 inclusiv 2).
Deci f(524)=f(500)+f(20)+f(4)+4=208.
f(12524)=f(10000)+f(2000)+f(524)+524=5333.

[Zeus]

Deci pana la urma vrei rezolvarea completa sau nu?... ca n-ai zis nimic! Daca da ti-o scriu !

[cybercracke]

@Zeus, cred ca raspunsul tau este gresit, eu am gasit ca n=28263827. sunt curios cum ai rezolvat problema propusa de ralucast.

[Zeus]

Aveti dreptate domle... asha este n-am fost atent la gasirea numarului de cifre al numarului n.

[cybercracke]

@zeus de fapt si raspunsul tau este corect dar nu este primul n. raspunsul gasit de tine reprezinta al 3-lea n. primul si cel care se cere in problema este n=28263827 pe urma al 2-lea n=35000000, al 3-lea n=242463827 si tot asa. eu am rulat programul in intrvalul 1 - 999999999 si am mai gasit inca 3 valoari pt n si il las sa mai calculeze pana o sa crape procesorul .

[Zeus]

Amice inteleg acelasi lucru l-am facut si eu. Ce nu inteleg si nici u n-ai precizat este daca stii sa rezolvi problema?... eu mi-am gasit greseala din rationament. In fine, nu orice prb se poate pune pe calculator.

[cybercracke]

a o rezolva inseamna a ajunge la un raspuns corect. eu am ajuns la rezultatul care indeplinsete conditiile specificate in enuntul problemei. faptul ca cineva poate sa rezolve o problema intr-un mod este ok, daca acea persoana poate sa rezolve aceesi problema in mai multe moduri este excelent. de fapt asta m-ai intrebat, daca stiu sa rezolva problema si in alt mod, da? raspunsul meu este urmatorul: am un cap pe umeri si pot si stiu sa il folosesc. Referitor la afirmatie ta, ca nu orice problema se poate pune pe calculator. Gresesti! Orice problema se poate pune pe calculator daca stii cum!

[Zeus]

N-am chef sa ma contrazic cu tine... asha ca fie ca tine... felicitari si toate cele... nu-mi bat capu` aiurea... deci ca tine sa fie.

[Akiba]

gt