Kezdőlap


Feladat:	F.2593	Korcsoport: 18-	Nehézségi fok: átlagos
Megoldó(k):	Forgács Ágnes , Hajdú Gábor , Hajnal Zoltán
Füzet:	1987/április, 152 - 154. oldal		PDF \| MathML
Témakör(ök):	Számhalmazok, Halmazok számossága, Kombinatorika, Feladat
Hivatkozás(ok):	Feladatok: 1986/szeptember: F.2593

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. Hívjuk pozitív egész számok egy sorozatát "gazdaságosnak'', ha rendelkezik a feladatban leírt tulajdonsággal, tehát az elemeiből készíthető összegek között nincsenek egyenlők. Egy ilyen súlysorozat mérősúlyaival például nem mérhetünk egyenlő tömegeket, ha a súlyok különböző csoportjait helyezzük a súlyserpenyőbe. A 2 hatványok sorozata például nyilván gazdaságos, hisz bármely eleme nagyobb a nála kisebbek összegénél, de épp ez az oka annak, hogy ez a sorozat túl gyorsan növekszik: nyolcadik eleme, $2^{7}$ már nagyobb, mint 100. A 2 hatványok azonban felhasználhatók 100-nál kisebb számokból álló gazdaságos sorozat készítésére.
A 2 első hat nem negatív kitevőjű hatványa, az 1, 2, 4, 8, 16, 32 sorozat tehát gazdaságos, az elemeiből készíthető összegek éppen az 1 és a $2^{6} - 1 = 63$ közé eső egészeket adják. Ezért a 3-szorosaikból, a 3, 6, 12, 24, 48, 96 számokból képezett összegek között sincsenek egyenlők, és ezek az összegek éppen a 3 és a $3 \cdot 63 = 189$ közé eső, 3-mal osztható számok.
Azt állítjuk, hogy ha ehhez a hat darab számhoz még hozzávesszük a 95 és a 97 számokat, akkor az így kapott 8-elemű sorozat még mindig gazdaságos marad. A már meglevőkön kívül ugyanis a következő új összegeket kaphatjuk :
1. A 97 szerepel bennük tagként, a 95 pedig nem; az ilyen összegek 1 maradékot adnak 3-mal osztva, és nyilván bármely kettő különböző.
2. A 95 szerepel bennük tagként, a 97 pedig nem ; az ilyen összegek 2 maradékot adnak 3-mal osztva, és közöttük sincsenek egyenlők.
3. Mind a két új szám, a 95 és a 97 is szerepel bennük tagként. Az ilyen összegek oszthatók 3-mal, de nem kisebbek, mint $95 + 97 = 192$ ; természetesen ezek az összegek is páronként különbözők.
Látható, hogy a két újabb szám hozzávételével létrejövő új összegek az eddigiektől és egymástól is különböznek és így a 3, 6, 12, 24, 48, 95, 96, 97 számok valóban a feladat egy megoldását adják.

Megjegyzés. Általában is igaz, hogy a

3

3 \cdot 2

3 \cdot 2^{2}

...

3 \cdot 2^{k - 1}

3 \cdot 2^{k} - 1

3 \cdot 2^{k}

3 \cdot 2^{k} + 1

sorozat gazdaságos. A következő megoldásból kiderül, hogy nem a legjobb abban az értelemben, hogy a sorozat legnagyobb eleme csökkenthető. Az alábbiakban megadunk egy elégséges feltételt arra, hogy egy 8-elemű sorozat gazdaságos legyen ‐ a feltétel általában is megfogalmazható ‐, majd ezt felhasználva elkészítünk egy megfelelő sorozatot.

