Hogyan lehet lefedni egy 1997x1997-es négyzetet 3x3-as,5x5-ös és 8x8-as négyzetekkel?

Először megpróbálnék egy egyszerű megoldást keresni.

1992 osztható 8-cal. Ha az egyik oldal mentén egymás mellé lerakunk 8*8-asokat, akkor a végén 5 kocka marad, ahová letehetünk egy 5*5-öst.

Ilyen módon kirakhatunk több sort, értelemszerűen a 8-asokkal nem szabad "magasabban" végeznünk, mint az 5-ösökkel.

Az 5-ösökből álló oszlop nem végződhet 1995-nél, mert akkor csak 2 marad, 1990-nél sem, mert akkor 7 hely marad, ami szintén megoldhatatlan. Ha 1985-nél végződik, akkor 12 hely marad, ami viszont már elkezdhető kirakni 3*3-asokkal.

Nem vagyunk kész, de úgy érzem, een az úton lesz megoldás, ezért megosztottam veletek. Tévedés jogát fönntartom.

Szerintem jó a megoldásom, de nézzétek meg azért:

Úgy kezdjük, hogy a 3x3-as és 5x5-ös elemekből összeépítünk egy nagyobb alakzatot:

leteszünk 5 darabot a 3x3-asból egymás mellé (3x15)

majd föléjük teszünk 3 darab 5x5-öset egymás mellé (5x15) , így kaptunk egy 8x15-ös alakzatot.

két ilyen 8x15-ösból összerakható egy 8x30-as

viszont ha a 8x15-ös mellé két darab 8x8-ast tennénk, akkor az egy 8x31-es alakzat lesz.

tehát előállítható a 8x31 és 8x30-as is.

ezekből viszont már kirakható egy 8x1997-es sáv

mert 31*17+30*49 =1997, tehát a 30-as alakzatból kell 49 darab, a másikból meg 17 darab.

Építsünk most először egy 13x15-ös alakzatot.

Megvan a korábbi 8x15-ös, és efölé pakolunk még egy sort 5x5-ösekből, így megkapjuk a 13x15-öt

a 8x15-ös és 13x15-ös alakzatokból pedig kirakható egy 15x1997-es sáv.

mert: 8*66+13*113=1997

Tudunk akkor 8x1997-es és 15x1997-es sávot csinálni.

Ezekből pedig már kirakható a 1997x1997-es négyzet is,

ugyanis: 8*64+15*99=1997

Nagyon szép a #12-es megodás, gratulálok!

Picit lehet rajta egyszerűsíteni, úgy értem kisebb alakzatokat használni. A kulcslépés továbbra is az ottani 8×15-ös alakzat létrehozása. Ebből először 8 magas csíkot csinálunk, mint ott is. Ehhez olyan másik 8 magas alakzat kell, aminek a szélessége relatív prím a 8×15-ös szélességével (vagyis 15-tel). Ez lehet maga a 8×8-as négyzet is! Vagyis a 8×15 és 8×8-as alakzatokból is összerakhatjuk a 8×1997-es csíkot.

Az, hogy a szélességek relatív prímek legyenek, szükséges és elégséges feltétel, mert prím összegű lineáris diofantoszi egyenletről van szó (és még illene hozzátenni néhány dolgot, de azt elhagyom.)

Egy másmilyen magas csíkot kaphatunk pl. úgy, hogy elforgatjuk a 8×15-ösünket (ezt tette a #12 válaszoló is), így 15 magasat kapunk. Kell egy másik 15 magas is, aminek szélessége relatív prím a 8-cal, ez lehet akár a 3 is: öt darab 3×3-asból csinálunk 15×3-as alakzatot. Vagyis 15×8 és 15×3-as alakatokból is kirakhatunk egy 15×1997-es csíkot.

Van tehát 8 magas és 15 magas csíkunk is, ezek is relatív prímek, ezekből is ösze lehet rakni 1997 magasat. Ez már ugyanaz, mint amit #12 csinált, ezzel kész is vagyunk.

Számszerűen összefoglalva:

- Csináljunk 8 magas csíkot mondjuk 131 darab 8×15-ös és 4 darab 8×8-asból (131·15+4·8=1997) vagy máshogy.

- Csináljunk 15 magas csíkot mondjuk 244 darab 15×8-as és 15 darab 15×3-asból (244·8+15·3=1997) vagy máshogy.

- Végül csináljunk 1997 magas négyzetet mondjuk 131 darab 15×1997 és 4 darab 8×1997 csíkból, vagy máshogy.

Sok más megoldás is lehet csak a számok módosításával, mert a diofantoszi egyenletnek jó sok megoldása van.

------

Érdekes, hogy nem csak 1997×1997-es négyzetet lehet ugyanezzel a módszerrel kirakni. Lehetne a feladat idei is 2012×2012-es négyzettel, mert nem kell prímnek lennie az összegnek, csak relatív prímnek a 3, 5 és 8-cal (ha osztható bármelyikkel, akkor van triviális megoldás is, pl. jövőre csak a 3×3-as négyzetekből is kirakható lesz a 2013×2013.)

Másik érdekesség, hogy 98×98-as mérettől kezdve tetszőlegesen nagy négyzet kirakható így. (Ez azért van, mert a 15x+8y=n diofantoszi egyenletnek n=(15-1)(8-1)=98-tól kezdve minden n-re vannak pozitív megoldásai, hisz 15 és 8 relatív prímek). Ennél kisebb négyzetekre is némelyik megoldható, de nem mind.