Kezdőlap


Feladat:	1362. matematika gyakorlat	Korcsoport: 14-15	Nehézségi fok: nehéz
Megoldó(k):	Ábrahám L. , Bakós T. , Bara T. , Bartha M. , Bartolits J. , Besenyei L. , Császár Gy. , Cséplő G. (Bp.) , Domokos Mária , Hargitay B. , Hasenfratz Anna , Horváth Eszter , Horváth Mária , Illés Gábor , Izsák Éva , Kémeri Viktória , Kollár J. (I. oszt.) , Kovács Z. , Lakner P. , Meszéna G. , Nagy Z. , Oláh Vera , Pallagi D. , Párkány Katalin , Pócsi Gy. , Pósfai Gy. , Remsei F. , Rózsás L. , Rudolf L. , Ruttkai Zsófia , Rövid K. , Schvarcz T. , Somogyi Á. , Sparing L. , Terlaky T. , Turschl J. , Törő Ágnes , Vass Éva , Vecsernyés P. , Wettstein J.
Füzet:	1971/október, 65 - 67. oldal		PDF \| MathML
Témakör(ök):	Rekurzív eljárások, Kombinációk, Számsorozatok, Gyakorlat
Hivatkozás(ok):	Feladatok: 1971/április: 1362. matematika gyakorlat

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. Minden jelenlevőnek 2 más jelenlevővel van a kérdés szempontjából figyelembe veendő kapcsolata, egyikkel házastársi (a vázlaton kettős vonal) és testvéri (egyes vonal). Jelöljük $n$ házaspár esetén a lehetséges (mondjuk valaki által tippelhető) esetek számát $t_{n}$ -nel.
Kezdjük a meggondolásunkat a társaság legidősebb tagjával, $A$ -val (egyértelműen kiválasztható), legyen a házastársa $a$ , testvére pedig $b$ , továbbá $b$ házastársa $B$ (1. ábra). Ezek nyilvánvalóan mind különböző személyek, tehát $n \geq 2$ , ennélfogva $t_{1} = 0$ .
Az $n = 2$ esetben nincs is több jelenlevő, így a második testvérpár csak $B$ , $a$ lehet, de mivel $b$ -ként a második házaspár mindegyik tagja figyelembe veendő, azért $t_{2} = 2$ .
Ha $n = 3$ , akkor $B$ és $a$ nem lehetnek testvérek, különben a harmadik házaspár egyben testvérpár is volna. Így $B$ testvére a harmadik házaspár valamelyik tagja, jelöljük $c$ -vel, házastársát $C$ -vel, és ekkor $C$ testvére csak $a$ lehet. Eddigi gondolatmenetünkben most $b$ -re 4-féleképpen tippelhetünk az $A$ , $a$ után hátra levő 2 házaspár tagjai közül, $c$ -re 2-féleképpen, ezért $t_{3} = 4 \cdot 2 = 8$ (2. ábra).

\begin{matrix} \begin{matrix} {\underset{︸}{a = A - b = B}}_{}^{} & {\underset{︸}{a = A - b = B - c = C}}_{}^{} & {\underset{︸}{c = C - d = D}}_{}^{} \\ 1. ábra & 2. ábra & 3. ábra \end{matrix} \end{matrix}

n = 4

esetben

B

testvére ismét lehet

a

, vagy a társaság egy az eddigiektől (

A

a

b

B

) különböző tagja, most ezt jelölje

c

.
Az előbbi esetben az első két házaspár olyan megoldást ad, mint

n = 2

esetén és ugyanez áll a kimaradt két házaspárra, az utóbbiak lehetőségeit a közülük legidősebb személyből,

C

-ből kiindulva vesszük számba, a társaság ekkor 2 körbe állítható (1. és 3. ábra).
Az utóbbi esetben

c

házastársának,

C

-nek testvére ismét nem

a

, tehát a 4. házaspár valamelyik tagja, legyen

d

, ekkor ennek házastársa,

D

alkot testvérpárt

a

-val; ekkor a tippet leíró ábra a ,,‐

d = D

