Talningarfræði

Dæmi 4. Úrslitakeppni 1996-97

Látum $x$ vera rauntölu. Sannið að um einhverja af tölunum $x,2x,\ldots, 99x$ gildir að munurinn á henni og einhverri heilli tölu er minni en $\frac{1}{100}$.

Lausn

Setjum $a_i=ix-[ix]$, fyrir $i=1,2,\ldots,99$. (Hér táknar $[x]$ stærstu heilu tölu sem er minni en eða jöfn $x$.) Við sjáum að $0\leq a_i\lt 1$ fyrir öll $i$. Skiptum nú bilinu $[0,1[$ í 100 bil, $s_1$ til $s_{100}$ þannig að $s_j=[\frac{j-1}{100}, \frac{j}{100}[$. Gerum nú ráð fyrir að tilgátan sem á að sanna sé röng og leiðum fram mótsögn. Nú er ekki til $i$ þannig að $0\leq a_i\leq \frac{1}{100}$ eða $\frac{99}{100}\leq a_i\lt 1$ því þá væri tilgátan sönn. Engin af tölunum $a_i$ lendir þá í $s_1$ eða $s_{100}$ og því skiptast þessar $99$ tölur niður á 98 bil ($s_2$ til $s_{99}$) og samkvæmt skúffureglu Dirichlets lenda einhverjar tvær tölur í sama bili. (Skúffuregla Dirichlets segir að ef við röðum hlutum í skúffur sem eru færri en hlutirnir, þá lendi a.m.k. tveir hlutir í einhverja skúffu.) Segjum að $a_i$ og $a_j$ lendi í sama bili og $i\lt j$. Þá er $|a_i-a_j|\lt \frac{1}{100}$. En $$|a_i-a_j|=|jx-[jx]-(ix-[ix])|=|(j-i)x-([jx]-[ix])|$$ svo að $$|(j-i)x-([jx]-[ix])| \lt \frac{1}{100}.$$ En þetta jafngildir því að munurinn á $(j-i)x$ og einhverri heiltölu (nefnilega $[jx]-[ix]$) er minni en $\frac{1}{100}$ og $(j-i)x$ er einmitt ein af tölunum $x, 2x,\ldots, 99x$, því $99\geq j\lt i\geq 1$.

Dæmi 18. Neðra stig 1996-97

Tölurnar frá $1$ upp í $999$, að báðum meðtöldum, eru skrifaðar á blað. Hver er summa allra tölustafanna?

Lausn

Summa tölustafanna breytist ekki þó við byrjum á $0$ í stað $1$ og bætum $0$-um fyrir framan eins og tveggja stafa tölur þannig að allar tölurnar séu þriggja stafa. Nú er ljóst að við höfum skrifað alla tölustafina $0,1,\ldots, 9$ jafn oft. Þar sem við höfum alls skrifað $3000$ tölustafi þá hefur hver verið skrifaður $300$ sinnum og summa þeirra allra því $$300\cdot(0+1+2+3+4+5+6+7+8+9)=300\cdot 45=13.500.$$

Dæmi 3. Úrslitakeppni 1995-96

Gefnar eru $52$ heiltölur. Sýnið að meðal þeirra séu tvær tölur, þannig að $100$ gangi annað hvort upp í summu eða mismun þeirra.

Lausn

Skrifum tölurnar $x_1,x_2,\ldots, x_{52}$ á 52 miða og stillum 51 skúffu upp fyrir framan okkur sem við númerum frá 0 og upp í 50. Látum $r_j$ vera afganginn þegar við deilum 100 í $x_j$. Þá er $0\leq r_j \leq 99$. Við setjum nú miðann með $x_j$ í skúffu $r_j$ ef $r_j\leq 50$ en í skúffu $100-r_j$ ef $r_j\gt 50$. Þá fer til dæmis $x_j$ í skúffu $50$ ef $r_j=50$ og í skúffu $49$ ef $r_j=49$ eða $r_j=51$.

Nú eru miðarnir $52$ talsins en skúffurnar aðeins $51$. Því hljóta tveir miðar að lenda í sömu skúffunni. Segjum að það séu miðarnir með tölunum $x_j$ og $x_k$. Ef $r_j=r_k$, þá gengur 100 upp í $x_j-x_k$ en ef $r_j\neq r_k$, þá er $r_j+r_k=100$ og því gengur 100 upp í $x_j+x_k$.

Dæmi 16. Neðra stig 1995-96

Ef við skrifum heilu tölurnar frá $1$ upp að $999$ (báðar meðtaldar) niður á blað, hvað höfum við þá skrifað tölustafinn $0$ oft?

Lausn

Byrjum á að skrifa tölurnar frá $0$ og upp í $999$ niður á blað. Ef talan hefur færri en $3$ tölustafi, þá skrifum við $0$ fyrir framan hana. Þannig skrifum við $007$ fyrir $7$ og $075$ í stað 75. Við höfum þá skrifað $1000$ tölur, þrjá tölustafi í hverri tölu og augljóslega höfum við skrifað hvern tölustafanna $10$ jafn oft. Við höfum því skrifað $3\cdot 1000/10=300$ núll. Núna strokum við út öll núll í upphafi talna þannig að í stað $027$ standi 27 o.s.frv. Þá standa eftir tölurnar frá $1$ og upp í $999$. Við höfum þá strokað $0$ úr hundruðasæti í tölunum $000$ til $099$, samtals $100$ stykki. Einnig strokuðum við út $10$ núll í tugasætunum í tölunum $00$ til $09$, samtals $10$ stykki. Að lokum strokuðum við einnig út töluna $0$. Þá höfum við strokað út $111$ núll og eftir eru $300-111=189$ núll.

Dæmi 20. Neðra stig 1994-95

Hver er summa allra þriggja stafa talna sem innihalda bara tölustafina $1, 3, 5, 7, 9$.

Lausn

Við ætlum að leggja saman allar tölur af gerðinni $$ x\cdot 100+y\cdot 10+z, $$ þar sem $x,y$ og $z$ eru oddatölur á bilinu $1$ til $9$. Í hverju sæti kemur hver talnanna $1,3,5,7$ og $9$ fyrir $25$ sinnum því þegar við höfum valið eina þeirra í eitt sætið, þá má velja tölur í hin sætin á $5\cdot5=25$ vegu. Því er summan $$ (1+3+5+7+9)\cdot 25\cdot(100+10+1)=25\cdot 25\cdot 111=69.375. $$

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. Efra stig 1993-94

Látum $Q$ vera mengið $$ Q = \{p/q\;|\; p,q\in {\mathbb{N}},\; 1\le p\le 10\;\text{og}\;1\le q\le 10\}. $$ Hversu mörg stök eru í Q? (Hér táknar $\mathbb{N}$ mengi náttúrlegra talna.)

Lausn

Hér virðist fátt annað til ráða en að skrifa öll stökin upp og telja þau svo. Í hverja línu í töflunni skrifum við aðeins þau stök sem ekki hafa þegar verið talin upp í línunum fyrir ofan.

$q$	Stök $Q$
$1$	$1,2,3,4,5,6,7,8,9,10$
$2$	$\frac{1}{2},\, \frac{3}{2},\, \frac{5}{2},\, \frac{7}{2},\, \frac{9}{2}$
$3$	$\frac{1}{3},\, \frac{2}{3},\, \frac{4}{3},\, \frac{5}{3},\, \frac{7}{3},\, \frac{8}{3},\, \frac{10}{3}$
$5$	$\frac{1}{5},\, \frac{2}{5},\, \frac{3}{5},\, \frac{4}{5},\, \frac{6}{5},\, \frac{7}{5},\, \frac{8}{5},\, \frac{9}{5}$
$7$	$\frac{1}{7},\, \frac{2}{7},\, \frac{3}{7},\, \frac{4}{7},\, \frac{5}{7},\, \frac{6}{7},\, \frac{8}{7},\, \frac{9}{7},\, \frac{10}{7}$
$4$	$\frac{1}{4},\, \frac{3}{4},\, \frac{5}{4},\, \frac{7}{4},\, \frac{9}{4}$
$8$	$\frac{1}{8},\, \frac{3}{8},\, \frac{5}{8},\, \frac{7}{8},\, \frac{9}{8}$
$9$	$\frac{1}{9},\, \frac{2}{9},\, \frac{4}{9},\, \frac{5}{9},\, \frac{7}{9},\, \frac{8}{9},\, \frac{10}{9}$
$6$	$\frac{1}{6},\, \frac{5}{6},\, \frac{7}{6}$
$10$	$\frac{1}{10},\, \frac{3}{10},\, \frac{7}{10},\, \frac{9}{10}$

Sjáum að þetta eru samtals $63$ stök.

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

Hver er stuðullinn við $x^{50}$ þegar margfaldað er upp úr $$ (1+x+x^{2}+\cdots+x^{100})(1+x+x^{2}+\cdots+x^{25})? $$

Lausn

Fyrir hvern lið í seinni sviganum fáum við $x^{50}$ nákvæmlega einu sinni þegar við margföldum hann inn í fyrri svigann. Það eru $26$ liðir í seinni sviganum svo stuðullinn við $x^{50}$ er $26$.

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

Á hraðskákmóti eru $13$ keppendur og teflir hver þeirra fjórum sinnum við sérhvern hinna. Þá er fjöldi skáka sem er tefldur jafn

Lausn

Lausn 1: Ef allir keppendur skrá allar sínar skákir, þá skráir hver þeirra $4\cdot 12$ skákir. Alls er þá skráðar $4\cdot12\cdot 13$ skákir á mótinu. En þar sem tveir tefla hverja skák, þá er hver skák skráð tvisvar og fjöldi þeirra því $\frac12\cdot4\cdot 12\cdot 13=312$.

Lausn 2: Röðum keppendunum upp í einfalda röð. Sá fyrsti í röðinni teflir fjórum sinnum við hvern hinna keppendanna svo þar eru $4\cdot 12$ skákir. Þær skákir sem eru enn ótaldar og annar keppandinn í röðinni teflir eru þær sem hann teflir við þá sem eru fyrir aftan hann í röðinni. Þær eru $4\cdot 11$ talsins. Þannig göngum við eftir röðinni, ótaldar skákir sem sá þriðji teflir eru $4\cdot 10$ og svo framvegis. Ótöldu skákirnar sem sá næst síðasti teflir eru þá $4$ og allar skákirnar hafa verið taldar þegar við komum að þeim seinasta. Alls eru þá tefldar $$ 4\cdot (12+11+10+\cdots+1)=4\cdot \frac{(12+1)12}{2}=24\cdot 13=312$$ skákir á mótinu.

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

Reipi er skorið í tvennt á stað, sem er valinn af handahófi. Hver eru líkindi þess, að lengri búturinn sé að minnsta kosti tvöfalt lengri en sá styttri?

Lausn

Merkjum tvo staði á reipinu þannig að hver partur sé einn þriðji af lengd þess. Þegar við skerum reipið, þá er lengri endinn að minnsta kosti tvöfalt lengri en sá styttri þá og því aðeins að reipið sé ekki skorið á miðpartinum. Við megum því skera reipið hvar sem er á $\frac{2}{3}$ hluta þess. Líkindin eru því $\frac{2}{3}$.

Stærðfræðikeppni framhaldsskólanema

Dæmi 4. Úrslitakeppni 1996-97

Dæmi 18. Neðra stig 1996-97

Dæmi 3. Úrslitakeppni 1995-96

Dæmi 16. Neðra stig 1995-96

Dæmi 20. Neðra stig 1994-95

Dæmi 5. Úrslitakeppni 1993-94

Dæmi 6. Efra stig 1993-94

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

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

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

Stærðfræðikeppni framhaldsskólanema

STAK