Feladat: F.1775 Korcsoport: 16-17 Nehézségi fok: nehéz
Megoldó(k):  Angyal J. ,  Bacsó G. ,  Bálint L. ,  Balog J. ,  Balogh Z. ,  Bartolits I. ,  Benis Gy. ,  Breuer Péter ,  Császár Gy. ,  Csetényi A. ,  Fazekas I. ,  Fórizs Erzsébet ,  Füredi Z. ,  Földes Tamás ,  Földes Tibor ,  Gál P. ,  Gáspár Gy. ,  Gergely I. ,  Glöckner Gy. ,  Győri M. ,  Hanyecz P. ,  Horváth L. ,  Kertész Á. ,  Kishalmi Rózsa ,  Kollár I. ,  Koppány I. ,  Lang I. ,  Monori A. ,  Pach J. ,  Pálffy L. ,  Pap Gy. ,  Párkány Erzsébet ,  Petz D. ,  Pintér I. ,  Plánka J. ,  Rudas T. ,  Sebő A. ,  Szász Gy. ,  Szendrei Ágnes ,  Szendrei Mária ,  Szentiványi Gy. ,  Szeredi J. ,  Szigeti G. ,  Tordai M. ,  Tóth-Pál Éva ,  Turán György ,  Vályi G. ,  Varga Gy. ,  Wettl F. 
Füzet: 1972/április, 148 - 151. oldal  PDF  |  MathML 
Témakör(ök): Permutációk, Kombinációk, Feladat
Hivatkozás(ok):Feladatok: 1971/május: F.1775

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. a) Ha a dobozba csak egyféle sajtot teszünk, az elhelyezés egyértelmű, és a sajt fajtájának a megválasztására 3 lehetőségünk van. Így 3 elrendezést kapunk.

 

b) Kétféle sajtot téve a dobozba, figyelembe vesszük, hogy az egyes fajtákból hány cikket használunk fel. A cikkek számát háromféleképpen választhatjuk meg: egyikből 5 cikket veszünk, a másikból 1-et; vagy 4-et és 2-t, vagy pedig mindkét fajtából hármat. Ha egy fajtából 5 cikket teszünk a dobozba, és egy másikból 1-et, az elhelyezés egyértelmű; az elsők fajtáját 3-féleképpen választhatjuk meg, a másodikét 2-féleképpen. Az elhelyezések száma ezek szerint 3⋅2=6.
 

Akkor is 6-féleképpen választhatjuk meg a kétféle sajt fajtáit, ha egyikből 4-et, egy másikból 2-t használunk fel, ekkor azonban már nem egyértelmű az elhelyezés: a két azonos fajtájú sajtcikk vagy szomszédos, vagy másod‐szomszédjai egymásnak, vagy egymással szemben vannak. Az ilyen választások és elhelyezések száma tehát 6⋅3=18.
 

Ha két fajtából három‐három cikket veszünk, akkor az elhelyezésre négy lehetőségünk van (1. ábra).
 
 
1. ábra
 

A felhasznált két fajtát pedig most csak 3-féleképpen választhatjuk meg (ennyiféleképpen lehet azt megadni, hogy melyiket nem használjuk fel a három fajta közül), eszerint az ilyen elhelyezések száma 4⋅3=12.
 

c) Ha mindhárom fajtából teszünk a dobozba, az egyes fajtákból rendre 4+1+1, vagy 3+2+1, vagy 2+2+2 cikket választhatunk. A (4+1+1) esetben ismét a csak egy‐egy cikkel képviselt fajtát célszerű elhelyezni, majd a dobozt a 4 egyforma sajttal feltölteni. Az 1‐1 db cikk ‐ mint fent ‐ lehet szomszédos, másod-szomszéd és szemközti. Az első két esetben 3-féleképpen választhatjuk meg e párból annak a fajtáját, amelyik az óramutató járása szerint előbb áll, és 2-féleképpen a másiknak a fajtáját. Ha viszont e pár tagjai szemköztiek, az elhelyezést egyértelműen meghatározza, hogy melyik fajtából használunk 4 cikket. Az elhelyezések száma itt 2⋅3⋅2+3=15.
 

