Úrslitakeppni | stæ.is

Dæmi 5. Úrslitakeppni 1993-94

Á hversu marga vegu er unnt að raða tölunum $1,2,\ldots,n$ í sæti þannig að eftirfarandi gildi fyrir sérhvert $i = 2,\ldots,n$: Talan í $i$-ta sæti er annaðhvort minni en allar tölurnar á undan eða stærri en allar tölurnar á undan.

Lausn

Byrjum á því að líta á aftasta sætið. Ef talan þar er minni en allar tölurnar á undan, þá er hún jöfn $1$. Ef hún er stærri en allar tölurnar á undan, þá er hún jöfn $n$. Það eru því aðeins tveir möguleikar á því að setja tölu í sæti númer $n$. Á sama hátt sjáum við að talan í sæti $n-1$ er annað hvort minnsta talan eða stærsta talan sem eftir er, þegar talan í sæti $n$ hefur verið ákveðin. Það eru því einnig tveir möguleikar til þess að setja tölu í sæti númer $n-1$. Við rekjum okkur áfram niður á við niður í sæti númer $2$ og í hverju skrefi höfum við $2$ valmöguleika. Þá er aðeins ein tala eftir til þess að setja í sæti númer $1$. Fjöldi möguleika er því $2^{n-1}$.

Dæmi 6. Úrslitakeppni 1993-94

Reynir er að flísaleggja rétthyrningslaga gólfflöt. Til þess notar hann hvítar og svartar ferningslaga flísar sem hann leggur í munstur eins og á skákborði. Hann byrjar á að setja heila flís í eitt hornið og heldur áfram út frá því horni. Þegar hann hefur lokið við flísalagninguna þá tekur hann eftir því að samanlagt flatarmál hvítu flísanna á gólfinu er jafnt samanlögðu flatarmáli svörtu flísanna. Sýnið að önnur hliðarlengd gólfflatarins er heilt margfeldi af hliðarlengd flísanna og að fjöldi flísa meðfram þessari hlið er jöfn tala.

Lausn

Til einföldunar skulum við hugsa okkur að flísarnar séu ein lengdareining á kant og að byrjað sé á að setja hvíta flís í horn. Síðan hugsum við okkur að hliðarlengdir gólfflatarins séu $x=2m+a$ og $y=2n+b$, þar sem $m$ og $n$ eru heilar tölur, $0\lt a \leq 2$ og $0\lt b \leq2$.

Þegar við erum búin að flísaleggja rétthyrning með hliðarlengdir $2m$ og $2n$, þá höfum við lagt jafn margar hvítar og svartar flísar í hverja röð og flatarmál þeirra því jafnt. Við leggjum nú líka flísar á rétthyrninginn af breidd $b$ meðfram þeirri hlið svæðisins sem við höfum þegar lagt sem hefur lengdina $2m$. Við leggjum eina eða tvær raðir af flísum eftir því hvort $b \leq 1$ eða $b \gt 1$ og allar flísarnar í hvorri röð eru jafn stórar. Þar sem $2m$ er slétt tala, þá leggjum við jafn margar hvítar flísar og svartar í hvora röð og því samanlagt flatarmál hvítu flísanna jafnt samanlögðu flatarmáli þeirra svörtu.

Við förum eins að með rétthyrninginn af breidd $a$ meðfram hinni hlið svæðisins sem við byrjuðum á að leggja. Þá er aðeins eftir að leggja flísarnar í hornið sem á að líta út eins og einhver af myndunum fjórum hér til hliðar. Flatarmál hvítu og svörtu flísanna sem við höfum þegar lagt er jafnt svo flatarmál hvítu flísanna og þeirra svörtu í þessu horni þarf líka að vera jafnt. Við sýnum að svo getur ekki verið.

Greinilegt er að flatarmál svörtu og hvítu bútanna er ójafnt ef $0\lt a \leq 1$ eða $0\lt b \leq 1$. Ef $a \gt 1$ og $b \gt 1$ og við gefum okkur að flatarmál hvítu og svörtu skikanna sé jafnt, þá er $$ 1+(a-1)(b-1)=(a-1)+(b-1). $$ Þessi jafna jafngildir $$ 0=1-(a-1)-(b-1)+(a-1)(b-1)=(2-a)(2-b) $$ svo að annaðhvort er $a=2$ eða $b=2$. Höfum þá sýnt að önnur hliðarlengd gólfflatarins er heilt margfeldi af hliðarlengd flísanna og að fjöldi flísa meðfram þeirri hlið er jöfn tala.

