Vita:Diofantoszi egyenlet

Ez a szócikk témája miatt a matematikai műhely érdeklődési körébe tartozik.
Bátran kapcsolódj be a szerkesztésébe!

Besorolatlan

Ezt a szócikket még nem sorolták be a kidolgozottsági skálán.

Nem értékelt

Ezt a szócikket még nem értékelték a műhely fontossági skáláján.

Értékelő szerkesztő: ismeretlen

Volna egy idevágó, életből vett kérdésem: súlya ismeretében meg lehet-e mondani egy zsák aprópénz értékét?

Tényleg életből vett: katolikus plébániánkon rendszeresen perselyezünk, és mise után konyhai mérlegen meg tudjuk mérni a zsákba tett aprópénzt. Címletekre bontás után tényleg méréssel ellenőrizzük a számolás eredményét, de eszembe jutott, hogy jó poén lenne egy azonnali válasz. Egyenletként:

a db 5 Ft-os * 4,22 gramm +

b db 10 Ft-os * 6,1 gramm +

c db 20 Ft-os * 6,98 gramm +

d db 50 Ft-os * 7,7 gramm +

e db 100 Ft-os * 7,95 gramm +

f db 200 Ft-os * 9,06 gramm +

37 gramm (a zsák önsúlya) =

x gramm

a, b, c, d, e és f egész számok, és biztosan tudjuk, hogy van egy megoldás.

Megoldásként működő számítógépi algoritmus is elfogadható, amennyiben 1 percen belül lefut egy mai otthoni számítógépen.

Majd megpróbálkozom vele. Az x is egész? Mert akkor érdemes vele foglalkozni. Szalakóta ^vita 2014. április 25., 11:41 (CEST)Válasz

Ha az egyenletemet beszorzod 100-zal, szóval ha a súly szempontjából századgrammban gondolkodsz, akkor x is egész, hiszen egész számok szorzatösszege :-)

1 megoldás biztosan van, hiszen valamennyi aprópénz ténylegesen van a zsákban. Az persze szívás, ha valaki kabátgombot vagy Eurot dob be. Akkor úgy módosítja az x értékét, hogy többé nincs releváns megoldás, de ezt minősítsük balesetnek.

A súlyok egyébként valóságosak: ezekkel a darabsúlyokkal kijön egy kupac egynemű, szétválogatott apró darabszáma, és végülis az üdítőitalautomaták is működnek valahogy, leginkább a pénzek súlyával operálva.

Igazán elegáns és praktikusan használható egy olyan Visual Basic Sub volna, aminek a bemenete x, kimenete az a,b,c,d,e,f De ha van matematikai algoritmus, akkor ezt már én is megírom, csak gondoltam, földobom a problémát, mint matematikai kérdést, amire viszont nincs válaszom.

Ha megengeded, firkálgatok ide, ha jutunk valamire, akkor persze mindez törölhető.

1. Egy tetszőleges x súly az max. x/4,22 és min. x/9,06 darabszámú pénzdarabból tevődik össze. Hozzá lehet tenni, hogy a pénzdarabok darabszáma max. 1000 (ennél több nem fér a zsákba). Ezek után talán érdemes lenne valami eljárást találni, ami sorba teszi az összes lehetséges súlyt. Ha ez megvan, akkor már brutal force logikával is rá lehet engedni a számítógépet, hogy a lehetséges súlyokat összevesse az x-ünkkel.

2. Legyen a pénzdarabok összszáma n. Tehát a + b + c + d + e + f = n Az előbbiek szerint n-re tudunk egy minimális és egy maximális becslést adni: n(max)=x/4,22 és n(min)=x/9,06 Így az első releváns súly, amit vizsgálnunk kell, az az n(min)*4,22 A második lehetséges súly úgy képződik, hogy kicserélünk egy 5 Ft-ost egy 10 Ft-osra. A harmadik, hogy kettőt cserélünk ki. Mi ennek a sornak a programozható szabálya?