A (3+2+1) esetben 3-féleképpen választhatjuk azt a fajtát, amelyből csak egy cikket használunk, és ezután 2-féleképpen azt, amelyikből kettőt. Helyezzük el először az 1 cikkel képviselt fajtát, ez után a többi öt hely közül az azonos fajtájú két cikk helyét (52)=10-féleképpen választhatjuk meg. Így 10⋅6=60 elhelyezést kapunk.
 

Végül a (2+2+2) esetben az azonos fajtájú cikkpárok vagy mind szomszédosak, vagy csak két pár, vagy csak egy marad szomszédos közülük, vagy egy sem. Az elhelyezések száma az előzők mintájára rendre 2, 3, 3⋅2=6, az utolsó elv mellett pedig 5 (CHCMHM, CMCHMH, CHMCHM, CHMCMH és CMHCMH), így ebben az esetben együttvéve 16 elhelyezést kapunk.
Eredményeinket összegezve, a lehetőségek száma: 3+(6+18+12)+(15+60+16)=130.
 

Turán György (Budapest, Fazekas M. Gyak. Gimn., III. o. t.)
 

II. megoldás (vázlat). Osztályozzuk az elhelyezéseket aszerint, hogy bennük a cikkeken körbehaladva hány olyan szomszédpárt találunk, amelynek a tagjai különböző fajtájúak. Más szóval a dobozkitöltések feldarabolását tekintjük olyan blokkokra, amelyek egymáshoz csatlakozó ugyanolyan fajtájú sajtcikkekből állnak.
 

1. Ha ilyen pár nincs, akkor a cikkek egyformák, tehát 3 elhelyezés van.
 

2. Csak egy ilyen blokkválasztó vonal nyilván nem lehet, a következő eset tehát az, amikor két helyen csatlakozik egymáshoz két különböző fajtájú sajtcikk. Ekkor tehát kétféle sajtot használunk, ezekből rendre 5+1, 4+2, 3+3 cikket vehetünk, és a lehetőségek száma a fajták választását is figyelembe véve rendre 3⋅2+3⋅2+3=15.
 

3. Ha az elhelyezésben három blokk van, az egyes blokkokra rendre (4+1+1), (3+2+1) vagy (2+2+2) cikket tehetünk, és a fajták választása szerint rendre 3⋅2+2⋅3⋅2+2=20 a lehetőségek száma.
 

4. Ha négy blokk van, akkor bennük a cikkek száma vagy (3+1+1+1), vagy (2+2+1+1). A lehetőségek száma az első esetben 2⋅3⋅3, és ugyanennyi a második esetben is, feltéve, hogy a két kettes blokk szomszédos; ha viszont ezek szemköztiek, és különböző fajtájúak, a lehetőségek száma 3. Ha szemköztiek és azonos fajtájúak, a lehetőségek száma 3⋅3. Így összesen 2⋅2⋅3⋅3+3+3⋅3=48 elhelyezést adhatunk meg.
 

5. Öt blokk esetén csak (2+1+1+1+1) lehet a számuk. Helyezzük el először a két szomszédos egyforma cikket (fajtáját 3-féleképpen választhatjuk meg, ezt a továbbiakban A-val jelöljük). Az óramutató járása szerint haladva tovább, utánuk egy tőlük különböző fajtájú cikket kell választanunk (két lehetőség, a választott fajtát B-vel jelöljük), az esetek kifejlesztését a 2. ábra mutatja, itt 5⋅3⋅2=30 elhelyezés van.
 
 
2. ábra
 

6. Végül, ha minden szomszédpárt különböző fajtájú sajtok alkotnak, 4 lényegesen különböző elrendezés van:
 

  I.A B A B A B,  III.A B C A B C,
  II.A B A B A C,  IV.A B C A C B,  
 


és a betűk helyére fajtákat írni 3+3⋅2+2+3=14-féleképpen lehet.
Mindezek szerint összesen 3+15+20+48+30+14=130 lehetőség van.
 

