Žentas nusipirko žurnalą „Наука в фокусе“. Kitaip nei kai kurie mūsų gentainiai, jis stengiasi gerinti rusų kalbos įgūdžius. Mes labai patenkinti, kad rusiškai su juo gali bendrauti Luko ir Emelie močiutė bei promočiutė, kurios niekada nesimokė anglų kalbos.
*
Ir aš šį tą įdomaus radau žurnale! Galėčiau vėl „užkurti“ diskusiją apie pasaulio atsiradimą, bet nebesinori… Geriau pateiksiu vieną ten rastą matematinį uždavinėlį.
*
Kazino žaidėjas turi tik 5 ir 7 vertės žetonų. Kokios didžiausios sumos jis negali pastatyti?
*
Atsakymas toks: 5*7-5-7=23.
Pastebėkime, kad formulė tinka ir porai 3, 5 (3*5-3-5=7) ir net porai 2, 3 (2*3-2-3=1).
Kodėl tokia formulė?
Ar ji tinka visoms skaičių poroms?
Pasimėgaukite!
Atsakymai
Burgis, 2012-08-07 16:59:02
Ačiū?…
Marius A., 2012-08-07 17:35:55
Hm, visai ne ačiū. 😉
Kodėl reikėjo pasakyti atsakymą, nedavus pagalvoti?
Ir dar su formule…
Burgis, 2012-08-07 18:33:18
Mariui A.: atsakymas ir formulė yra žurnale, bet ten nėra paaiškinimų… Kita vertus, eksperimentiškai (perrinkimu) lengva gauti atsakymą ir pastebėti vieną dėsningumą (kokį?), bet man pasirodė, kad sunkiau atsakyti į mano klausimus.
Marius A., 2012-08-07 22:39:33
Na, akivaizdu, jog ji netinka skaičiams, kurių vienas yra kito kartotinis, tarkim 2 ir 4 arba 3 ir 6.
Yra dar netinkančių, ieškoti?
Matas, 2012-08-07 23:04:07
Turbūt netiks visiems skaičiams, kurių didžiausias bendras daliklis nėra 1, ar ne tiesa?
Burgis, 2012-08-08 07:23:05
Siūlau pradėti nuo formulės įrodymo…
miklis, 2012-08-08 14:16:17
Pradžiai – lema: jei a ir b tarpusavyje pirminiai, tai aibės {a, 2a, 3a, …, (b-1)a} narius dalydami iš b gausime liekanų aibę {1, 2, … , b-1}.
—————————————————
Jos įrodymas šiek tiek primena Ferma mažosios teoremos įrodymą. Tarkim, kad lema su tam tikrais a ir b negalioja. Vis vien, akivaizdu, kad liekanų aibėje nulinė liekana nepasitaikys. Vadinasi, pagal Dirichle principą lemos negaliojimas įmanomas tik tada, kai liekanų aibėje bus dvi vienodos liekanos. Iš to seka, kad egzistuoja tokie natūralieji i ir j, mažesni už b, kad i*a ir j*a duotų tas pačias liekana. Ir čia gauname prieštarą, nes tada (i-j)*a dalijasi iš b, kas nėra galima.
***
Dabar grįžtam prie uždavinio apie monetas. Tarkim lošėjas turi žėtonus su vertėm a ir b, a>b, DBD(a,b)=1. Bet kuris monetų išdėstymas su natūraliuoju monetų skaičiumi n yra galimas tada ir tik tada, jei aibėje {n-ka | k∈N, n-ka>=0} bus bent vienas skaičius dalus iš b (tiks ir 0). Matome, kad skaičius n=ab-a-b netenkina šios savybės, nes tada turėsim aibę {ab-a-b, ab-2a-b, …, a-b}, kuri duos tas pačias liekanas dalijant iš b, kai ir aibė {-a, -2a, …, -(b-1)a}, o pagal lemą tai yra liekanų derinys {1, 2, 3,…, b-1}.
***
O kas, jei egzistuoja n>ab-a-b, su kuriuo dar vis neegzistuoja žėtonų kombinacija? Remiantis ankstesnėmis išvadomis, aibė, suformuota imant kiekvieno aibės {ab-a-b, ab-2a-b, …, a-b} elemento dalijant iš b liekaną, lygi {1, 2, …, b-1}, užrašykime šį teiginį tarkim taip:
{ab-a-b, ab-2a-b, …, a-b} -> {1, 2, …, b-1}.
Analogiškai, galios ir
{ab-a-b+q, ab-2a-b+q, …, a-b+q} -> {1+q, 2+q, …, b-1+q}, q∈N.
Tačiau su kiekvienu q, nedaliu iš b, gausim, kad aibėje {1+q, 2+q, …, b-1+q} egzistuoja nulinė liekana, vadinasi su visomis tokiomis q reikšmėmis lošėjas galės pastatyti ab-a-b+q monetų. Kad lošėjas negalėtų pastatyti monetų, q būtinai turi dalytis iš b.
*
Kai q>=b, pasikeičia vienas esminis dalykas: aibė {n-ka | k∈N, n-ka>=0} lygi nebe {ab-a-b+q, ab-2a-b+q, …, a-b+q}, o tampa dar ilgesne, nes prie jos narių jau pakliūva ir q-b>=0 (Čia n=ab-a-b). Jos ilgis yra nemažesnis už b. Tačiau tuomet tarp b-1 liekanų, gaunamų tos aibės narius dalijant iš b kažkuri turi pasitaikyti bent dukart. Panašiai kaip ir lemoje, narius, duodančius tas pačias liekanas, žymėkime ab-ia-b+q ir ab-ja-b+q. Šių narių skirtumas (i-j)a niekaip negali dalintis iš b ir čia vėl gaunam prieštarą. Todėl nėra tokios q>=b reikšmės, su kuria lošėjas negalėtų pastatyti monetų.
***
Valio įrodymas baigtas! Stebėtina, tačiau negaunam jokių prieštaravimų net kai viena iš lošėjo monetų lygi 1. Aukštesnis šio uždavinio lygis: lošėjas turi ne dvi o daugiau monetų 😉
miklis, 2012-08-08 14:28:57
Dar toks uždavinys:
Keliais būdais įmanoma sumokėti už prekę, kurios kaina 1Lt?
Įdomu, ar kas pasiūlys ne kompiuterinį šio uždavinio sprendimo variantą?
laisvamanis, 2012-08-08 17:43:26
brr, nėra smagu pasijusti nevisaverčiu…. pilnaverčio sūnaus tėčiu. aš tik chemikas, o jis – būsimas matematikas
miklis, 2012-08-08 19:11:00
Kuo chemikas turi jaustis nevisavertis prieš matemiką? Visos mokslo sritys turi būt kažkuo įdomios, reikalingos ir svarbios.
Burgis, 2012-08-08 19:47:50
mikliui: Jūsų reitingas pakiltų iki dangaus, jei visi žinotų, kas Jūs toks. Bet gal galėtumėte paprasčiau, paprastiems mirtingiesiems?
miklis, 2012-08-09 11:26:38
Kol kas noriu išlaikyti anonimiškumą. Pasakau tik tiek, kad esu baigęs Jūsų gimnaziją. Na, sunkoka matematinį uždavinį įrodyt nematiškai, bet gal viskas žemiškiau atrodytų, jei vietoj raidžių imtume konkrečius skaičius, tarkim tuos pačius 7 ir 5 vertės žėtonus. Vertės 5*7-7-5=23 neišeis sudėlioti, nes nė vienas iš skaičių {23, 16, 9, 2} nesidalija iš 5, galim tik pastebėti, kaip jie tvarkingai duoda liekanas 1, 2, 3, 4. Jei ieškotume didesnių verčių, su kuriom dar lošėjas negalėtų pastatyti žėtonų, tai vienu atveju turėtume vertę 23 paadidint 5k+1, 5k+2, 5k+3, 5k+4 (k∈N), bet tuomet visada bent vienas iš liekanų 1, 2, 3, 4 pasikeičia į 0, kas duoda prieštaravimą. O jei didiname per 5k, tai vertė turi padidėti bent iki 28, bet tuomet gauname ir 5 skirtingas liekanas dalijant iš 5, iš kurių bent viena turi būt nulinė – sekoje (28, 21, 14, 7, 0) nulinę liekaną duos nulis. Dabar suprantamiau gal parašiau?
praeivis, 2012-08-09 15:00:43
International Mathematical Olympiad 1983 m. trečias uždavinys – šio uždavinio apibendrinimas.
Paulius, 2012-08-09 17:07:49
Šiokia tokia idėja kilo ir man, tik sunkoka su aprašymu… Įrodymų nerašysiu kolkas, pabandysiu perteikti tik patį principą. Pridedu pavyzduką su 5 ir 7, kad būtų aiškiau.
- Visas pastatyti įmanomas sumas turint 5 ir 7 vertės žetonus, galima užrašyti, kaip
5*a + 7*b = S, kur a ir b atitinkamai 5 ir 7 vertės žetonų kiekis.
- Parinkime tokius skaičius, jog
7*3- 5*4 = 1 (operacija P)
5*3 – 7*2= 1 (operacija K)
Pavadinkime veiksmą, kai prie esamos sumos pridedame reiškinį (7*3- 5*4) operacija P, o pridedant reiškinį (5*3 – 7*2) – operacija K.
Matome, jog pridėjus bet kurį iš šių reiškinių, suma padidėja vienetu. Vadinasi, jei turime sumą S išreikštą, kaip S=5*a + 7*b, tai atlikdami operacijas P arba K, gauname jau sumą padidintą vienetu, ir kuri taip pat išliks pavidalo 5*A + 7*B. Taigi iš S visada galime gauti S+1 ir tokiu būdų visas įmanomas sumas aukštesnes už S. Tačiau pastebėkime, jog operacijas P ir K galime taikyti tik tada, kai a>3 arba b>1, kadangi A ir B nusako žetonų kiekį, tad šie skaičiai privalo būti neneigiami. Nesunku įsitikinti, kad bet kokia suma išreikšta pavidalu 5*a + 7*b ir didesnė už 5*3 + 7*1 =22 tenkins šią sąlygą. Tad telieka ją surasti.
23=7*5 -5 -7= 5*a + 7*b, – sprendinių neturi. Tuo tarpu :
24= 5*2 + 7*2.
Vienetu didesnę sumą galime gauti pritaikę operaciją K:
24+1= (5*2 + 7*2) + (5*3 – 7*2)=5*5=25
Toliau taikant vieną iš operacijų P arba K, gausime visas aukštesnes reikšmes už 23, vadinasi 23 – pati didžiausia suma, kurios negalima pastatyti.
Apibendrinimas:
Tarkime, jog turime x ir y vertės žetonus. Vadinasi, visas įmanomas pastatyti sumas galima užrašyti pavidalu x*a+y*b, kur a ir b – atitinkamai x ir y vertės žetonų kiekis. Be to, DBD(x;y) =1
1.Teiginys: lygtis x*y-x-y=x*a+x*b neturi teigiamų sveikųjų sprendinių (a;b), kai DBD(x;y)=1
2.Teiginys: lygtis x*y-x-y+1= x*a+x*b visada turės natūraliųjų sprendinių porą (a;b).
- Teiginys: visuomet galima parinkti tokius sveikuosius teigiamus skaičius a1, a2, b1, b2, jog
x*a1 – y*b2 = 1 (opercaija P)
y*b1 – x*a2 = 1 (operacija K)
ir a1+a2=y, o b1+b2=x.
- Teiginys: jeigu egzistuoja suma x*a +y*b, jog
x*a+y*b > (x*y-x-y),
tai arba a>(a2-1) arba b>(b2-1).
- Tegu S = (xy-x-y)+1 = x*A + y*B. Neprarasdami bendrumo, tarkime, jog B>(b2-1).
Tuomet taikome operacija P: (x*A + y*B) + 1=
=(x*A + y*B) +(x*a1 – y*b2)=
= x(A+a1) +y(B-b2)= S+1.
Kaip ir pavyzdyje su 5 ir 7, taikydami vieną iš operacijų P arba K, gauname visas įmanomas sumas didesnes už (x*y-x-y), vadinasi, (x*y-x-y) – pati didžiausia suma, kurios negalima pastatyti turint x ir y vertės žetonus.
Burgis, 2012-08-09 19:35:44
mikliui: o, kokia garbė gimnazijai! Bet apie anonimiškumą vėl parašysiu atskiroje temoje.
***
Visiems: jūs šaunuoliai! Bet aš vis tik neimčiau šaudyti iš patrankos į žvirblį…
*
Pabandykime taip. Kalbama apie lošimo žetonus. Ko gero, neverta nagrinėti skaičių, didesnių už 9, tiesa? Paėmus bet kokią porą skaičių iki 9, lengva sudėlioti grandinėles iki tos vietos, kur visos sumos tampa įmanomos. Pavyzdžiui, tebus tie skaičiai 3 ir 7. Galimos sumos, naudojant tik žetonus su 3: 3, 6, 9, 12, 15, …
Galimos sumos, naudojant tik žetonus su 7: 7, 14, 21, 28, …
Panaudoję 3 ir 7, gauname dešimt ir iškart nutiesiame nuo šio skaičiaus grandinėlę, pridėdami kartotinius 3 ir kartotinius 7: 13, 16, 19, 21, 24, …; 17, 24, 31, …
Pastebėkime, kad iki 30 nepatikrintų liko visai nedaug… Galima patikrinti: 11 (negalimas) ir … ?
***
Tai – empirinis sprendimas. Bet gal ir pakanka?
Lėlys, 2012-10-17 21:33:17
Mano vaikis atsako į antrą klausimą be jokių matematinių vedžiojimų: Formulė netinka toms skaičių poroms, kuriose nėra nei vieno nelyginio skaičiaus (tarkim 4, 6)….
Gal per paprastas atsakymas, bet jis akivaizdus 🙂