Vázolom a jelenlegi meggondolásaimat:

Áttérünk századgrammokra, kiszámítjuk a legnagyobb közös osztót, majd ennek és a 100-nak a legkisebb közös többszörösét. Ha lehetnének negatív együtthatók, akkor ezek mind felírhatók lennének. Mivel ilyeneket nem használhatunk, ezért ezeket ki kell szűrni. Továbbá meg kell adni egy maximum értéket, ameddig vizsgálódunk, mivel végtelen sok megoldás van.

A zsák önsúlyát utólag kell hozzáadni. A particionálás egy másik probléma, egy bő matematikai elmélettel. De annak is megpróbálok utánajárni.

Ha megkérhetlek, akkor négy hullámvonallal írd alá a vitalapokra írt üzeneteidet. Köszönettel Szalakóta ^vita 2014. április 30., 06:29 (CEST) . Csomorkány ^vita 2014. április 30., 10:33 (CEST) Biztosan véges sok megoldás van, hiszen az x-et ismerjük. A maximum-érték az életben olyan n=500 db. (ennyi pénzérme fér el a zsákban), de amíg csak elméletben gondolkodunk, egyszerűsíthetünk mondjuk n=20 pénzérmére. Én számítógépprogramozó-aggyal gondolkodom, ezért lehet, hogy lesznek nyelvi problémáink :-), de talán termékeny, ami azóta az eszembe jutott. Legyen xnl az az érték, amivel konkrét n pénzdarab összsúlya legjobban megközelíti az x-et. Triviális példán, ha x=1000 (századgramm), és n = 1, tehát egy pénzdarab legjobb közelítését keressük, akkor xnl = 906, és az ehhez tartozó kombináció: a=0, b=0, c=0, d=0, e=0, f=1 azaz egy pénzdarabból egy 200 Ft-os súlya van legközelebb az x-hez.Válasz

Namost, ha egy (gyors) belső eljárás bármely konkrét n-re és x-re föltárja az x-hez legközelebbi xnl-t, ill. annak a..f összetételét, akkor egy külső eljárás egy egyszerű ciklussal össze tudja állítani a lehetséges xnl-ek halmazát, és megoldás ott van, ahol x=xnl

Ez azért is tűnik termékeny iránynak, mert az xnl-ek meghatározása biztosan tiszta matematika, míg az x lemérése során mérési pontatlanság azért adódhat. Tehát egy belső algoritmus dolga tiszta matematikával meghatározni az xnl-t, és a külső algoritmus dolga levizsgálni, hogy a mért x-hez legközelebbi xnl-ek közül melyik tűnik reálisnak. Itt már mindenféle statisztikai huncutság is bevethető, ha egynél több jelölt van. Csomorkány ^vita 2014. április 30., 10:33 (CEST) Izé... próbálkoztam a négy hullámvonallal, de elnyelte a felület. Íme: Csomorkány ^vita 2014. április 30., 10:35 (CEST) 2014. június 15., 23:16 (CEST)Csomorkány ^vita Támadt egy gondolatom, ami talán egy lépéssel közelebb visz a megoldáshoz. Vegyünk föl egy virtuális pénzdarabot, aminek 0 gram a súlya. Ekkor az eddigiek egy egyenletrendszerben írhatóak föl imígyen:Válasz

a db 0 Ft-os * 0 gramm +

b db 5 Ft-os * 4,22 gramm +

c db 10 Ft-os * 6,1 gramm +

d db 20 Ft-os * 6,98 gramm +

e db 50 Ft-os * 7,7 gramm +

f db 100 Ft-os * 7,95 gramm +

g db 200 Ft-os * 9,06 gramm +

37 gramm (a zsák önsúlya) =

x gramm

Azaz századgrammokban:

0a + 422b + 610c + 698d + 770e + 795f + 906g = x

ÉS:

a + b + c + d + e + f + g = 500

