Kezdőlap


Feladat:	F.2326	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Megyesi Gábor
Füzet:	1982/március, 111 - 112. oldal		PDF \| MathML
Témakör(ök):	Sakktáblával kapcsolatos feladatok, Feladat, Számelrendezések
Hivatkozás(ok):	Feladatok: 1981/október: F.2326

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.

Nyilvánvaló, hogy $k > n$ esetén a kívánt kitöltés megvalósítható, hiszen nem is létezik $k \times k$ -as résztáblázat. Így a továbbiakban feltehetjük, hogy $k ≦ n$ .
Ha $k$ osztója $n$ -nek (speciálisan ha $k = n$ ), akkor az $n \times n$ -es tábla lefedhető $k \times k$ -as résztáblákkal úgy, hogy minden mező pontosan egyszer legyen lefedve. Ha most minden $k \times k$ -as résztáblában a számok összege negatív, akkor az egész táblázatban is az összeg negatív, noha ennek pozitívnak kellene lennie. Így ebben az esetben a kitöltést nem lehet a feltételeknek megfelelően elvégezni.
A megmaradt esetben ( $k ≦ n$ , $k$ nem osztója $n$ -nek) legyen $n = q k + r$ , ahol $q$ és $r$ természetes számok, $0 < r < k$ , továbbá legyen $p$ olyan pozitív szám, amelyre

\begin{matrix} k - 1 < p < \frac{n}{q} - 1. \end{matrix}

Ilyen szám mindig van, hiszen

k = (n - r) / q < n / q

. Az

n \times n

-es táblázat

k

-adik,

2 k

-adik,

...

q k

-adik oszlopában minden mezőbe írjunk

(- p)

-t, a többi mezőbe pedig

1

-et. A táblázat minden sora egyforma, így a beírt számok összege

\begin{matrix} n (n - q) + n q \cdot (- p) = n q (\frac{n}{q} - 1 - p) > 0 \end{matrix}

p

választása miatt. Másrészt bármely

k \times k

-as összefüggő résztáblázatban pontosan egy oszlopban áll

(- p)

, a többiben

1

-ek, vagyis a számok összege

\begin{matrix} k \cdot (k - 1) + k \cdot (- p) = k (k - 1 - p) < 0. \end{matrix}

Ez pedig azt jelenti, hogy ez a kitöltés teljesíti a feladatban szereplő feltételeket.
Összefoglalva, a keresett (

n

k

) számpárok pontosan azok, amelyekben

k

nem osztója

n

-nek.

Megyesi Gábor (Szeged, Ságvári E. Gyak. Gimn., I. o. t.)