II. megoldás. Természetesnek tűnik, hogy kíséreljük meg előírni a létrejövő összegek nagyságviszonyát: az innen nyerhető feltételek remélhetőleg segítségünkre lesznek a sorozat konstrukciójában.
Próbáljuk meg tehát a készíthető összegeket a következőképpen rendezni:
a) ha két összeg különböző számú tagból áll, akkor legyen az a kisebb, amelyiknek kevesebb tagja van;
b) ha két összeg ugyanannyi tagból áll, akkor legyen az a kisebb, amelyikben ‐ az esetleges közös tagok elhagyása után ‐ a legkisebb tag kisebb.
Ha van ilyen számsorozat, akkor az nyilván gazdaságos, csak az nem világos, vajon teljesíthető-e a két feltétel egyidejűleg. Vegyük észre, hogy mindkét feltétel valahogyan azt biztosítja, hogy a sorozat elemei egymáshoz képest ne legyenek túl nagyok ‐ például a legnagyobb elem kisebb, mint a két legkisebb összege ‐, várható tehát, hogy ezek révén sikerül 100-nál kisebb számokból álló megoldását találni a feladatnak.
Jelölje a sorozat elemeit nagyság szerint növekvő sorrendben

a_{1}, a_{2}, ..., a_{s}

. Az elemek rendezése miatt a második feltétel teljesül, ha

\begin{matrix} a_{i} + a_{8} & < a_{i + 1} + a_{i + 2}, & ( & 1 ≦ i ≦ 5); & (1) \\ a_{i} + a_{7} + a_{8} & < a_{i + 1} + a_{i + 2} + a_{i + 3}, & ( & 1 ≦ i ≦ 3); & (2) \\ a_{i} + a_{6} + a_{7} + a_{8} & < a_{i + 1} + a_{i + 2} + a_{i + 3} + a_{i + 4}, & ( & i = 1) . & (3) \end{matrix}

A fenti egyenlőtlenségek bal oldalán az

a_{i}

-t tartalmazó legnagyobb, jobb oldalán pedig az

a_{i}

-nél nagyobb elemeket tartalmazó legkisebb összegek állnak. A biztosan elhagyható közös tagok miatt a feltételt elegendő a legfeljebb négy tagú összegekre előírni. Ugyanez az oka az

i

-re vonatkozó megszorításoknak is, hisz például

i = 2

-re (3) és (2) azonos,

i = 4

-re pedig mindhárom feltétel az

a_{4} + a_{8} < a_{5} + a_{6}

alakot ölti.
Vegyük észre még, hogy

i = 1 -

re (3)-ból következik (2) ‐ mert

a_{5} < a_{6}

‐

i = 1

2

3

-ra pedig (2)-ből hasonlóan következik (1).
A sorozatnak először a három legnagyobb elemét,

a_{8}

-at,

a_{7}

-et és

a_{6}

-ot adjuk meg, ezután

a_{5}

és

a_{4}

kiválasztására (1)-et,

a_{3}

és

a_{2}

kiválasztására az erősebb (2)-t,

a_{1}

kiválasztására pedig a még erősebb (3)-at használjuk.
Az első feltételhez szükséges, hogy a sorozat kis elemei se legyenek túl kicsik, ezért az öt legkisebb elem értékét az (1), (2), illetve (3) szerint lehetséges legnagyobbnak választjuk, azaz (1)-ből

i = 5

-re és

i = 4 -

\begin{matrix} a_{5} = a_{6} + a_{7} - a_{8} - 1, a_{4} = a_{5} + a_{6} - a_{8} - 1 : \end{matrix}

(2)-ből

i = 3

-ra és

i = 2

-re

\begin{matrix} a_{3} = a_{4} + a_{5} + a_{6} - a_{7} - a_{8} - 1, a_{2} = a_{3} + a_{4} + a_{5} - a_{7} - a_{8} - 1; \end{matrix}

végül (3)-ból

i = 1

-re

\begin{matrix} a_{1} = a_{2} + a_{3} + a_{4} + a_{5} - a_{6} - a_{7} - a_{8} - 1. \end{matrix}

(4)

Ekkor tetszőleges

a_{8} > a_{7} > a_{6}

számokból kiindulva nyilván

a_{6} > a_{5} > a_{4} > a_{3} > a_{2} > a_{1},

másrészt így az egyenlő tagszámú összegek valóban különbözők lesznek.
Biztosítani kell még, hogy a sorozat elemei pozitív számok legyenek, továbbá természetesen a különböző tagszámú összegek rendezésére vonatkozó előírást. Ez utóbbi meglepő módon következik a látszólag kevesebbet állító

