Kezdőlap


Cím:	Két arithmetikai feladat megoldásáról
Szerző(k):	Weisz József
Füzet:	1905/december, 91 - 97. oldal	PDF \| MathML
Témakör(ök):	Szakmai cikkek

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.

A következökben két feladat általános megoldását keresve, a talált eredményeket oly számpéldák megfejtésére használhatjuk fel, melyeket enélkül csak találgatás által oldhatnánk meg. E találgatás köre és ideje bizonyos rendszer követésével ugyan meglehetősen korlátolható, de mivel utóvégre mégis csak találgatás, nem vehető egyenértékűnek ama ideális eljárással, mely az ily feladatok megoldását is egyenlettől várja, egészen eltekintve attól, hogy a dolog lényegébe való bepillantást sem teszi lehetővé.
E feladatok elseje a következő:
Hány szám alkotható $n$ külömböző (egész) számból az összeadás műveletével.
A számokat egyesével véve $(\binom{n}{1})$ számot kapunk; két-két számot összeadva és figyelembe véve, hogy önmagával a szám nem kombinálható, valamint azt is, hogy $a + b = b + a, (\binom{n}{2})$ külömböző számot nyerünk.
Három-három szám összegezése által az így nyert számok száma $(\binom{n}{3})$ .
$i$ -esével kombinálva a számokat $(\binom{n}{i})$ kombinációt kapunk.
Mind az $n$ számot összeadva, csak egy számot kapunk; az $n$ -es kombinációk száma $(\binom{n}{n})$ .
Az $n$ elemből az összeadás műveletével alkotható külömböző számok összes száma tehát:

\begin{matrix} \sum = (\binom{n}{1}) + (\binom{n}{2}) + (\binom{n}{3}) + \dots + (\binom{n}{i}) + \dots + (\binom{n}{n - 1}) + (\binom{n}{n}) \end{matrix}

Ezen egyenlet mindkét oldalához

(\binom{n}{0}) = 1

-et adva

\begin{matrix} 1 + \sum = (\binom{n}{0}) + (\binom{n}{1}) + (\binom{n}{2}) + \dots + (\binom{n}{i}) + \dots + (\binom{n}{n - 1}) + (\binom{n}{n}) = \sum_{i = 0}^{}^{n} (\binom{n}{i}) . \end{matrix}

Ámde a binomi együtthatókról ismeretes tétel alapján, mely az

{(1 + 1)}^{n}

hatvány kifejtésével bizonyítható:

\begin{matrix} \sum_{i = 0}^{}^{n} (\binom{n}{i}) = 2^{n}, \end{matrix}

így tehát

\begin{matrix} \sum = 2^{n} - 1 = \frac{2^{n} - 1}{2 - 1} . \end{matrix}

Ez tehát az

n

elemből tisztán összeadás útján alkotható külömböző számok száma, hol még meg kell jegyeznünk azt, hogy az így nyert számok közül még ama esettől teljesen eltekintve, hogy az

n

elem között egyenlők is lehetnek, amit ki is zártunk, lehetnek egyenlők, mert például lehetséges, hogy:

\begin{matrix} a + b = c + d, \end{matrix}

de ez általában nem következik be és így a fenti eredmény veendő általános érvényűnek.

A második feladat ez:
Hány szám képezhető

n

elemből az összeadás és kivonás műveletével csak abszolút értékre való tekintettel?
A tárgyalás általánossága kedvéért ragadjunk ki az

n

számú elemből

k

számút és tegyük tel, hogy csak az összeadás jelével kapcsoljuk őket, miáltal előbbiek szerint

(\binom{n}{k})

számot nyerünk. Mivel pedig

(\binom{k}{0}) = 1

. Az ily módon nyert számok száma így írható:

\begin{matrix} (\binom{n}{k}) (\binom{n}{0}) . \end{matrix}

Ha már most az egyik szám a

k

közül negatív jelű, akkor mindegyik

k

-s csoportból

(\binom{k}{1})

számú újabb csoport alkotható, mert a

k

-s csoport

k

számú elemeinek mindegyike egyenként negatív jelet vehet fel, tehát az előbbi

(\binom{n}{k})

csoportból összesen

(\binom{n}{k}) (\binom{k}{1})

számú oly

k

