problema interesanta

Contributii personale; Concursuri scolare; Olimpiada.
ralucast
utilizator
utilizator
Mesaje: 4
Membru din: 10 Iul 2012, 11:48

problema interesanta

Mesaj de ralucast » 10 Iul 2012, 11:53

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
senior
senior
Mesaje: 422
Membru din: 10 Mai 2012, 17:22
Localitate: Constanta

Mesaj de Zeus » 10 Iul 2012, 12:01

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

ralucast
utilizator
utilizator
Mesaje: 4
Membru din: 10 Iul 2012, 11:48

Mesaj de ralucast » 10 Iul 2012, 12:02

as fi avut nevoie de o rezolvare strict matematica..

Integrator
guru
guru
Mesaje: 1555
Membru din: 16 Ian 2011, 08:32

Re: problema interesanta

Mesaj de Integrator » 10 Iul 2012, 13:55

ralucast scrie: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
utilizator
utilizator
Mesaje: 4
Membru din: 10 Iul 2012, 11:48

Mesaj de ralucast » 10 Iul 2012, 14:48

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).

Avatar utilizator
ex-admin
profesor
profesor
Mesaje: 1278
Membru din: 25 Ian 2007, 00:29

Mesaj de ex-admin » 11 Iul 2012, 02:14

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
guru
guru
Mesaje: 1555
Membru din: 16 Ian 2011, 08:32

Mesaj de Integrator » 11 Iul 2012, 07:07

admin scrie: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
senior
senior
Mesaje: 422
Membru din: 10 Mai 2012, 17:22
Localitate: Constanta

Mesaj de Zeus » 11 Iul 2012, 10:44

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
senior
senior
Mesaje: 422
Membru din: 10 Mai 2012, 17:22
Localitate: Constanta

Mesaj de Zeus » 11 Iul 2012, 11:59


\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. :D\\
Dupa ce faci calculele incerci sa-l gasesti pe m.\\ (ptr ca poate fi si mai mic de 9) Succes la calcule.
[/tex]

Integrator
guru
guru
Mesaje: 1555
Membru din: 16 Ian 2011, 08:32

Mesaj de Integrator » 11 Iul 2012, 17:31

Zeus scrie: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! :oops:

Zeus
senior
senior
Mesaje: 422
Membru din: 10 Mai 2012, 17:22
Localitate: Constanta

Mesaj de Zeus » 11 Iul 2012, 21:35

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
senior
senior
Mesaje: 422
Membru din: 10 Mai 2012, 17:22
Localitate: Constanta

Mesaj de Zeus » 12 Iul 2012, 09:27

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

cybercracke
utilizator
utilizator
Mesaje: 3
Membru din: 02 Aug 2012, 16:14

Mesaj de cybercracke » 02 Aug 2012, 16:21

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

Zeus
senior
senior
Mesaje: 422
Membru din: 10 Mai 2012, 17:22
Localitate: Constanta

Mesaj de Zeus » 02 Aug 2012, 16:59

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

cybercracke
utilizator
utilizator
Mesaje: 3
Membru din: 02 Aug 2012, 16:14

Mesaj de cybercracke » 02 Aug 2012, 17:07

@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 :D .

Zeus
senior
senior
Mesaje: 422
Membru din: 10 Mai 2012, 17:22
Localitate: Constanta

Mesaj de Zeus » 02 Aug 2012, 17:15

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
utilizator
utilizator
Mesaje: 3
Membru din: 02 Aug 2012, 16:14

Mesaj de cybercracke » 02 Aug 2012, 17:32

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
senior
senior
Mesaje: 422
Membru din: 10 Mai 2012, 17:22
Localitate: Constanta

Mesaj de Zeus » 02 Aug 2012, 21:51

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
utilizator
utilizator
Mesaje: 1
Membru din: 17 Sep 2013, 14:32

cred ca am rezolvat-o

Mesaj de Akiba » 17 Sep 2013, 14:44

gt

Scrie răspuns
  • Subiecte similare
    Răspunsuri
    Vizualizări
    Ultimul mesaj