Talningarfræði

Dæmi 22. Neðra stig 1993-94

Hversu margar náttúrlegar tölur hafa tölustafi sína í strangt vaxandi röð (eins og til dæmis talan $2458$)?

Lausn

Fyrst er vert að minnast á tvö atriði varðandi hvernig á að skilja þetta dæmi. Fyrst er það spurningin um hvað á að gera við einstafs tölur, til dæmis töluna $5$. Eru tölstafir hennar í vaxandi röð? Þarna kemur fram munur á stærðfræðilegri málnotkun og venjulegri málnotkun. Margir mundu segja að það væri út í hött að segja að einn tölustafur myndaði vaxandi röð, en í stærðfræðilegri málnotkun er það ekkert óeðlilegt. Einnig kemur upp sú spurning hvort talan $0$ er náttúruleg tala. Hér er það hreint smekksatriði hvað menn segja og ekkert allsherjar samkomulag til. Það hvaða afstöðu menn tóku til þessara spurninga hafði ekki áhrif á stigagjöf fyrir dæmið. Lausnin hér miðast við að eins stafs tölur eru taldar með en $0$ ekki.

Lausn 1: Skoðum rununa $123456789$. Sérhverja tölu sem hefur tölustafi sína í strangt vaxandi röð má fá út úr þessari runu með því að taka burt einhverja tölustafi. Þá sjáum við til dæmis, að fjöldi fimm stafa talna sem hafa tölustafi sína í strangt vaxandi röð er jafn fjölda möguleika á því að taka burt fjóra stafi, eða jafn $9\choose4$. Til að fá heildarfjöldann þá verðum við að reikna út $${\begin{pmatrix}9\\ 0\end{pmatrix}}+{\begin{pmatrix}9\\ 1\end{pmatrix}}+\cdots+{\begin{pmatrix}9\\ 8\end{pmatrix}}.$$ Það má nota ýmsar leiðir til að sjá út að þessi tala er $511$. Það má jafnvel reikna þetta beint, en til gamans sýnum við hér aðra leið til að fá svarið. Við notum tvíliðuregluna sem segir að $$(a+b)^n=\sum_{k=0}^n {\begin{pmatrix}n\\ k\end{pmatrix}} a^kb^{n-k}.$$ Þá er $${\begin{pmatrix}9\\ 0\end{pmatrix}}+{\begin{pmatrix}9\\ 1\end{pmatrix}}+\cdots+{\begin{pmatrix}9\\ 9\end{pmatrix}}=(1+1)^9=2^9=512,$$ og þar sem við sleppum síðasta liðnum, það er $\begin{pmatrix}9\\ 9\end{pmatrix}$, þá fáum við $511$.

Lausn 2: Annað hvort kemur tala í rununni $123456789$ fyrir í tölu sem hefur tölustafi sína í strangt vaxandi röð eða ekki. Fyrir hverja tölu eru því tveir möguleikar, annaðhvort er talan með eða ekki. Við teljum ekki með þann möguleika að engin tala sé með og svarið við dæminu er því $2^9-1=511$.

Dæmi 12. Efra stig 1992-93

Námsmaður nokkur gengur daglega frá $A$ til $B$. Hann gengur annaðhvort alltaf í suður eða austur, en til tilbreytingar þá kastar hann upp krónu um hvort hann fer í suður eða austur ef hann á val. Hver eru líkindi þess að hann fari um gatnamót $C$?

Lausn

Látum $(m,n)$ tákna punktinn sem við erum í eftir að hafa farið $m$ sinnum suður og $n$ sinnum austur.

Einfaldast er að leysa dæmið þannig að við rekjum okkur út frá upphafspunktinum og reiknum út líkindi þess að við förum um hvern punkt fyrir sig. Til dæmis eru líkindi þess að við förum um $(1,0)$ greinilega $\frac{1}{2}$. Til að komast til $(1,1)$ þá verðum við annað hvort að koma frá $(1,0)$ eða frá $(0,1)$. Ef við erum í öðrum hvorum þessara punkta, þá eru helmings líkindi á að við förum næst í $(1,1)$. Því eru líkindin á því að við förum um $(1,1)$ helmingur líkinda þess að við förum um $(1,0)$ að viðbættum helmingi líkinda þess að við förum um $(0,1)$, eða samtals $\frac{1}{2}$.
Athugum þó að þegar við erum komin í jaðarpunkt þá eigum við ekki lengur neitt val. Til dæmis ef við erum í $(0,3)$, þá verðum við næst að fara í $(1,3)$. Ef við táknum líkindi þess að fara um punktinn $(m,n)$ með $p(m,n)$, þá höfum við að \begin{align} p(0,0) &= 1,\\ p(0,1) &= p(1,0) =\tfrac{1}{2},\\ p(0,2) &= p(2,0) = \tfrac{1}{4},\\ p(0,3) &= p(3,0) = \tfrac{1}{8},\\ p(1,1) &= \tfrac{1}{2}p(0,1)+\tfrac{1}{2}p(1,0) = \tfrac{1}{2},\\ p(1,2) &= \tfrac{1}{2}p(1,1)+\tfrac{1}{2}p(0,2)=\tfrac{3}{8},\\ p(2,1) &= \tfrac{1}{2}p(1,1)+\tfrac{1}{2}p(2,0)=\tfrac{3}{8},\\ p(1,3) &= p(0,3)+\tfrac{1}{2}p(1,2)=\tfrac{5}{16},\\ p(3,1) &= \tfrac{1}{2}p(3,0)+\tfrac{1}{2}p(2,1)=\tfrac{1}{4},\\ p(2,2) &= \tfrac{1}{2}p(1,2)+\tfrac{1}{2}p(2,1)=\tfrac{3}{8},\\ p(2,3) &= \tfrac{1}{2}p(2,2)+p(1,3)=\tfrac{1}{2},\\ p(3,2) &= \tfrac{1}{2}p(2,2)+\tfrac{1}{2}p(3,1)=\tfrac{5}{16},\\ p(3,3) &= p(2,3)+\tfrac{1}{2}p(3,2)=\frac{21}{32}. \end{align}