'' résszel hosszabb a 2. ábrabelinél, ismét 1 körbe állítható az összes jelenlevő. Most

b

-re mindenképpen 6-féle tipp lehetséges, tovább pedig az 1. és 3. ábra szerint

d

-re

t_{2}

, azaz 2 tipp (ekkor ugyanis

c

-t nem választjuk, hanem kiadódik), az utóbbi esetben pedig

c

-re 4 és

d

-re 2, vagyis a folytatásra

4 \cdot 2

, így

t_{4} = 6 (2 + 4 \cdot 2) = 60

.
Végül

n = 5

esetében az eddigiek mintájára a vagy

B

-nek vagy

C

-nek vagy pedig az ötödik pár

E

tagjának a testvére. Az első és második esetben a még maradó 3, ill. 2 házaspárból alakul az újabb kör az

n = 3

, ill.

n = 2

szerint;

b

-re mindenképpen 8 lehetőség van,

c

vagy kiadódik vagy 6 személy közül választható, az utóbbi esetben

d

vagy kiadódik vagy 4 közül,

e

pedig 2 közül választható:

\begin{matrix} t_{5} = [t_{3} + 6 (t_{2} + 4 \cdot 2)] = 8 (8 + 60) = 544. \end{matrix}

II. megoldás. Jelöljük a házaspárokat az

1,2, ..., n

sorszámokkal, a

k

-adik pár két tagját

k_{1}

-gyel és

k_{2}

-vel (

1 \leq k \leq n

); legyen továbbá az

n

házaspár testvér-párokba rendezési lehetőségeinek száma

t_{n}

.
Legyen

1_{1}

testvére

k_{i}

, ahol

k \neq 1

és

i = 1

, vagy 2, tehát megválasztására

2 (n - 1)

lehetőség van. Tekintsük

k_{i}

házastársának,

k_{3 - i}

-nek testvérét. Ha ez éppen

1_{2}

, akkor az 1-es és a

k

jelű házaspárt elintéztük és a maradó

(n - 2)

házaspár testvérpárokba rendezési lehetőségeinek számat

t_{n - 2}

.
Ha pedig

k_{3 - i}

és

1_{2}

nem testvérek, akkor tekinthetők egy ál-házaspárnak, mert megvan ugyanaz a tulajdonságuk, ami számunkra a valódi házaspárokból egyetlen figyelembe veendő, hogy ti. nem alakítható belőlük testvérpár. Így a további

(n - 1)

párból (valódi és ál) kell

(n - 1)

testvérpárt alakítanunk, erre

t_{n - 1}

lehetőség van. Más lehetőség nincs

k_{3 - i}

-re, eszerint

\begin{matrix} t_{n} = (2 n - 2) (t_{n - 2} + t_{n - 1}) . \end{matrix}

Ezzel

t_{n}

meghatározását visszavezettük

t_{n - 1}

és

t_{n - 2}

meghatározására, és tulajdonképpen bármely

n

természetes szám esetére megoldottuk a feladatot a kapott ún. rekurzív (visszafutó, korábbi értékekre támaszkodó) képlettel.
Mármost

t_{1} = 0

és

t_{2} = 2

(hiszen

1_{1}

testvérének próbálandó

2_{1}

is,

2_{2}

is, és ez meghatározza a másik testvérpárt is), ezek alapján

t_{3} = 4 (t_{1} + t_{2}) = 8

;

t_{4} = 6 (t_{2} + t_{3}) = 60

; végül

t_{5} = 8 (t_{3} + t_{4}) = 544

Megjegyzés. Az I. megoldás gondolatmenetét követve tetszőleges

n

-re kapjuk a

\begin{matrix} t_{n} = (2 n - 2) t_{n - 2} + (2 n - 2) (2 n - 4) t_{n - 3} + ... + (2 n - 2) (2 n - 4) \cdot ... \cdot 4 t_{1} + \\ + (2 n - 2) (2 n - 4) \cdot ... \cdot 4 \cdot 2 \end{matrix}

összefüggést. Ennek alapján is meghatározható

t_{n}

értéke lépésről lépésre.