[es] - Zadatak o proizvodu i sumi

pixelmania
Marko Jovanović
Beograd

Član broj: 3766
Poruke: 129
*.adsl.sezampro.yu.

ICQ: 113685276
Sajt: www.pixelmania.go.to

Profil

Zadatak o proizvodu i sumi

^{16.01.2003. u 21:30 - pre 258 meseci}

E ljudi, treba mi hitno vaša pomoć, a zadatak je stvarno zanimljiv (i rešiv, samo ne znam kako).

Jedan dečak je zamislio dva cela broja između 2 i 99. Jednom drugu (imenujmo ga P) je rekao samo proizvod ta dva broja, drugome (imenujmo ga S) je rekao samo zbir ta dva broja.
Kasnije su se P i S sreli. Evo kako je tekao njihov razgovor:

P: Ja ne znam o koja dva broja se radi.
S: Već sam znao da ne znaš!
P: Sada ja znam!
S: Sada i ja znam!!

Dakle, vi treba da rešite dilemu o koja se to dva zamišljena broja radi.

Unapred hvala,
pixelmania

Bojan Bašić: izmenjen naslov

[Ovu poruku je menjao Bojan Basic dana 01.04.2004. u 02:31 GMT]

coito ergo sum - Marko Jovanović

Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.rcub.bg.ac.yu

Sajt: localhost

+5 Profil

Re: JAKO JAKO HITNO!!! (A UZGRED ZANIMLJIVO)

^{17.01.2003. u 03:08 - pre 258 meseci}

zadatak nije dobro postavljen (ili mu fali josh neki uslov). decak S nikako nije mogao da zna koji su to brojevi.

elem, da dokazem moju predjasnju tvrdnju:

podjimo od prve izjave decaka S: "Već sam znao da ne znaš!".

sta ovo znaci. kako je S mogao da zna da li P zna brojeve ili ne? Jedino kako je P mogao na osnovu proizvoda da odredi dva nepoznata broja je ako bi ti brojevi bili prosti. znaci, ako je recimo proizvod 35, P bi mogao da zna da su to brojevi 5 i 7.

e sad, ako je S bio siguran da P ne zna, onda je S znao da zamisljeni brojevi nisu prosti. kako je S to mogao da zna. pa tako sto je znao da se broj koji je on znao (zbir) nikako ne moze predstaviti kao zbir dva prosta broja. znaci da je zbir nepoznatih brojeva (koji je S znao) mogao biti recimo 11, 17, 23, 27, 29, 35, 37, 41, 47, 51, 53, 57, 59, 65, 67, 71, 77, 79, 83, 87, 89, 93, 95, 97 ili 101 (probajte da dobijete neki od ovih brojeva kao zbir dva prosta broja).

e sad, kada je S rekao P da je znao da P ne zna brojeve, onda je P mogao da zakljuci isto sto i S, i da zna da je zbir nepoznatih brojeva jedan od gore-pomenutih.

sada je za svoj proizvod mogao da isproba sve moguce kombinacije, i cim nadje neku od gore-pomenutih, znao je resenje. ali S nije imao nikakve sanse da sazna resenje, zato sto nije imao dovoljno informacija. evo dva primera, koja uzrokuju da P zna resenje, ali S ga ne zna:

brojevi: 2 i 9
P zna proizvod: 18
S zna zbir: 11

P razmislja: 18=2*9 i 18=3*6
P kaze: je ne znam koji su brojevi
S razmislja: zbir je 11. znaci nisu prosti, znaci:
S kaze: znao sam da ne znash.
P razmislja (uz gorepomenutu logiku) zbir je jedan od brojeva 11, 17,
P razmislja: moji moguci zbirovi su 11 i 9.
P nalazi da se 11 poklapa u svacijim zbirovima, i otkriva da su brojevi 2 i 9
P kaze: sad znam
S nema dovoljno informacija da zna bilo sta...

