Kezdőlap


Feladat:	1336. matematika feladat	Korcsoport: 16-17	Nehézségi fok: átlagos
Megoldó(k):	Vesztergombi Katalin
Füzet:	1965/április, 171 - 172. oldal		PDF \| MathML
Témakör(ök):	Gráfok összefüggősége, Irányított gráfok, Kombinatorikai leszámolási problémák, Feladat
Hivatkozás(ok):	Feladatok: 1964/szeptember: 1336. matematika feladat

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. Az 1. ábra bejárása azonos feladat a 2. ábráéval. Ennek két szimmetriatengelye van, a $C D$ és az $A B$ egyenes. Kezdőpont csak $A$ és $B$ lehet, a felsorolásokban $A$ -t vesszük annak, így a végpont $B$ . A $C$ és $D$ közti két közvetlen út miatt az első ilyen átmenet útszakaszát $2$ -féleképpen választhatjuk. Az $A B$ szimmetriatengelyre tekintettel elég a csomópontoknak azokat a bejárási felsorolásait megadnunk, amelyekben a tükrös $C$ , $D$ pár tagjai közül előbb haladunk át $C$ -n, mint $D$ -n. Ezek szerint a bejárások száma a megadandó felsorolások számának $2 \cdot 2 \cdot 2 = 8$ -szorosa lesz.

1. ábra

2. ábra

Az első két útszakaszra

3

lehetőség van:

A B C

A C B

és

A C D

. Az első eset 3. szakasza

2

-féleképpen választható, 7. szakasza viszont egyértelműen

D B

, mert

B

-be már csak így juthatunk el (ezt a továbbiakban kövér betűkkel tüntetjük fel, a még beiktatandó betűk helyét jelző pontok után):

A B C A ... DB

ill.

A B C D ... DB

. Az előbbiben csak

D C

állhat a pontok helyén, az utóbbiban

A C

vagy

C A

(a még meg nem rajzolt

D A C

,,háromszög'' kétféleképpen járható be).
A második eset az

A C B A ... DB

és

A C B D ... DAB

továbbfejlesztéseken át

1 - 1

felsorolást ad, a pontok helyére csak

D C

, ill.

C

írható.
A harmadik eset 3. lépése

3

-féleképpen választható:

A C D A B ... B

A C D C B ... B

és

A C D B ... B

, és a pontok helyére a még hátra levő szakaszokból álló

B C D

, ill.

B A D

háromszög, ill. a

B A D C

négyszög bejárása mindig

2

-féleképpen írható be.
Ezek szerint a csomópontok felsorolásainak száma

(1 + 2) + (1 + 1) + 3 \cdot 2 = 11

. a keresett lehetőségek száma pedig

11 \cdot 2 \cdot 2 \cdot 2 = 88

.
Vesztergombi Katalin ( Budapest, Fazekas M. gyak. g. III. o. t.)

II. megoldás. A 926. gyakorlat II. megoldásának gondolatát alkalmazzuk a

C

-beli váltókra. Az ottani

3 a

és

3 b

ábrák szerint bejárandó útvonalunk az itteni

3 a

és

3 b

ábrákra egyszerűsödik.

3. ábra

3 a

ábránk azonos a 926. gyakorlat 2. ábrájával, csupán

C

helyére

D

-t kell írnunk. Így kapjuk az ottani I ‐ IV. felsorolásból a következőket:

\begin{matrix} \begin{matrix} A & B & y_{1} & D & x_{1} & A & x_{2} & D & y_{2} & B, & (I'.) \\ A & x_{1} & D & x_{2} & A & B & y_{1} & D & y_{2} & B, & (II'.) \\ A & x_{1} & D & y_{1} & B & y_{2} & D & x_{2} & A & B, & (III'.) \\ A & x_{1} & D & y_{1} & B & A & x_{2} & D & y_{2} & B, & (IV'.) \end{matrix} \end{matrix}

ahol az

x

és

y

betűk azokat a helyeket jelölik a szomszédos

A, D

, ill.

B, D

betűpárok között, ahová pl. az

A

-ból

C

-n át

D

-be vivő, rövidítve rajzolt útba

C

beírható, persze csak az egyik

x

helyére. Az egyik

C

(I' .)

-ben csak

y_{1}

helyére léphet, a többi háromban pedig

x_{1}

helyére, hogy felsorolásunkban előbb szerepeljen

C

, mint

D

; a másik

C

-re mindig

2

lehetőség van, innen

8

felsorolást kapunk.
A

3 b

ábra lényegében azonos a 926. gyakorlat

4 b

ábrájával, az

A B A B

felsorolás egyik szomszédos betűpárja közé egy

C

betűt kell iktatnunk, egy másik közé

D C D

-t, a harmadik közé semmit, éspedig úgy, hogy

C

beiktatása előzze meg

D C D

beiktatását. Erre

3

lehetőség van.
Így ismét megkaptuk az I. megoldás

11

felsorolását.