Kezdőlap


Cím:	Mikor keletkezik "jó" csillag?
Szerző(k):	Miklós Ildikó
Füzet:	2003/november, 450 - 454. 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.

Októberi számunk I. 59.-es informatika feladatában $n$ -ágú szabályos csillagokat kellett rajzolni, mégpedig az összes lehetségeset. Ezeket úgy kapjuk, hogy a szabályos $n$ -szög ( $n \geq 5$ ) egyik csúcspontjából indulva minden $k$ -adikat összekötjük, amíg vissza nem érünk a kiindulási pontba (1. ábra). Csak azok az elfogadható megoldások, ahol valóban csillag keletkezik.

1. ábra

Definíció [1]. A szabályos csillagsokszöget a sík véges sok szakasza alkotja, ha minden végpontjuk két szakasz közös végpontja, és található hozzájuk olyan egybevágóság, amely a szakaszok egyikét egy tetszőlegesen előírt másikra fekteti, s amely a teljes alakzat helyét nem változtatja meg. A szabályos sokszögvonal is ilyen alakzat, de ezt nem nevezzük szabályos csillagsokszögnek. Egy szabályos sokszögnek a középponttól egyenlő (

0

-tól különböző) távolságra levő átlói szabályos csillagsokszöget alkotnak.

Tekintsük azt a szabályos csillagot, amelyet úgy kapunk, hogy a szabályos ötszögre alkalmazzuk a definíció második részét (2a. ábra).

2a. ábra

Erre a csillagötszögre valóban igaz, hogy bármely két szakaszához található egybevágóság: vagy forgatással, vagy tengelyes tükrözéssel egymásra fektethetők (2b. ábra). A csillagötszög elnevezés megtévesztő, a 2. ábrák csillagának nyilván tíz oldala van.

2b. ábra

Milyen további tulajdonságai vannak ezeknek az alakzatoknak? A szabályos csillag-

n

-szögnek

2 n

oldala van, a szimmetriák miatt az oldalak egyenlő hosszúak; szögei (amelyekből ugyancsak

2 n

van) közül minden második,

n

darab egyenlő nagyságú (ez legyen

α

), a további, az előzőekkel szomszédos

n

darab szög ugyancsak egyenlő. A sokszögek szögösszegéből könnyen adódik, hogy

\begin{matrix} α + β = 360^{\circ} - \frac{360^{\circ}}{n} . \end{matrix}

3a. ábra

Legyen ugyanis a megfelelő szabályos sokszög kiindulási csúcsa

A_{0}

, a

k

-adik csúcs

A_{1}

, a csillagsokszög

A_{0}

-lal (az óramutató járása szerint) szomszédos csúcsa pedig

B_{1}

. Az

A_{0} A_{1} O

háromszögben (3a. ábra)

γ = \frac{k}{n} \cdot 360^{\circ}

(hiszen a szabályos

n

-szög első és

k

-adik csúcsáról van szó), tehát

\begin{matrix} α = 180^{\circ} - γ = (1 - \frac{2 k}{n}) \cdot 180^{\circ} . \end{matrix}

(1)

A_{0} B_{1} O

háromszögben:

\begin{matrix} A_{0} O B_{1} ∢ = \frac{360^{\circ}}{2 n} = \frac{180^{\circ}}{n} = 180^{\circ} - \frac{α}{2} - \frac{β}{2}, \end{matrix}

(2)

amiből látszik, hogy valóban

\frac{α}{2} + \frac{β}{2} = 180^{\circ} - \frac{180^{\circ}}{n}

, tehát

α + β = 360^{\circ} - \frac{360^{\circ}}{n}

, amely összeg

k

-tól független. (1)-ből és (2)-ből kiszámítható

β

értéke is:

\begin{matrix} β = 180^{\circ} + (k - 1) \frac{360^{\circ}}{n} . \end{matrix}

A forgásszimmetria miatt a csillagsokszög másodszomszédos csúcsai egy-egy körön helyezkednek el: a

k_{1}

és egy, az előzővel koncentrikus

k_{2}

körön (3b. ábra).

3b. ábra

Úgy tűnik, a csillagsokszög minden második szöge konkáv. Igaz-e ez? Ha a belső,

k_{2}

kör sugarát növeljük (vagy csökkentjük), egy olyan alakzatot kapunk, amely megfelel a definíciónak, tehát ugyancsak nevezhetjük szabályos csillagsokszögnek. Erre általában nem igaz, hogy oldalai a szabályos sokszög átlóira illeszkednek. A ,,belső'' pontok mozgatását egészen addig folytathatjuk, amíg már nem lesznek konkáv szögeink, de még nem érik el a

k_{1}