elemből álló csoport képezhető, melyben az elemek közül csak egy negatív jelű.
Ha két elem kapcsolódik negatív jellel, akkor mindegyik

k

-s csoportból

(\binom{k}{2})

számú új szám alakulhat. Összesen tehát a két negatív jelű elemmel alkotható

k

elemű számok száma

(\binom{n}{k}) (\binom{k}{2})

.
Ha a

k

elemből

i

számúnak előjele negatív, akkor a

k

-s csoportból ily módon alkotott számok száma

(\binom{n}{k}) (\binom{k}{i})

.
Végül, ha mind a

k

elem negatív jellel kapcsolódik, az így alkotható számok száma

(\binom{n}{k}) (\binom{k}{k})

.
Az

n

elemből alkotható összes

k

elemű számok száma tehát, melyek összeadás és kivonás útján keletkezhetnek:

\begin{matrix} (\binom{n}{k}) [(\binom{k}{0}) + (\binom{k}{1}) + (\binom{k}{2}) + \dots + (\binom{k}{i}) + \dots + (\binom{k}{k - 1}) + (\binom{k}{k})] = (\binom{n}{k}) 2^{k} . \end{matrix}

Azonban e számok nem lesznek mind külömbözőek, amennyiben ől.

| a - b | = | b - a |

vagy pl.

| a + b - c - d | = | c + d - a - b |

.
Ennek figyelembe vételével azt találjuk, hogy a fenti összegben minden szám éppen kétszer fordul elő, ha csak abszolút értékre vagyunk tekintettel. Így tehát az

n

elemből az összeadás és kivonás műveletével alkotható

k

elemű külömböző számok száma

\frac{1}{2} (\binom{n}{k}) 2^{k}

.
Miután

k

az összes egészszámú értékeket felveheti

1

-től

n

-ig, az

n

elemből összeadás és kivonás útján alkotható összes külömböző számok száma:

\begin{matrix} \sum = \frac{1}{2} [(\binom{n}{1}) 2^{1} + (\binom{n}{2}) 2^{2} + (\binom{n}{3}) 2^{3} + \dots + (\binom{n}{k}) 2^{k} + \dots + (\binom{n}{n - 1}) 2^{n - 1} + (\binom{n}{n}) 2^{n}] \end{matrix}

vagy pedig miután

\begin{matrix} \frac{1}{2} (\binom{n}{0}) 2^{0} = \frac{1}{2} \end{matrix}

azért

\begin{matrix} \frac{1}{2} + \sum = \frac{1}{2} [(\binom{n}{0}) 2^{0} + (\binom{n}{1}) 2^{1} + (\binom{n}{2}) 2^{2} + \dots + (\binom{n}{k}) 2^{k} + \dots + (\binom{n}{n}) 2^{n}], \end{matrix}

vagyis

\begin{matrix} \frac{1}{2} + \sum = \frac{1}{2} {(1 + 2)}^{n} = \frac{1}{2} \cdot 3^{n}, \end{matrix}

miből

\begin{matrix} \sum = \frac{1}{2} (3^{n} - 1) = \frac{3^{n} - 1}{2} = \frac{3^{n} - 1}{3 - 1} . \end{matrix}

Érdekes a két feladat eredményének összehasonlítása egy konkrét számpélda esetén. Így pld.

5

külömböző számból tisztán összeadással

31

külömböző szám alkotható, összeadás és kivonással

141

.
A talált eredményeket már most vizsgálat alá vesszük.

n

számú elemből csak az összeadás jelével

\frac{2^{n} - 1}{2 - 1}

számú szám alkotható. E számok közül, mint jeleztük, lehetnek egymással véletlenül egyenlők is, de minket különösen azon eset érdekel, mikor e számok egymástól mind külömbözőek.
Ezen esetre is eleve kimondhatjuk, hogy ezen külömböző számok száma legfeljebb

\frac{2^{n} - 1}{2 - 1}

lehet.
Kimutatjuk most azt, hogy ha az

n

elem úgy van választva, hogy az elemek egy mértani sor tagjai, akkor mind a

\frac{2^{n} - 1}{2 - 1}

szám külömböző, megjegyezve azt, hogy a

\frac{2^{n} - 1}{2 - 1}

szám külömbözőségének ez nem szükséges, de elegendő feltétele.
Tegyük ugyanis fel, hogy a szóban levő elemek:

