Sekwencja Beatty'ego

W matematyce sekwencja Beatty'ego (lub jednorodna sekwencja Beatty'ego ) to sekwencja liczb całkowitych , którą można znaleźć, biorąc pod uwagę dodatnie wielokrotności dodatniej liczby niewymiernej . Sekwencje Beatty'ego zostały nazwane na cześć Samuela Beatty'ego , który napisał o nich w 1926 roku.

Twierdzenie Rayleigha , nazwane na cześć Lorda Rayleigha , stwierdza, że uzupełnienie sekwencji Beatty'ego, składające się z dodatnich liczb całkowitych, których nie ma w sekwencji, samo w sobie jest sekwencją Beatty'ego generowaną przez inną liczbę niewymierną.

Sekwencje Beatty'ego mogą być również używane do generowania słów Sturmian .

Definicja

Każda liczba niewymierna $jeden,$ generuje sekwencję Beatty'ego

{\ Displaystyle {\ mathcal {B}} _ {r} = \ lfloor r \ rfloor \ lfloor 2r \ rfloor \ lfloor 3r \ rfloor ,\ldkropki}

Dwie liczby niewymierne i naturalnie

{\ displaystyle s = r / (r-1)}

równanie

r

\ displaystyle 1 /r+1/s=1}

. Dwie sekwencje Beatty'ego

i

komplementarnych

przez sekwencji Beatty'ego . Tutaj „komplementarny” oznacza, że każda dodatnia liczba całkowita należy do dokładnie jednej z tych dwóch sekwencji.

Przykłady

Kiedy jest to złoty podział $}$ ${\ Displaystyle r = (1 + {\ sqrt {5}})/2 \ około 1,618}$ , komplementarna sekwencja Beatty'ego to r {\ displaystyle generowany przez ${\ Displaystyle s = r + 1 = (3 + {\ sqrt {5}}) / 2 \ około 2,618}$ . W tym przypadku sekwencja, znana jako dolna sekwencja Wythoffa , to ${\ Displaystyle (\ lfloor nr \ rfloor)}$

1 , 3 , 4 , 6 , 8 , 9 , 11 , 12 , 14 , 16 , 17 , 19 , 21 , 22 , 24 , 25 , 27 , 29 , ... ( sekwencja A000201 w OEIS ),

a sekwencja komplementarna , górna sekwencja Wythoffa , to ${\ Displaystyle (\ lfloor ns \ rfloor)}$

2 , 5 , 7 , 10 , 13 , 15 , 18 , 20 , 23 , 26 , 28 , 31 , 34 , 36 , 39 , 41 , 44 , 47 , ... (sekwencja A001950 w OEIS ).

Sekwencje te definiują optymalną strategię gry Wythoffa i są używane w definicji tablicy Wythoffa .

Jako inny przykład, dla pierwiastka kwadratowego z 2 , ${\ Displaystyle R = {\ sqrt {2}} \ około 1,414}$ , ${\ Displaystyle s = 2 + {\ sqrt {2}}\około 3,414}$ . W tym przypadku sekwencje są

1, 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, 22, 24, ... (sekwencja A001951 w OEIS ) i

3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, 40, 44, 47, 51, 54, 58, ... (sekwencja A001952 w OEIS ) .

R $\ Displaystyle r = \ pi \ około 3,142}$ $(\ pi -1) \ około 1,467}$ i / Czy

3, 6, 9, 12, 15, 18, 21, 25, 28, 31, 34, 37, 40, 43, 47, 50, 53, ... (sekwencja A022844 w OEIS ) i

1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, ... (sekwencja A054386 w OEIS ) .

Żadna liczba w pierwszej sekwencji nie występuje w drugiej i odwrotnie.

Historia

Sekwencje Beatty'ego wzięły swoją nazwę od problemu postawionego w The American Mathematical Monthly przez Samuela Beatty'ego w 1926 roku. Jest to prawdopodobnie jeden z najczęściej cytowanych problemów, jakie kiedykolwiek pojawiły się w Monthly . Jednak jeszcze wcześniej, w 1894 roku, o takich sekwencjach krótko wspomniał Lord Rayleigh w drugim wydaniu swojej książki The Theory of Sound .

Twierdzenie Rayleigha

Twierdzenie Rayleigha (znane również jako twierdzenie Beatty'ego $displaystyle$ , że dana liczba niewymierna istnieje tak, że sekwencje Beatty'ego $} displaystyle {\ mathcal {B}} _ {r}}$ $r$ $i$ dodatnich liczb całkowitych : każda dodatnia liczba całkowita należy dokładnie do jednej z dwóch sekwencji.

Pierwszy dowód