kört (ekkor szabályos

2 n

-szög keletkezik). Ezt megtehetjük, hiszen

\begin{matrix} α + β = 360^{\circ} - \frac{360^{\circ}}{n} < 360^{\circ} (4a. ábra). \end{matrix}

A definíció szerint ez is szabályos csillagsokszög, de ha a szabályos sokszöget nem tekintjük annak, előírhatjuk, hogy csillagsokszögünk minden második szöge legyen konkáv. Van egy átmeneti állapot, amikor

β = 180^{\circ}

, ekkor a csillagsokszög

n

oldalú szabályos sokszöggé alakul át.

4a. ábra

Ha a belső,

k_{2}

körre eső csúcsokat elforgatjuk a középpont körül, a forgásszimmetria továbbra is teljesül minden második oldalra, de a szomszédos oldalakra a tükörszimmetria már nem, tehát a keletkezett ,,körfűrész'' nem szabályos csillagsokszög (4b. ábra).

4b. ábra

Nézzük meg most már, hogy melyek az informatika feladat jó megoldásai, ha a szabályos

n

-szög

k

-szomszédos csúcsait kötjük össze. Így egy folytonos, zárt poligont (töröttvonalat) kapunk, amelynek bizonyos szakaszai metszik egymást, így ezt hurkolt poligonnak [1] nevezzük (csak ekkor beszélhetünk a feladat megoldásának tekintett szabályos csillagról).
Ha

k > \frac{n}{2}

, akkor ugyanazt az ábrát kapjuk, mint ha egy csúcsból indulva minden csúcsot az

(n - k)

-adik szomszédjával kötjük össze. Páros

n

esetén

k = \frac{n}{2}

sem ad megoldást, ekkor ugyanis egyetlen szakaszt kapunk, a körülírt kör átmérőjét. Így feltehető, hogy:

2 \leq k < \frac{n}{2}

.
Nézzük először az

n = 11

esetet (ez szerepelt a kitűzésben példaként).

2 \leq k < 5, 5

miatt a lehetséges esetek:

k = 2,3,4,5

. Ha

k = 2

, a csúcsok összekötésének sorrendje:

\begin{matrix} 0., 2., 4., 6., 8., 10., 1., 3., 5., 7., 9., 0. \end{matrix}

(A 6. lépésnél nincs értelme 12. csúcsot írni, hiszen ez megegyezik az elsővel.) 11 prím, így a 11. lépésben záródik be a sokszög. A lehetséges eseteket az 5. ábra mutatja.

5. ábra

Hasonló igaz, ha az

n

prímszám. Ilyenkor a lehetséges értékek:

k = 2,3, ..., [\frac{n}{2}]

(ahol

[x]

jelenti az

x

szám egész részét,

n

páratlan prím, így

\frac{n}{2}

nem egész), a megoldások száma

[\frac{n}{2}] - 1

.
Ha

n = 10

, akkor

2 \leq k < 5

miatt a lehetséges értékek:

k = 2,3,4

, ezeket mutatja rendre a 6. ábra. A

k = 2

esetben már az 5. lépésben elérjük a kiindulási pontot, anélkül, hogy a keletkezett szakaszok metszenék egymást, szabályos ötszöget kaptunk. Általánosan elmondhatjuk, hogy ha

k ∣ n

, akkor szabályos

\frac{n}{k}

-szöget kapunk, amit a feladat nem tekint megoldásnak.

6. ábra

k = 4

esetben szabályos ötágú csillagot kapunk, ami megoldás lehetne, de a feladat szövege nem ide sorolja,

n = 10

esetben tízágú csillagokat kell rajzolnunk. Általánosan: ha

k

-nak és

n

-nek van közös osztója, azaz ha nem relatív prímek, akkor egy

\frac{n}{(n; k)}

-ágú szabályos csillagot kapunk (ahol

(n; k)

n

és a

k

legnagyobb közös osztója), ami a feladatnak nem megoldása.
A

k = 3

esetben valóban szabályos tízágú csillagot kapunk. Általánosan: ha

k

és

n

relatív prímek (

k \geq 2

), akkor be tudjuk járni a csúcsokat anélkül, hogy az

n

-edik lépés előtt visszaérnénk a kiindulási pontba, a poligon hurkolt lesz és így

n

-ágú csillagot kapunk.
Végül

n = 10

-re csak egy ,,jó'' megoldást kaptunk, holott ha az informatika feladatot úgy értelmezzük, hogy összekötjük a középponttól egyenlő távolságra levő átlókat, három különböző megoldást is kapnánk (hiszen ennyi lehetséges

k

van, 7. ábra).

7. ábra