Vagyis az eddigi szóbeli föltételt, hogy max. 500 pénzdarab fér el egy zsákban, beépítettük az egyenletrendszerünkbe. Hát, ennyi másfél hónap alatt, de ez talán egy valós lépés. A második egyenlet lehetséges egész megoldásai véges halmazt adnak ki. Ha mondjuk az a + b + c = 20 egyenlet egész megoldásait nézzük, az így jön ki: 20 0 0 19 1 0 19 0 1 18 2 0 18 1 1 18 0 2 17 3 0 17 2 1 17 1 2 17 0 3 ...

Látható a szabály: 1 + 2 + 3 + ... + 21 féle megoldás van, azaz (21 + 1) X 10 + 11 = 231 Ennek megfelelően az a + b + c = 500 egyenlet megoldásainak a száma 1 + 2 + ... + 501 = 502 * 250 + 251 = 125 751 Jó lenne belátni, hogy az első egyenletbe behelyettesítve a fönti értékeket, monoton növekvő sorrendet kapunk. Nézzük most az a + b + c + d =20-at! 20 0 0 0 19 1 0 0 19 0 1 0 19 0 0 1 18 2 0 0 18 1 1 0 18 1 0 1 18 0 2 0 18 0 1 1 18 0 0 2

A lehetséges megoldások száma: 1 + (1+2) + (1+2+3) + (1+2+3+4)...(1+2+...+21) No, idáig jutottam :-) Ill. egy kérdés. Egy tetszőleges összetételről meg lehet-e mondani, hogy hanyadik a sorban?

Tehát mondjuk a 19 1 0 0 kombó a 2. az a + b + c + d = 20 lehetséges megoldásainak a sorában. Hanyadik az 5 7 3 5 összetétel? Vagy az eredeti föladványban hanyadik a 95 34 76 81 65 43 106 összetétel? Ha ezt meg tudjuk mondani, akkor intervallumfelezéssel elkezdhetünk közeledni a keresett x-hez. Megkeressük a középső összetételt, ha a súlya több a kívánatosnál, akkor lefelé nézzük a rákövetkezőt, ha kevesebb, akkor fölfelé, stb.

Definiáld a sorrendet, és akkor félig készen vagyunk. Szalakóta ^vita 2014. június 16., 19:30 (CEST)Válasz