Dæmi 1. Úrslitakeppni 1993-94

Fimmburarnir Ari, Bryndís, Davíð, Elín og Guðjón fæddust á klukkutíma fresti. Hver þeirra um sig veit hvar í röðinni hann fæddist. Guðjón veit líka að Elín fæddist tveimur tímum á undan Bryndísi. Guðjón segir: „Ef ég gef mér þá forsendu, sem mér finnst mjög trúleg, að Ari sé ekki elstur, þá veit ég í hvaða röð við fæddumst.Þessi ,,trúlega forsenda, sem Guðjón gaf sér, er reyndar alveg hárrétt. Í hvaða röð fæddust fimmburarnir?

Lausn

Táknum nöfn fimmburanna með upphafsstöfum þeirra. Við vitum að $A$ fæddist ekki fyrstur og að $B$ fæddist önnur á eftir $E$. Fyrst $G$ giskar á að $A$ fæddist ekki fyrstur, og $G$ veit hvar í röðinni hann sjálfur er, þá fæddist $G$ ekki heldur fyrstur.

Ef $G$ er annar í röðinni, þá samræmast báðar raðirnar $E,\, G,\, B,\, A,\, D$ og $E,\, G,\, B,\, D,\, A$ forsendunum hér að ofan. En gefið er að $G$ geti ákvarðað röðina ótvírætt út frá þessum forsendum svo að $G$ er ekki annar í röðinni.

Ef $G$ er þriðji, þá er nauðsynlega $E$ önnur og $B$ fjórða. Nú er $A$ ekki fyrstur svo hann er fimmti og þá nauðsynlega $D$ fyrstur. Röðin ákvarðast þá ótvírætt svo fimmburarnir fæddust í röðinni $D,\, E,\, G,\, B,\, A$.

Ef $G$ er fjórði, þá gætu fimmburarnir fæðst hvort heldur sem er í röðinni $E,\, A,\, B,\, G,\, D$ eða $E,\, D,\, B,\, G,\, A$ án þess að vera í mótsögn við forsendurnar hér að ofan. Það er í mótsögn við að $G$ geti ákvarðað röðina ótvírætt út frá þeim og því er $G$ ekki fjórði í röðinni.

Ef $G$ er fimmti, þá gætu fimmburarnir fæðst hvort heldur sem er í röðinni $E,\, A,\, B,\, D,\, G$ eða $E,\, D,\, B,\, A,\, G$ án þess að vera í mótsögn við forsendurnar hér að ofan. Það er enn í mótsögn við að $G$ geti ákvarðað röðina ótvírætt út frá þeim og því er $G$ ekki fimmti í röðinni.

Dæmi 2. Úrslitakeppni 1993-94

Sýnið að brotið $$ \frac{n^2+n-1}{n^2+2n} $$ sé fullstytt fyrir allar náttúrlegar tölur $n\gt 0$.

Lausn

Byrjum á að umrita brotið $$\frac{n^2+n-1}{n^2+2n}=\frac{(n+2)^2-3(n+2)+1}{n(n+2)}.$$ Hugsum okkur að $p$ sé frumtala sem gengur upp í nefnarann. Sýnum að hún geti ekki gengið upp í teljarann. Þar sem $p$ er frumtala sem gengur upp í $n(n+2)$, þá gengur $p$ annað hvort upp í $n$ eða $n+2$. Ef $p$ gengur upp í $n$, þá getur $p$ ekki gengið upp í $n^2+n-1=n(n+1)-1$ því þá gengi $p$ líka upp í $1$. Ef $p$ gengur upp í $n+2$, þá getur $p$ ekki gengið upp í $(n+2)^2-3(n+2)+1=(n+2)((n+2)-3)+1$ því þá gengi $p$ upp í $1$. Við höfum sýnt að útilokað er að nokkur frumtala gangi upp í bæði teljara og nefnara og því er brotið fullstytt fyrir allar náttúrlegar tölur $n$.

