Melyik az a legnagyobb szám amelyik nem osztható 6,9 és 20 többszörösének összegével? Vagyis keresem azt az "A (max) " számot, amely nem egyenlő 6 szor x + 9 szer y + 20 szor z-vel: "A (max) " nem egyenlő 6*x+9*y+20*z -vel.

Vagyis keresni kell azt a küszöböt, ami fölött az összes szám előáll a 6,9,20 lineáris kombinációjaként.

Mondjuk a 9y ilyen, kérdés, hogy mi az y. Az őt követő számoknál tipikusan azt fogjuk tenni, hogy beáldozunk valamennyi 9-est, és a helyébe jön valahány 6-os meg 20-as.

9y+1 = 9(y-5) + 20·2 + 6

9y+2 = 9(y-3) + 20

9y+3 = 9(y-3) + 6·5

9y+4 = 9(y-4) + 20·2

9y+5 = 9(y-3) + 20 + 6·2

9y+6 egyértelmű, a rá következők meg már felfoghatók úgy, hogy 9y+6+1 stb, tehát a fenti 9-es "beáldozás" működik ott is.

Vagyis y=5 volt a legtöbb szükséges 9-es, tehát 45 fölött már biztos, hogy minden szám előállítható 6,9,20 lineáris kombinációjaként.

Nézzük, hogy alatta mi a legnagyobb. (A 45-öt persze nem kell nézni)

44 = 20+6·4

43 = ... ez nekem úgy tűnik, nem állítható elő, tehát ez a legnagyobb ilyen szám.

---

Ez nem versenyfeladat véletlenül?

Igen, az egy elírás, ez az igazi:

9y+2 = 9(y-2) + 20 = 9y-18+20

szóval 2 helyett 3-at írtam véletlenül, de 2-re gondoltam.

vagyis itt 2 darab 9-es helyett lesz 1 darab 20-as.

A "beáldozás" csak ez a 6 féle lehet, tehát nem random (a hatodik az, amikor nem kell "beáldozni" 9-est, simán hozzájön egy 6-os), utána periódikusan ismétlődik. Ezt nem hangsúlyoztam ki, de gondoltam, hogy érthető volt. Nézzünk egy példát:

pl. egy nagy szám a 810 (amikor y=90), folytassuk onnan a lineáris kombinációkat:

810 = 90·9

itt kezdődik egy periódus:

811 = (90-5)·9 + 2·20 + 6

812 = (90-2)·9 + 20

813 = (90-3)·9 + 5·6

814 = (90-4)·9 + 2·20

815 = (90-3)·9 + 20 + 2·6

816 = 6 + 90·9

innen már periódikusan ismételhetünk:

817 = 6 + (90-5)·9 + 2·20 + 6

818 = 6 + (90-2)·9 + 20

819 = 6 + (90-3)·9 + 5·6

stb.

822-től már a második periódus jön:

822 = 2·6 + 90·9

823 = 2·6 + (90-5)·9 + 2·20 + 6

824 = 2·6 + (90-2)·9 + 20

stb...

Érthető?