Złociaków nigdy dosyć

Wyobraźmy sobie, że trafiliśmy do dziwnego kraju, w którym jedynymi dostępnymi środkami płatniczymi są monety o nominałach $|a$ i $b:$ Formy płatności nie rozwinęły się na tyle, żeby płacić kartą lub czekiem, na domiar złego wybraliśmy się do cukierni, w której kasa jest zupełnie pusta i sprzedawca nie może wydać nam reszty. Nie chcąc tracić swoich złociaków, rozglądamy się za pysznościami w cenach $|a + a;a + b;xa + yb :::$ Niektórych kwot, oczywiście, nie daje się uzyskać z nominałów $a$ i $|b;$ a niektóre można otrzymać na wiele sposobów.

Dla wszystkich względnie pierwszych liczb naturalnych $a, b⩾ 2$ istnieje taka największa niewygodna kwota $|n,$ że wszystkie kolejne $n +1,n + 2,n+ 3 ...$ mogą być uzyskane za pomocą tych nominałów. Wyjaśnienie, że taka największa niewygodna $n$ faktycznie istnieje, jej postać oraz parę innych obserwacji użytkowania tylko dwóch nominałów można znaleźć w $|∆4 . 14$ A teraz rzucimy na sprawę nowe światło.

(1)

n = n(a,b) = ab − a− b

jest największą liczbą, która nie jest postaci

|xa +yb

dla

x,y ⩾ 0

- mimo największych starań nie uzyskamy jej ze złociaków.

(2)

Dokładnie połowa liczb ze zbioru

{1,2,...,n− 1}

jest postaci

z = xa + yb, gdziex, y⩾ 0.

(

∗

)

(3)

Jeśli

z ∈ {1,2,...,n − 1},

to dokładnie jedna z liczb:

|z

albo

n − z

