Informatikai és Hírközlési Minisztérium Oktatási Minisztérium Apache Php Mysql Fazekas Mihály Gyakorlóiskola
  Bejelentkezás
Üdvözöljük a Matematika portálon!  
Beharangozó: Garay Barna: Az ingamozgás kaotikussága

Szőnyi Tamás

Az Eötvos Loránd Tudományegyetem Számítástudományi Tanszékének professzora

A Zarankiewicz probléma

2010. június 1.



Próbálkozzunk az alábbi példával!

Feladat a) Helyezzünk el a sakktábla felén — tehát egy 4× 8-s táblán — minél több bábut úgy, hogy ne legyen négy olyan bábu, amelyek mezőinek középpontjai — a tábla széleivel párhuzamos oldalakkal bíró — téglalap csúcsai!

b) Helyezzünk el minél több bábut a 7× 7-es táblán!

Az is jó, ha sikerül ,,sok'' bábut elhelyeznünk, de a teljes megoldás mindkét feladatrész esetén két lépésből áll: I. a bábuk ügyes elhelyezése; II. annak igazolása, hogy több bábu nem helyezhető el.

Az olvasó összevetheti legjobb konstrukcióit a

oldalakon található maximális elrendezésekkel.

A problémát általános formában Zarankiewicz vetette fel 1951-ben:

Zarankiewicz probléma Tekintsük az n× m-es négyzetrácsot, azaz az {(i,j): i=1,... m, j=1,... ,n} alakú rácspontokat. Válasszunk ki ezek közül minél többet úgy, hogy a kiválasztott pontok között ne legyen négy olyan pont, amelyek a koordináta-tengelyekkel párhuzamos oldalú téglalap csúcsai! Hány pontot választhatunk ki ilyen módon?

Fent kitűzött feladatunkból kiindulva megláthatjuk a probléma három arcát. A 4× m-es (m> 5$) illetve általában az n× m-es esetben - akkor ha m legalább ,,n alatt a 2"- pontosan meg tudjuk válaszolni a kérdést, és egy egyszerű kombinatorikus okoskodásra van csak szükségünk. A 7× 7-es esetben is tudjuk a pontos választ és a kiválasztott pontok egy véges síkot írnak le. Végül akkor, ha n és m különböző, általában nem ismerjük a pontos választ Zarankiewicz kérdésére (még akkor sem, ha n és m közel van egymáshoz).

Az előadásban azt szeretném megmutatni, hogy egy ilyen egyszerű probléma is számos matematikai fogalomhoz (pl. blokkrendszerek, véges síkok) kapcsolható, továbbá érzékeltetni azt, hogy már ilyen egyszerű(nek látszó) kérdéseknél sem mindig ismerjük a teljes választ. Az előadásban a probléma általánosításairól és a (nem teljes) megoldásról is szó lesz.


Kiemelt támogatónk 2006-ban:
Tigra Computer
Támogatóink 2003-ban:
Oktatási Minisztérium
Powered by:
Apache + Php + Mysql
Kapcsolat
hraskoa@fazekas.hu
Copyright © 2004-2010 Fazekas Mihály Fővárosi Gyakorló Általános Iskola és Gimnázium. Served by pingvin.