14. feladat
2004/04/29 22:37
1164 megtekintés
A cikk már legalább egy éve nem frissült, az akkor még aktuális információk lehet, hogy mára elavultak.
Egy 8 × 8-as sakktáblára elhelyeztünk 8 db 2 × 2-es lapot. Igaz-e, hogy minden esetben elhelyezhető a kilencedik ilyen lap is? Legalább hány 2 × 2-es lap helyezhető el egy n × n-es sakktáblán?

Színezzük ki a sakktáblát az ábrán látható módon. Ekkor előfordulhat, hogy egy fekete tartományba akár négy 2 × 2-es lap metsz bele, de az nem lehet, hogy egy lapnak két tartománnyal, vagy eggyel se legyen közös pontja, azaz bármely 2 × 2-es lap belemetsz pontosan egy fekete tartományba. Ez azt is jelenti, hogy ha elhelyezünk 8 darab lapot a sakktáblán, akkor biztosan lesz legalább egy olyan fekete tartomány, amelyiknek még nincsen közös mezője egyik, korábban már felrakott lappal sem. Erre az üres tartományra biztosan elhelyezhető a kilencedik lap. Látható, hogy amennyiben a fekete részekre rakjuk a lapokat, akkor 9-nél több már nem helyezhető el. Hasonló színezési eljárással lehet összeszámolni az n×n-es sakktáblára felhelyezhető 2×2-es lapok minimális számát. Ez a szám n=3l, illetve n=3l+1 esetén l×l , míg n=3l+2 alakú számokra (l+1)×(l+1).

Csatlakozz hozzánk!

Ajánljuk

European Schoolnet Academy Ingyenes online tanfolyamok tanároknak
School Education Gateway Ingyenes tanfolyamok és sok más tanárok számára
ENABLE pilot Program iskoláknak a bullying ellen
eBiztonság Minősítés Minősítési rendszer oktatási intézményeknek