Kirjevalmennus, maalis-/huhtikuu 2017
Ratkaisuita toivotaan huhtikuun loppuun mennessä postitse osoitteeseen Jouni Seppänen
Ahmatie 8 A 3 00800 Helsinki
tai sähköpostitse osoitteeseen jks@iki.fi.
Helpompia tehtäviä
1.
Taululle on kirjoitettu luvut1,2, . . . ,2017. Yhdellä askelella jotkin kaksi lu- kua pyyhitään ja tilalle kirjoitetaan niiden summa. Onko näitä askelia toista- malla mahdollista saada taululle luvut, jotka kaikki ovat jaollisia luvulla7?2.
Olkoonf(x)kokonaislukukertoiminen polynomi. Tiedetään, ettäf(20) = 14 jaf(19) = 15. Onko olemassa kokonaislukun, jollef(n)on jaollinen luvulla210?3.
Suorakulmaisen särmiön sivujen pituudet ovat positiivisia kokonaislukuja.Oletetaan, että suorakulmaisen särmiön tilavuus on (mittayksiköitä huomioi- matta) yhtä suuri kuin sen pinta-ala (tahkojen yhteenlaskettu ala). Osoita, ettei särmiön minkään sivun pituus voi olla14.
4.
Olkoon f(x) kokonaislukukertoiminen polynomi. Osoita, että on olemassa enintään yksi alkulukupari(p, q), jolle(f(p2)−f(6q2))(p2+q2−12)on alkuluku.5.
Olkoot n > 1 kokonaisluku ja p alkuluku. Osoita, että jos n | (p−1) ja p| n3−1, niin4p−3on neliöluku.
6.
Etsi kaikki alkuluvutp, joilla yhtälöparilla (p+ 1 = 2m2p2+ 1 = 2n2 on kokonaislukuratkaisu(m, n).
7.
Binomikertoimeksi kutsutaan lukua nk, joka kertoo, monellako tavallan:n alkion perusjoukosta voidaan valitak:n alkion osajoukko. Nimitys tulee binomin potenssin kaavasta
(a+b)n = n
0
an+ n
1
an−1b+ n
2
an−2b2+· · ·+ n
n
bn.
Binomikertoimelle on algebrallinen kaava nk
=k!(n−k)!n! .
Todista seuraavat binomikerroinkaavat, mieluummin kombinatorisella argu- mentilla (bijektioilla tai laskemalla sama joukko kahdella eri tavalla) kuin bino- mikertoimen algebrallisen kaavan avulla.
(a) n
k
= n k
n−1 k−1
, (c)
n
X
i=0
n i
n n−i
= 2n
n
, (b)
n k
k p
= n
p
n−p k−p
, (d) n
0
+ n
2
+· · ·= n
1
+ n
3
+· · ·.
8.
Kuinka monta erilaista tapaa on värittää neliön jokainen sivu eri värillä, kun väritykset lasketaan samanlaisiksi, jos ne saadaan kääntämällä neliötä tasossa?(Peilaaminen vaatii neliön kääntämistä tason ulkopuolisen avaruuden kautta, joten sellaiset väritykset ovat keskenään erilaisia, jotka saadaan toisistaan ai- noastaan peilaamalla eikä tason käännöllä.)
9.
Kuinka monta tapaa on värittää kuution jokainen tahko eri värillä, kun kuu- tiota avaruudessa kääntelemällä saadut väritykset ovat keskenään samanlaisia?Vaativampia tehtäviä
10.
Monellako tavalla voi laatoittaa 2×n-suorakulmion2×2-neliöillä ja L:n muotoisilla kolmen ruudun palasilla?11.
Monellako tavalla voi laatoittaa 4×n-suorakulmion3×1-laatoilla?12.
Monellako tavalla voi täyttää2×2×n-laatikon1×1×2-tiiliskivillä? Todista myös, että josnon parillinen, tapojen määrä on neliöluku.13.
Fibonaccin luvut määritellään alkuehdoilla F0 = 0 ja F1= 1 sekä palau- tuskaavallaFn+2=Fn+1+Fn. Todista, että(a) Fn−12 +Fn2=F2n−1, (b) Fn2+ 2Fn−1Fn=F2n,
(c) Fn(Fn+1+Fn−1) =F2n.
14.
Joukon permutaatio on sen bijektio itselleen eli tapa järjestää sen alkiot.Kaikkiaann-alkioisella joukolla onn! = 1·2·3·. . .·npermutaatiota. Montako sel- laista joukon{1,2,3, . . . , n} permutaatiotapon, joille|p(i)−i| ≤2kaikilla i?
Vastaukseksi riittää antaa alkuehdot ja palautuskaava joka esittää permutaa- tioiden lukumääränf(n)lukujenf(n−1), f(n−2), . . . , f(n−k)avulla jollakin vakiollak. Suljettua muotoa ei tarvitse ratkaista.
15.
Olkoot a, b ja c positiivisia reaalilukuja ja n positiivinen kokonaisluku.Osoita, että
an
b+c + bn
c+a+ cn
a+b > an−1+bn−1+cn−1
2 .
16.
Pöydällä on 101 kolikkoa klaava ylöspäin. Voimme valita mitkä tahansa neljä kolikkoa ja kääntää ne kaikki toisin päin. Onko tätä operaatiota toistamalla mahdollista kääntää pöydän kolikoita niin, että lopuksi niissä on kaikissa kruuna ylöspäin?17.
Tasossa on annettu n pistettä jan suoraa, joista mitkään kaksi eivät ole yhdensuuntaisia. Onko mahdollista nimetä pisteet luvuilla1,2, . . . ,nja suorat samoin luvuilla1,2, . . . ,nsiten, että kun piirretään kullakin luvuniarvolla1, 2, . . . ,njana pisteestäikohtisuoraan suoralleisaakka, mitkään kaksi näistän janasta eivät leikkaa toisiaan?18.
Todista, että kaikilla positiivisilla kokonaisluvuillakon olemassakperäk- käistä kokonaislukua, joilla on kaikilla vähintään10100 tekijää.19.
Tutkitaan monikulmioita, joiden kärkipisteet ovat tason hilapisteissä, eli pisteissä, joiden molemmat koordinaatit ovat kokonaislukuja. Olkoot ajab po- sitiivisia kokonaislukuja. Jos n-kulmion P kärkien koordinaatit ovat (x1, y1), (x2, y2), . . . ,(xn, yn), sanotaan, ettäP on(a, b)-monikulmio, jos päteea= max
1≤i≤nxi− min
1≤i≤nxi ja b= max
1≤i≤nyi− min
1≤i≤nyi, eli monikulmio mahtuu juuri ja juuri johonkina×b-suorakulmioon.
Olkoot a, b > 1. Todista, että on olemassa (a, b)-monikulmio, jonka ala on korkeintaanp
2 max(a, b).
20.
Matilla onn+ 1korttia, jotka on numeroitu luvuilla0,1,2, . . . , n−1jan.Kortit 1,2, . . . jan ovat sekaisin pakassa. Matti haluaa järjestää kortit seuraa- valla tavalla:
(i) Ensin Matti laittaa kortin numero0 pakan pohjalle.
(ii) Sitten Matti toistaa seuraavaa ”siirtoa”: jos pakan päällimmäinen kortti on numeroltaank, hän siirtää kortin paikallek+1. Tällöinkseuraavaa korttia siirtyvät pakassa yhden askeleen ylemmäs. Muiden korttien järjestys ei tässä siirrossa muutu.
(iii) Jos pakan päällimmäinen kortti on kortti numeroltaan0, Matti lopettaa.
Jos siis esimerkiksi korttipakka olisi alussa järjestyksessä (2,4,1,3,0), missä2 ja 0 ovat päällimmäinen ja alimmainen kortti, vastaavasti, ensin Matti siirtää päällimmäisen kortin2kolmanneksi, eli järjestys on(4,1,2,3,0), ja seuraavaksi Matti siirtää kortin numero 4viimeiseksi, ja järjestys on(1,2,3,0,4).
Todista, että riippumatta pakan alkuperäisestä järjestyksestä, ennen pitkää kortti 0 on päällimäisenä, ja Matti voi lopettaa järjestämisen. Todista lisäksi, että tällöin kortit ovat järjestyksessä (0,1,2, . . . , n). Olkoon lisäksif(n)pienin positiivinen kokonaislukuk, jolle minkä tahansa korttien0,1, . . . , nsekoituksen järjestäminen kestää korkeintaanksiirtoa. Määritäf(n).