Van-e a feladatnak mindig megoldása, ha

n

nem prím? Ha

n = 6

k

értéke csak 2 lehet, ekkor viszont szabályos háromszöget kapunk, ami nem megoldás.
Ha

n

legalább 3, akkor van nála kisebb hozzá relatív prím, például

n - 1

. Mi viszont a

k

-nak azokkal az értékeivel dolgozunk, amelyekre

k

kisebb az

n

felénél. Láttuk, hogy ha

n = 6

, akkor azért nincs a feladatnak megoldása, mert a 6 felénél, a 3-nál kisebb számok között csak az 1 relatív prím a 6-hoz. Vannak-e még ilyen számok? Az alábbiakban megmutatjuk, hogy nincsenek.
A következő összetett szám:

n = 8

, ehhez a felénél kisebb relatív prím a 3.

n = 9

esetén megoldás a 2 (de a 4 is),

n = 10

esetén megoldás a 3. Képezzük most a következő szorzatot:

\begin{matrix} s_{r} : = p_{1} \cdot p_{2} \cdot ... \cdot p_{r}, \end{matrix}

ahol

p_{i}

i

-edik prímszám.

s_{3} = 2 \cdot 3 \cdot 5 = 30

, ami nyilván nagyobb 5-nél (a legnagyobb tényezőnél), ezért minden

n

-re, ahol

5 < n < 30

, létezik

k \in {2; 3; 5}

, hogy

(k; n) = 1

. Ellenkező esetben ugyanis az

n

prímtényezős felbontásában szerepelnie kellene az első három prímnek, ám ekkor

n \geq 30

. Hasonlóan kapjuk az általánosítást: Ha

n

kisebb az előző

r

prím szorzatánál, akkor a

{p_{1}, p_{2}, ..., p_{r}}

halmaz valamelyik eleme és az

n

relatív prímek. Így ha

p_{r} < n < s_{r}

, akkor van olyan

k \leq p

, hogy

(k; n) = 1

. Az

[5; 30]

intervallumban már megvizsgáltuk a 11-nél kisebb számokat, az ennél nagyobbaknál viszont az előbbiek miatt biztosan van

\frac{n}{2}

-nél kisebb

n

-hez relatív prím, hiszen az előző halmaz összes prím eleme kisebb 11 felénél.
Az intervallum alsó határa az

r

-edik prímszám, a felső határa az első

r

prím szorzata, ami sokkal gyorsabban nő, mint az alsó határ, így az intervallumok hossza gyorsan nő. (Pl. ha

r = 4

, akkor ez a

[7; 210]

intervallum; ha

r = 5

, akkor a

[11; 2310]

.) A felső határt a második lépéstől kezdve mindig 2-nél nagyobb prímmel szorozzuk, így minden

n

-re találunk egy (vagy több) olyan intervallumot, amelynek tagja

\frac{n}{2}

is és

n

is, így az intervallumnak megfelelő prímhalmazban találunk

\frac{n}{2}

-nél kisebb

n

-hez relatív prímet. Tehát minden 6-nál nagyobb

n

esetén van informatikai feladatunknak legalább egy megoldása. A megoldások száma általában nyilván

\frac{φ (n) - 2}{2}

, ahol

φ (n)

jelöli az

n

-nél kisebb

n

-hez relatív számok számát. (Ehhez gondoljuk meg, hogy

k

és

n

pontosan akkor relatív prímek, ha

n - k

és

n

is azok, másfelől ha

k = 1

vagy

n - 1

, akkor nem kapunk megoldást.) A fenti becslések épp azt eredményezik, hogy

φ (n) > 2

, ha

n > 6

Mindez persze nem jelenti azt, hogy hatágú csillag nem létezik, hiszen ismerünk is ilyet (8. ábra). Ezt valóban a szabályos hatszög középpontjától egyenlő távolságra lévő átlói alkotják, mégpedig az egyetlen lehetséges módon. Ha minden lehetséges csillagsokszöget szeretnénk megkapni, programozási feladatunkon úgy kellene módosítani, hogy ha visszaérünk a kiindulási pontba anélkül, hogy

n

-ágú csillagot kaptunk volna, az eljárást megismételjük a második pontból indulva, majd a harmadikból, és így tovább, amíg még találunk ,,szabad'' pontokat.

8. ábra

Eddigi okfejtésünk talán bonyolultnak tűnhet, de egy egyszerű programmal meg lehet keresni egy adott számhoz a felénél kisebb, vele relatív prímeket. Ezekre pedig már megalkothatjuk ,,jó'' csillagainkat.

Hivatkozás

[1]	Hajós György: Bevezetés a geometriába, Tankönykiadó (Budapest, 1991).