Ugrás a tartalomhoz

Matematikai versenyfeladatok

Makó Zita, Szilágyi Ibolya, Téglási Ilona

Kempelen Farkas Hallgatói Információs Központ

A feladatok megoldásai

A feladatok megoldásai

  1. Ha egy körmérkőzéses bajnokságon résztvevő van, akkor mindegyikük játszik a többi résztvevővel, ez mérkőzés. De így minden mérkőzést minden résztvevőnél számoltunk, ezért a mérkőzések száma csak ennek fele: .

    Ha eredetileg résztvevő volt, akkor a mérkőzések tervezett száma .

    feleannyi résztvevő esetén:

    Ezek különbsége 145.

    ennek pozitív megoldása . Tehát eredetileg 20 résztvevő lett volna.

    Ha a részvevők száma 20-ról negyedére, azaz 5-re csökken, akkor a mérkőzések száma -ről -re, tehát 180-nal csökken.

  2. Ha a lemondás után résztvevő marad, akkor a két lemondott játékosnak elmarad egyenként mérkőzése a megmaradtak ellen, és egy mérkőzése egymás ellen:

    1. Ha az első jegy 3-as, akkor a következő két helyen 10-10 jegy állhat, tehát 100 ilyen szám van.

      Ha az utolsó jegy 3-as, akkor az első helyen 9, a másodikon 10 jegy állhat, tehát 90 ilyen szám van.

      Kétszer számoltuk azokat, amelyeknek első és utolsó jegye is 3-as, itt a középső helyen 10 jegy állhat, tehát 10 ilyen szám van.

      Tehát összesen 100+90-10=180 olyan háromjegyű természetes szám van, melynek az első vagy az utolsó számjegye 3.

    2. Ha az első jegy 1-es, akkor a további 9 jegyből szám képezhető.

      Ha az első jegy 2-es, akkor a további 9 jegyből szám képezhető.

      Tehát a képezhető 10 jegyű számok száma:

    3. Minden számban a jegyek összege 12, ezért mind osztható 3-mal, de egy sem osztható 9-cel, így egyik sem lehet négyzetszám.

  3. Rajzoljunk egy 9 pontú gráfot, és abban a küldött lapok jelentsenek egy irányított élt. Akkor lesz olyan pár, akik üdvözölték egymást, ha van olyan pontpár, hogy -ból -be és -ből -ba is megy él, tehát ha van kettős él. Ha minden él egyszeres, akkor legfeljebb élt húzhatunk be.

    üdvözlőlap esetén 94=36 élt rajzolunk be, ez még elképzelhető, hogy mind egyszeres él. Ez meg is valósítható pl. úgy, hogy a 9 pontot egy körre írjuk, és mindegyikből a tőle pozitív irányban levő négy következőhöz megy él.

    üdvözlőlap esetén 95=45 élt rajzolunk be, itt már biztosan van kettős él.

    Tehát esetén biztosan lesz olyan pár, akik üdvözölték egymást.

    1. Az 1-gyel kezdődő számok száma annyi, ahányféleképpen a megmaradó 4db 2-es, 4 db 0 és 3 db 1-es számjegyet sorba lehet állítani:

      A 2-vel kezdődő számok száma is:

      Az összes 12 jegyű szám száma:

    2. Néggyel akkor és csak akkor osztható egy szám, ha az utolsó két jegyből álló szám osztható 4-gyel. Ezért a következő hat eset lehetséges:

      Az 1-gyel kezdődő 00-ra végződő számok száma:

      A 2-vel kezdődő 00-ra végződő számok száma:

      Az 1-gyel kezdődő 20-ra végződő számok száma:

      A 2-vel kezdődő 20-ra végződő számok száma:

      Az 1-gyel kezdődő 12-re végződő számok száma:

      A 2-vel kezdődő 12-ra végződő számok száma:

      Így a néggyel osztható számok szám a fenti hat szám összege: 7980.

    3. Mindegyik számban a jegyek összege . Ezért mindegyik szám osztható 3-mal, de egyik sem osztható 9-cel, tehát egyik sem lehet négyzetszám.

    1. Biztosan ki tudunk még 500-at venni.

      Képezzük a következő 1000 párt: (1;2000); (2;1999); (3;1998); (1000;1001).

      Nézzük sorban az először kivett 500 golyót.

      • ha valamelyiknek a fenti párja nincs a kivettek között, akkor vegyük ki a párját is.

      • ha egy pár mindkét eleme az előre kivettek között van, akkor vegyünk ki egy olyan párt, amelynek mindegyik eleme még a dobozban van.

        Az így kivett 1000 golyó 500 párt alkot a fentiek közül, és mivel minden pár azonos tömegű, így a kivett 1000 golyó tömege azonos a dobozban maradt 1000 golyó tömegével. Mindegyik összesen g=1000500 g.

    2. Nem biztos, hogy ki tudunk venni még 499-et.

      Ha először például az 1 g, 2 g, 501 g tömegűeket vesszük ki, akkor ez összesen g.

      Ha ehhez a legnehezebb 499-et vesszük ki, akkor ezek tömege g.

      Az 1000 golyó tömege 125751 g+873749 g=999500, így sem éri el az összes tömeg felét.

  4. Ha az első napon házaspár, azaz résztvevő volt, akkor mindenki emberrel fogott kezet, ez összesen kézfogás, de így minden kézfogást kétszer számoltunk, tehát a kézfogások száma . A második napon házaspár esetén a kézfogások száma .

    A feltételek szerint

    azaz,

    Ha és , akkor és is növekvő, ezért elegendő egy megfelelő értéket találni, amire a fenti egyenlőtlenség teljesül.

    esetén 910<100<1011. Ez 11-nél kisebb és nagyobb -eknél már nem teljesülhet.

    Tehát első nap 11, második nap 10 házaspár vett részt. Valóban, 11 házaspárnál 220, 10 házaspárnál 180 kézfogás történt.

    A végeredmény a másodfokú egyenlőtlenségek és , illetve figyelembe vételével is megkaphatjuk az eredményt.

  5. Csak páratlan jegyeket tartalmazó számban az egyes helyiértékekre 5-5-5 jegyet választhatunk, ez összesen 125 szám.

    Csak páros jegyeket tartalmazó számban az egyes helyiértékekre 4-5-5 jegyet választhatunk, ez összesen 100 szám.

    Összesen van 900 háromjegyű szám, tehát a páros és páratlan jegyet is tartalmazók száma 900-125-100=675.

    Tehát annak a valószínűsége, hogy a kiírt számban páros és páratlan számjegy is szerepel: .

    1. Bármely két egyenes meghatároz egy metszéspontot, ezért 45 metszéspont van.

    2. Minden egyenest 9 másik metsz, és a 9 metszéspont között 8 szakasz és a két végén 1-1 félegyenes van. Tehát 80 szakaszt és 20 félegyenest számolhatunk össze.

    1. Az egyes helyiértékekre 5,5,5 számjegyet választhatok, ezért csak a páratlan jegyet tartalmazó számok száma .

    2. 0 nem állhat az első helyen, ezért az egyes helyiértékekre 4,5,5 számjegyet választhatok, így a csak páros jegyeket tartalmazó számok száma .

    3. A 0, 1, 2, ,9 számokból kell kiválasztani hármat úgy, hogy ismétlés is lehetséges, de minden lehetséges hármast csak egyszer, nem növekvő sorrendben számolunk. Így a lehetőségek száma . Ebből egy nem jó, a 000, tehát az összes eset száma: 219.

  6. Mivel a 0-n kívül összesen 9 számjegyet használunk fel a 9 jegyű számhoz, ezért minden számjegy pontosan egyszer szerepel benne. A keresett számok 11-gyel oszthatóak, tehát az oszthatósági szabály szerint a páratlan helyeken álló számjegyek összegének és a páros helyeken álló számjegyek összegének különbsége osztható 11-gyel. Legyen a szám

    alakú: . A legnagyobb különbség (9+8+7+6+5)-(4+3+2+1)=25, a legkisebb (1+2+3+4+5)-(6+7+8+9)=-15. A számjegyek összege 45, (így a páratlan helyeken álló számjegyek összege pont 45 és a különbség összegének fele) tehát a különbség nem lehet páros: csak 11 vagy -11 lehet. Legyen a számjegyek összege, a páratlan helyeken, pedig a páros helyeken álló számjegyek összege. Ekkor egyrészt , másrészt , ahol . A két egyenlet megfelelő oldalait összeadva , ahonnan nyilvánvalóan látszik, hogy nem lehet páros, azaz csak vagy lehetséges. Ha a különbség 11, akkor az ötös csoportbeli számok összege 28. Keressük azon öt különböző számjegyet, melyek összege 28: (9 8 7 3 1), (9 8 6 4 1), (9 8 6 3 2), (9 8 5 4 2), (9 7 6 5 1), (9 7 6 4 2), (9 7 5 4 3), (8 7 6 5 2), (8 7 6 4 3). Ha a különbség -11, akkor kereshetjük azon 4 számjegyet, melyek összege 28: (9 8 7 4) és (9 8 6 5). Mivel a számjegyek különbözők és egyik sem 0, ezért a csoporton belül bármilyen sorrendben követhetik egymást: a páratlan helyeken álló 5 számjegyből álló csoport 5!, a páros helyeken álló csoport 4 tagjának összesen 4! különböző sorrendje van. A 9 számjegy két részre osztásakor tehát 5!.4! különböző számot kapunk, melyek egy jó kettéosztás esetén mind oszthatóak 11-gyel. Összesen 9+2=11 jó kettéosztása volt a számjegyeknek, tehát darab olyan 11-gyel osztható 9-jegyű szám van, amiben a nulla kivételével minden számjegy előfordul.

  7. Legyen a gráf G=(V,E), és definiáljunk egy új gráfot. Az új gráf csúcsai legyenek V nemüres részhalmazai. Két részhalmazt akkor kössünk össze, ha diszjunktak, és nem megy él az egyik halmazból a másikba.

    Nézzük, mennyi lehet egy részhalmaznak a foka az új gráfban. Ha egy H domináns, akkor minden P pont vagy benne van H-ban, vagy megy él P-ből H-ba. Ez azt jelenti, hogy ha V egy nemüres részhalmaza diszjunkt H-tól, akkor megy belőle él H-ba, tehát semmiképpen sincs összekötve H-val az új gráfban, vagyis egy domináns részhalmaz foka nulla.

    Most tegyük fel, hogy H nem domináns. Álljon azokból a pontokból, amelyek nincsenek H-ban, és nem is megy belőlük él H-ba. Ez tehát nem üres. Egy akkor és csak akkor lesz H-val összekötve, ha -nek részhalmaza. Mivel az üres halmaz nincs a csúcsok között, ha -ben pont van, akkor H-nak szomszédja van, ami páratlan, mivel k>0.

    Tehát pontosan a nem domináns részhalmazoknak páratlan a foka az új gráfban, így páros sok van belőlük. Az üres halmaz nyilván sosem domináns, így összesen páratlan sok nem domináns halmaz van, de összesen páros sok részhalmaz van, tehát páratlan sok domináns részhalmaz van.

  8. Vizsgáljuk meg először, hogy kiválasztható-e 4 jó űrhajós, vagyis 4 olyan űrhajós, hogy közülük bármelyik 3 megfelelő személyzetet alkosson. Vegyünk egy tetszőleges űrhajóst. Két másik űrhajóst kössünk össze egy piros madzaggal, ha -val együtt megfelelő személyzetet alkotnak, ellenkező esetben pedig kék madzaggal kössük össze őket. Ha van 4 űrhajós, melyek közül bármely kettő kék madzaggal van összekötve, akkor vegyünk ezek közül hármat, legyenek ezek .

    Az űrhajósok közül csak alkothat megfelelő személyzetet, tehát a feladat feltétele szerint nekik mindenképpen megfelelő személyzetet kell alkotniuk. Vagyis ha 4 űrhajós közül bármelyik kettő kék madzaggal van összekötve, akkor közülük bármelyik 3 megfelelő személyzet lesz. Ha pedig van 4 űrhajós, melyek közül bármely kettő piros madzaggal van összekötve, akkor a feladat feltételének megfelelően válasszunk ki közülük hármat, akik megfelelő személyzetet alkotnak, legyenek most ezek . Ekkor az űrhajósok közül bármely 3 megfelelő személyzetet alkot.

    • Jelölje tehát ) azt a legkisebb természetes számot, amelyre igaz, hogy ha egy csúcsú teljes gráf minden élét piros vagy kék színűre festjük, akkor vagy lesz benne egy csúcsú teljes részgráf, amelyiknek minden éle piros, vagy pedig egy csúcsú teljes részgráf, amelyiknek minden éle kék. A fenti okoskodás szerint, ha az űrhajós mellé kiválasztunk további űrhajóst, akkor közöttük lesz 4 jó űrhajós. Más szóval, bármely űrhajós között lesz 4 olyan, hogy közülük bármely 3 jó személyzetet alkot.

    • Nyilván , és nem nehéz megmutatni, hogy esetén , hiszen ha egy szögpontú teljes gráf minden élét piros vagy kék színűre festjük, akkor egy csúcsát kiválasztva, abból vagy kiindul legalább kék színű él, vagy pedig kiindul legalább piros színű él. Ebből az egyenlőtlenségből szerinti teljes indukcióval adódik, hogy

    • Ezek szerint . Tekintsünk most űrhajóst. Vegyünk megint csak egy tetszőleges űrhajóst, két másik űrhajóst pedig kössünk össze egy piros madzaggal, ha -val együtt megfelelő személyzetet alkotnak, ellenkező esetben meg kékkel. Ha van 5 űrhajós, melyek közül bármely kettő kék madzaggal van összekötve, akkor a már látott gondolatmenet szerint közülük bármely 3 jó személyzetet kell, hogy alkosson. Ha nincs 5 ilyen űrhajós, akkor viszont kell lennie 21 olyan űrhajósnak, melyek közül bármely kettő piros madzaggal van összekötve. Mint láttuk, ezek között van 4 jó űrhajós, akik mellé még -t kiválasztva kapunk 5 jó űrhajóst.