Kezdőlap


Feladat:	2009. évi Kürschák matematikaverseny 1. feladata	Korcsoport: 16-17	Nehézségi fok: nehéz
Füzet:	2010/február, 68 - 69. oldal		PDF \| MathML
Témakör(ök):	Kürschák József (korábban Eötvös Loránd), Egész számok összege, Számelrendezések, Szélsőérték-feladatok differenciálszámítás nélkül
Hivatkozás(ok):	Feladatok: 2010/február: 2009. évi Kürschák matematikaverseny 1. 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.

Megoldás. A feladat szövegéből adódóan $n$ és $k$ pozitív egészek. Világos, hogy $n = 1$ esetén $S = k$ , ezért a továbbiakban feltesszük, hogy $n \geq 2$ . A táblázat minden sorában a beírt számok összege $1 + 2 + ... + k = \frac{1}{2} k (k + 1)$ , így a táblázatbeli számok összege $\frac{1}{2} n k (k + 1)$ . A $k$ oszlop valamelyikében tehát az összeg legalább $\frac{1}{2} n (k + 1)$ , vagyis $S \geq \frac{1}{2} n (k + 1)$ . Ebből

\begin{matrix} S \geq ⌈ \frac{1}{2} n (k + 1) ⌉ 1 \end{matrix}

következik, tekintve, hogy

S

a definíciójából adódóan egész szám. Megmutatjuk, hogy

n \geq 2

esetén ez lesz az

S

pontos értéke. Ehhez azt kell igazolni, hogy létezik olyan táblázatkitöltés, amiben minden oszlopösszeg legfeljebb

\begin{matrix} ⌈ \frac{1}{2} n (k + 1) ⌉ . \end{matrix}

n

páros, akkor könnyű ilyet találni: a páratlanodik sorokba növekvő, a páros sorszámúakba csökkenő sorrendben írjuk be az egészeket. Ezáltal az

i

-edik oszlopösszeg

\begin{matrix} \frac{n}{2} i + \frac{n}{2} (k + 1 - i) = \frac{1}{2} n (k + 1) \end{matrix}

lesz. Ha

n

páratlan (és

n \geq 3

), akkor is megtehetjük, hogy az első

n - 3

sort a fentiek szerint töltjük ki (hiszen páros számú sorról van szó), és ezáltal minden oszlopban az első

n - 3

elem összege

\frac{1}{2} (n - 3) (k + 1)

lesz. Ahhoz tehát, hogy minden oszlopban az összeg legfeljebb

\begin{matrix} ⌈ \frac{1}{2} n (k + 1) ⌉ \end{matrix}

legyen, az szükséges, hogy a táblázat utolsó három sorát úgy töltsük ki, hogy minden oszlop utolsó három elemének összege legfeljebb

\begin{matrix} ⌈ \frac{1}{2} n (k + 1) ⌉ - \frac{1}{2} (n - 3) (k + 1) = ⌈ \frac{1}{2} n (k + 1) - \frac{1}{2} (n - 3) (k + 1) ⌉ = ⌈ \frac{3}{2} (k + 1) ⌉ \end{matrix}

legyen. Ez pedig éppen azt jelenti, hogy az utolsó

3

sorba egy a feladatban leírt

3 \times k

méretű táblázatot kell elhelyeznünk. A továbbiakban tehát az

n = 3

esetre szorítkozunk.
Ha

k = 2 m + 1

páratlan, azaz

S = \frac{3 (k + 1)}{2} = 3 (m + 1)

, akkor az alábbi módon kitöltött táblázat megfelel a célnak:

\begin{matrix} \begin{matrix} 1 & 2 & ... & i & ... & m + 1 & m + 2 & ... & j & ... & 2 m + 1 \\ 2 m + 1 & 2 m - 1 & ... & 2 m + 3 - 2 i & ... & 1 & 2 m & ... & 4 m + 4 - 2 j & ... & 2 \\ m + 1 & m + 2 & ... & m + i & ... & 2 m + 1 & 1 & ... & j - m - 1 & ... & m \end{matrix} \end{matrix}

Ha pedig

k = 2 m

páros szám és

\begin{matrix} S = ⌈ \frac{3 (k + 1)}{2} ⌉ = ⌈ \frac{6 m + 3}{2} ⌉ = 3 m + 2, \end{matrix}

akkor például az alábbi módon tölthetjük ki a

3 \times k

méretű táblázatot:

\begin{matrix} \begin{matrix} 1 & 2 & ... & i & ... & m & m + 1 & ... & j & ... & 2 m \\ 2 m & 2 m - 2 & ... & 2 m + 2 - 2 i & ... & 2 & 2 m - 1 & ... & 4 m + 1 - 2 j & ... & 1 \\ m + 1 & m + 2 & ... & m + i & ... & 2 m & 1 & ... & j - m & ... & m \end{matrix} \end{matrix}

Könnyen ellenőrizhető, hogy mindkét táblázatban minden sorban szerepel

1

és

k

között az összes egész, továbbá, hogy egyetlen oszlopösszeg sem nagyobb

S

-nél.

□

⌈ x ⌉

x

szám felső egész része; a legkisebb egész szám, amely nem kisebb

x

-nél.