Biorąc pod uwagę ${\ Displaystyle r> 1 \,,}$ niech ${\ Displaystyle s = r / (r-1)}$ . Musimy pokazać, że każda dodatnia liczba całkowita leży w jednej i tylko $mathcal$ z dwóch sekwencji i $}}$ ${B}} _ {$ . Zrobimy to, biorąc pod uwagę pozycje porządkowe zajmowane przez wszystkie ułamki i k $k/s},$ $displaystyle$ gdy są one łącznie wymienione w porządku niemalejącym dla dodatnich całkowitych j k .

$k$ dwie liczby nie mogą zajmować tej samej pozycji (jako ), załóżmy przeciwnie, dla j i . Wtedy ${\ Displaystyle r / s}$ = ${\ Displaystyle j/k}$ , liczba wymierna , ale także ${\ Displaystyle r/s=r(1-1/r)=r-1,}$ nie jest liczbą wymierną. Dlatego żadne dwie liczby nie zajmują tej samej pozycji.

jot ${\ displaystyle j/r}$ istnieją dodatnie liczby całkowite ${\$ $i}$ takie, że ${\ displaystyle i/r \ równoważnik j/r$ i ${\ Displaystyle \ lfloor js/r \ rfloor}$ dodatnie liczby całkowite ${\ Displaystyle k}$ takie, że k $\ Displaystyle k/s \ równoważnik j/r}$ pozycja na liście to $r$ $\ lfloor js / r \ rfloor$ . Równanie implikuje ${\ Displaystyle 1/r + 1/s = 1}$

{\ Displaystyle j + \ lfloor js / r \ rfloor = j + \ lfloor j (s-1) \ rfloor = \ lfloor js \ rfloor.}

$lfloor kr \ rfloor}$ pozycja na liście to $⌋$ .

$displaystyle \ lfloor ns \ rfloor$ $liczba$ całkowita (czyli każda pozycja na liście) ma postać n , ale nie oba. Odwrotne stwierdzenie jest również prawdziwe: jeśli p i q są dwiema liczbami rzeczywistymi takimi, że każda dodatnia liczba całkowita występuje dokładnie raz na powyższej liście, to p i q są niewymierne, a suma ich odwrotności wynosi 1.

Drugi dowód

Zderzenia : Załóżmy, że wbrew twierdzeniu istnieją liczby całkowite j > 0 oraz k i m takie, że

{\ Displaystyle j = \ lewo \ lfloor {k \ cdot r} \ prawo \ rfloor = \ lewo \ lfloor {m \ cdot s} \ prawo \ rfloor \,.}

Jest to równoważne z nierównościami

{\ Displaystyle j \ równoważnik k \ cdot r <j + 1 {\ tekst {i}} j \ równoważnik m \ cdot s <j +1.}

Dla niezerowego j irracjonalność r i s jest niezgodna z równością, więc

{\ Displaystyle j <k \ cdot r <j + 1 {\ tekst {i}} j <m \ cdot s <j + 1 ,}

który prowadzi do

{\ Displaystyle {j \ ponad r}<k <{j + 1 \ ponad r} {\ tekst {i}} {j \ ponad s}<m <{j + 1 \ ponad s}.}

Dodając je razem i używając hipotezy, otrzymujemy

{\ Displaystyle j <k + m <j + 1}

co jest niemożliwe (nie można mieć liczby całkowitej między dwiema sąsiednimi liczbami całkowitymi). Zatem przypuszczenie musi być fałszywe.

Antykolizje : Załóżmy, że wbrew twierdzeniu istnieją liczby całkowite j > 0 oraz k i m takie, że

{\ Displaystyle k \ cdot r <j {\ tekst {i}} j + 1 \ równoważnik (k + 1) \ cdot r {\ tekst {i}} m \ cdot s <j {\ tekst {i}} j +1\równik (m+1)\cdot s\,.}

Ponieważ j + 1 jest niezerowe, a r i s są niewymierne, możemy wykluczyć równość, więc

{\ Displaystyle k \ cdot r <j {\ tekst {i}} j + 1 <(k + 1) \ cdot r {\ tekst {i}} m \ cdot s <j {\ tekst {i}} j + 1<(m+1)\cdot s.}

Wtedy dostajemy

{\ Displaystyle k <{j \ nad r} {\ tekst {i}} {j + 1 \ ponad r}<k+1{\text{ i }}m<{j \over s}{\text{ i }}{j+1 \ponad s}<m+1}

Dodając odpowiednie nierówności, otrzymujemy

\ Displaystyle k + m <j {\ tekst {i}} j + 1 <k + m + 2}

{\ Displaystyle k + m <j <k + m + 1}

co też jest niemożliwe. Zatem przypuszczenie jest fałszywe.

Nieruchomości

Liczba $b$ do sekwencji Beatty'ego wtedy i tylko wtedy, gdy $\ displaystyle {\ mathcal {B}} _ {r}}$

{\ Displaystyle 1 - {\ Frac {1} {r}} <\ lewo [{\ Frac {m} {r}} \ prawej] _ {1}}

