Hogyan lehet bebizonyítani, hogy csak 32x33-as téglalapot lehet csinálni 9 adott négyzetből?

Azt kell megnézni, hogy milyen téglalapok jöhetnek számításba; értelemszerűen azok, amelyeknek a területe pont ugyanannyi, és oldalai egész számok. A megfelelő szorzatokat úgy kaphatjuk meg, hogy az egyik számot osztjuk, és azzal szorozzuk a másikat, például a 32x33-nál ha a 32-t osztjuk 2-vel, akkor a 33-at szorozni kell, tehát a 16x66-os szorzatot, így téglalapot kapjuk. Ezzel csak az a probléma, hogy ebbe a téglalapba a 18x18-as négyzet nem fér bele, és ha tovább osztunk 2-vel, akkor ugyanez lesz a történet.

Ha a másik oldalról nézzük, akkor a 33-at osztjuk, itt két lehetőség van; vagy 3-mal osztunk, vagy 11-gyel, de mindkét esetben azt a megoldást fogjuk kapni, hogy a 18x18-as négyzet nem fog beleférni.

Ezzel beláttuk, hogy másik téglalap nem rakható ki.

Teljesen jogos, ezt nagyon benéztem.

Sokkal egyszerűbb a megoldás, mint elsőre gondoltam; nemes egyszerűséggel azért, mert nem lehet egyszerre mindkét tényező páros, így ami marad, az a 96x11, 352x3, 1056x1, de ezeket már kizártam a válaszomban.

Hogy miért nem lehet egyszerre páros a két tényező, szerintem innen már hamar ki fog derülni számodra.

Biztos, én vagyok a hülye, de ezt nem értem:

"mindig fogsz tudni találni olyan sávot, amelyben páratlan sok egységnégyzet nincs lefedve"

Én így bizonyítom:

2^5*3*11-es méretű téglalapot kell csinálni, aminek mindkét oldala minimum 18.

Nézzük mik lehetnek:

(2*11)*(2^4*3) = 22*48

(3*11)*(2^5) = 33*32

(2^2*11) * (2^4) = 44 * 16 hopp ez már nem jó, mert 16<18.

Vagyis csak két téglalap jöhet szóba.

22*48 nem lesz jó, mert leteszed a 18x18-ast fölé rakod a 4x4-est, és lesz egy 14x4-es részed, amit nem tudsz kitölteni.

Tehát egyetlen téglalap jöhet szóba a 32*33.

Ehhez kell mutatni egy kitöltést, hogy teljes legyen a megoldás.

Veszed a 22*48-as téglalapot, és berakod valahova a 15*15-ös négyzetet. Mivel a téglalap mindkét oldala páros, ezért fogsz találni 15 oszlopot és 15 sort (ezeket neveztem sávoknak), ahol páratlan sok egységnégyzet (7 és 33) lesz található, így ezek a csak páros oldalhosszú négyzetekkel nem lesznek kitölthetőek. Úgy kellene sakkozni a maradék páratlan hosszú négyzettel, hogy ne legyen ilyen sáv, de nem lesz megoldható; ha lerakjuk a 9*9-es négyzetet a 15*15-ös mellé (és itt a "mellé" azt jelenti, hogy a kisebb négyzet minden sora vagy oszlopa egybeesik a nagyobb négyzet 9 sorával vagy oszlopával), akkor ugyan eltüntettünk 9 sort/oszlopot, ugyanakkor született 9 másik is, tehát a "rossz sávok" száma nem változott, csak annyiban, hogy eddig volt 15 sor és 15 oszlop, most van 6 sor és 24 oszlop, vagy fordítva. Legfeljebb 1+7=8 sorra és ugyanennyi oszlopra lehetünk ráhatással a többi páratlan oldalhosszú négyzettel, viszont van 24 sor vagy oszlop, amit ennyivel nem tudunk. Felvetődhet az is, hogy rossz volt a kiindulóalap, tehát a 9*9-es négyzet nem esik egybe a 15*15-ös négyzettel, azzal viszont csak annyit érünk el, hogy több rossz sáv fog születni (legfeljebb 15+9=24 oszlop és sor).

Tehát mindig fogunk találni olyan sávot a páros*páros alakú téglalapban, hogy azokban páratlan sok egységnégyzet van, ami nem lesz kirakható a páros oldalhosszú négyzetekkel.