Úrslitakeppni | stæ.is

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 3. Úrslitakeppni 1993-94

Gefið er strik $A B$, hringur með miðju $A$ sem liggur gegnum $B$ og annar hringur með miðju $B$ sem liggur gegnum $A$. Ferningurinn $C D E F$ hefur tvo hornpunkta sína á strikinu $AB$ og hina tvo hvorn á sínum hringnum, eins og myndin sýnir. Reiknið hliðarlengd hans ef lengd $|A B|=1$.

Lausn

Táknum hliðarlengd ferningsins með $x$. Lítum á rétthyrnda þríhyrninginn $B C F$. Við höfum að $|B C|=x+\frac{1}{2}(1-x)=\frac{1}{2}(1+x)$, $|C F|=x$ og $|F B|=1$. Regla Pýþagorasar gefur þá að $$\frac{1}{4}(x+1)^2+x^2=1$$ og því er $5x^2+2x-3=0$. En $5x^2+2x-3=(5x-3)(x+1)$ svo að $x=\frac{3}{5}$ því $x \gt 0$.

Dæmi 4. Úrslitakeppni 1993-94

Finnið allar margliður $x^3+a x^2+b x+c$ þannig að $a$, $b$ og $c$ séu heilar tölur og þær séu jafnframt rætur margliðunnar.

Lausn

Ef $a$, $b$ og $c$ eru rætur $x^3+ax^2+bx+c$, þá er \begin{align} x^3+a x^2+b x+c&=(x-a)(x-b)(x-c)\\ &=x^3-(a+b+c)x^2+(a b+b c+c a)x-a b c \end{align} og því \[a=-a-b-c,\quad\quad b=a b+b c+c a,\quad\quad c=-a b c.\] Ef $c\neq 0$, þá gefur seinasta jafnan að $ab=-1$ og því er $a=1$ og $b=-1$ eða $a=-1$ og $b=1$. Í fyrra tilfellinu gefur fyrsta jafnan að $c=-2a-b=-1$ og þá er $a b+b c+c a=-1+1-1=-1=b$ svo annarri jöfnunni er líka fullnægt. Í seinna tilfellinu gefur fyrsta jafnan að $c=-2a-b=1$ en þá er $a b+b c+c a=-1-1+1=-1\neq b$ svo önnur jafnan gildir ekki.

Ef hinsvegar $c=0$, þá verða fyrstu tvær jöfnurnar að $2 a+b=0$ og $b=ab$. Ef $b\neq 0$, þá gefur seinni jafnan að $a=1$ og sú fyrri að $b=-2$. Ef hinsvegar $b=0$, þá gefur fyrri jafnan að $a=0$.

Höfum þá að $(a,b,c)=(0,0,0)$, $(a,b,c)=(1,-2,0)$ eða $(a,b,c)=(1,-1,-1)$.

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 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$.