a^{p}, a^{q}, a^{l}, a^{m}

stb. és ezek között következő összefüggés állana fenn:

\begin{matrix} a^{p} + a^{q} + a^{l} + a^{m} + \dots = a^{x} + a^{y} + a^{v} + a^{z} + \dots \end{matrix}

(I)

hol

p, q, l, m

stb. pozitív egész számok. Legyen az elemek legkisebbike pl.

a^{p}

, akkor az

(I)

egyenlet így is írható:

\begin{matrix} 1 + a^{q - p} + a^{l - p} + a^{m - p} \dots = a^{x - p} + a^{y - p} + a^{v - p} + a^{z - p} + \dots \end{matrix}

(II)

Mértani sorról lévén szó,

p, q, l, m, x, y, v, z ...

egymástól külömbözőek és így

q - p, l - p ...

stb. külömbözőek a zérustól és így a hatványmennyiségek mindegyike a

(I I)

egyenletben külömbözö az

(I)

-től.
Ha

a

páros szám, minden hatványa és így hatványainak összege is páros szám. A

(I I)

egyenlet jobb oldalán álló páros szám tehát a bal oldalon álló páratlannal volna egyenlő, ami kiinduló feltevésünk helytelenségét bizonyítja. Ugyanerre jutunk, ha

a

-t páratlannak tételezzük fel.
Teljesen ugyanez áll a második feladat esetén is. Ugyanis nem kell egyebet tennünk, mint az

(I)

egyenletet ezen alakra hozni:

\begin{matrix} a^{p} + a^{q} - a^{x} - a^{z} + \dots = a^{y} - a^{l} + a^{v} - a^{m} - \dots \end{matrix}

Ezen egyenlet szerint feltesszük, hogy valamely mértani sor bizonyos számú tagját az összeadás és kivonás jelével kapcsolva, az így nyert eredmény ugyanezen mértani sor más elemeinek az összeadás és kivonás jeleivel való kapcsolás által nyert eredményével volna egyenlő.
Ezen feltevés helytelensége teljesen azonos módon bizonyítható, mint előbb.
Ha tehát

n

elem úgy van választva, hogy valamely mértani sor tagjai, más szóval egy és ugyanazon alapszám hatványai, akkor az ezen

n

elemből tisztán összeadással, vagy összeadás és kivonás által alkotható

\frac{2^{n} - 1}{2 - 1}

, illetőleg

\frac{3^{n} - 1}{3 - 1}

számú szám egymástól mind külömböző lesz.
Azon esetben, ha az így alkotott számok egymástól mind külömbözőek, különös figyelmet érdemel azon eset, midőn az egymástól külömböző

\frac{2^{n} - 1}{2 - 1}

, illetőleg

\frac{3^{n} - 1}{3 - 1}

számú szám a természetes számsort alkotja

1

-től

\frac{2^{n} - 1}{2 - 1}

, illetőleg

\frac{3^{n} - 1}{3 - 1}

-ig. Határozzuk meg ezen esetben az

n

számot.
Vegyük az első esetet, midőn az

n

számból pusztán összeadás által az

1

-től

\frac{2^{n} - 1}{2 - 1}

-ig terjedő összes egész számokat alkothatjuk.
Miután mind az

n

szám összeadása által az alkotható számok legnagyobbikát, tehát esetünkben

\frac{2^{n} - 1}{2 - 1}

-et kell kapnunk, világos, hogy a kérdéses

n

szám összege

\begin{matrix} \sum (n) = \frac{2^{n} - 1}{2 - 1} . \end{matrix}

(1)

De az (1) egyenlet egy oly

n

tagú mértani sor összege, melynek els tagja

1

, hányadosa pedig

2

, maga a sor:

\begin{matrix} 1, 2, 4, 8, ... 2^{n - 1} \end{matrix}

Valóban e számok és csakis ezek felelnek meg a feltételnek, amit könnyű belátni. Ugyanis a fenti mértani sor elemeinek száma

n

lévén, előbbiek szerint legfeljebb

\frac{2^{n} - 1}{2 - 1}

külömböző szám alkotható belőlük összeadás útján és hogy eme

\frac{2^{n} - 1}{2 - 1}

számú szám tényleg egymástól külömböző, az az előbb mértani sorok tagjaira adott általános bizonyításból folyik.
Keressük most azon

