Epäviralliset viikkokisat

Ollin viikkokisojen inspiroimina monet ovat alkaneet pitää omia viikkokisojaan. Tässä on kaikki tähänastiset epäviralliset viikkokisat: IMOMO, IMOMOMO, FINEST, IMODIUM.

Ratkaisut postataan ensi viikolla lyhytlistoineen.

(HUOMIO: Orion Pharma, Kansainvälinen Merenkulkujärjestö ja IMOMO- Sushi House eivät ole tekemissä kilpailujen kanssa.)

2 tykkäystä

Pahoittelut ratkaisujen myöhästymisestä. Ratkaisut ja joidenkin kisojen lyhytlistat löytyvät tästä:
IMOMO (Lyhytlistalla), IMOMOMO (Lyhytlistalla), FINEST (Lyhytlistalla), IMODIUM.

Tämän viikon kisa on POG-geometriakisa, jonka ratkasut postataan tämän viikon lauantaina.

IMOMO-kilpailun tehtävässä 3 pyydettiin löytämään kaikki n, joilla n/d(n) on alkuluku. Tässä on ajatuksia koskien tehtävää.

Pätee siis n = d(n)p jollain alkuluvulla p. Olkoon p^ap_1^{a_1} \cdots p_k^{a_k} luvun n alkutekijähajotelma. Pätee siis

p^{a-1}p_1^{a_1} \cdots p_k^{a_k} \ge (a + 1)(a_1 + 1) \cdots (a_k + 1).

Intuitiivisesti yhtälön vasen puoli on suurempi kuin oikea puoli paitsi hyvin pienessä määrässä tapauksia. Idean tarkka toteuttaminen ei ole aivan helppoa. Yksi tapa on käyttää Bernoullin epäyhtälöä. Bernoullin epäyhtälön todistaminen yleisessä tapauksessa ei ole triviaalia, mutta tässä tapauksessa nähdään, että binomilauseella saadaan suoraan
p^a = (1 + (p-1))^a \ge 1 + a(p-1)
kaikille alkuluvuille p ja kokonaislukueksponenteille a \ge 1. Tämä alaraja on tehtävää varten hyvä, koska se kasvaa lineaarisesti sekä a:n että p:n suhteen. Lisäksi termejä muotoa 1 + a(p-1) on helppo verrata tekijöiden määrän kaavan termeihin muotoa 1 + a.

Bernoullin epäyhtälön soveltamisen jälkeen tehtävä on varsin suoraviivainen. Eri tapauksia pitää toki käydä jonkin verran läpi, koska n:n paikalle käy melko suuri määrä lukuja. Vaikeaa tämä ei kuitenkaan ole.

Lisäharjoitusta kaipaava voi ratkoa vuoden 2000 IMO-lyhytlistan tehtävän, jossa pyydetään ratkaisemaan yhtälö 4n = d(n)^3.

Kirjoitan myöhemmin lisää kommentteja koskien kisojen tehtäviä.

FINEST-kilpailun tehtävässä 3 tutkitaan Pythagoraan kolmikoita. Tavoitteena on todistaa, että mille tahansa kahdelle kolmikolle (a, b, c) ja (A, B, C) on olemassa ketju kolmikoita, joka alkaa kolmikosta (a, b, c), päättyy kolmikkoon (A, B, C) ja jossa ketjun kahdella peräkkäisellä kolmikolla on aina yksi yhteinen alkio.

Tämä tehtävä oli mielestäni aikas vaikea. Vaikeutta tuo se, että toisaalta tehtävässä on paljon kaikenlaista kokeiltavaa, toisaalta taas on vaikea keksiä mitään oikeasti hyödyllistä. Alla esitetty ratkaisu on oleellisesti ottaen sama kuin lyhytlistalla oleva malliratkaisu.

Tehtävää ratkoessa on tietysti hyvä tietää seuraava, yleisesti tunnettu karakterisaatio Pythagoraan kolmikoille: Olkoot a, b ja c kokonaislukuja, joilla a^2 + b^2 = c^2. Tällöin on olemassa kokonaisluvut k, x ja y siten, että (x, y) = 1, tasan yksi luvuista x ja y on parillinen, ja a = k(x^2 - y^2), b = 2kxy, c = k(x^2 + y^2).

