Kezdőlap


Feladat:	Pontversenyen kívüli P.290	Korcsoport: 18-	Nehézségi fok: nehéz
Megoldó(k):	Bencze István , Erdélyi Tamás , Varga Lívia
Füzet:	1980/szeptember, 19 - 21. oldal		PDF \| MathML
Témakör(ök):	Kombinatorika, Pontversenyen kívüli probléma
Hivatkozás(ok):	Feladatok: 1977/október: Pontversenyen kívüli P.290

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.

Legyen egy teli hordó hasznos súlya $2$ egységnyi (hasznos súly jelentse a hordók tartalmának súlyát), így az össz hasznos súly $3 k$ egység. A teherautók terhelésének vizsgálatakor a hordók súlyától eltekinthetünk, hiszen mindhárom teherautóra $k$ hordót kell raknunk. Ebben az esetben a teherautók mindegyikére $k$ egységnyi súly kerül.
Megmutatjuk, hogy elegendő $k$ páros értékeit vizsgálni. Ha ugyanis $k$ páratlan, $k = 1$ nyilván nem lehetséges. Könnyen látható az is, hogy $k = 3$ esetén csak egy megoldás van. Vizsgáljuk a $k > 3$ páratlan értékeket. Belátjuk, hogy ,,jó'' rakodás esetén minden teherautóra kerül teli, félig telt és üres hordó is. Ha az egyik teherautón nem lenne teli hordó, akkor a másik két teherautó valamelyikre legalább $\frac{k + 1}{2}$ db teli hordó jutna, s igy azon a hasznos súly legalább $(k + 1)$ lenne, ami nagyobb, mint $k$ . Félig telt hordó is biztosan lesz mindegyik autón, mert ha valamelyiken csak teli és üres hordó lenne, annak hasznos súlya páros egységnyi lenne, márpedig mindegyik teherautó hasznos súlya páratlan egységnyi, ti. $k$ egységnyi.
Üres hordónak is kell lenni mindegyik teherautón, mert amelyiken nem lenne, annak összes hasznos súlya $k$ -nál nagyobb lenne.
Jelölje $G (k)$ a keresett elhelyezési lehetőségek számát $k$ ‐ pontosabban $k$ teli, $k$ félig telt és $k$ üres hordó ‐ esetén. Fenti fejtegetéseinkből következik, hogy

\begin{matrix} G (2 n + 1) = G (2 n - 2) n > 1 \end{matrix}

s ezért elég a páros esettel foglalkozni.
A következőkben mindegyik fajtából

2 n

hordót tételezünk fel és a hordók elhelyezését a következőképpen végezzük: először helyezzük el a teli hordókat, ügyelve arra, hogy egyik autóra se tegyünk

n

-nél többet. Ez már meghatározza a félig telt és üres hordók számát az egyes teherautókon. Ha

x

y

és

z

jelöli az egyes teherautókon levő teli hordók számát, az elmondottakból következik, hogy a ,,jó'' elhelyezések

G (2 n)

száma megegyezik az

\begin{matrix} x + y + z = 2 n \end{matrix}

egyenlet olyan megoldásainak számával, ahol

(x

y

z)

nem negatív egészek, továbbá:

x ≦ n

y ≦ n

z ≦ n

és az összeadandók sorrendjére nem vagyunk tekintettel.
Ha bevezetjük az

a = n + 1 - x

b = n + 1 - y

c = n + 1 - z

új változókat, láthatjuk, hogy a keresett megoldásszám az

\begin{matrix} a + b + c = n + 3 = m \end{matrix}

egyenlet megoldásszámával egyezik meg, ahol

a

b

c

pozitív egészek, és az összeadandók sorrendje mellékes.
Rendezzük az összeg összeadandóit nagyság szerinti sorrendbe. Világos, hogy az első (a legkisebb) összeadandó kisebb vagy egyenlő, mint

[\frac{m}{3}]

, azaz az első összeadandóra

[\frac{m}{3}]

lehetőség van. Ha az első összeadandó

u

, akkor a második nem lehet

u

-nál kisebb és

