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 file
Témakör(ök): Permutációk, Kombinációk, Feladat
Hivatkozás(ok):Feladatok: 1971/május: F.1775

Van 1‐1 doboz Caro, Holló és Mackó sajtunk, kiborítjuk tartalmukat az asztalra. Hányféleképpen lehet a 18 egyforma cikkből 6-ot visszarakni az egyik dobozba, címkéjükkel fölfelé? (2 elhelyezést nem tekintünk különbözőnek, ha alkalmas elforgatással átvihetők egymásba.)

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 32=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 63=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 43=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 232+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 106=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, 32=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 32+32+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 32+232+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 233, é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 33. Így összesen 2233+3+33=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 532=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.B B B,  III.B C B C,
  II.
B B C,  IV.B C C B,  
 


és a betűk helyére fajtákat írni 3+32+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.