(Todistuksen idea: k vastaa syttiä syt(a, b, c). Sievennetään se pois, ja tutkitaan yhtälöä a^2 + b^2 = c^2, kun syt(a, b, c) = 1. Tarkastelu modulo 4 antaa, että tasan yksi luvuista a ja b on parillinen. Olkoon b parillinen. Kirjoitetaan yhtälö muodossa b^2 = (c-a)(c+a). Oikean puolen tekijöiden syt jakaa 2a:n. Nähdään siis, että syt on tasan 2. Kirjoitetaan c-a = 2y^2, c+a = 2x^2.)

Pyörittelin joitain erikoistapauksia jonkin aikaa, kunnes huomasin seuraavan tuloksen: mistä tahansa kolmikosta (a, b, c) pääsee johonkin kolmikkoon muotoa (3n, 4n, 5n). Päädyin tähän miettimällä, miten kolmikoiden karakterisaation luvun k vaihteleminen vaikuttaa itse kolmikkoon. Todistus onkin varsin suoraviivainen. Kirjoitetaan karakterisaation mukaisesti a = k(x^2 - y^2), b = 2kxy, c = k(x^2 + y^2). Nyt tasan yksi luvuista x ja y on parillinen. Tutkitaan nyt kolmikkoa A = \frac{kxy}{2}(2^2 - 1^2), B = 2 \cdot \frac{kxy}{2} \cdot 2 \cdot 1, C = \frac{kxy}{2}(2^2 + 1²). Tämä on Pythagoraan kolmikko, jossa b = B ja joka on muotoa (3n, 4n, 5n). Tulos on täten todistettu.

Käytin seuraavaksi melko paljon aikaa tutkimalla, mihin kaikkiin kolmikkoihin muotoa (3n, 4n, 5n) pääsee kolmikosta (3, 4, 5). En tehnyt tähän liittyen mitään fiksua - piirtelin vain kuvia, jossa kuvataan kolmikoiden ja ketjujen muodostama verkkorakenne. Samalla yritin tietysti saada myös intuitiota siitä, millainen rakenne on. Sain todistettua, että ainakin pareihin (3n, 4n, 5n), missä n \le 10, päästään kolmikosta (3, 4, 5).

Tylsistyttyäni listaukseen mietin strategiaa tehtävän ratkaisemiseksi. Mietin seuraavaa kysymystä: “Valitaan pienin n, johon kolmikosta (3, 4, 5) ei pääse. Mitä luvusta n voidaan sanoa?” Intuitiivisesti ajattelin n:n olevan alkuluku. Sitten palaset loksahtivat paikalleen: n:n tulee oikeasti olla alkuluku. Jos nimittäin tiedämme, että parista (3, 4, 5) pääsee pariin (3k, 4k, 5k), tarkoittaa se sitä, että osaamme (tietyssä mielessä) kertoa ja jakaa kolmikoiden luvut k:lla. Jälkeenpäin mietittynä tämä tulos tuntuu varsin selvältä, mutta minulta kului kyllä tovi ennen kuin keksin tämän.

Koska olen jo tarkistanut, että kolmikot muotoa (3n, 4n, 5n), n \le 10 ovat saavutettavissa, osaan kertoa ja jakaa kolmikoiden luvut kahdella, kolmella, viidellä ja seitsemällä. Valitaan sitten jokin alkuluku p, ja oletetaan, että kaikilla p:tä pienemmillä alkuluvuilla jakaminen ja kertominen onnistuu. Tutkin aluksi tapausta p \equiv 1 \pmod{4}, koska tällöin tiedetään olevan olemassa kokonaisluvut x ja y, joilla p = x^2 + y^2. Nyt saamme seuraavan yhteyden: (3p, 4p, 5p) \to (4(x^2 - y^2), 8xy, 4(x^2 + y^2)). Luku 8xy on kiva, koska se on tulomuodossa ja koostuu täten pienistä alkuluvuista. Luku löytyykin kolmikosta (2xy \cdot 3, 2xy \cdot 4, 2xy \cdot 5). Koska kahdella, x:llä ja y:llä jakaminen onnistuu (induktio-oletuksen nojalla), pääsemme nyt kolmikkoon (3, 4, 5).

Olin varsin tietoinen siitä, että edellisen kaltainen argumentti ei tulisi toimimaan alkuluvuille muotoa p \equiv 3 \pmod{4} - näitä ei voi esittää kahden neliön summana. Olin hetken ajan hämmentynyt: “Miten ihmeessä nämä p voi sitten käsitellä?”. Tutkin, miten olin aiemmin käsitellyt tapauksen p = 7. Yhdessä osassa verkkorakennelmaani olin käyttänyt kolmikkoa muotoa (2n+1, 2n(n+1), (n+1)^2 + n^2). (Tämä kolmikko on varsin luonnollinen, jos haluaa löytää jonkin kolmikon, johon jokin pariton luku kuuluu.) Jokainen pariton alkuluku on tietysti muotoa 2n+1. Hetken mietinnän jälkeen päädyin seuraavaan ratkaisuun:

Koska p on pariton, voidaan kirjoittaa p = 2n+1. Tutkitaan kolmikkoa (3p, 4p, 5p). Tällä on yhteinen alkio kolmikon (3\cdot (2n+1), 3\cdot 2(n+1)n, 3 \cdot ((n+1)^2 + n^2)). Keskimmäinen alkio puolestaan löytyy kolmikosta (3 \cdot 2(n+1)n, 4 \cdot 2(n+1)n, 5 \cdot 2(n+1)n). Kahdella, n:llä ja n+1:llä jakaminen onnistuu (induktio-oletuksen nojalla), joten tästä kolmikosta päästään kolmikkoon (3, 4, 5). Olemme valmiit. (Huomaa, että esitetty todistus ei käytä muuta tietoa p:stä kuin sen, että se on ykköstä suurempi pariton luku.)

Tässä POG-kilpailun ratkaisut. Tällä viikolla on luvassa ABABOU-algebrakilpailu.

IMODIUM-kilpailun ykköstehtävässä tutkitaan reaalikertoimisia polynomeja p ja q, joilla p(z)q(\overline{z}) on reaaliluku kaikilla z \in \mathbb{C}. Malliratkaisu on varsin elegantti, enkä itse keksinyt mitään niin siistiä. Tässä on hahmotelma omasta ratkaisustani.

Ilman yleisyyden menettämistä voidaan olettaa, että p ja q ovat pääpolynomeja. Olkoon n = \deg(p) ja m = \deg(q). Oletetaan, että n, m > 0. Valitaan jokin pieni kulma \alpha (sanotaan 0 < \alpha < \frac{1}{100(n+m)}) ja erittäin suuri säde r > 0. Olkoon z = re^{i\alpha}. Nyt p(z) on kompleksiluku, jonka argumentti on noin n\alpha. (Arvon p(z) voidaan ajatella olevan summa vektoreista, jotka vastaavat polynomin p termejä. Näistä isoin dominoi, ja sen argumentti on tasan n\alpha. Perustelisin tätä kilpailutilanteessa vielä hieman tarkemmin.) Vastaavasti q(\overline{z}):n argumentti on noin - m\alpha. Argumenttien summan tulee olla nolla (modulo \pi), mikä onnistuu \alpha:n pienuuden vuoksi vain jos m = n.

Kirjoitetaan nyt p(z) = z^n + P(z), q(z) = z^n + Q(z). Saamme, että z^nQ(\overline{z}) + \overline{z}^nP(z) + P(z)Q(\overline{z}) on reaalinen kaikilla z. Käytetään yllä esitetty trikkiä uudestaa. Valita z niin, että sen itseisarvo on suuri ja argumentti pieni. Nyt summan z^nQ(\overline{z}) + \overline{z}^nP(z) + P(z)Q(\overline{z}) argumenttiin vaikuttaa oleellisesti vain summan ensimmäiset kaksi termiä (koska \deg(PQ) on pienempi kuin \max(\deg(z^nQ), \deg(z^nP))). Ei ole vaikeaa nähdä, että \deg(P) = \deg(Q) ja P:n ja Q:n korkeimman asteen termien kertoimet ovat samat. (Perustelu on vastaava kuin edellisessä kappaleessa.)

Nähdäkseni tätä menetelmää voidaan jatkaa siirtymällä aina askeleittain pienemmän asteen termeihin polynomeissa p ja q. Seuraa, että p = q.

Tässä ABABOU-kilpailun ratkaisut. Kyseessä oli tyypillistä helpompi kisa, joten onneksi vaikeustaso pomppaa takaisin ylös IMON’T-lukuteoriakilpailun avulla.

Lisähaastena tehtävään 3 esitetään sen yleistys: Osoita, että jos P(x) \in \mathbb{Z}[x] ja P:n suurimman asteen kerroin on positiivinen, niin on olemassa äärettömän monta kokonaislukua n siten että \phi(P(n)) < n^d, missä d = \mathrm{deg}(P).

Kilpailun laatijat eivät tiedä haastetehtävään alkeellista ratkaisua, joten siitä ei kannata lannistua.

Tässä IMON’T-kilpailun ratkaisut. Teemaan sopiva COOMBI-kombinatoriikkakisa myöhästyy viikolla, joten tällä viikolla julkaistaan kaikista ensimmäinen epävirallinen viikkokisa, IMOMOMONDO.