[\frac{m - u}{2}]

-nél nagyobb. Ily módon a második összeadandóra

[\frac{m - u}{2}] - (u - 1)

lehetőség van. A harmadik összeadandót az első kettő egyértelműen meghatározza. Mivel

u

felveheti az

1

2

3

...

[\frac{m}{3}] - 1

[\frac{m}{3}]

értékeket, így a lehetőségek száma

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

Hozzuk egyszerűbb alakra ezt a kifejezést. Ha

m

-et

3

-mal osztva

r

a maradék (

r = 0

1

vagy

2

);

m = 3 p + r

, akkor

\begin{matrix} G (2 n) = [\frac{3 p + r - 1}{2}] + [\frac{3 p + r - 2}{2}] + [\frac{3 p + r - 3}{2}] + ... + \\ + [\frac{3 p + r - p}{2}] - (1 + 2 + ... + (p - 1)) . \end{matrix}

Vegyük észre, hogy

[\frac{q}{2}] = \frac{q}{2} - \frac{1}{4} + \frac{{(- 1)}^{q}}{4}

,

s ezért (a számolást nem részletezve)

\begin{matrix} G (2 n) = \frac{p (2 p + r)}{2} - \frac{p}{4} + (\frac{1}{2} + \frac{2}{2} + \frac{3}{2} + ... + \frac{p - 1}{2}) + \\ + (\frac{{(- 1)}^{r}}{4} + \frac{{(- 1)}^{r + 1}}{4} + ... + \frac{{(- 1)}^{r + p - 1}}{4}) + \frac{p (p - 1)}{2} . \end{matrix}

Jelöljük

ε

-nal a

\frac{{(- 1)}^{r}}{4} + \frac{{(- 1)}^{r + 1}}{4} + ... + \frac{{(- 1)}^{r + p - 1}}{4}

összeget.

Nyilván

ε

csak

\frac{1}{4}

0

vagy

- \frac{1}{4}

lehet. Mivel

\frac{1}{2} + \frac{2}{2} + \frac{3}{2} + ... + \frac{p - 1}{2} = \frac{p (p - 1)}{4}

, azt kapjuk hogy

G (2 n) = \frac{p (2 p + r)}{2} - \frac{p}{4} + \frac{p (p - 1)}{4} + ε .

Ezt tovább alakíthatjuk:

\begin{matrix} G (2 n) = \frac{p (3 p + 2 r)}{4} + ε = \frac{m^{2}}{12} - \frac{r^{2}}{12} + ε . \end{matrix}

Vegyük észre, hogy ha

r = 0

, akkor

ε = 0

vagy

\frac{1}{4}

; ha

r = 1

, akkor

ε = 0

vagy

- \frac{1}{4}

, s végül, ha

r = 2

, akkor

ε = 0

vagy

- \frac{1}{4} .

Ezért

\begin{matrix} - \frac{1}{3} ≦ - \frac{r^{2}}{12} + ε ≦ \frac{1}{4}, s így G (2 n) = [\frac{m^{2}}{12} + \frac{1}{2}], \end{matrix}

mert

\begin{matrix} \frac{1}{4} ≧ ε - \frac{r^{2}}{12} ≧ 0 esetén G (2 n) - 1 < \frac{m^{2}}{12} ≦ G (2 n) és (ε - r^{2} / 12) < \frac{1}{2}, \\ - & \frac{1}{3} ≦ ε - \frac{r^{2}}{12} < 0 esetén G (2 n) < \frac{m^{2}}{12} < G (2 n) + 1 és - ε + \frac{r^{2}}{12} + \frac{1}{2} < 1. \end{matrix}

Összefoglalva eredményeinket, a következő igaz

\begin{matrix} 1. & G (3) = 1 \\ 2. & G (2 n) = [\frac{n^{2} - 6 n + 15}{12}] n = 1,2,3, ... \\ 3. & G (2 n + 1) = G (2 n - 2) n = 2,3, ... \end{matrix}

Bencze István (Miskolc, Földes F. Gimn.)
Erdős László (Budapest, Berzsenyi D. Gimn.)