Megjegyzés. Az alábbi táblázat megkönnyíti az I. és II. megoldásban különböző szempontok szerint számba vett elrendezések azonosítását.
 


  I \ II123456Össz.|63-----13|5+1-6----16|4+2-3-12--18|3+3-3-16-312|4+1+1--1619--15|3+2+1--121824660|2+2+2--121316516|Össz.31520483014130|
 

III. megoldás. Könnyű lenne megadni a választ, ha rögzítenénk azt a dobozt, amelyikbe visszarakunk 6 cikket, és benne az I., II., ..., VI. helyet is kijelölnénk. Így ugyanis mind a 6 helyre 3‐3-féleképpen választhatjuk egymástól függetlenül a C,- H,- M-sajttípus egy‐egy cikkét, tehát 36=729-féle elhelyezést kapunk. Az így kapott elhelyezések azonban feladatunk szempontjából nem mind különbözők. Például az MCMHCH elrendezésből alkalmas forgatásokkal a nem azonosnak tekintett
CMHCHM,MHCHMC,HCHMCM,CHMCMH,HMCMHC
elhelyezéseket kapjuk. Általában egy elhelyezésből ‐ a dobozt körbeforgatva ‐ öt további, a fenti leszámlálásban ugyancsak figyelembe vett elhelyezést kapunk. Nem szabad azonban ennek alapján arra gondolnunk, hogy a feladat megoldását úgy kapjuk meg, hogy az előbbi 729-et osztjuk 6-tal. (Erre utal már csak az a körülmény is, hogy 729 nem is osztható 6-tal.) Némely elhelyezésből ugyanis így 5-nél kevesebb új elhelyezési tervet kapunk, sőt esetleg egyet sem. Ilyen például MCMMCM, amelyből csak az első két lépésben kapunk tőle formálisan különböző tervet: CMMCMM, MMCMMC, és az eredeti tervet már a harmadik lépésben visszakapjuk.
Az ilyen elrendezéseket külön fel kell sorolnunk előbb, hogy a visszamaradók számát 6-tal oszthassuk. Azokat az elrendezéseket keressük tehát első lépésben, amelyeket már egy 360∘-nál kisebb forgatás önmagába visz át, más szóval amelyeknek valamilyen ciklikus szimmetriájuk van.
A ciklus tagjainak száma nyilvánvalóan csak 6 vagy ennek osztója lehet, vagyis 3, 2 vagy 1. A rövidebb ciklusokban csak 3, 2, ill. 1 tagot választhatunk szabadon, sőt itt is figyelembe veendő, hogy amint némely ciklus nem igazi 6-tagú, ugyanúgy az 1-tagú ciklus kiadódik a 2-tagúak között is, a 3-tagúak között, és a 6-tagúak között is.
Mármost az egytagú ciklus 3-féleképpen választható. A kéttagúakat keresve a gondolható 32-ből el kell hagyni azt a 3-at, amelyeknek a tagjai egyenlők: CC, HH és MM, vagyis a valódi kéttagúak száma, rögzített doboz esetén 32-3, és ezek forgatással (32-3)/2=3 különböző berakást jelentenek. Hasonlóan a valódi háromtagúak száma, rögzítéssel 33-3=24, forgatással ennek 3-adrésze: 8.
Ezek szerint, a rögzítést tekintetbe véve, 36-3-(32-3)-(33-3)=696 olyan berakásmód marad, amely valóban hattagú ciklusba tartozik bele, tehát a keresett szám:
3+32-32+33-33+36-3-(32-3)-(33-3)6=130.

Szendrei Mária (Szeged, Ságvári E. Gyak. Gimn., IV. o. t.)

Breuer Péter (Eger, Gárdonyi G. Gimn., III. o. t.)
 

Megjegyzés. Eredményünk így is értelmezhető: ha dominójátékot készítünk szabályos hatszög alakú kövekből úgy, hogy a köveket 6 egybevágó szabályos háromszögre osztjuk, és ezekbe minden lehető módon 2, 1 vagy 0 pontot írunk, akkor a kőkészlet 130 darabból fog állni.