Ja sam pisao nešto tako po papirićima, koje sam jutros bacio, ali sam krajnji uslov rešio pomoću Wofram Mathematica.
Ovaj zadatak se može jednostavno rešiti ko zna matematiku, ZZZZ je dao postupak koji je do one priče o algoritmu u redu, ali posle može efikasnije da se uradi nekim matematičkim softverom.
Međutim, sinoć kasno nisam bio raspoložen za višu matematiku, pa sam zadatak rešavao kao što bi to uradio neko u osnovnoj školi, i to u 5. ili 6. razredu.
Zbog jednostavnosti, neka na početku ima 2n+1 lubenica (pošto očigledno mora biti neparan broj).
Prvi kupac: (2n+1)/2 + 1/2 = n + 1 (kupio n+1); ostalo n
Drugi kupac: imalo n = 3k + 2, kupio (3k + 2)/3 + 1/3 = k + 1; ostalo 2k + 1
Treći kupac: imalo 2k + 1 = 4m + 3, kupio (4m + 3)/4 + 1/4 = m + 1; ostalo 3m + 2
Četvrti kupac: imalo 3m + 2 = 5x + 4, kupio (5x + 4)/5 + 1/5 = x + 1, ostalo 4x + 3
Broj 4x + 3 mora biti deljiv sa 13, a broj x + 1 sa 12 (broj lubenica koji je kupio poslednji nakupac). Takođe, zanemarivanjem onih razlomaka, posle četvrtog nakupca ostaje otprilike približno 20% lubenica (da ne pišem sve detaljno, na primeru 120 lubenica, prvi kupac uzme 60, drugi 20, treći 10 i četvrti 6, što je 96, a ostane 24 što je 20% od 120). Kako je ukupno više od 1000 lubenica, znači da posle četvrtog kupca ostane približno više od 200 lubenica zbog onih razlomaka ako bi polazni broj bio 1001 lubenica, tako da ova dva uslova možemo proveravati za x >= 49. Ovi uslovi nisu dovoljno, jer treba i uslove za broj lubenica kupaca 1-3 uzeti u obzir, tj. preračunati n, k, m preko x, ali videćemo da su ova dva uslova dovoljna da se dođe do rešenja.
U Wolfram Mathematica koristimo FindInstance i nađemo rešenja za npr. x između 49 i 600:
Code:
FindInstance[Mod[4 x + 3, 13] == 0 && Mod[x + 1, 12] == 0 && 49 < x < 600, x, Integers]
i dobije se:
Code:
{{x -> 503}}
Ovo ne mora biti rešenje (jer treba da budu zadovoljene i jednačine po m, k i n u smislu deljivosti broja lubenica sa 12), ali proverom se dobija da je to rešenje (inače, ko ima vremena, može da odredi uslove i za broj lubenica prva tri kupca tako što će m, k, n izraziti preko x):
x = 503
Ostalo nakon 4. kupca: 4*503+3 = 2015
4. kupac kupio: x+1 = 503 + 1 = 504, pre njega bilo: 3m+2 = 5x+4 = 5*503+4 = 2519 => m = 839
3. kupac kupio: m+1 = 839 + 1 = 840, pre njega bilo: 2k+1 = 4m+3 = 4*839 + 3 = 3359 => k = 1679
2. kupac kupio: k + 1 = 1679 + 1 = 1680, pre njega bilo: n = 3k+2 = 3*1679+2 = 5039 => n = 5039
1. kupac kupio: n + 1 = 5039 + 1 = 5040, pre njega bilo: 2n + 1 = 2*5039 + 1 = 1079.
Ispravno bi bilo u "FindInstance" uzeti u obzir i uslove za prva 3 kupca, tj. izraziti n, k, m preko x, u ovom slučaju bi se dobilo isto da je x=503, međutim u nekom drugom slučaju možda ovo x ne bi bilo rešenje, pa bismo morali da nađemo neko sledeće za veće x i ponovo proveravamo...
Dakle, ovo je rešenje koje bi bilo jasno i nekom osnovcu (osim možda one funkcije u Wolfram Mathematica), bez priče o modularnoj matematici.
U uslovima koje je dao "ZZZZ" u prethodnoj poruci nedostaje i uslov da je x+1 deljivo sa 12 (onda je deljivo sa 2 i 6, tako da je taj uslov nepotreban) kao i sa 20 (već je deljivo sa 12, što znači sa 4, pa je dovoljno uzeti da je deljivo još i sa 5), što je broj lubenica koje su kupili kupci 1-4.
Ako se ne uzmu ovi uslovi, Mathematica pronalazi rešenje x = 1499 (da nema uslova da lubenice koje su kupili nakupci 1-4 mogu da se spakuju u gomilice po 12, ovo bi bilo rešenje, čak i ostatak može da se spakuje na gomilice po 13).
Code:
In[1]:= FindInstance[Mod[x, 2] == 1 && Mod[x, 3] == 2 && Mod[x, 4] == 3 && Mod[x, 5] == 4 && Mod[x, 13] == 4 && 1000 < x < 11000, x, Integers]
Out[1]= {{x -> 1499}}
Međutim, nešto nije u redu sa dodatnim uslovima, jer takođe pronalazi i rešenje x = 5399.
Code:
In[2]:= FindInstance[Mod[x, 2] == 1 && Mod[x, 3] == 2 && Mod[x, 4] == 3 &&Mod[x, 5] == 4 && Mod[x, 13] == 4 && Mod[x + 1, 12] == 0 &&
Mod[x + 1, 5] == 0 && 5000 < x < 5500, x, Integers]
Out[2]= {{x -> 5399}}
Code:
In[44]:= FindInstance[Mod[x, 2] == 1 && Mod[x, 3] == 2 && Mod[x, 4] == 3 && Mod[x, 5] == 4 && Mod[x, 13] == 4 &&
Mod[x + 1, 12] == 0 && Mod[x + 1, 5] == 0 && 10000 < x < 10100, x, Integers]
Out[44]= {{x -> 10079}}
Sad me već bole oči, ali ako "ZZZZ" može da predloži koji je uslov potreban u FindInstance da bi odmah rešenje bilo 10079 čak i ako opseg pretrage za x obuhvata i rešenje 5399.
Potpis
Blessed are those who can laugh at themselves, for they shall never cease to be amused.
