XXII/1–2. sz´ am, 2014. m´ a j.
¨ EGY OTLET
A Venn-diagram ´ es a logikai szita alkalmaz´ asai ´n Tuzson Zolta Az ´ abr´ aknak nemcsak a geometri´ aban van fontos szerep¨ uk, hanem a legk¨ ul¨onb¨ oz˝ obb feladatok megold´as´ aban is seg´ıthetik a kiindul´ asi adatok elrendez´es´et, ¨osszef¨ ugg´esek felismer´es´et, megk¨ onny´ıthetik a felt´ art ¨ osszef¨ ugg´esek k´es˝obbi felid´ez´es´et ´es ellen˝ orz´es´et. A matematika k¨ ul¨onb¨ oz˝o ter¨ uletein m´ar r´eg´ota haszn´alatosak az u ´gynevezett Venn-diagramok, a halmazok k¨oz¨otti kapcsolatok, viszonyok szeml´eltet´es´ere, adott tulajdons´ aggal rendelkez˝o halmazok ´es azok sz´ amoss´ag´anak (elemei sz´am´ anak) meghat´aroz´as´ara, valamint egyes ´ all´ıt´ asok logikai ´ert´ek´enek meg´allap´ıt´as´ara, logikai k¨ovetkeztet´esek vizsg´alat´ara (ez´ert is nevezik ezeket m´eg halmaz´abr´ aknak is). Egy Venn-diagramot k¨or¨ okkel, vagy m´as z´ art g¨ orb´ekkel, vagy enn´el ´altal´ anosabb alakzatokkal, p´eld´ aul n egyszer˝ u z´ art g¨ orb´evel adunk meg a s´ıkon. Minden g¨ orbe belseje valamilyen halmazt ´ abr´ azol, a z´ art g¨ orb´en k´ıv¨ ul es˝o r´esz pedig annak komplementer´et. Az {A1 , A2 , . . . , An } g¨ orbecsal´ adot Venn-diagramnak nevezz¨ uk, ha a g¨ orb´ek a n s´ıkot pontosan 2 diszjunkt tartom´ anyra bontj´ ak, ´es a tartom´anyok megegyeznek az ¨ osszes lehets´eges X1 ∩ X2 ∩ . . . ∩ Xk alak´ u halmazzal, k ∈ {1, 2, . . . , n}, ahol minden Xi hely´ere az Ai egyszer˝ u, z´ art g¨ orbe belsej´et vagy k¨ ulsej´et ´ırhatjuk, i ∈ {1, 2, . . . , n}. A k¨orvonalakr´ ol az egyszer˝ u z´ art g¨ orb´ekre t¨ ort´en˝o ´altal´ anos´ıt´as ok´ ara nyomban r´avil´ ag´ıt az al´abbi ´eszrev´etel, mely m´ar Venn 1880-as dolgozat´ aban megtal´alhat´o: B´ armely diagramban legfeljebb h´ arom k¨ orvonal fordulhat el˝ o. A bizony´ıt´as l´enyege: n darab k¨orvonal a s´ıkot legfeljebb n2 − n+ 2 r´eszre osztja (v.¨o.[1]). Ez´ert a Venn-diagram ´ertelmez´ese alapj´ an k¨ovetkezik: n ≤ 3. Az n = 1, n = 2 ´es n = 3 eseteknek megfelel˝o diagramok a s´ıkot rendre 21 , 22 , 23 r´eszre osztj´ak, l´asd a k¨ovetkez˝o ´ abr´ akat:
142
Tuzson Zolt´ an
M´ asfajta g¨ orb´ekkel b´ armely n ´ert´ekre lehet n g¨ orb´et tartalmaz´ o Venndiagramot k´esz´ıteni (l´asd ugyanott). A probl´ema ellenben ott van, hogy az n > 3 sz´ am n¨ oveked´es´evel az ´ abr´ ak egyre bonyolultabbak, nehezen haszn´alhat´ok feladatok megold´as´ara. N´ezz¨ unk n´eh´anyat n = 4 eset´en:
Mind a n´egy ´abra a s´ıkot 16 diszjunk tartom´anyra osztja, mind a n´egy eset ´ altal´ anos´ıthat´ on> 4 eset´en is, a m´asodik tal´ an a legegyszer˝ ubb ´es a legk¨ozelebb ´all a k¨orrel alkotott diagramokhoz, hiszen ez ellipszisekkel k´esz¨ ult. A harmadik a ,,kifli” alak miatt ´ altal´ anos´ıthat´o n > 4-re, a mell´ekelt ´ abr´ an l´athat´o az n = 5 eset. A negyediket t´eglalapokb´ ol k´esz´ıtett¨ uk.
Egy ¨ otlet
143
Eml´ıt´esre m´elt´ ok Edwards konstrukci´ oi, aki a Venn-diagramot g¨ ombfelsz´ınen k´esz´ıti el, majd kivet´ıti a s´ıkba. Az els˝o h´ arom halmazt h´ arom egym´ ast metsz˝o f˝ok¨or hat´ arolja, a negyedik´e meg u ´gy kanyarog, mint teniszlabd´ an a varrat. A visszavet´ıt´es ut´an fogasker´ek alak´ u halmazok keletkeznek, ahol minden egyes tov´abbi halmaznak egyre t¨ obb foga van. ´Ime n´eh´any konstrukci´o (v.¨o. [2]):
K¨ onnyen bel´athat´o, hogy n > 3 eset´en az egyes tartom´anyok azonos´ıt´asa m´ar k¨or¨ ulm´enyes. Az elk¨ovetkez˝okben bemutatjuk e diagramok n´eh´any alkalmaz´asi lehet˝os´eg´et. Egyik azonnali alkalmaz´as´ at az u ´gynevezett logikai szita-formul´ak k´epezik. A tov´abbiakban jel¨ olje |X| az X halmaz elemeinek a sz´am´ at (sz´ amoss´ag´at). A k´etk¨or¨ os Venn diagram seg´ıts´eg´evel l´atjuk, hogy ha k´et halmaz elemsz´ am´ at ¨osszeadjuk, akkor a metszet elemeit k´etszer sz´ amoljuk, ´ıgy az uni´o elemsz´ am´ ara kapjuk, hogy (1)
|A ∪ B| = |A| + |B| − |A ∩ B|.
Tov´abb´a, ha X ⊂ S , akkor nyilv´anval´ o, hogy |S − X| = |S| − |X|, ´es most az X = A ∪ B v´alaszt´assal, az A, B ⊂ S felt´etelekkel, az (1) alapj´an kapjuk, hogy (1′ )
|S − (A ∪ B)| = |S| − |A| − |B| + |A ∩ B|.
Az (1) ´es (1′ ) ¨osszef¨ ugg´eseket m´asodrend˝ u szita-formul´anak h´ıvjuk (a logikai szit´ara m´eg haszn´alatos a tartalmaz´ as-kiz´ ar´ as formula elnevez´es is). Hasonl´o ¨osszef¨ ugg´est ´ allap´ıthatunk meg h´ arom halmaz eset´en is, ha a h´ arom k¨or¨ os Venn-diagramot k¨ovetj¨ uk. Ez alapj´ an fel´ırhat´ o, hogy (2) |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A| + |A ∩ B ∩ C|. Az el˝ obbiek mint´ a j´ara, az A, B, C ⊂ S felt´etelek mellett levezethet˝o a k¨ovetkez˝o ¨sszef¨ o ugg´es is: (2′ ) |S −(A∪B ∪C)| = |S|−|A|−|B|−|C|+|A∩B|+|B ∩C|+|C ∩A|−|A∩B ∩C|.
144
Tuzson Zolt´ an
A (2) ´es a (2′ ) k´epezik a harmadrend˝ u szita-formul´akat. Term´eszetesen a szitaformula ´erv´enyes marad h´ aromn´ al t¨ obb tag eset´en is. Ennek az ´altal´ anos alakja:
(3)
X [ n n = |Ai | − A i i=1
i=1
X
1≤i<j≤n
|Ai ∩ Aj | +
X
1≤i<j
\ n Ai + · · · + (−1)n+1
|Ai ∩ Aj ∩ Ak |
i=1
´es tov´abb´a
(3′ )
[ n n X = |S| − S − |Ai | + A i i=1
i=1
−
X
1≤i<j
X
1≤i<j≤n
|Ai ∩ Aj |
n \ |Ai ∩ Aj ∩ Ak | + · · · + (−1)n+2 Ai i=1
A (3) ´es a (3′ ) n-ed rend˝ u szita-formul´akat p´eld´ aul teljes indukci´oval bizony´ıthatjuk. A tov´abbiakban olyan alkalmaz´asokat mutatunk be, amelyeknek a megold´asa Venn-diagrammal ´es a szita-formul´aval egyar´ ant elv´egezhet˝ok, de mutatunk olyan feladatokat is, amelyekn´el az egyik vagy a m´asik m´odszer el˝ony¨osebb.
1. feladat. Egy fagyisn´ al csoki ´es van´ılia fagyib´ ol lehet v´alasztani. A fagyisn´al 11en ´ allnak sorban, k¨oz¨ ul¨ uk 5-en k´ertek csokis fagyit. Van´ıli´at 3-mal t¨ obben k´ertek mint csak csokist. H´ anyan k´ertek csoki ´es van´ılia fagyit is?
Megold´ as. Jel¨olje Cs azok halmaz´at, akik csoki, V azok´et, akik van´ılia fagyit v´as´ aroltak. K´esz´ıts¨ uk el a mell´ekelt ´ abr´ an l´athat´o Venn-diagramot. Legyen x = |Cs ∩ V|, akkor |Cs − V| = 5−x ´es |V − Cs| = 8−x, ez´ert az (5−x)+x+(8−x) = 11 egyenletb˝ ol x = 2. Teh´at ketten k´ertek csoki ´es van´ılia fagyit is.
Egy ¨ otlet
145
2. feladat. H´ anyf´ele k´eppen alak´ıthatunk ki 6 bet˝ us szavakat az a, e, m, o, u, y bet˝ ukkel u ´gy, hogy ne tartalmazz´ak a me ´es you szavakat? Megold´ as. Legyenek S = az ¨ osszes sz´ o, A = a me-t tartalmaz´ o szavak, B = a you-t tartalmaz´ o szavak. A szitak´eplet: |S − (A ∪ B)| = |S| − |A| − |B| + |A ∩ B|. De |S| = 6!, |A| = 5! (mert ,,me, a, o, u, y” sz´ama 5), |B| = 4! (mert ,,you, a, m, e” sz´ama 4), |A ∩ B| = 3! (mert a ,,me, you, a” sz´ ama 3). Teh´at a v´alasz: 720 − 120 − 24 + 6 = 582. 3. feladat. Az oszt´alyban 38 tanul´o van. Mindenki u ˝zi a k¨ovetkez˝o sport´ agak valamelyik´et: atl´etika, r¨oplabda, u ´sz´ as. 19-en atletiz´ alnak, 21-en r¨oplabd´ aznak, 12 tanul´o u ´szik; 7 tanul´o atletiz´ al ´es r¨oplabd´ azik, 6 tanul´o atletiz´ al ´es u ´szik, 3 tanul´o r¨oplabd´ azik ´es u ´szik. H´ any tanul´o u ˝zi mindh´ arom sportot?
Megold´ as. Legyen |A ∩ B ∩ C| = x ´es bentr˝ ol kifele haladva t¨ oltj¨ uk ki a halmaz´ abr´ at, majd ¨osszegezz¨ uk a benne l´athat´o kifejez´eseket: (11 + x) + (6 + x) + (3 + x) + (7 − x) + (3 − x) + (6 − x) + x = 38 ⇒ x = 2 Szita-formul´aval is dolgozhatunk. Legyenek:
A = {atl´etiz´al´ ok},
R = {r¨oplabd´ az´ok},
Teh´at fel´ırhat´ o, hogy:
U = {´ usz´ ok}.
|A ∪ R ∪ U | = |A| + |R| + |U | − |A ∩ R| − |R ∩ U | − |U ∩ A| + |A ∩ R ∩ U |.
Be´ırva a sz´amoss´agokat kapjuk, hogy: 38 = 19 + 21 + 12 − 7 − 3 − 6 + |A ∩ R ∩ U |, vagyis |A ∩ R ∩ U | = 2 tanul´o u ˝zi mindh´ arom sportot.
146
Tuzson Zolt´ an
4. feladat. Egy 24-es l´etsz´am´ u sportoszt´ aly tanul´oi n´egy sport´ agban szerepelnek: k´ezilabd´ aznak, fociznak, j´egkorongoznak ´es kos´ arlabd´ aznak. Minden tanul´o sportol, de senki sem szerepel kett˝ on´el t¨ obb sport´ agban. Tudjuk, hogy 9-en nem k´ezilabd´ aznak, 11-en nem fociznak, 16-an nem j´egkorongoznak, 12-en pedig nem kos´arlabd´ aznak. Tudjuk m´eg, hogy 10-en fociznak, de nem kosaraznak, 11-en pedig k´ezilabd´ aznak, de ˝ok sem kosaraznak. H´ anyan, ´es milyen ¨ osszet´etelben u ˝znek k´et-k´et sport´ agat?
Megold´ as. A feltev´esb˝ ol azt kapjuk, hogy 24 − 9 = 15-en k´ezilabd´ aznak, 24 − 11 = 13-an fociznak, 24 − 16 = 8-an j´egkorongoznak, 24 − 12 = 12-en pedig kos´ arlabd´ aznak. Mivel 15 + 13 + 8 + 12 = 48, ´es ez az ¨osszes tanul´ok sz´am´ anak a 2-szerese, k¨ovetkezik, hogy mindenki pontosan k´et sport´agban vesz r´eszt, mert senki sem szerepel 2-n´el t¨ obb sport´ agban. Az ´ abr´ an l´athat´o halmazok az egyes sport´ agakban szerepl˝ o tanul´okat jel¨ olik, a bet˝ uk pedig a k´et-k´et sport´ agat u ˝z˝ok sz´ am´ at jelentik, a k¨ovetkez˝ok´eppen: a – k´ezilabda-foci;
b – k´ezilabda-j´egkorong;
c – foci-j´egkorong;
d – k´ezilabda-kos´arlabda; e – j´egkorong-kos´ arlabda; f – foci-kos´arlabda. Ekkor (1)
a + b + d = 15,
(2)
a + c + f = 13,
(3)
b + c + e = 8,
(4)
d + e + f = 12,
(5)
a + c = 10,
(6)
a + b = 11.
Az (1) ´es (6) egyenl˝ os´egb˝ ol azt kapjuk, hogy d = 4, a (2) ´es (5) alapj´an f = 3, a (4) alapj´an e = 5. 12-en nem kosaraznak, teh´ at a + b + c = 12, de a + c = 10, ´ıgy b = 2, (5)-b˝ol ´es (6)-b´ol a = 9 ´es c = 1.
147
Egy ¨ otlet
5. feladat. Ha n = 210 · 311 · 57 , akkor hat´ arozzuk meg a ϕ(n)-net, az n-n´el kisebb ´es n-nel relat´ıv pr´ım sz´ amoknak a sz´ am´ at. Megold´ as. A keresett sz´ amok nem oszthat´ok se 2-vel, se 3-mal, se 5-tel. Ezek sz´ am´ at megkapjuk, ha a sz´ amok sz´ am´ ab´ol kivonjuk a 2; 3; 5 k¨oz¨ ul legal´ abb eggyel oszthat´ok sz´am´ at. Legyenek rendre A = {k ∈ N : k < n, 2 | k},
B = {k ∈ N : k < n, 3 | k},
C = {k ∈ N : k < n, 5 | k}.
Teh´at az n pr´ımt´enyez˝os alakj´ at figyelembe v´eve, |A| = n/2, |B| = n/3, |C| = n/5, |A ∩ B| = n/6, |B ∩ C| = n/15, |C ∩ A| = n/10 ´es |A ∩ B ∩ C| = n/30. A logikai szita alapj´an: ϕ(n) = n − |A ∪ B ∪ C|
= n − (|A| + |B| + |C|) + (|A ∩ B| + |B ∩ C| + |C ∩ A|) − |A ∩ B ∩ C| n n n n n n n + − =n− − − + + 3 5 6 10 15 30 2 1 1 1 1 1 1 1 = + − =n 1− − − + + 2 3 5 6 10 15 30 1 1 1 1− 1− . =n 1− 2 3 5 ´ Megjegyz´ es. Eszrevehet˝ o, hogy az el˝ obb kapott elj´ar´as ´es eredm´eny ´altal´ anos´ıtαk 1 α2 hat´ o, ugyanis ha az n sz´ am pr´ımt´enyez˝os felbont´ asa n = pα 1 p2 · · · pk , akkor 1 1 1 ϕ(n) = n 1 − 1− ··· 1 − . p1 p2 pk
6. feladat. (Elcser´elt levelek) H´ anyf´elek´eppen helyezhet¨ unk el 4 k¨ ul¨onb¨ oz˝o embernek ´ırt levelet 4 nekik megc´ımzett bor´ıt´ekba u ´gy, hogy semelyik lev´el se a j´o c´ımz´eshez ker¨ ulj¨on? Megold´ as. Legyen Ai azon esetek halmaza, amelyben az i-vel jel¨olt c´ımzett (i ∈ {1, 2, 3, 4}) megkapja a levelet. Ekkor |Ai | = 3!, |Ai ∩ Aj | = 2!, |Ai ∩ Aj ∩ Ak | = 1!, hiszen ha h´ arom lev´el j´ o helyre megy, akkor a negyedik is, |A1 ∩ A2 ∩ A3 ∩ A4 | = 1. A logikai szita alapj´ an 4 4 X X [ X = |Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | − |A1 ∩ A2 ∩ A3 ∩ A4 | A i i=1
i=1
=
C41
· 3! −
C42
· 2! +
C43
· 1! −
C44
1 1 1 1 = 4! . − + − 1! 2! 3! 4!
148
Tuzson Zolt´ an
A k´erd´esre a v´alasz pedig: 1 1 1 1 a4 = 4! − |A1 ∪ A2 ∪ A3 ∪ A4 | = 4! 1 − + − + = 9. 1! 2! 3! 4! ´ Megjegyz´ es. Eszrevehet˝ o, hogy az el˝ obb kapott elj´ar´as ´es eredm´eny ´altal´ anos´ıthat´ o n bor´ıt´ek eset´en is, amelyre a v´alasz 1 1 1 1 . an = n! 1 − + − + · · · + (−1)n 1! 2! 3! n! 7. feladat. Hat´ arozzuk meg azokat a pozit´ıv, egyn´el kisebb irreducibilis t¨ orteket, melyek azzal a tulajdons´ aggal rendelkeznek, hogy a sz´aml´al´o juk ´es a nevez˝o j¨ uk osszege 2001. ¨ Megold´ as. Azon pozit´ıv, egyn´el kisebb t¨ orteknek a sz´ama amelyeknek a sz´aml´al´o juk ´es a nevez˝o j¨ uk ¨osszege 2001, ´eppen 1000. Meg kell n´ezn¨ unk, hogy ezek k¨oz¨ ul a ort, ahol a < b, a + b = 2001, legyen d egy k¨oz¨os h´ any irreducibilis. Ha b egy ilyen t¨ oszt´o ja az a-nak ´es a b-nek. Ekkor d | a + b = 2001, ahonnan d ∈ {3, 23, 29}. Legyenek A, B, C rendre azon ab t¨ orteknek a halmaza amelyek rendre 3-mal, 23-mal, 29-cel egyszer˝ us´ıthet˝ok. A logikai szita alapj´ an: |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |B ∩ C| − |C ∩ A| + |A ∩ B ∩ C|, ahol |A ∩ B ∩ C| = 0, mert 3 · 23 · 29 = 2001. Ha ab ∈ A, akkor a = 3x, b = 3y ´es 3x + 3y = 2001 vagyis x + y = 667 ´es 0 < x < y term´eszetes sz´ amok. Ekkor x ∈ {1, 2, . . . , 333}, ´ıgy megkapjuk, hogy |A| = 333. Teljesen hasonl´ o m´odon meghat´arozva a t¨ obbi halmaz sz´amoss´ag´at is kapjuk, hogy |B| = 43, |C| = 34, ´es |A ∩ B| = 14, |B ∩ C| = 1, |C ∩ A| = 11. ´Igy |A ∪ B ∪ C| = 333 + 43 + 34 − 14 − 1 − 11 = 384. Teh´at az irreducibilis t¨ ortek sz´ama 1000 − 384 = 616. 8. feladat. H´ anyf´elek´eppen tehet¨ unk be 30 sz´ al vir´ agot 15 k¨ ul¨onb¨oz˝o sz´ın˝ u v´az´aba, ha a vir´agok k¨ ul¨onb¨ oz˝oek, ´es minden v´az´aba kell jusson legal´ abb egy vir´ag. Megold´ as. Az ¨osszes lehets´eges kioszt´ asok halmaz´at jel¨olj¨ uk H-val, ´es legyen Ai azon kioszt´ asok halmaza amelyekn´el az i-dik v´aza u ¨res marad, 1 ≤ i ≤ 15. A j´o kioszt´ asok halmaza teh´ at H −(A1 ∪A2 ∪. . .∪A15 ). Tov´abb´a |H| = 1530 , |Ai | = 1430 (f¨ uggetlen¨ ul az i-t˝ol) hiszen vir´ agonk´ent 14-f´ele k´eppen d¨ onthet¨ unk (az i-edik v´aza u ¨resen kell maradjon), |Ai ∩ Aj | = 1330 mert jelenleg k´et v´aza tiltott (az i-edik ´es a j-edik v´aza). Hasonl´ok´eppen egy k-as metszetnek (15 − k)30 eleme van (k v´aza
149
Egy ¨ otlet
k ´ tiltott). Altal´ aban k-as metszetb˝ol C15 darab van, ennyif´elek´eppen v´alaszthatjuk ki a 15 v´aza k¨oz¨ ul a k u ¨reset. A szita-formula szerint teh´at:
30 30 X X k k 30 k H −(A1 ∪A2 ∪. . .∪A3 ) = 1530 − ·(15−k)30 . (−1) C ·(15−k) = (−1)k C15 15 k=1
k=0
´ Megjegyz´ es. Eszrevehet˝ o, hogy az el˝ obb kapott elj´ar´as ´es eredm´eny ´altal´ anos´ıthat´ o p darab vir´agsz´al ´es q darab v´aza eset´en is, amikor is a v´alasz p X
k=0
(−1)k Cqk · (q − k)p .
9. feladat. H´ anyf´elek´eppen u ¨ltethet¨ unk le egy sorba 3 angolt, 3 franci´at ´es 3 t¨ or¨ok¨ot u ´gy, hogy h´ arom azonos nemzetis´eg˝ u ne u ¨lj¨on egym´ as mell´e? Megold´ as. A logikai szita formul´at alkalmazzuk h´ arom halmaz eset´en. Legyen A = a 3 angol egym´ as mellet u ¨l F = a 3 francia egym´ as mellet u ¨l T = a 3 t¨ or¨ ok egym´ as mellet u ¨l ¨ Osszes u ¨ltet´esi lehet˝os´egek: 9!. |A| = |F | = |T | = 7! · 3!, |A ∩ F | = |A ∩ T | = |F ∩ T | = 5! · 3! · 3!, |A ∩ F ∩ T | = 3! · 3! · 3! · 3!. ´Igy az |S − (A ∪ B ∪ C)| = |S| − |A| − |B| − |C| + |A ∩ B| + |B ∩ C| + |C ∩ A| − |A ∩ B ∩ C| szitak´eplet alapj´an a k´ert ´ert´ek: 9! − C31 · 7! · 3! + C32 · 5! · 3! · 3! − C33 · 3! · 3! · 3! · 3!. ´ Megjegyz´ es. Eszrevehet˝ o, hogy az el˝ obb kapott elj´ar´as ´es eredm´eny ´altal´ anos´ıthat´ o, ha 3–3–3 szem´ely helyett k–k–k szem´elyt vesz¨ unk, akkor az eredm´eny: (3k)! − C31 · (2k + 1)! · k! + C32 · (k + 2)! · k! · k! − C33 · k! · k! · k! · k!. Ha pedig a 3 csoport helyett p csoportot tekint¨ unk, akkor az eredm´eny: (pk)! − Cp1 · ((p − 1)k + 1)! · k! + Cp2 · ((p − 2)k + 2)! · k! · k! − · · · + (−1)p Cpp |k! · k!{z· · · k!} (k+1)−tag
150
Tuzson Zolt´ an
10. feladat. 4 h´ azasp´ ar hogyan helyezhet˝o el egy kerek asztal k¨or¨ ul u ´ gy, hogy h´ azast´ arsak nem ker¨ ulnek egym´ as mell´e. Megold´ as. A logikai szita-formul´at alkalmazzuk n´egy halmaz eset´en. Az Ai , 1 ≤ i ≤ 4 halmazba azok a (sz´ amunkra nem kedvez˝o) esetek ker¨ ulnek, amelyekben az i-edik f´erj ´es feles´eg egym´ as mellett u ¨lnek. Az ¨ osszes eset sz´ama 7!. Ha egy h´ azasp´ar egym´ as mellett u ¨l (a t¨ obbi lehet, hogy egym´ as mellett u ¨l, lehet, hogy nem), akkor az egym´ as mellett u ¨l˝o p´ ar C41 -f´ele k´eppen v´alaszthat´o ki, a p´ ar ´es a t¨ obbi 6 ember a kerek asztal k¨or¨ ul 6!-f´elek´eppen u ¨lhet le, ´es a p´ ar egym´ashoz k´epest k´etf´elek´eppen helyezkedhet el, teh´at ezeknek az eseteknek a sz´ ama C41 · 6! · 2 A t¨ obbi eset hasonl´ o m´odon sz´amolhat´ o ki. Az ¨ osszes esetek sz´ ama teh´ at: 7! − C41 · 6! · 2 + C42 · 5! · 22 − C43 · 4! · 23 + C44 · 3! · 2. ´ Megjegyz´ es. Eszrevehet˝ o, hogy az el˝ obb kapott elj´ar´as ´es eredm´eny ´altal´ anos´ıthat´ o a 4 helyett k h´ azasp´ arra, amikor az eredm´eny a k¨ovetkez˝o lesz: (2k)! − Ck1 · (2k − 1)! · 2 + Ck2 · (2k − 2)! · 22 − · · ·
+ (−1)k−1 Ckk−1 · (k + 1)! · 2k−1 + (−1)k Ckk · k! · 2k
Befejez´es¨ ul megjegyezz¨ uk, hogy m´eg sok m´as egyszer˝ ubb vagy nehezebb feladat megoldhat´o a bemutatott m´odszerekkel. Szakirodalom [1] A Matematika Tan´ıt´ asa, 3/1983. [2] http://hu.wikipedia.org/wiki/Venn-diagram ´ [3] Tuzson Zolt´ an, Hogyan oldjunk meg aritmetikai feladatokat, Abel kiad´ o, Kolozsv´ ar, 2011. [4] Tuzson Zolt´ an, A Venn-Euler diagram felhaszn´ al´ asa halmazelm´eleti feladatok megold´ as´ ara, ML 5/1994, 174.-178. [5] Dumitru Busneag, Ioan Maftei, Teme pentru cercurile se concursurile de matematica ale elevilor, Scrisul Romanesc, Craiova, 1983 [6] Kir´ aly Bal´ azs, T´ oth L´ aszl´ o, Kombinatorika jegyzet ´es feladatgy˝ ujtem´eny, P´ecsi Tudom´ anyegyetem, 2011. [7] L´ ang Csab´ an´e, Kombinatorika, ELTE, Budapest 2008. [8] Szab´ o L´ aszl´ o, Diszkr´et matematika, Sopron, 2011. Tuzson Zolt´ an, Sz´ekelyudvarhely
