Kezdőlap


Feladat:	1999. évi Nemzetközi Matematika Diákolimpia 13. feladata	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Keszegh Balázs , Kiss Gergely
Füzet:	1999/október, 389 - 390. oldal		PDF \| MathML
Témakör(ök):	Sakktáblával kapcsolatos feladatok, Kombinatorikai leszámolási problémák, Lefedések, Nemzetközi Matematikai Diákolimpia
Hivatkozás(ok):	Feladatok: 1999/szeptember: 1999. évi Nemzetközi Matematika Diákolimpia 13. feladata

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Osszuk be a négyzetet keretekre az ábra szerint, és kívülről kezdve színezzünk minden második keretet feketére. A táblán minden mező pontosan két feketével szomszédos, tehát már ahhoz is meg kell jelölnünk a fekete mezőknek legalább a felét, ha csak annyit akarunk, hogy minden fekete mezőnek legyen megjelölt szomszédja. $N$ tehát legalább ezek számának fele. Számoljuk ezt össze abban az esetben, amikor $n$ 4-gyel is osztható, illetve ha 4-gyel nem osztható (az 1. ábrán a színezés az a) esetnek megfelelő).

\begin{matrix} \begin{matrix} 4 ∣ n : & \frac{1}{2} [12 + (16 + 12) + ... + (\frac{n - 4}{4} 16 + 12)] = \frac{1}{2} [\frac{n}{4} 12 + 16 \frac{n - 4}{4} \cdot \frac{n}{4} \cdot \frac{1}{2}] = & a) \\ = \frac{1}{2} [3 n + \frac{n (n - 4)}{2}] = \frac{n^{2} + 2 n}{4}, \end{matrix} \end{matrix}

\begin{matrix} \begin{matrix} 4 ∤ n : & \frac{1}{2} [4 + (4 + 16) + ... + (4 + \frac{n - 2}{4} 16)] = \frac{1}{2} [\frac{n + 2}{4} 4 + 16 \frac{n - 2}{4} \cdot \frac{n + 2}{4} \cdot \frac{1}{2}] = & b) \\ = \frac{1}{2} [n + 2 + \frac{n^{2}}{2} - 2] = \frac{n^{2} + 2 n}{4} . \end{matrix} \end{matrix}

Ezt az értéket viszont el is érhetjük, csak a fekete kereten belül jelölve ki mezőket az alábbi módon: a fekete keretek bal alsó sarkából indulva két szomszédos mezőt kijelölünk, majd kettőt nem, majd kettőt megint igen stb., mindig a keret mentén lépegetve. Így nyilván minden keret felét jelöljük ki, így nyilván összesen

\frac{n^{2} + 2 n}{4}

mezőt. A fekete keretek mezőinek nyilván lesz jelölt szomszédja, a fehér keretek mezői mellett pedig van valamelyik szomszédos fekete kereten jelölt mező, hiszen ezek közül a belső jelölését pontosan kettővel ,,feljebb'' kezdtük el, így a két keret jelölt mezői váltogatják egymást.