\begin{matrix} a_{1} + a_{2} + a_{3} + a_{4} > a_{6} + a_{7} + a_{8} \end{matrix}

(5)

feltételből; eszerint elegendő, ha csak arra figyelünk, hogy a legkisebb négy tagú összeg nagyobb legyen, mint a legnagyobb háromtagú.
Valóban, az elemek rendezése miatt

\begin{matrix} a_{2} - a_{8} < a_{3} - a_{7} < a_{4} - a_{6} < {\underset{︸}{a_{5} - a_{5}}}_{0}^{} < a_{6} - a_{4} < a_{7} - a_{3} < a_{8} - a_{2} . \end{matrix}

(6)

Ha most az itt felsorolt különbségeket nagyság szerint növekvő sorrendben rendre

a_{1}

-hez adjuk, akkor minden lépésben a legkisebb

k

-tagú és a legnagyobb (

k - 1

)-tagú összeg különbségét kapjuk, ha

k = 2

3

...

8

. Ez a különbség (6) szerint az első három lépés során csökken, a negyedikben nem változik, attól fogva pedig nő, így a legkisebb

k

-tagú és a legnagyobb (

k - 1

)-tagú összeg különbsége a

k = 3

(és a

k = 4

) esetben minimális. Az (5) feltétel szerint pedig ez a minimum pozitív, így a legkisebb

k

-tagú összeg minden

2 ≦ k ≦ 8

esetén nagyobb, mint a legnagyobb (

k - 1

)-tagú. Az (5) feltétel tehát valóban biztosítja, hogy a különböző tagszámú összegek olyan módon legyenek rendezve, ahogyan azt előírtuk.
Ha most

a_{7} = a_{8} - 1, a_{6} = a_{8} - 2

, akkor a rekurziós formulák szerint

a_{5} = a_{8} - 4, a_{4} = a_{8} - 7, a_{3} = a_{8} - 13, a_{2} = a_{8} - 24, a_{1} = a_{8} - 46.

Az így definiált sorozatra pontosan akkor teljesül (5), ha

a_{8} > 87

. Eszerint például

a_{8} = 88

-ból kiindulva a

\begin{matrix} 88, 87, 86, 84, 81, 75, 64, 42 \end{matrix}

sorozatot kapjuk; ez a sorozat a konstrukcióról bizonyítottak szerint megfelel a feladat előírásainak.

Megjegyzések. 1. Ha a sorozat értelmezését adó feltételeket kissé módosítjuk (az

a_{1}

-et (4) helyett elegendő a (2) szerinti

a_{1} = a_{2} + a_{3} + a_{4} - a_{7} - a_{8} - 1

összefüggésből számolni, ugyanis ha a nyolc szám összege páratlan, akkor nyilván nem kaphatunk egyenlő négy tagú összegeket; másrészt ‐ és ezt gondolja meg az olvasó ‐ ha (5) helyett csak annyit írunk elő, hogy a legkisebb négy tagú összeg 1-gyel legyen kisebb a legnagyobb háromtagúnál, akkor még mindig nem lesznek egyenlők a különböző tagszámú összegek között), akkor a 84, 83, 82, 80, 77, 71, 60, 40 sorozatot kapjuk.
Számológéppel sem sikerült olyan 8-elemű gazdaságos sorozatot találni, ahol a legnagyobb elem 84-nél kisebb, bár a program nem nézett végig minden lehetőséget.
Az Sz. 55. feladatban olyan programot kellett írni, amely kétjegyű számokból álló gazdaságos sorozatot állít elő. A beküldött programok döntő többsége nem alkalmas a feladat valódi megoldására, hiszen ‐ jó esetben ‐ évekig futna. A szerzőket ez a tény nem látszott zavarni.
2. A probléma szoros kapcsolatban van az F. 2584. feladattal (a megoldást lásd az 1986. évi 7. szám 304. oldalán). Ott azt bizonyítottuk be, hogy két jegyű számokból álló 10-elemű gazdaságos sorozat nem létezik. Az ottani bizonyítás 9-elemű sorozatra nem működik, másfelől a mostani konstrukciók egyike sem ad 9-elemű gazdaságos sorozatot.