Matematikailag bizonyítani kellene, hogy amit itt intuitíve sejtünk, az azonos a súlysorrenddel. Praktikusan elég a sejtés. Végülis az a = 500 az nulla századgramm, tehát nyilván a legkisebb lehetséges súly. Utána mindig a legkisebbet cserélgetjük, ez miért lenne más, mint a súlysorrend? A megoldás, hogy először megnézzük a súlysorrendben középső kombinációt, majd ha az x-ünk nagyobb, akkor fölfelé, ha kisebb, akkor lefelé felezzük az intervallumot, stb. No, most büszke vagyok, már csak meg kell csinálni :-) 2014. június 16., 5:23 (CEST)Csomorkány ^vita Most kevésbé vagyok büszke :-( Elkezdtem fölírni a sorozatomat úgy, ahogyan intuitíve logikusnak látszik, és bele is futottam az első kivételbe, ahol az intuitív sorrend nem azonos a súlysorrenddel. 2 db. 5 Ft-os könnyebb, mint 1 db. 200 Ft-os. Márpedig ugye intuitíve először az összes lehetséges esetet kell fölírni, ahol 1 db. pénz van a zsákban, és utána következnek a 2 db-ok, amik elmélet szerint mindig nehezebbek. De nem. Maradjunk abban, hogy ha ebben az irányban keressük a megoldást, akkor a Szent Grál, amit meg kell találni, a súlysorrend :-) Ha gyakorlati haszna nincs is ennyi, azért az is vicces volna, ha földobnám a pénztárcámat a mérlegre, és megmondanám, mennyi apró van benne. Vagyis ha lecsökkentem az összdarabszámot 500-ról olyan 30-ra... 2014. június 16., 18:30 (CEST)Csomorkány ^vita No, megvan a válasz, de sajnos negatív. A súly nem elégséges infó a darabszám, és így az érték meghatározásához. Rájöttem az algoritmusra, hogyan lehet az a + b + c + d + e + f + g = n egyenlet összes egész megoldását tetszőleges n-re fölírni, lentre leteszem Excel Visual Basicben. No, ezzel a függvénnyel elkezdtem brutal force módon menőzni. n=25-ig működött is a dolog, n=25-re 736 281 lehetséges megoldás jön ki, miközben a maximális súly (ha mindegyik 200 Ft-os), csak 906*25 = 22 650 századgramm Ez azt jelenti, hogy egy-egy konkrét súlyérték átlagosan 736 281 / 22 650 = 32 különféle pénzösszetételből jöhet ki. n=25-re egyszerű Excel sorbarendezéssel előállítottam a Szent Grált is, vagyis a súlysorrendet. Ennek alapján szétnéztem középtájt, nos egy példa: x = 14902 századgramm súlyt 111 féle aprópénzösszetételből mérhetünk, ennyi a súlya 4 db 10 Ft-osnak + 2 db 100 Ft-osnak és 12 db 200 Ft-osnak is, ekkor 2640 Ft van apróban a pénztárcánkban, de ennyi a súlya 7 db. 5 Ft-osnak, 7 db. 10 Ft-osnak és 11 db. 20 Ft-osnak is, ekkor viszont csak 325 Ft-unk van. 880 Ft-ra és 14902 századgrammra jön ki 4 db 10 Ft + 12 db 20 Ft + 4 db 100 Ft + 1 db 200 Ft ill. 8 db 5 Ft + 5 db 10 Ft + 2 db 20 Ft + 3 db 50 Ft + 6 db 100 Ft Nos, ha már n = 25 pénzdarabnál ennyire sokféle megoldás jön ki egy-egy súlyértékre, akkor az n = 500-zal értelmetlenség foglalkozni. Mindegy, félig azért büszke vagyok :-) Már berozsdáltam matekból, jót tett ez a kis edzés. Szalakóta: egy darabig még kinn hagynád a cuccot? Augusztus után törölhető. Itt az Excel Visual Basic függvény, aki akar játszani vele, megteheti. Azért neveztem "hetkirak"-nak, mert ugyebár hétféle értékre rakja ki a lehetséges megoldásokat a Munka1 munkatáblába n számú Forint aprópénzdarabra. n max = 25: ennél többel az Excel nem boldogul.Válasz

Sub hetkirak(n) Dim a, b, c, d, e, f, g Dim s

   a = n
   b = 0
   c = 0
   d = 0
   e = 0
   f = 0
   g = 0
   s = 0
   While a > -1
       b = n - a
       While b > -1
           c = n - a - b
           While c > -1
               d = n - a - b - c
               While d > -1
                   e = n - a - b - c - d
                   While e > -1
                       f = n - a - b - c - d - e
                       While f > -1
                           g = n - a - b - c - d - e - f
                           While g > -1
                               If a + b + c + d + e + f + g = n Then
                                   s = s + 1
                                   Worksheets("Munka1").Range("A" & s) = a
                                   Worksheets("Munka1").Range("B" & s) = b
                                   Worksheets("Munka1").Range("C" & s) = c
                                   Worksheets("Munka1").Range("D" & s) = d
                                   Worksheets("Munka1").Range("E" & s) = e
                                   Worksheets("Munka1").Range("F" & s) = f
                                   Worksheets("Munka1").Range("G" & s) = g
                               End If
                               g = g - 1
                           Wend
                           f = f - 1
                       Wend
                       e = e - 1
                   Wend
                   d = d - 1
               Wend
               c = c - 1
           Wend
           b = b - 1
       Wend
       a = a - 1
   Wend

End Sub