Középiskolai Matematikai és Fizikai Lapok, 1996 (46. évfolyam, 1-9. szám)

1996-01-01 / 1. szám

Л__L 2. feladat. Egy n oldalú konvex sokszög belsejében nincs olyan pont, amelyen sokszög kettőnél több átlója halad át. Hány metszéspontja van a sokszög átlóinak a sok­szög belsejében ? A megoldás dallama hasonló az előbbihez. A sokszög bármely négy csúcsa egy konvex négyszöget határoz meg, a négyszög átlóinak metszéspontja pedig megad egy metszéspontot a keresettek közül. Egy metszéspont és négy csúcs ily módon történő pár­­baállítása kölcsönösen egyértelmű: annyi metszéspont van, ahányféle módon ki tudunk választani 4-et az n csúcs közül, azaz 3. feladat. Mutassuk meg, hogy egy n elemű halmaz részhalmazainak száma 2". Az állítás igazolható teljes indukcióval, vagy úgy is, hogy felhasználjuk az összefüggést. Elegáns útja a bizonyításnak a következő: ha az n-elemű halmaz {ai,a 2,... .. .,an}, úgy ennek egy részhalmazát egyértelműen kijelöli egy n hosszúságú 0-1 sorozat. Ha a sorozatban a fc-dik helyen 1 -es áll, akkor cy. eleme a részhalmaznak, ha pedig 0 áll a fc-adik helyen, akkor nem, így a részhalmazok száma ugyanannyi, mint az n hosszú 0-1 sorozatok száma: 2". 4. feladat. Mutassuk meg, hogy az 1,2,..., 10* számokban előforduló számjegy száma egyenlő az 1,2,..., 10^+1 számokban levő 0-k számával. Az első sorozatból tetszőleges számot választva, annak valamely számjegye után beszúrunk egy nullát. Ez a megfeleltetés kölcsönösen egyértelmű az első sorozatbeli számok számjegyei és a második sorozatbeli számok 0 számjegyei között. Ha látjuk, hogy mindegyik lovon egy huszár ül, és néhány huszár gyalog sétál, akkor nyilván a huszárok száma nagyobb a lovak számánál. Egyenlőtlenséget is tudunk a párbaállítás módszerével igazolni. Lássuk a következő feladatot! 5. feladat. Jelölje Tn egy n elemű halmaz különböző partícióinak (diszjunkt osztá­lyokra bontásainak) számát. Bizonyítsuk be, hogy fennáll a Tn ss n! egyenlőtlenség. Legyen az n-elemű halmaz {1,2,3, .. .,n). Tekintsük a halmaz egy partícióját, és minden részhalmazban az elemeket rendezzük nagyság szerint csökkenő sorrendbe, majd ezeket a sorozatokat első elemük szerint növekedve írjuk egymás után. Például, ha a = = 6 és az egyik partíció {1,5}, {2,3}, {4,6}, úgy ehhez a 3­25164 sorozat tartozik. Ily módon megadhatjuk az n elem egy permutációját, különböző partíciókhoz különböző permutációkat. Vagy olyan permutáció is, amelyhez nem tartozik partíció, pl.: 3 26451. (Gondoljuk meg, miért?) Megjegyzés: Az n-elemű halmaz partícióinak számát a Tn Bell-féle szám jelöli. 6. feladat. Az 1 < aj <(12< ... ) n természetes számokra igaz, hogy egyik а [UNK] sem osztója a többi szorzatának. Mutassuk meg, hogy к ^ 7r(n), ahol т [UNK](п) a prímszámok száma n-ig. 2

Next