Úloha 5.u1: Sčítací posloupnost (5 b)

Zadáno v čísle 23.5.

Řešeno v čísle 23.7.

Zadání

Postupně tvoříme posloupnost následujícím způsobem:

Začínáme se dvěma jedničkami. Mezi ně přidáme dvojku. Poté přidáme číslo 3 mezi všechna čísla, jejichž součet je 3. To samé opakujeme s dalšími čísly. Číslo $n$ přidáme mezi všechna sousedící čísla v posloupnosti, jejichž součet je roven $n$. Po přidání čísla 5 tedy bude posloupnost vypadat následovně:

\[ 1, 5, 4, 3, 5, 2, 5, 3, 4, 5, 1. \]

Zjistěte, jak se dá charakterizovat počet výskytů čísla $n$ (poté, co bylo do posloupnosti přidáno).

Řešení

Počet výskytů čísla $n>1$ je roven počtu čísel nesoudělných s $n$, která jsou menší než $n$. Dokážeme to tak, že si uvědomíme, že před přidáním jsou každá dvě sousední čísla nesoudělná a každá uspořádaná dvojice sousedních čísel je unikátní.

Budeme tvrdit, že posloupnost má po $n$ krocích výpočtu nějakou vlastnost $V$. Ukážeme, že kdyby po $n$ krocích výpočtu vlastnost $V$ neměla, tak by ji bývala neměla už po $n-1$ krocích výpočtu. A tak se dostaneme až k tomu, že danou vlastnost by musela nemít už na začátku, což ale ověříme, že není pravda.

Vezměme tedy dvojici sousedních čísel $a, b$ v $(n-1)$-ním kroku (kde $a$ leží vlevo od $b$). Pokud platí $a+b=n$, tak se mezi tato čísla v $n$-tém kroku vloží $n$. Po tomto kroku vypadá posloupnost následovně: $(\dots , a, n, b, \dots )$. Nyní se podíváme, jak by posloupnost vypadala, kdyby $a$ a $b$ byla soudělná. Předpokládejme, že $a > b$ (pro $b < a$ provedeme důkaz analogicky). Pak $a$ muselo vzniknout jako $b + x$, pro nějaké $x < a$. To znamená, že $x=a-b$, takže i $x$ je dělitelné všemi společnými děliteli čísel $a$ a $b$. To znamená, že dvě sousední soudělná čísla byla v posloupnosti už v předchozím kroku. Takto můžeme pokračovat dál, ale jednou musíme dospět k původní posloupnosti $(1, 1)$, což je spor, neboť 1 a 1 jsou nesoudělná1.

Stejným zpětným postupem je jasné, že každá uspořádaná dvojice $(a, b)$ se může v posloupnosti objevit jen jednou, jinak by se nějaká jiná objevila dvakrát už dříve, ale posloupnost $1, 1$ obsahuje jen jednu dvojici. Také se v některém kroku při tvorbě posloupnosti musí objevit všechny uspořádané dvojice nesoudělných čísel $(a, b)$, protože kdyby tam nějaká chyběla, v předchozím kroku by chyběla dvojice $(b, a-b)$ a na začátku žádná dvojice nesoudělných čísel nechybí ($(1, 1)$ je jediná taková dvojice).

Dohromady máme, že číslo $n$ se objeví přesně tolikrát, kolik existuje uspořádaných dvojic $(a, b)$ takových, že $a$ a $b$ jsou nesoudělná a že $a+b = n$. Těch je ale přesně tolik, co přirozených čísel $a$ takových, že $a < n$ a $a$ je nesoudělné s $n$ (tedy počet přirozených čísel nesoudělných s $n$, která jsou menší než $n$).

Poznámky: Počet čísel nesoudělných s $n$, která jsou menší nebo rovna $n$, se obvykle označuje $\varphi (n)$ a říká se mu Eulerova funkce2. Někteří řešitelé (a organizátoři) si nejdříve posloupnost naprogramovali a pak uhádli, o jakou posloupnost se jedná. Hodila se jim k tomu online encyklopedie celočíselných posloupností (OEIS3), kde je Eulerova funkce uvedena jako A000010 (tedy 10. nejdůležitější posloupnost na světě :-)). Postup, kterým získáváme stále menší dvojice soudělných čísel, je v podstatě známý Euklidův algoritmus4. Řešitelka Mgr. Beáta Hroncová si všimla, že čísla v posloupnosti odpovídají jmenovatelům tzv. Fareyových zlomků. Pomocí jejich vlastností se dá také přijít k řešení úlohy5.

Anet a Pepa


1) Dvě čísla jsou nesoudělná, právě když je jejich největší společný dělitel jedna.

2) https://en.wikipedia.org/wiki/Euler’s_totient_function

3) https://oeis.org, posloupnost $\varphi (n)$ v ní najdete na adrese https://oeis.org/A000010

4) https://en.wikipedia.org/wiki/Euclidean_algorithm

5) https://en.wikipedia.org/wiki/Farey_sequence