Dæmi 1. Úrslitakeppni 1992-93

Myndin sýnir tvo hringa í planinu og þrjá sameiginlega snertla þeirra. Punktarnir $G$ og $H$ eru skurðpunktar, en punktarnir $A$, $B$, $C$, $D$, $E$ og $F$ eru snertipunktar. Sýnið að strikin $GE$ og $FH$ eru jafnlöng.

Lausn

Lykillinn að lausn þessa dæmis er að ef við höfum punkt $P$ fyrir utan hring og drögum snertla við hringinn í gegnum $P$, þá eru strikin frá $P$ til snertipunktanna tveggja jafn löng. Þannig er til dæmis $|AG|=|GE|$. Ennfremur sjáum við að $|AB|=|CD|$. Þetta er bein afleiðing reglunnar hér að ofan ef línurnar $AB$ og $CD$ skerast en er einnig augljóst ef þær skerast ekki, því þá eru $AC$ og $BD$ miðstrengir í hringunum svo að $ABDC$ er rétthyrningur og því $|AB|=|CD|$. Nú fáum við að $$ \begin{aligned} |AB| &= |AG|+|GB|\\ &=|AG|+|GF|\\ &= |AG|+|GE|+|EF|\\ &= 2|GE|+|EF|. \end{aligned} $$ Á sama hátt fæst að $|CD|= 2|FH|+|EF|$. Þar sem $|AB|=|CD|$ fáum við þá að $|GE|=|FH|$.

Dæmi 2. Úrslitakeppni 1992-93

Gefnar eru sex fullyrðingar:

($\textbf{a}$) Allar fullyrðingarnar hér að neðan eru sannar.

($\textbf{b}$) Engin fullyrðinganna hér að neðan er sönn.

($\textbf{c}$) Allar fullyrðingarnar hér að ofan eru sannar.

($\textbf{d}$) Ein fullyrðinganna hér að ofan er sönn.

($\textbf{e}$) Engin fullyrðinganna hér að ofan er sönn.

($\textbf{f}$) Engin fullyrðinganna hér að ofan er sönn.

Hverjar fullyrðinganna eru sannar?

Lausn

Það sem við gerum er að vinna okkur niður listann og prófa hvort það sé mögulegt að viðkomandi fullyrðing sé sönn eða hvort við fáum mótsögn.

Byrjum á að athuga hvort (a) er sönn. Ef (a) væri sönn þá væri fullyrðing (e) líka sönn. En (e) segir að (a) sé ósönn, svo að (a) getur ekki verið sönn því að það leiðir til mótsagnar.

Gerum nú ráð fyrir að (b) sé sönn. Þá er (d) ekki sönn og neitun (d), sem er þá sönn, segir að engin fullyrðinganna fyrir ofan (d) sé sönn. Hér höfum við aftur mótsögn.

Við höfum sýnt að bæði (a) og (b) eru ósannar svo að (c) getur ekki heldur verið sönn.

Nú höfum við að engin fullyrðinganna (a), (b), (c) er sönn og því getur (d) ekki verið sönn.

Við höfum sýnt að engin fullyrðinganna (a), (b), (c), (d) er sönn, eða með öðrum orðum, við höfum sýnt að (e) er sönn.

Fullyrðing (f) segir sér í lagi að (e) sé ósönn svo að (f) er ósönn.

Niðurstaðan er þá að (e) er sönn en allar hinar fullyrðingarnar eru ósannar.

Dæmi 3. Úrslitakeppni 1992-93

Sýnið að $2^n$ gengur upp í $$(n+1)(n+2) \cdots (2 n)$$ fyrir allar náttúrulegar tölur $n$.

Lausn

Við skoðum tvær lausnir á þessu dæmi. Sú fyrri byggir á einföldu bragði en sú seinni notar þrepun.