gdzie

{\ Displaystyle [x] _ {1}}

oznacza część ułamkową

{\ Displaystyle x}

, tj.

{\ Displaystyle [x] _ {1} = x-\lpodłoga x\rpodłoga }

.

Dowód: ${\ Displaystyle m \ in B_ {r}}$ ${\ Displaystyle \ Strzałka w prawo \ istnieje n, m = \ lfloor nr \ rfloor}$ ${\ Displaystyle \ Leftrightarrow m <nr <m + 1}$ ${\ Displaystyle \ Leftrightarrow {\ Frac {m} {r} <n <{\ Frac {m }{r}} + {\ Frac {1} {r}}}$ ${\ Displaystyle \ Strzałka w prawo n- {\ Frac {1} {r} < {\ Frac {m {r} <n}$ ${\ Displaystyle \ Leftrightarrow 1- {\ Frac {1} {r}} <\ lewo [{\ Frac {m} {r}} \right]_{1}}$

Ponadto ${\ Displaystyle m = \ lewo \ lfloor \ lewo (\ lewo \ lfloor {\ Frac {m} {r}} \ prawo \ rfloor + 1 \ prawo) r\prawo\rpodłoga }$ .

Dowód: ${\ Displaystyle m = \ lewo \ lfloor \ lewo (\ lewo \ lfloor {\ Frac {m} {r}} \ prawo \ rfloor + 1 \ prawo) r \ right \ rfloor}$ ${\ Displaystyle \ Strzałka w lewo m <\ lewo (\ lewo \ lfloor {\ Frac {m} {r}} \ prawo \ rfloor + 1 \ prawej) r <m + 1}$ ${\ Displaystyle \ Strzałka w lewo {\ Frac {m} {r} <\ lewo \ lfloor {\ Frac { m} {r}} \ prawo \ rfloor + 1 <{\ Frac {m + 1} {r}}}$ ${\ Displaystyle \ Leftrightarrow \left\lfloor {\frac {m}{r}}\right\rfloor +1-{\frac {1}{r}}<{\frac {m}{r}}<\left\lfloor {\ frac {m} {r}} \ prawo \ rfloor +1}$ ${\ Displaystyle \ Strzałka w lewo 1 - {\ Frac {1} {r} }<{\frac {m}{r}}-\left\lfloor {\frac {m}{r}}\right\rfloor =\left[{\frac {m}{r}}\right]_{ 1}}$

Związek z sekwencjami Sturmian

Pierwsza różnica

{\ Displaystyle \ lfloor (n + 1) r \ rfloor - \ lfloor nr \ rfloor}

sekwencji Beatty'ego związanej z liczbą niewymierną

charakterystycznym

Sturmianskim słowem nad alfabetem

{\ Displaystyle \ {\ lfloor r \ rfloor, \ lfloor r \ rfloor +1\}}

.

Uogólnienia

Po niewielkiej modyfikacji twierdzenie Rayleigha można uogólnić na dodatnie liczby rzeczywiste (niekoniecznie irracjonalne) i ujemne liczby całkowite: jeśli dodatnie liczby rzeczywiste $_$ spełniają 1 $displaystyle$ $r}$ _ $_$ _ ${\ Displaystyle (\ lceil ns \ rceil -1) _ {n \ in \ mathbb {Z}}}$ tworzą partycję liczb całkowitych. ${\ displaystyle s$ klawiatury fortepianu są rozmieszczone jako takie sekwencje dla $5$ .

Twierdzenie Lambeka-Mosera uogólnia twierdzenie Rayleigha i pokazuje, że bardziej ogólne pary ciągów zdefiniowane na podstawie funkcji całkowitej i jej odwrotności mają tę samą właściwość dzielenia liczb całkowitych.

${\ Displaystyle (\ lfloor k \ alfa _ {i} \ rfloor) _ {k, i \ geq 1}}$ Uspienskiego stwierdza $ja$ że jeśli takimi zawiera wszystkie dodatnie liczby całkowite dokładnie raz, a następnie ${\ Displaystyle n \ leq 2.}$ To jest , nie ma odpowiednika twierdzenia Rayleigha dla trzech lub więcej sekwencji Beatty'ego.

Dalsza lektura

Holshouser, Artur; Reiter, Harold (2001). „Uogólnienie twierdzenia Beatty'ego” . Southwest Journal of Pure and Applied Mathematics . 2 : 24–29. Zarchiwizowane od oryginału w dniu 19.04.2014 r.
Stolarski, Kenneth (1976). „Sekwencje Beatty'ego, ułamki ciągłe i niektóre operatory przesunięć” . Kanadyjski Biuletyn Matematyczny . 19 (4): 473–482. doi : 10.4153/CMB-1976-071-6 . MR 0444558 . Zawiera wiele referencji.

Linki zewnętrzne