zasto S nema dovoljno informacija. pa zato sto par 2 i 9 nije jedini koji zadovoljava sve kriterijume zadatka. i brojevi 3 i 8 zadovoljavaju istu pricu. i mnogi drugi parovi brojeva... evo opet istog dijaloga (i razmisljanja) sa pocetnim brojevima 3 i 8. zapazite da do S stizu apsolutno iste informacije kao u prethodnom slucaju, i on mora isto da razmislja, tako da on ne moze biti siguran da li su dva zamisljena broja 3 i 8, ili 2 i 9: (boldovane su sve informacije koje S cuje / zna, i sve sto on razmislja, da bi se videlo da su iste kao i u prethodnom slucaju)

brojevi: 3 i 8
P zna proizvod: 24
S zna zbir: 11

P razmislja: 24=2*12 i 24=3*8 i 24=4*6
P kaze: je ne znam koji su brojevi
S razmislja: zbir je 11. znaci nisu prosti, znaci:
S kaze: znao sam da ne znash.
P razmislja (uz gorepomenutu logiku) zbir je jedan od brojeva 11, 17, 23
P razmislja: moji moguci zbirovi su 14 i 11 i 10.
P nalazi da se 11 poklapa u svacijim zbirovima, i otkriva da su brojevi 3 i 8
P kaze: sad znam
S nema dovoljno informacija da zna bilo sta...

blogče :: unescaped beta^{^» ^{go-paste extenzija} ^» ^{reč dana: backup} ^» ^{bočne koalicije}}

Odgovor na temu

pixelmania
Marko Jovanović
Beograd

Član broj: 3766
Poruke: 129
*.adsl.sezampro.yu.

ICQ: 113685276
Sajt: www.pixelmania.go.to

Profil

Re: JAKO JAKO HITNO!!! (A UZGRED ZANIMLJIVO)

^{17.01.2003. u 22:24 - pre 258 meseci}

Hvala, zombie.

Ipak, jeste da je zadatak prepričavan, ali s obzirom na to da je bio na nekom od prošlogodisnjih takmičenja (arhimedesovo, tako nešto...) - trebao bi biti tačno postavljen. Dok sam tražio na internetu da nije neko možda dao obrazloženje naišao sam da je Dejan Ristanović (urednik PC Pressa) na svom sajtu dao sličan zadatak, ali nije dao i objašnjenje http://user.sezampro.yu/~dejanr/Refer/pit100.htm .Ono što mi se čini da je suštinska razlika je što je njegova granica ta dva broja izmedju 2 i 20. Sada mi se već jako spava (imao sam 13 časova danas - idem i u muzičku

) i ne mogu da proverim da li je na taj način moguće naći rešenje... Ipak, hvala na pomoći.

coito ergo sum - Marko Jovanović

Odgovor na temu

nervozna
sicg

Član broj: 1868
Poruke: 317
*.pg-dialup.cg.yu

ICQ: 153640035

Profil

Re: JAKO JAKO HITNO!!! (A UZGRED ZANIMLJIVO)

^{18.01.2003. u 01:08 - pre 258 meseci}

Zombie, pogrešio si u rezonovanju.

Broj 11 ne može da bude tražena suma, jer baš iz primera koji si naveo se lepo vidi da ta suma mora biti eliminisana. Zašto? U slučaju koji si naveo, S ne bi bio u stanju da kaže o kojim se brojevima radi!!! Dakle, cilj je da se od mogućih suma nađe ona za koju neće biti dvoumljenja između parova brojeva koji zadovoljavaju iste uslove. Dakle, ne možeš unapred da pretpostaviš rešenje (pa još netačno), moraš ga eliminacijom tražiti.

Osim toga, broj 2 je prost broj (deljiv jedino sobom i jedinicom), pa se moraju isključiti i sume koje nastaju onda kad je 2 jedan od sabiraka.