Lausn 1: Skoðum sléttu tölurnar í margfeldinu sér og fáum tiltölulega auðveldlega að $$ \begin{aligned} (n+1)(n+2)\cdots(2n-1)(2n)&=\frac{(2n)!}{n!}\\ &= \frac{1\cdot2\cdot3\cdot4\cdots(2n-2)(2n-1)(2n)}{n!}\\ &=\frac{2\cdot 4\cdot 6\cdots (2n)\cdot 1\cdot 3\cdot 5\cdots (2n-1)}{n!}\\ &= \frac{2^nn!(1\cdot3\cdot5\cdots(2n-1))}{n!}\\ &= 2^n(1\cdot3\cdot5\cdots(2n-1)). \end{aligned} $$ En nú blasir við að $2^n$ gengur upp í $(n+1)(n+2)\cdots(2n)$.

Lausn 2: Hér er einfalt að beita þrepasönnun. Staðhæfingin er augljóslega rétt ef $n=1$. Gerum nú ráð fyrir að $n\gt 1$ og að niðurstaðan sé rétt fyrir $n-1$. Þá gengur $2^{n-1}$ upp í $n(n+1)\cdots(2(n-1))$. Tökum nú eftir að $$ \begin{aligned} &(n+1)(n+2)\cdots(2n-2)(2n-1)(2n)\\ =\;&2(2n-1)\big(n(n+1)(n+2)\cdots(2n-2)\big). \end{aligned} $$ Þar sem að $2^{n-1}$ gengur upp í $n(n+1)\cdots(2(n-1))$, þá fáum við að $2^n$ gengur upp í $(n+1)(n+2)\cdots(2n)$.

Dæmi 4. Úrslitakeppni 1992-93

Tiltekið leyndarmál felst í $n$ ólíkum staðreyndum. Í hópi $n$ manna veit hver sinn hluta af leyndarmálinu. Mennirnir skrifast á og í hverju bréfi upplýsir sendandi allt sem hann veit þá um leyndarmálið. Hver er minnsti fjöldi bréfa sem senda þarf þar til allir í hópnum þekkja alla hluta leyndarmálsins?

Lausn

Hægt er að komast af með að senda bara $2n-2$ bréf. Menn númer $1,2, \ldots,n-1$ senda allir bréf með sínum hluta leyndarmálsins til manns númer $n$. Þá hafa alls verið send $n-1$ bréf. Nú veit maður númer $n$ allt um leyndarmálið og getur sent öllum hinum þá hluta sem þeir vita ekki. Alls þarf maður númer $n$ þá að senda $n-1$ bréf og þá hafa alls verið send $2n-2$ bréf.

Nú sýnum við að ekki er hægt að komast af með færri bréf. Ef það eru fleiri en einn í hópi þeirra sem fyrstir fá að vita leyndarmálið, þá getum við hugsað okkur að einn þeirra opni póstinn sinn á undan öllum hinum og að hin bréfin séu ekki send fyrr en hann hafi opnað póstinn sinn. Þetta breytir augljóslega ekki fjölda bréfa sem eru send. Á þessum tímapunkti í bréfaskriftunum er því staðan sú að nákvæmlega einn mannanna veit allt um leyndarmálið. Til að sú staða komi upp þarf sérhver hinna að hafa sent frá sér sinn hluta af leyndarmálinu svo það hafa að minnsta kosti $n-1$ bréf verið send. Hina mennina vantar þá alla að minnsta kosti einn hluta svo hver þeirra þarf að fá að minnsta kosti eitt bréf í viðbót. Það á því eftir að senda að minnsta kosti $n-1$ bréf svo alls verða að minnsta kosti $2n-2$ bréf send.

Dæmi 5. Úrslitakeppni 1992-93

Gefnar eru rauntölur $x,y,z \gt 0$ þannig að $x+y+z = 1$. Sýnið að $$ \left(1 + {1 \over x}\right)\left(1 + {1 \over y}\right) \left(1 + {1 \over z}\right)\;\ge\;64. $$

Lausn

