Toukokuun valmennustehtävien ratkaisut
1. Ratkaisu 1. Koska(m, n) = 1((m, n)tarkoittaa suurinta yhteistä tekijää), niin myös(2m−1,2n−1) = 1 tunnetun kaavan(2m−1,2n−1) = 2(m,n)−1nojalla (tämän kaavan voi todistaa induktiollam+nsuhteen).
Siispä2m−1 =mk ja2n−1 =nk. Erityisestim|2m−1. Oletetaan, ettäm >1, ja olkoonpluvunmpienin alkutekijä. Tällöin2m≡1 (modp), mistä tunnetusti seuraam|p−1. Täten 1< m≤p−1, joten luvulla mon jokin alkutekijä, joka on pienempi kuinp; ristiriita. Näin ollenm= 1, ja samalla tavallan= 1. Tällöin kolmikot(m, n, k) = (1,1, k)selvästi kelpaavat.
Ratkaisu 2. Kuten edellä, päädytään yhtälöön 2m = mk + 1. Jos k on parillinen, niin saadaan yhtälö muotoa 2m = x2+ 1, ja koska 4 ei jaa x2+ 1, on oltava m = 1. Jos k on pariton, voidaan kirjoittaa mk+ 1 = (m+ 1)(mk−1−mk−2+...−m+ 1), joten molemmat tulontekijät ovat kakkosen potensseja. Ol- koonm+ 1 = 2a. Tällöinm≡ −1 (mod 2a), jotenmk−1−mk−2+...−m+ 1≡k (mod 2a). Kuitenkin jos m≥2, k≥2,niinmk−1−mk−2+...−m+ 1≥m2−m+ 1≥m+ 1, joten2a jakaa kyseisen luvun. Tämä tarkoittaak≡0 (mod 2a), jotenk≥m+ 1. Tällöin saadaan2m≥mm+1+ 1, mikä on selvästi mahdotonta.
On siis oltavak= 1tai m= 1. Jos k= 1, niin 2m−1 =m, ja tästä saadaan helposti m= 1. Siispäm= 1, ja samoinn= 1, joten saadaan ratkaisut(1,1, k).
2. (a) Ratkaisu. Merkitään symbolilla Ω(n) luvun n alkutekijiden määrää moninkerrat mukaan laskien.
Selvästi Ω(mn) = Ω(m) + Ω(n), jotenΩ(P(x))on parillinen jos ja vain jos Ω(x+a)≡Ω(x+b) (mod 2). Tarkastellaan jonoja(Ω(n+ 1),Ω(n+ 2), ...,Ω(n+ 2014))modulo2(eli jokainen koordinaatti otataan modulo 2). Eri jonoja on 22014 ja jonoja yhteensä on äärettömän monta, joten löytyy kaksi eri lukua a jab, joille Ω(a+j)≡Ω(b+j) (mod 2)kaikillaj= 1, ...,2014. Tämä tarkoittaakin, ettäΩ((x+a)(x+b))on parillinen, kunx= 1, ...,2014.
(b) Ratkaisu. Oletetaan, ettäΩ(P(n))on parillinen kaikillan∈Z+ja ettäd=b−a >0. TällöinΩ(n(n+d)) on parillinen kaikilla n > a. Erityisesti valitsemallan =kd, k ∈Z+, saadaan Ω(k(k+ 1)d2)≡0 (mod 2) kaikilla riittävän suurilla k. Siten Ω(k)≡Ω(k+ 1) (mod 2) kaikilla riittävän suurilla k. Tämä tarkoittaisi, että Ω(k) (mod 2) olisi vakio suurilla k, mutta tämä on mahdotonta, koska Ω(2k) = 1 + Ω(k) kaikilla k. Siispä väite on todistettu.
3. Ratkaisu. Valintam=n= 1antaa f(1)2+f(1)|4, jotenf(1) = 1. Valitaan sitten m= 1, n=p−1, missäpon alkuluku. Saadaanf(p−1)+1|p2elif(p−1) =p−1taif(p−1) =p2−1. Jälkimmäisessä tapauk- sessa saadaanf(p−1)2+ 1|(1 + (p−1)2)2, mikä on mahdotonta, koska(p2−1)2+ 1>(1 + (p−1))2. Siispä f(p−1) =p−1. Olkoonnmielivaltainen. Päteef(n)+(p−1)2|(n+(p−1)2)2, jotenf(n)+(p−1)2|(n−f(n))2, koskan−f(n)≡f(n) + (p−1)2 (mod f(n) + (p−1)2). Kuitenkin jospon riittävän suuri alkuluku, saadaan ristiriita, elleif(n) =n. Sitenf(n) =nkaikilla n, ja tämä kelpaa.
4. Ratkaisu. Oletetaan, ettei mikään epäyhtälöistä päde. Tällöin|ab−c|2+|bc−a|2+|ca−b|2+ 6abc≥36. Toisaalta vasen puoli ona2b2+b2c2+c2a2+a2+b2+c2, jotena2b2+b2c2+c2a2+a2+b2+c2≥36. Suuruus- järjestysepäyhtälön ja aritmeettis-kvadraattisen epäyhtälön nojalla seuraaa4+b4+c4+ 3
qa4+b4+c4
3 ≥36.
Oletettiin a4+b4+c4 = 27, joten saatiin yhtälö 36 ≥36. Siten yhtäsuuruuden on pädettävä käytetyissä epäyhtälöissä. Aritmeettis-kvadraattisessa epäyhtälössä pätee yhtäsuuruus jos ja vain jos muuttujat ovat yh- tä suuret, eli a2 =b2 =c2. Tämä tarkoittaa a2=b2 =c2 = 3, mutta toisaalta on oltava(abc)2= 94, mikä
1
on ristiriita.
5. Ratkaisu. Oletetaan, että tällainenfolisi olemassa. Tällöin valintan=f(m)antaaf(m+2013) =f(m)+
2013, ja induktiollaf(2013m+r) = 2013m+f(r), kunr= 0,1, ...,2012.Merkitään vieläf(r) = 2013k+`, 0≤`≤2012. Nytr+ 2013 =f(f(r)) =f(2013k+`) = 2013k+f(`). Josk≥2, vasen puoli on suurempi, eli ristiriita. Josk= 0, niinr+ 2013 =f(`)jaf(r) =`. Jos taask= 1, niinr=f(`)jaf(r) =`+ 2013. Lisäksi r6=`. Nyt luvut{1,2, ...,2013} jakautuvat pareihin(a, b), joille f(a) =bjaf(b) =a+ 2013tai f(b) =aja f(a) =b+ 2013. Jokainen jäsen esiintyy täsmälleen yhdessä parissa. koska jos olisi parit(a, b)ja(a, c), niin b =f(a) =c,ja samoin ei voi olla pareja (a, b) ja(a0, b). Kuitenkin lukuja 1,2, ...,2013 on pariton määrä;
ristiriita.
6. Ratkaisu. Tehtävässä pitäisi olla maksimi minimin sijasta. Havaitaan, että jos vain yhdellä yhtälöistä f(x) =s, s∈S,on kokonaislukuratkaisu, niin saadaan ylärajadeg(f)ratkaisujen määrälle. Oletetaan sitten, että ratkaisuja on ainakin kahdella eri s1, s2 ∈S. Voidaan lisäksi olettaa, että s1 on se S:n alkio, joilla on eninten vastaavia kokonaislukuratkaisuja. Olkoon yhtälöilläf(x) =s1, f(x) =s2kokonaislukuratkaisujakja
`kappaletta vastaavasti. Tällöinf(x) = (x−x1)...(x−xk)Q(x) +s1= (x−y1)..(x−y`)R(x) +s2joillakin ko- konaisluvuillaxijayija polynomeillaQ, R∈Z[x]. Nyt erityisestis2=f(y1) = (y1−x1)...(y1−xk)Q(y1)+s1, jotens2−s1= (y1−x1)...(y1−xk)Q(y1).Koska luvutxi ovat pareittain erisuuria, pätee|y1−xi| ≥2paitsi korkeintaan kahdellai. Sitens2−s1≥2k−2. OlkoonaS joukonSlukujen suurin mahdollinen erotus. Saatiin 4aS ≥ 2k, joten k ≤log2(4aS). Luvun k maksimaalisuuden nojalla relaatiollaf(x)∈ S on enintään k|S|
ratkaisua. Ratkaisuja on siis enintäänlog2(4aS)|S|, ja tämä on haluttu vakioCS.
7. Ratkaisu. Olkoonn alkusi parillinen. Joukko{1,2, ..., n} voidaan osittaa n2 osajoukoksi, joilla on sama summa: muodostetaan parit{1, n},{2, n−1}, ...,{n2,n2+ 1}.Tämä on suurin mahdollinen määrä osajoukko- ja. Nimittäin jokaisen osajoukon (mahdollisesti yhtä poikkeusta lukuun ottamatta) pitää sisältää vähintään kaksi lukua, sillä joukon, joka sisältää luvun n, summa on vähintäänn. Poikkeustapauksessa {n} on eräs joukoista, joten joukkoja voi silloinkin muodostaa korkeintaan1 +n−1
2
= n2.
Olkoon nytnpariton. Osituksessa{n},{1, n−1},{2, n−2}, ...,{n−12 ,n+12 }on n+12 joukkoa, joista kullakin on sama summa. Enempää joukkoja ei voi muodostaa, koska jälleen jokainen joukko, paitsi mahdollisesti yksi, sisältää ainakin kaksi alkiota. Vastaus on siisn+1
2
molemmissa tapauksissa.
8. (a) Ratkaisu.Tulkitaan pöydän kortit binäärilukuna vasemmalta oikealle. Jokainen kultainen kortti vas- taa ykköstä ja musta kortti nollaa. Alussa pöydällä on luku11...1 (2009 ykköstä). Jokaisella askeleella luku pienenee, joten peli päättyy enintään22009siirrossa.
(b) Ratkaisu. Jälkimmäinen pelaaja voittaa aina. Sanotaan, että kortti on erityinen, jos sen järjestysluku on10,60,110, ...,1960. Erityisiä kortteja on 40. Jokaisella siirrolla täsmälleen yksi erityinen kortti muuttaa väriään. Alussa kultaisia erityisiä kortteja on40, joten jokaisen ensimmäisen pelaajan siirron jälkeen kultai- sia erityisiä on pariton määrä. Tämä tarkoittaa, että jälkimmäisellä pelaajalla on aina jäljellä jokin sallittu siirto, joten hän ei voi hävitä (kultaisen erityisen kortin voi kääntää, koska erityiset kortit eivät ole50 vii- meisen joukossa). Koska peli päättyy, jälkimminen pelaaja voittaa.
9. Ratkaisu. Oletetaan vastaväite. Tällöin luvutS(a) (modn!), missäa on joukon{1,2, ..., n} permutaa- tio, ovat kaikki eri lukuja. Koska permutaatiota onn!, tämä tarkoittaa, että S(a) (modn!)saa kaikki arvot 0,1, ..., n!−1 tasan kerran. SiispäP
aS(a)≡0 + 1 +...+ (n!−1) = (n!−1)(n!)2 (modn!). Toisaalta permu- taatioita, joilleaj saa tietyn arvon, on(n−1)!, joten
X
a
S(a) =X
a n
X
j=1
cjaj=
n
X
j=1
(n−1)!(cj·1 +...+cj·n) = (n−1)!(c1+...+cn)·n(n+ 1)
2 .
Koskan >1on pariton, luku(n−1)!(c1+...+cn)·n(n+1)2 on jaollinen luvullan!. Kuitenkin luku (n!−1)(n!)2
2
ei ole jaollinen luvullan!, mikä on ristiriita, koska tulosten piti olla samat (mod n!).
10. Ratkaisu. Tällaista kolmiota ei ole. Jos tällaisella kolmiolla olisi sivuta, b, cja piirin puolikasp= a+b+c2 , niin Heronin kaavalla
p(p−a)(p−b)(p−c) = 20142= 22·192·532.
Jos pei ole kokonaisluku, eli se on muotoa m2 jollakin parittomalla m, niin alan neliö ei myöskään ole ko- konaisluku. Siispä p on kokonaisluku. Koska p−a+p−b+p−c = p, niin päädytään yhtälöön muotoa xyz(x+y+z) = 22·192·532, missäx≥y≥zovat positiivisia kokonaislukuja. Käymällä läpi eri vaihtoehdot luvuillex, yjaznähdään, ettei tällaista kolmiota ole.
11. Ratkaisu. Olkoot F ja G janojen AB ja CD keskipisteet ja olkoon P samalla puolella janaa F G kuin B ja C. Pätee P F ⊥ AB, P G ⊥ CD ja ∠F EB = ∠ABE,∠GEC = ∠DCE. Tästä saadaan
∠F P G=∠F EG= 90◦+∠ABE+∠DCE. Koska kolmioidenABP jaCDP alat ovatF E·F P jaGE·GP, väite on F EEG = GPP F. Tämä taas on yhtäpitävää EF G ∼P GF kanssa, ja tämä tarkoittaa, että EF P G on suunnikas. Tämä puolestaan tarkoittaa∠EF P =∠EGP eli∠ABE =∠DCE, ja tämä on yhtäpitävää sen kanssa, ettäABCD on jännenelikulmio.
12. Ratkaisu. Merkitään AC =a, CE =b, EA=c. Ptolemaioksen epäyhtälölläa·EF+b·AF ≥c·CF.
Koska EF = AF, saadaan AFCF ≥ a+bc . Symmetrian nojalla saadaan kaksi vastaavaa epäyhtälöä lisää, ja laskemalla ne yhteen seuraa
BC BE +DE
AD +AF CF ≥ a
b+c + b
b+c + c c+a.
Nyt väite seuraa suoraan Nesbittin epäyhtälöstä, ja jos yhtäsuuruus pätee, niina=b=c,jotenABCDEF on säännöllinen kuusikulmio, ja tällöin yhtäsuuruus selvästi pätee.
3
