-- Olvasási idő kb.: 1 perc és 52 másodperc

257. feladvány: Legkevesebb trapéz

Legfeljebb hány pontot lehet kijelölni az alábbi 36 pontból álló négyzetrács pontjai között úgy, hogy a kijelölt pontok közül semelyik négy ne alkosson trapézt? Trapéznak hívjuk az olyan négyszöget, aminek van legalább két párhuzamos oldala. Az elfajult trapézt, amiben kettőnél több pont esik egy egyenesre, nem tekintjük trapéznak!

Érdemes lehet az elfajultság kizárását kihasználni, azaz a lehető legtöbb pontot egy egyenesről kiválasztani! De melyikről? És hány pontot lehet még azon kívül választani?

Némi próbálgatás után könnyű találni olyan megoldást, amiben hat pontnál többet választunk. Ha viszont hat pontnál többet választunk, akkor a skatulyaelv alapján lesz olyan sor a négyzetrács hat sora között, amibe több pont kerül, és lesz olyan oszlop is a hat oszlop között, amibe több pont kerül. Viszont sem sorból, sem oszlopból nem lehet több olyan, amibe több pont is kerül, hiszen akkor lenne olyan trapéz, aminek vagy vízszintes vagy függőleges irányú párhuzamos oldalpárjai lennének. Annak a konfigurációnak tehát, ami a legtöbb (hatnál több) pontot tartalmazza, olyannak kell lennie, amiben soronként és oszloponként csak egy pont lehet – egy sor és egy oszlop kivételével, amiben több pont is szerepelhet. Lényegében tehát egy egymást metsző sor és oszlop (kereszt) pontjaiból válogathatunk.

Mármost egy kereszt pontjainak a száma tizenegy, akármelyik egymás metsző sort és oszlopot választjuk is. A kérdés már csak az, hogy elérhető-e tizenegy, esetleg csak tíz, netán kevesebb a maximum. Némi próbálgatás után rájöhetünk, hogy érdemes a sor és az oszlop pontjait minél jobban eltávolítani egymástól az átlós irányú oldal párok kizárása miatt, és megtalálhatjuk az alábbi, kilencpontos megoldást, ahol pirossal jelöltük a választott pontokat. Könnyen belátható, hogy egyik meredekség sem szerepel az ábrán kétszer, de az elkezdett piros oszlopba tizedik pontot már nem tudunk választani.

Ha belátnánk, hogy tíz és tizenegy pontos megoldás nincsen, akkor készen is lennénk. Ezeket viszont könnyű végignézni, hiszen a tükrözési és forgatási szimmetria miatt csak néhány keresztet kell átvizsgálni, és megnézni, hogy a teljesen tömött kereszt megfelelő-e megoldásnak, esetleg kihagyható-e belőle valamely pont. A lehetséges változatokat gyorsan kizárhatjuk, ha az átlós, azaz 45 fokos meredekséggel rendelkező pontpárokat vizsgáljuk. Például a kereszt közepének négy szomszédja nem lehet a pontok között, mert azok négyzetet alkotnak.

Ha szereted a fejtörőket, tekintsd meg korábbi feladványainkat is! Ha megjegyzésed lenne, vagy feladványt javasolnál, írj az eszventura@qubit.hu e-mail címre! Ha pedig tetszik a rovat, akkor ezt a Vendégkönyvben kifejezésre juttathatod.

Az Ész Ventura feladványügyi rovat gazdája: Gáspár Merse Előd fizikus, kognitív kutató, társasjáték-fejlesztő és bűvész.

Forrás