Hér er þægilegt að nota ójöfnuna um rúmfræðilegt og venjulegt meðaltal, en hún segir í því tilfelli sem við þurfum á að halda, að ef $a, b, c$ eru frekar jákvæðar rauntölur, þá er $$\frac{a+b+c}{3}\geq \sqrt[3]{abc},$$ og almennt að ef $a_1, a_2,\ldots,a_n$ eru frekar jákvæðar rauntölur, þá er $$\frac{a_1+a_2+\cdots+a_n}{n}\geq \sqrt[n]{a_1a_2\cdots a_n}.$$ Með aðstoð þessara ójöfnu getum við reiknað beint of augum og sannað niðurstöðuna $$ \begin{aligned} \left(1 + {1 \over x}\right)\left(1 + {1 \over y}\right) \left(1 + {1 \over z}\right) &=1+\frac{1}{x}+\frac{1}{y}+\frac{1}{z} +\frac{1}{xy}+\frac{1}{yz}+\frac{1}{zx}+\frac{1}{xyz}\\ &=1+\frac{xy+yz+xz}{xyz}+\frac{x+y+z}{xyz}+\frac{1}{xyz}\\ &\geq 1+\frac{3\sqrt[3]{x^2y^2z^2}}{xyz}+\frac{3\sqrt[3]{xyz}}{xyz}+\frac{1}{xyz}\\ &= 1+\frac{3}{\sqrt[3]{xyz}}+\frac{3}{\sqrt[3]{x^2y^2z^2}}+ \frac{1}{xyz}\\ &=\left(1+\frac{1}{\sqrt[3]{xyz}}\right)^3\\ &\geq \left(1+\frac{3}{x+y+z}\right)^3=64. \end{aligned} $$

Dæmi 6. Úrslitakeppni 1992-93

Fjarlægð milli mótlægra hliða í reglulegum áttflötungi er $d$. Hver er lengd kantanna? (Reglulegur áttflötungur hefur sex horn, átta hliðar og tólf kanta. Hliðarnar eru jafnstórir jafnhliða þríhyrningar. Myndirnar sýna reglulegan áttflötung, á annarri myndinni er hann gegnsær en á hinni ekki.)

Lausn

Við byrjum á að merkja horn áttflötungsins eins og sýnt er á myndinni. Þar sem áttflötungurinn er reglulegur fellur hann í sjálfan sig ef við tökum einhverja hlið í hvaða aðra hlið sem er. Af því leiðir að $ABFD$, $B C D E$ og $A C F E$ eru ferningar með hliðarlengdir $x$, að hornalínurnar $A F$, $B D$ og $C E$ skerast allar í sama punkti $M$, sem er jafnframt miðpunktur ferninganna, og hornalínurnar liggja annaðhvort í ferningunum eða eru hornréttar á þá. Látum $N$ vera miðpunkt $A B$.

Við höfum nú að $M N C$ er rétthyrndur þríhyrningur, lengd $M N$ er $x/2$ og lengd $M C$ er helmingur lengdar hornalínunnar í ferningnum $B C D E$ með hliðarlengd $x$ svo $|M C|=\sqrt{2}x/2$. Regla Pýþagorasar gefur því að $$|N C|=\sqrt{\left(\frac{x}{2}\right)^2 +\left(\frac{\sqrt{2}x}{2}\right)^2}=\frac{\sqrt{3}x}{2}.$$ Hæðin á hliðina $N C$ í þríhyrningnum $M N C$ er $d/2$ og með því að reikna út flatarmál $M N C$ á tvo mismunandi vegu fáum við jöfnuna $$ \frac{1}{2}\cdot\frac{x}{2}\cdot\frac{\sqrt{2}x}{2}=\frac{1}{2}\cdot |MN|\cdot|M C|=|M N C|=\frac{1}{2}\cdot|N C|\cdot h_M=\frac{1}{2}\cdot \frac{\sqrt{3}x}{2}\cdot \frac{d}{2}$$ og því er $x=\frac{\sqrt{3}}{\sqrt{2}}d$.

Stærðfræðikeppni framhaldsskólanema

Dæmi 5. Úrslitakeppni 1993-94

Dæmi 6. Úrslitakeppni 1993-94

Dæmi 1. Úrslitakeppni 1993-94

Dæmi 2. Úrslitakeppni 1993-94

Dæmi 1. Úrslitakeppni 1992-93

Dæmi 2. Úrslitakeppni 1992-93

Dæmi 3. Úrslitakeppni 1992-93

Dæmi 4. Úrslitakeppni 1992-93

Dæmi 5. Úrslitakeppni 1992-93

Dæmi 6. Úrslitakeppni 1992-93

Stærðfræðikeppni framhaldsskólanema

STAK