Líkindi þess að námsmaðurinn fari um punktinn $C$ eru þá $p(3,3)=\frac{21}{32}$.

Í svona dæmum gæti það virst vera einföld leið að telja bara fjölda mismunandi leiða til $B$, telja svo fjölda leiða sem liggja um $C$ og segja svo að svarið sé kvóti þessara talna. Hérna dugar þessi aðferð ekki því leiðirnar til $B$ hafa ekki allar jöfn líkindi. Til dæmis eru líkindi þess að leiðin sem liggur um $(0,3)$ verði farin jöfn $\frac{1}{8}$ en líkindi þess að leiðin sem liggur um $(4,0)$ sé farin eru jöfn $\frac{1}{16}$.

Dæmi 10. Neðra stig 1992-93

Allar heilu tölurnar frá $1$ og upp í $1.000.000$ eru prentaðar út. Hve oft kemur tölustafurinn $5$ fyrir?

Lausn

Hægt er að telja hve oft $5$ kemur fyrir í eins stafs tölum, tveggja stafa tölum og svo framvegis. Það má hinsvegar einnig komast hjá þeirri talningu með eftirfarandi röksemdarfærslu. Athugum að við þurfum ekki að hafa áhyggjur af tölunni $1.000.000$, því í henni kemur tölustafurinn $5$ hvergi fyrir. Því getum við gert ráð fyrir að hún sé ekki á listanum, en í staðin skulum við bæta $0$ fremst í listann þannig að við prentum út $1.000.000$ tölur eftir sem áður. Hugsum okkur að við prentum núll fremst í tölunum þannig að allar verði þær $6$ stafa langar. Þannig prentum við til dæmis $000555$ þar sem talan $555$ á að koma. Tölustafurinn $5$ kemur jafnoft fyrir á þessum lista eins og þeim upphaflega. Í allt þá prentum við út $6\cdot 1.000.000$ tölustafi og tölustafurinn $5$ kemur jafnoft fyrir á þessum lista og hver hinna $9$ tölustafanna. Svarið er því $6.000.000/10=600.000$.

Dæmi 8. Neðra stig 1991-92

Ef talan $p$ er valin úr menginu $\{ 1 , 3 , 5 \}$ og $q$ er valin úr menginu $\{ 2 , 4 , 6 , 8 \}$, þá er fjöldi möguleika á því að velja $p$ og $q$ þannig að $p+q\lt 11$ jafn

Lausn

Ef $p=1$, þá er $p+q\lt 11$ fyrir öll $q$. Ef $p=3$ þá er $p+q\lt 11$ fyrir öll $q$ nema $q=8$ og ef $p=5$ þá er $p+q\lt 11$ fyrir öll $q$ nema $q=6$ og $q=8$. Það eru því alls $4+3+2=9$ möguleikar á að velja $p$ og $q$ þannig að $p+q\lt 11$.

Dæmi 14. Neðra stig 1991-92

Maja sló grasflöt sem var rétthyrningur $20$ m sinn um $12$ m að stærð. Hún byrjaði á því að slá ræmu umhverfis flötinn og hélt svo áfram eins og sýnt er á myndinni. Ef sláttuvélin sló braut sem var $1$ m á breidd, hversu oft þurfti Maja að beygja um $90^\circ$ til vinstri?

Lausn

Hugsum okkur að upp á blaðinu sé norður. Maja byrjar því í norðvestur horni blettsins og gengur í suður. Þar sem bletturinn er stærri á austur—vestur hliðina heldur en á norður—suður hliðina, þá endar Maja á því að ganga í austur eða vestur. Hún labbar $12$ sinnum í austur eða vestur og þar sem hún labbar í austur áður en hún labbar í vestur í fyrsta skipti, þá endar hún á því að labba í vestur. Í hvert skipti sem Maja byrjar að slá í suður verður hún að taka fjórar vinstribeygjur áður en hún byrjar næst að slá í suður. Hinsvegar þarf hún ekki að snúa sér í suður í síðasta skiptið sem hún labbar í vestur, svo í síðasta hringnum tekur hún aðeins þrjár vinstribeygjur. Alls eru vinstri beygjurnar þá $5\cdot 4 + 3=23$.

