Catalanin lukujen yleistys

Tässä postauksessa käydään läpi eräs Suomen loppukilpailutehtävä, joka osoittautuu Catalanin lukujen yleistykseksi.

MAOL:n loppukilpailu 2014, Tehtävä 3

Pisteet $P = (a, b)$ ja $Q = (c, d)$ ovat $xy$-tason ensimmäisessä neljänneksessä, ja $a, b, c$ sekä $d$ ovat kokonaislukuja, joille $a<b, a<c, b<d$ ja $c<d$. Reitti pisteestä $P$ pisteeseen $Q$ on positiivisten koordinaattiakselien suuntaisista, yksikön pituisista askelista muodostuva murtoviiva, ja sallittu reitti on reitti, joka ei leikkaa eikä kosketa suoraa $x = y$. Montako sallittua reittiä on?

KöMaL ja ositusongelma

KöMaL on unkarilainen “matematiikkalehti”. KöMaLin sivuilta löytyy lisäksi paljon kilpailumatematiikan tehtäviä, vaihdellen helpohkoista hyvin haastaviin. Tässä postauksessa käydään läpi yksi näistä tehtävistä:

Tehtävä (KöMaL, A647)

Olkoon $k$ epänegatiivinen kokonaisluku. Osoita, että vain äärellisen monella positiivisella kokonaisluvulla $n$ on olemassa joukot $A$ ja $B$, joilla $A \cup B = \lbrace 1, 2, \ldots , n \rbrace $, $A \cap B = \emptyset$ ja

Sinilausebash

Tässä postauksessa johdatellaan sinilausebashaukseen, eli miten sinilauseella voidaan laskennallisesti ratkaista geometrian tehtäviä.

Schurin lause

Tässä postauksessa käsitellään Schurin lausetta: jokaisella kokonaislukukertoimisella ei-vakiolla polynomilla on äärettömän monta alkutekijää.

Juuren ottaminen moduloissa

Tässä postauksessa käsitellään miten muotoa $a^n \equiv b^n \pmod{m}$ olevasta yhtälöstä voi ottaa juuren tietyin ehdoin.

Kobayashin lause

Tässä postauksessa käsitellään Kobayashin lausetta.

Kiinatehtävä, osa 3

Tässä postauksessa käsitellään seuraavan tehtävän ratkaisu:

Kiinan IMO-joukkueen valintakoe 2, 2015, tehtävä 6

Osoita, että on olemassa äärettömän monta $n \in \mathbb{Z_+}$ jolla $n^2 + 1$ ei ole jaollinen millään alkuluvun neliöllä (engl. squarefree)

Lukujonon neliöominaisuus kolmella tavalla

Tässä postauksessa käydään kolme hyvin erilaista ja varsin mielenkiintoista ratkaisua seuraavalle tehtävälle:

Valmennustehtävät, 2018 tammikuu, tehtävä 21

Määritellään $a_0 = a_1 = 3$ ja $a_{n+1} = 7a_n - a_{n-1}$ jokaisella $n \in \mathbb{Z_+}$. Osoita, että $a_n - 2$ on neliöluku jokaisella $n \in \mathbb{Z_+}$.

Tekijöihinjakoa

Tässä postauksessa käydään läpi muutama asia liittyen tekijöihinjakoon.

Kiinatehtävä, osa 2

Tässä postauksessa käsitellään seuraavan tehtävän ratkaisu:

Kiinan IMO-joukkueen valintakoe 5, 2010, tehtävä 3

Olkoon $k$ positiivinen kokonaisluku. Osoita, että on olemassa sellainen positiivinen kokonaisluku $N$, niin että kaikilla $n \ge N$ luvulla ${n \choose k}$ on vähintään $k$ erisuurta alkutekijää.

Cyclotomisten polynomien soveltaminen valmennustehtävään

Tehtävä tammikuun valmennustehtävät, tehtävä 14

Kiinatehtävä, osa 1

Tässä postauksessa käsitellään seuraavan tehtävän ratkaisu:

Kiinan IMO-joukkueen valintakoe 4, 2010, tehtävä 3 Olkoon $f(n)$ luvun $n$ itseään pienempien tekijöiden summa, esimerkiksi $f(10) = 1 + 2 + 5$. Määritellään $f^1(n) = f(n)$, ja $f^i(n) = f^{i-1}(f(n))$ kaikilla $i > 1$.

Olkoon annettu $k \in \mathbb{N}$. Osoita, että on olemassa $n \in \mathbb{N}$, jolla

Catalan

Tämän postauksen tavoite on selittää alkeet Catalanin luvuista.

Carmichaelin funktio

Carmichaelin funktio $\lambda$ määritellään niin, että $\lambda (p^k) = \phi(p^k)$ kaikilla parittomilla alkuluvuilla $p$ ja $k \ge 0$, $\lambda (2^k) = 2^{k-2}$ kaikilla $k > 2$.