IMON’T-kilpailun kolmostehtävässä pyydettiin osoittamaan, että kun a, b \in \mathbb{Z}_+, niin äärettömän monella n \in \mathbb{Z}_+ pätee \phi(an + b) < n. Todistus oikeastaan osoittaa, että millä tahansa c > 0 on olemassa äärettömän monta n, joilla \phi(an + b) < cn.

Luonnollinen jatkokysymys on: kuinka pieniä fiifunktion arvot voivat olla? Osoittautuu, että oikea raja on n/\log \log n. Siis: on olemassa sellaiset vakiot c, C > 0, joilla on seuraava ominaisuus: äärettömän monella n pätee \phi(n) < Cn/\log \log n, mutta vain äärellisen monella n pätee \phi(n) < cn/\log \log n. Alla on hahmotelma todistukselle.

Koska \phi(n)/n = \prod_{p | n} (1 - 1/p), minimoituu suhde silloin, kun n valitaan olemaan ensimmäisen k alkuluvun tulo jollain k. Valitaan jokin suuri luku x, ja valitaan n olemaan alkulukujen p \le x tulo. Alkulukulauseen yksi ekvivalentti muotoilu Chebyshevin funktion avulla sanoo, että \prod_{p \le x} p \approx e^x. (Tarkemin: tämä tulo on e^{(1 + o(1))x}.) Siis n on nyt kokoluokkaa e^x. Mertens’n (kolmas) lause puolestaan sanoo, että \prod_{p \le x} (1 - 1/p) \approx 1/\log x. (Tarkemmin: oikea puoli on (c + o(1))/\log x jollain vakiolla c > 0.) (Tämän väitteen todistus on verrattain helppo. Otetaan ensiksi logaritmi puolittain, ja käytetään Taylorin polynomeista saatavaa approksimaatiota \log(1 - x) \approx -x, kun x \approx 0. Nyt ongelma palautuu alkulukujen käänteislukujen summan kasvunopeuden analysoimiseen, johon löytyy näppärä todistus Wikipediasta.)

Saamme siis, että tällä luvun n valinnalla pätee \phi(n)/n \approx e^x/\log x \approx n/\log \log n.

Tehtävästä oli ehdotettu myös yleistys, joka tutkii funktiota \phi(P(n)), missä P on kokonaislukukertoiminen polynomi. Ideana on tosiaan, että ns. Chebotarevin tiheyslauseen nojalla niiden alkulukujen (P:n ns. alkutekijöiden) p tiheys on positiivinen (ja siis olemassa). Chebotarevin tiheyslause on kuitenkin varsin raskas työkalu, eikä edes tuloksen ymmärtäminen ole triviaalia. Tässä tapauksessa voimme käyttää heikompaa Frobeniuksen lausetta, joka on jo helpommin muotoilevassa, mutta jonka ymmärtäminen vaatii silti jonkin verran esitietoja.

Tässä on kuitenkin heuristinen perustelu sille, miksi polynomin alkutekijöiden tiheyden voisi odottaa olevan positiivinen. Olkoon P siis jokin epävakio kokonaislukukertoiminen polynomi. Valitaan jokin alkuluku p. Jos P on epävakio modulo p (mikä tapahtuu kaikilla paitsi äärellisen monella p), on yhtälöllä P(x) \equiv c \pmod{p} enintään \deg(P) ratkaisua Lagrangen lauseen nojalla millä tahansa vakiolla c. Siis P saa kunkin arvon enintään \deg(P) kertaa, joten se saa vähintään p/\deg(P) arvoa modulo p. Voisi ajatella, ettei 0 ole mitenkään erityisen epätodennäköinen arvo, joten heuristisesti P saa arvon 0 modulo p vähintään osuudella 1/\deg(P) alkuluvuista.

Mielenkiintoisesti edellä esitetty heuristiikka antaa myös oikean alarajan polynomin alkutekijöiden tiheydelle. Voidaan osoittaa, että minkä tahansa epävakiolla P alkutekijöiden tiheys on vähintään 1/\deg(P). Tämä alaraja on myös tiukka: yhtäsuuruuden saavuttaa mm. syklotomiset polynomit.

Pahoittelut epävirallisten viikkokisojen myöhästymisestä. Tällä viikolla on luvassa kaksi kisaa, COOMBI-kombinatoriikkakisa ja Suomen IMODIUM 2021- Joukkuevalintakoe. Lopuksi vielä viime kisan, IMOMOMONDO:n ratkaisut löytyvät tästä.