Dæmi 19. Neðra stig 1991-92

Fjörutíu spjöld eru merkt með tölunum frá 1 upp í 40. Tíu spjöld eru valin af handahófi og tölurnar á þeim lagðar saman. Fjöldi mögulegra útkoma er

Lausn

Minnsta mögulega summan er $\frac{1}{2}\cdot (1+10)\cdot 10=55$ og sú stærsta $\frac{1}{2}\cdot(31+40)\cdot 10=355$.

(Hér notfærum við okkur að ef við eigum að leggja saman $n$ tölur $a_1, a_2, \ldots, a_n$ þannig að $a_{k+1}-a_k$ er föst tala fyrir öll $k=0,\ldots,n-1$, þá er summan margfeldi fjölda talnanna við meðaltal fyrsta og síðasta liðarins.)

Ljóst er að við getum valið spil til að fá hvaða útkomu þarna á milli svo fjöldi mögulegra útkoma er $355-55+1=301$.

Dæmi 5. Úrslitakeppni 1991-92

Í skóla nokkrum eru $1000$ nemendur. Í skólanum er kenndur fjöldi tungumála. Hver nemandi lærir í mesta lagi $5$ tungumál. Svo vill til, að í sérhverjum hópi þriggja nemenda er hægt að finna tvo sem læra sama tungumálið. Sýnið að hægt sé að finna að minnsta kosti $100$ nemendur sem læra allir sama tungumálið.

Lausn

Tökum einhvern nemanda $A$. Fyrst skulum við gera ráð fyrir að ekki sé til nemandi $B$ þannig $B$ læri ekkert þeirra tungumála sem $A$ lærir. Þá lærir sérhver nemandi að minnsta kosti eitt þeirra tungumála sem $A$ lærir. Því má skipta nemendunum í hópa, jafnmarga og tungumálin eru sem $A$ lærir þannig að allir nemendurnir í hverjum hópi læri eitthvert tiltekið mál sem $A$ lærir. Nú lærir $A$ í mesta lagi $5$ tungumál og þegar $1000$ nemendum er skipt í hópa, $5$ eða færri, þá er gulltryggt að í einhverjum hópnum verða að minnsta kosti $100$ nemendur.

Gerum nú ráð fyrir að til sé nemandi $B$ sem lærir ekkert þeirra tungumála sem $A$ lærir. Þá segir skilyrðið í dæminu okkur að allir nemendur skólans læri að minnsta kosti eitt þeirra tungumála sem $A$ og $B$ læra. Samanlagt læra $A$ og $B$ í mesta lagi $10$ tungumál. Nú getum við eins og áður skipt nemendunum í hópa, ekki fleiri en $10$, þannig að allir nemendur í sama hópi læri eitthvert tiltekið tungumál sem annaðhvort $A$ eða $B$ læra. Þá er ljóst að í einhverjum hópnum verða að minnsta kosti $100$ nemendur.

Dæmi 6 Efra stig 1997-1998

Í körfuboltakeppni, þar sem hvert lið leikur einn leik á móti hverju hinna, vann sigurliðið alla leiki sína nema einn, neðsta liðið tapaði öllum leikjum sínum nema einum, og hin liðin unnu fjóra leiki hvert. (Athugið að í körfubolta lýkur leik aldrei með jafntefli.) Hve mörg voru liðin?

Lausn

Svar:9

Lausn: Látum $n$ tákna fjölda liða. Hvert lið leikur einn leik á móti hverju hinna og leikur því $n - 1$ leik. Því eru alls leiknir $\frac{n\cdot (n - 1)}{2}$ leikir á mótinu. Heildarfjöldi vinninga sem liðin fá er því $\frac{n\cdot (n - 1)}{2}$. Upplýsingar okkar segja að efsta liðið fékk $n - 2$ vinninga, neðsta liðið fékk $1$ vinning, og hin liðin, $n - 2$ að tölu, fengu $4$ vinninga hvert. Heildar fjöldi vinninga er því $(n-2)+1+(n-2)\cdot 4=5 n - 9$. Fáum þá jöfnuna \[ \frac{n\cdot (n - 1)}{2} = 5n - 9 , \] Sem er jafngild jöfnunni $n^2 - 11n + 18 =0$. Þegar þessi jafna er leyst fæst að $n=2$ eða $n=9$. Það að bara tvö lið hafi verið í mótinu fær ekki staðist, þá er bara leikinn einn leikur og samkvæmt forsendunum þá vinnur neðsta liðið þann leik og er því ekki neðst! Liðin eru því $9$.

Stærðfræðikeppni framhaldsskólanema

Dæmi 22. Neðra stig 1993-94

Dæmi 12. Efra stig 1992-93

Dæmi 10. Neðra stig 1992-93

Dæmi 8. Neðra stig 1991-92

Dæmi 14. Neðra stig 1991-92

Dæmi 19. Neðra stig 1991-92

Dæmi 5. Úrslitakeppni 1991-92

Dæmi 6 Efra stig 1997-1998

Stærðfræðikeppni framhaldsskólanema

STAK