jest postaci (

∗

Własności 1 i 2 zostały udowodnione w Delcie 4/2014. Z obu tych własności wynika własność 3 na mocy następującego rozumowania: nie może się zdarzyć, że dla pewnego $z ∈ {1,2,...,n − 1}$ obie liczby $z$ oraz $n − z$ są postaci ( $∗$ ), gdyż wówczas ich suma $|z+ (n −z) = n$ też byłaby postaci ( $∗$ ), a to jest sprzeczne z własnością 1 (przecież $n$ to największa liczba, której nie jesteśmy w stanie uzyskać!). Tak więc obie $z$ i $n − z$ nie mogą jednocześnie być postaci ( $∗$ ) - zatem z własności 2 otrzymujemy, że w każdym zbiorze ${z,n − z}$ dokładnie jedna z liczb jest postaci ( $∗$ )!

Dla $a = 9,b = 5$ mamy $n(9, 5) = 31,$ a liczby przedstawialne w postaci ( $∗$ ) (ich zbiór oznaczmy przez $P(a, b)$ ), mniejsze od $31,$ to

P (9,5) = {5,9,10,14,15,18,19,20,23,24, 25,27,28,29,30}.

Natomiast liczby nieprzedstawialne w postaci ( $∗$ ) mniejsze od $31$ to

(9,5)={1,2,3,4,6,7,8,11,12,13,16,17,21,22,26}. N

Już na tym prostym przykładzie można zauważyć, że istnieją dość długie ciągi kolejnych liczb naturalnych, z których każda jest przedstawialna. Zachodzi bowiem następujące twierdzenie.

Twierdzenie 1. Dla dowolnych względnie pierwszych $a > b ⩾2$ w zbiorze $|P(a,b)$ istnieje ciąg kolejnych $b − 1$ liczb naturalnych, ale nie istnieje taki ciąg długości $b.$

Dowód. Ponieważ liczby $1,2,...,b − 1$ oczywiście nie są przedstawialne, więc na mocy własności 3 kolejne liczby $n − 1,n− 2,...,n − b+ 1$ są przedstawialne. Gdyby w zbiorze ${1,2,...,n − 1}$ były kolejne liczby $m$ wszystkie należące do $P (a,b),$ to na mocy własności 3 żadna z liczb $n − m$ nie byłaby przedstawialna, co jednak jest sprzeczne z następującą obserwacją: odstępy między kolejnymi liczbami w $|P(a,b)$ są nie większe od $|b$ (rzeczywiście, jeśli $xa + yb ∈P (a,b),$ to następna liczba naturalna $|s$ w $|P(a,b)$ spełnia nierówność $s ⩽ xa +yb + b$ ).

W sformułowaniu kolejnego twierdzenia wielkość parametrów $a,b$ nie odgrywa żadnej roli - w tym sensie ma ono charakter bardziej uniwersalny niż twierdzenie 1.

Twierdzenie 2. Ciąg kolejnych pięciu liczb z $P (a,b)$ zawsze zawiera podciąg arytmetyczny długości $|3.$

Zanim je udowodnimy w ogólności, zobaczmy, jak to działa na naszym przykładzie. Ciąg $5,9,10,14, 15$ zawiera podciąg arytmetyczny $5,10,15$ ; ciąg $|9,10,14,15,18$ zawiera podciąg $10,14,18$ ; ciąg $14,15,18,19,20$ zawiera podciąg $|18,19,20$ itd.

Dowód. Niech $z1 < z2 < z3 < z4 < z5$ będą kolejnymi liczbami w $P(a,b).$ Dla każdego $k ∈ {1,2,3,4,5}$ istnieją więc takie liczby całkowite nieujemne $|x ,y , k k$ że

zk = xka + ykb.

Każdej parze liczb $(x ,y ) k k$ przyporządkujmy parę ich reszt modulo $2,$ np. jeśli $(xk,yk) = (12,15)$ to otrzymujemy parę reszt $|(0,1).$ Ponieważ wszystkie pary reszt modulo $2$ to: $(0,0),(0,1),(1,0),(1,1)$ więc istnieją różne liczby $| j,k ∈ {1,2,3,4, 5}$ takie, że $x ,x j k$ są tej samej parzystości oraz $|y j,yk$ są tej samej parzystości. Wynika stąd, że liczba

z j + zk x j + xk y j + yk ------ = ------a + ------b 2 2 2

jest postaci ( $∗$ ), a zatem

z j +zk-= z , gdzie m 2 m

gdyż liczby $z1 < z2 < z3 < z4 < z5$ są kolejne w $|P(a,b)$ !

Zachęta. Zachęcamy Czytelnika do napisania programu, który dla danych liczb względnie pierwszych $a > b⩾ 2$ będzie generował zbiory $P (a,b).$ Wtedy można eksperymentować z różnymi konkretnymi parami $|a,b$ i na podstawie obserwacji dostrzegać różne prawidłowości. Niektóre z nich da się ująć w formę twierdzeń, czyli udowodnić - tak powstaje matematyka.

Pokusimy się o jeszcze jeden przykład. Skoro ostatnie $b −1$ liczb z $P (a,b)$ są kolejnymi liczbami naturalnymi (dowód twierdzenia 1), to można zapytać o takie najmniejsze $c,$ że obie liczby $c$ oraz $c + 1$ należą do $|P(a,b).$ Wiemy, że $c ⩽ ab −a − 2b +1,$ ale eksperymentując z różnymi wartościami $|a,b,$ dochodzimy do następującej hipotezy.

Hipoteza. Dla danych liczb względnie pierwszych $a > b⩾ 2$ definiujemy $c(a, b)$ jako taką najmniejszą liczbę naturalną $c,$ że obie liczby $|c,c+ 1$ należą do $|P(a,b)($ tzn. mają postać ( $∗$ )). Wówczas $|c(a,b)$ można otrzymać w następujący sposób.
Niech $a/b = [c0;c1,...,ck]$ będzie takim rozwinięciem liczby $a/b$ na ułamek łańcuchowy, że $ck > 1$ (takie rozwinięcie jest jedyne). Niech $| f/g = [c0;c1,...,ck−1].$ Wówczas

c(a,b) = min(ag, bf ).

Teraz pojawiają się przynajmniej dwie możliwości: można próbować ją udowodnić lub obalić! Albo… rzucić się na głębszą wodę i zacząć badać pierwsze pojawienie się trójki kolejnych liczb w $P(a, b).$ Niech $|d = d(a, b)$ będzie taką najmniejszą liczbą $d,$ że $d, d + 1,d +2 ∈ P(a,b)$ (zakładamy tu, oczywiście, że $|b⩾ 4$ - patrz twierdzenie 1). Na drodze eksperymentów komputerowych otrzymaliśmy

d(13, 8) = 63; d(14,9) = 54; d(18,11) = 108.

Niestety, nie potrafimy sformułować żadnej hipotezy dotyczącej "wzoru" na $|d(a,b).$