Prema tome, polazne pretpostavke ne mogu biti rešenja već sume.
Znači, ako počnemo razmatranje od sume 11, parovi brojeva koji mogu odgovarati su (3,8) i (4,7) (između ostalih). Ako bi proizvod bio 24, P bi odmah odredio brojeve 3 i 8. Ali, da je proizvod bio 28, opet bi se odmah mogli odrediti brojevi 4 i 7. U oba slučaja suma je ista. Međutim, upravo zbog takve nejednoznačne situacije, S ne bi mogao da se odluči između ova dva para brojeva i ne bi mogao da kaže da zna o kojim se brojevima radi. Na taj način, suma 11 se eliminiše kao moguća.

Sve ostale sume se tako proveravaju i samo jedna daje jednoznačno rešenje. To je suma 17, proizvod je 52, a traženi brojevi su 4 i 13.

poz

[Ovu poruku je menjao nervozna dana 18.01.2003. u 03:36 GMT]

beeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeezi

Odgovor na temu

nervozna
sicg

Član broj: 1868
Poruke: 317
*.pg-dialup.cg.yu

ICQ: 153640035

Profil

Re: JAKO JAKO HITNO!!! (A UZGRED ZANIMLJIVO)

^{18.01.2003. u 01:17 - pre 258 meseci}

PS.Jedan info sa neta

Ovaj zadatak je proveren računarom i pokazalo se da gornje ograničenje intervala od 2 do x ne utiče na rečenje zadatka. U opsegu od 2 do dva miliona računar je davao isti odgovor. Najzanimljivije je da verovatno nigde nećete naći način na koji se dolazi do rešenja. Na netu.

poz

beeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeezi

Odgovor na temu

pixelmania
Marko Jovanović
Beograd

Član broj: 3766
Poruke: 129
*.adsl.sezampro.yu.

ICQ: 113685276
Sajt: www.pixelmania.go.to

Profil

Re: JAKO JAKO HITNO!!! (A UZGRED ZANIMLJIVO)

^{18.01.2003. u 10:37 - pre 258 meseci}

nervozna, ipak mi ostaje jedna nedoumica.

Parovi brojeva za 17 su (2,15) (3,14) (4,13) (5,12) (6,11) (7,10) (8,9)
dakle, zar ne postoji opet nedoumica da li je u pitanju (3,14) ili (4,13) (ili bilo koji drugi par). Ako bi proizvod bio 42, P bi odmah odredio brojeve 3 i 14, ali da je bio 52, opet bi se odmah moglo odrediti brojevi 4 i 13. U oba slučaja je suma ista - 17, pa S ne može da zna o koja dva broja se radi.

Zar tako ne bi trebalo isto eliminisati i broj 17 ? Ili ja tu nešto nisam dobro razumeo?

coito ergo sum - Marko Jovanović

Odgovor na temu

Noe
Stanisa S
PTR

Član broj: 6010
Poruke: 306
*.ptt.yu

Sajt: www.istanco.rs

+6 Profil

Re: JAKO JAKO HITNO!!! (A UZGRED ZANIMLJIVO)

^{18.01.2003. u 15:22 - pre 258 meseci}

Zombie je izgleda bio u pravu fali tu jos neki uslov.

rs domeni , rs hosting ,
.ES Domain ,
.IT Domain

Odgovor na temu

-zombie-
Tomica Jovanovic
freelance programmer
ni.ac.yu

Član broj: 4128
Poruke: 3448
*.rcub.bg.ac.yu

Sajt: localhost

+5 Profil

Re: JAKO JAKO HITNO!!! (A UZGRED ZANIMLJIVO)

^{18.01.2003. u 17:50 - pre 258 meseci}

evo da se ispravim: definitivno je zadatak dobro postavljen, i definitivno je resenje par (4, 13)

i to si nervozna bila u pravu. ali mi se cini da si resenje samo procitala negde na netu (kao i ostale navedene podatke o problemu) i da ti ono samo (resenje) nije bash najjasnije. evo zasto:

Citat:

Osim toga, broj 2 je prost broj (deljiv jedino sobom i jedinicom), pa se moraju iskljuciti i sume koje nastaju onda kad je 2 jedan od sabiraka

