Kezdőlap


Feladat:	Pontversenyen kívüli P.37	Korcsoport: 16-17	Nehézségi fok: nehéz
Megoldó(k):	Balogh Z. , Füredi Z. , Göndőcs F. , Kérchy L. , Kirchner I. , Komócsi S. , Lakatos B. , Lempert L. , Martoni V. , Pál J. , Papp Z. , Pressing L. , Prőhle Tamás , Reviczky J. , Simonyi Gy. , Szabó Gy. , Vajnági A. , Várady T.
Füzet:	1970/január, 26 - 28. oldal		PDF \| MathML
Témakör(ök):	Elsőfokú diofantikus egyenletek, Kombinatorikai leszámolási problémák, Kombinációk, Konstruktív megoldási módszer, Maradékos osztás, Oszthatósági feladatok, Természetes számok, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1969/szeptember: Pontversenyen kívüli P.37

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.

I. megoldás. Mindhárom adott $n$ -érték $3$ -mal osztható páratlan szám, közös alakjuk $6 k + 3$ , ahol rendre $k = 3, 9 (= 3^{2}), 27 (= 3^{3})$ .Megmutatjuk, hogy ha $n = 6 k + 3$ és $k ≧ 0$ , akkor (1)-nek a (2)-t is teljesítő megoldásainak száma $3 k^{2}$
(1)-nek természetes számokban $(\binom{n - 1}{2})$ megoldása van. Ezt a következőképpen látjuk be. A megoldások száma nyilván annyi, ahányféleképpen egy $n$ tagból álló csuklós mércéből (colstok) két csuklójában meghajlítva $3$ tagú töröttvonalat formálhatunk, feltéve, hogy a mérce elejét és végét megkülönböztetjük. A mércéből az egymás utáni vonalrészekbe jutó tagok száma rendre $x_{1}$ , $x_{2}$ , $x_{3}$ . Az $n$ tag közti $n - 1$ csukló közül $2$ -t a töröttvonal szögpontjai céljára valóban $(\binom{n - 1}{2})$ -féleképpen választhatunk ki.
Ezen megoldások közül eltávolítjuk azokat, amelyekben nem minden ismeretlen értéke különböző, a megmaradókat pedig csak növekvő sorrendben vesszük figyelembe.
$x_{1} = x_{2} = x_{3}$ egyetlen megoldásban lép fel, amikor közös értékük $2 k + 1$ .
Az $x_{1} = x_{2} \neq x_{3}$ típusú megoldásokban $x_{1}$ értéke most már 1, 2, $...$ , $2 k$ , $2 k + 2$ , $2 k + 3$ , $...$ , $3 k + 1$ lehet, és ez meghatározza a megoldást, tehát számuk $3 k$ . Ugyanennyi az $x_{1} = x_{3} \neq x_{2}$ , $x_{1} \neq x_{2} = x_{3}$ típusú megoldások száma is. Így (1)-nek különböző természetes számokban

\begin{matrix} (\binom{6 k + 3 - 1}{2}) - 1 - 3 \cdot 3 k = \frac{(6 k + 2) (6 k + 1)}{2} - 1 - 9 k = 18 k^{2} \end{matrix}

megoldása van. Ezek

3! = 6

-osával csak sorrendben különböznek, a növekvően rendezettek száma tehát valóban

3 k^{2}

Prőhle Tamás (Budapest, Fazekas M. Gyak. Gimn. IV. o. t.)

II. megoldás. Jelöljük az (1) egyenlet (2) feltételt kielégítő megoldásainak a számát

f (n)

-nel.

f (n)

értéke kis természetes számokra könnyen előállítható :

\begin{matrix} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ f (n) & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 2 & 3 & 4 & 5 & 7 \end{matrix}

Ha valamely

n

-re ismerjük az összes (a (2) feltételt kielégítő) megoldást, azokban mindegyik változóból 1-et levonva az összeg 3-mal csökken, és (2)-t továbbra is kielégítő, (különböző) megoldásokat kapunk, kivéve azt az esetet, amikor

x_{1} = 1

. Ha tehát az

n

-hez tartozó megoldások közül elhagyjuk azokat, melyekben

x_{1} = 1

, a visszamaradó megoldások száma egyenlő lesz az

(n - 3)

-hoz tartozó megoldások számával

x_{1} = 1

mellett

\begin{matrix} x_{2} + x_{3} = n - 1; 1 < x_{2} < x_{3} . \end{matrix}

(3)

n

páratlan:

n = 2 k + 1

, akkor

x_{2}

lehetséges értékei:

2,3, ..., k - 1

; (3) megoldásainak a száma

k - 2

. Ha

n

páros:

n = 2 k

, akkor

x_{2}

lehetséges értékei: 2, 3,

...

k - 1

, a megoldások száma ismét

k - 2

. Mindkét esetben

[\frac{n}{2}] - 2

a megoldások száma, tehát

\begin{matrix} f (n) - f (n - 3) = [\frac{n}{2}] - 2. \end{matrix}

Egyszerűbb eredményt kapunk, ha

f (n)

és

f (n + 6)

értékét hasonlítjuk össze: a fenti összefüggés alapján

\begin{matrix} f (n + 6) - f (n) = {f (n + 6) - f (n + 3)} + {f (n + 3) - f (n)} = \\ = [\frac{n + 6}{2}] - 2 + [\frac{n + 3}{2}] - 2 = [\frac{n}{2}] + [\frac{n + 1}{2}] = n . \end{matrix}

n = 6 k + l (l = 1, 2, 3, 4, 5, 6)

, akkor

\begin{matrix} f (n) = (n - 6) + f (n - 6) = (n - 6) + (n - 12) + f (n - 12) = ... = (n - 6) + \\ + (n - 12) + ... + l + f (l) = \\ \sum_{j = 0}^{k - 1} (l + 6 j) + f (l) = k (3 k + l - 3) + f (l), \end{matrix}

ahol

f (l) = 0

, ha

l < 6

és

f (6) = 1

. Speciálisan

l = 3

mellett

f (n) = 3 k^{2}

, amint azt az I. megoldásban is láttuk ‐ a bemutatott számpéldák mind ennek speciális esetei.

Megjegyzés. Egyszerű előállítás

f (n)

-re a következő: vesszük azt az egész számot, mely legközelebb van

\frac{{(n - 3)}^{2}}{12}

-höz. Ez ugyanis teljesül

n

kis értékeire és

\begin{matrix} \frac{{(n + 3)}^{2}}{12} - \frac{{(n - 3)}^{2}}{12} = n \end{matrix}

miatt a fenti

f (n + 6) - f (n) = n

összefüggés alapján minden további

n

-re is teljesül.