n

számot, melyekből összeadás és kivonás útján a természetes számsornak

1

-tól

\frac{3^{n} - 1}{3 - 1}

-ig terjedő összes tagjai előállíthatók. Mint előbb, úgy most is, ha mind az

n

elem pozitív jellel kapcsolódik, akkor kapjuk a legnagyobb számot,

\frac{3^{n} - 1}{3 - 1}

-et, tehát

\begin{matrix} \sum (n) = \frac{3^{n} - 1}{3 - 1} . \end{matrix}

(2)

Ez egyenlet jobb oldala egy oly

n

tagú mértani sor összege, melynek első tagja

1

, hányadosa

3

, maga a sor:

\begin{matrix} 1, 3, 9, 27, ... 3^{n - 1} \end{matrix}

Hogy e számok valóban megfelelnek és csakis ezek, az előbbi módon rögtön belátható.
A mondottak alkalmazását végül még két számpéldán mutatjuk meg, melyek tulajdonképpeni indító okai voltak a megelőző elméletnek.
Valaki

1023 K

-át

10

zsákban oly módon osztott meg, hogy bármely

1

-től

1023 K

-ig terjedő egész számú koronákban kifejezhető összeget egész számú zsákokban fizetheti (vagyis úgy, hogy bármely a mondott határok között levő összegnél sem fogja valamely zsák tartalmának csak egy részét igénybe venni.) Hogyan oszlik meg fenti összeg az egyes zsákokban?
Az előbbiek szerint

10

elemből legfeljebb

\frac{2^{10} - 1}{2 - 1}

külömböző szám alkotható. És mivel

\frac{2^{10} - 1}{2 - 1} = 1023

, azért, ha az

1

-től

1023

-ig terjedő összes egész számokat akarjuk alkotni, a szóban forgó tíz szám, mely esetünkben az egyes zsákok tartalmának kifejezője csak ez lehet :

\begin{matrix} 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, \end{matrix}

melyek tényleg a feladatnak megfelelnek.
Azt az általános tárgyalásból már tudjuk, hogy ezen

10

számból

1023

-nál nagyobb szám nem alkotható, de lássuk azt, hogy ha

10

számból pl.

1

-től

1000

-ig terjedő számokat akarnók alkotni, minő eredményre jutnánk?
Mindenekelőtt világos, hogy ez esetben a feladatnak több megoldása van. Az egyiket rögtön megkapjuk, ha a fenti

10

szám közül

9

-et megtartunk és a

10

-iket megkapjuk, ha

512

-ből

23

-at levonunk, vagyis a

10

-ik szám

489

. Egy másik megoldás az első nyolcz szám megtartásával, ha

9

-diknek

255, 10

-diknek

490

-et vesszük s í. t. Hogy ilyen esetben hány megoldás lehetséges, ugyan igen érdekes, de most fejtegetni nem kívánjuk.
Áttérünk inkább a második esetre vonatkozó számpéldára.
Egy kereskedőnek mérlegéhez

4

darab, összesen

40 kg

. súlynyi súlya van, melyekkel

1

-től

40 kg

-ig terjedőleg bármely egész számú kg-okban kifejezhető súlyt mérhet mérlegén. Melyek e súlyok?
Egyenlő karú mérlegről lévén szó, valamely tetszőleges súly az egyik mérlegserpenyőben vagy az illető serpenyőbe helyezett bizonyos számú súly által idézhető elő, mint ezen súlyok összege; vagy a másik serpenyőbe is helyezünk egyes súlyokat, miáltal utóbbiak súlyának összege az elóbbiekéből levonódik. Szóval itt azon esettel van dolgunk, midőn

n

elemből összeadás és kivonás által alkotunk számokat.
Miután esetünkben

n = 4

, az ezen

4

elemből alkotható számok száma legeljebb

\frac{3^{n} - 1}{3 - 1}

lehet és mivel az

1

-től

40 -

ig terjedő számok alkotandók, a keresett megoldás, vagyis az egyes súlyok értéke :

\begin{matrix} 1 kg, 3 kg, 9 kg  és, 27 kg . \end{matrix}

Ezen esetben is, ha az alkotandó számok száma

\frac{3^{n} - 1}{3 - 1}

-nél kisebb, a megoldások száma egynél nagyobb.