a brojevi koje si ti pominjala nisu prosti. 3, 7, ...? i jedan od brojeva samog resenja je prost: 13 (a i da, mislim da svi ovde znamo sta su prosti brojevi)

ja sam rekao da od zamisljenih brojeva, ne smeju biti OBA prosta. jedan naravno moze (sto je skoro uvek i slucaj)

znaci, 2 definitivno moze biti deo resenja, iako je prost (kao i 3, 7 i 13). to sto 2 nije resenje, to je druga stvar. (ne znaci da nije trebalo proveravati za 2!)

Citat:

Ako bi proizvod bio 24, P bi odmah odredio brojeve 3 i 8.

a 4*6? a 2*12?

no, nemam sada vremena da objasnjavam zasto je jedini moguci zbir 17. (bilo bi duze nego moj prvi post). mozda malo kasnije...

a sto se resenja tice, ne znam zasto ga nema nigde na netu. nije nista epohalno. program za resavanje se pise za najvise pola sata. i ja sam ovo nalazenje brojeva koji se ne mogu dobiti kao zbir prostih brojeva resio programcetom koji sam napisao za 15ak minuta (nisam ni ja tolko dokon da trazim rucno ;). za ovaj drugi deo (sada kada sam shvatio do kraja) mi ne bi trebalo vise od 15ak min...

blogče :: unescaped beta^{^» ^{go-paste extenzija} ^» ^{reč dana: backup} ^» ^{bočne koalicije}}

Odgovor na temu

pixelmania
Marko Jovanović
Beograd

Član broj: 3766
Poruke: 129
*.adsl.sezampro.yu.

ICQ: 113685276
Sajt: www.pixelmania.go.to

Profil

Re: JAKO JAKO HITNO!!! (A UZGRED ZANIMLJIVO)

^{18.01.2003. u 18:16 - pre 258 meseci}

zombie, jel' bi mogao da mi objasniš do sutra, jako bi mi značilo... please please please

coito ergo sum - Marko Jovanović

Odgovor na temu

nervozna
sicg

Član broj: 1868
Poruke: 317
195.66.187.*

ICQ: 153640035

Profil

Re: JAKO JAKO HITNO!!! (A UZGRED ZANIMLJIVO)

^{19.01.2003. u 00:03 - pre 258 meseci}

Ne, ne, ne, nisam ja pročitala rešenje na netu, niti mi je nejasno. Kad sam rekla da 2 ne može biti jedan od sabiraka, mislila sam na sumu dva prosta broja. Često sam nailazila na ljude koji broj 2 ne smatraju prostim, samo zato što je paran.

Zašto se isključuju sve parne sume? Postoji hipoteza u matematici (ne sećam se kako se zove), dokazana do broja od nekoliko desetina miliona, koja kaže da se svaki paran broj može predstaviti kao suma dva prosta broja. To je odgovor na tvoje pitanje zašto rešenja ne mogu biti parovi parnih brojeva (jer im je suma parna, a parne sume smo eliminisali).

Zašto par (2,15) nije rešenje? Njihov proizvod je 30, koji je proizvod i brojeva (5,6), pa se P ne bi mogao odlučiti između sume 11 i 17. Tako za sve ostale parove brojeva koji daju sumu 17. Na taj način se dolazi do para (4,13) kao rešenja. Naime, proizvod ovih brojeva je 52. Takođe i brojeva (2,26). Međutim, suma brojeva 2 i 26 je 28, a broj 28 je isključen kao moguća suma, jer je paran.

To je kompletno objašnjenje zadatka, sa detaljima.

Naravno da rešenje nije epohalno, zato sam i napisala da je najzanimljivije što objašnjenja nema na netu. Niti je problem napisati program koji će rešiti zadatak umesto našeg mozga. Računar se lepo našao da proveri jesmo li dobro razmišljali, ako smo razmišljali. A nekad i da uradi zadatak umesto nas.

poz

beeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeezi

Odgovor na temu