Битти последовательность - Beatty sequence

В математика, а Битти последовательность (или же однородная последовательность Битти) это последовательность из целые числа найдено, взяв этаж положительных кратные положительного иррациональный номер. Последовательности Битти названы в честь Сэмюэл Битти, писавший о них в 1926 году.

Теорема Рэлея, названный в честь Лорд Рэйли, заявляет, что дополнять последовательности Битти, состоящей из положительных целых чисел, не входящих в последовательность, сама по себе является последовательностью Битти, генерируемой другим иррациональным числом.

Последовательности Битти также можно использовать для создания Штурмские слова.

Определение

Положительное иррациональное число ${displaystyle r}$ генерирует последовательность Битти

${displaystyle {mathcal {B}}_{r}=lfloor rfloor ,lfloor 2rfloor ,lfloor 3rfloor ,ldots }$

Если ${displaystyle r>1,,}$ тогда ${displaystyle s=r/(r-1)}$ также положительное иррациональное число. Эти два числа естественным образом удовлетворяют уравнению ${displaystyle 1/r+1/s=1}$. Две последовательности Битти, которые они генерируют,

${displaystyle {mathcal {B}}_{r}=(lfloor nrfloor )_{ngeq 1}}$ и

${displaystyle {mathcal {B}}_{s}=(lfloor nsfloor )_{ngeq 1}}$,

сформировать пара дополнительных последовательностей Битти. Здесь «дополнительный» означает, что каждое положительное целое число принадлежит ровно одной из этих двух последовательностей.

Примеры

Когда р это Золотая середина, у нас есть s = р + 1. В этом случае последовательность ${displaystyle (lfloor nrfloor )}$, известный как нижняя последовательность Wythoff, является

• 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ... (последовательность A000201 в OEIS ).

и дополнительная последовательность ${displaystyle (lfloor nsfloor )}$, то верхняя последовательность Wythoff, является

• 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... (последовательность A001950 в OEIS ).

Эти последовательности определяют оптимальную стратегию для Игра Wythoff, и используются в определении Массив Wythoff

В качестве другого примера для р = √2, у нас есть s = 2 + √2. В этом случае последовательности

• 1, 2, 4, 5, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, 21, 22, 24, ... (последовательность A001951 в OEIS ) и
• 3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, 40, 44, 47, 51, 54, 58, ... (последовательность A001952 в OEIS ).

И для р = π и s = π / (π - 1) последовательности равны

• 3, 6, 9, 12, 15, 18, 21, 25, 28, 31, 34, 37, 40, 43, 47, 50, 53, ... (последовательность A022844 в OEIS ) и
• 1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 24, 26, ... (последовательность A054386 в OEIS ).

Любое число в первой последовательности отсутствует во второй, и наоборот.

История

Последовательности Битти получили свое название от проблемы, поставленной в Американский математический ежемесячный журнал к Сэмюэл Битти в 1926 г.^[1][2] Вероятно, это одна из наиболее часто упоминаемых проблем, когда-либо возникавших в Ежемесячно. Однако еще раньше, в 1894 г., такие последовательности кратко упоминал Джон У. Стратт (третий барон Рэлей) во втором издании его книги Теория звука.^[3]

Теорема Рэлея

В Теорема Рэлея (также известный как Теорема Битти) утверждает, что с учетом иррационального числа ${displaystyle r>1,,}$ Существует ${displaystyle s>1}$ так что последовательности Битти ${displaystyle {mathcal {B}}_{r}}$ и ${displaystyle {mathcal {B}}_{s}}$ раздел то набор положительных целых чисел: каждое положительное целое число принадлежит ровно одной из двух последовательностей.^[3]

Первое доказательство

Данный ${displaystyle r>1,,}$ позволять ${displaystyle s=r/(r-1)}$. Мы должны показать, что каждое натуральное число лежит в одной и только одной из двух последовательностей ${displaystyle {mathcal {B}}_{r}}$ и ${displaystyle {mathcal {B}}_{s}}$. Мы сделаем это, учитывая порядковые позиции, занимаемые всеми дробями ${displaystyle j/r}$ и ${displaystyle k/s}$ когда они перечислены вместе в порядке неубывания для положительных целых чисел j и k.

Чтобы увидеть, что никакие два числа не могут занимать одну и ту же позицию (как одно число), предположим противное, что ${displaystyle j/r=k/s}$ для некоторых j и k. потом ${displaystyle r/s}$ = ${displaystyle j/k}$, а Рациональное число, но также, ${displaystyle r/s=r(1-1/r)=r-1,}$ не рациональное число. Следовательно, никакие два числа не занимают одинаковые позиции.

Для любого ${displaystyle j/r}$, Существуют j числа ${displaystyle i/rleq j/r}$ и ${displaystyle lfloor js/rfloor }$ числа ${displaystyle k/sleq j/r}$, так что положение ${displaystyle j/r}$ в списке ${displaystyle j+lfloor js/rfloor }$. Уравнение ${displaystyle 1/r+1/s=1}$ подразумевает

${displaystyle j+lfloor js/rfloor =j+lfloor j(s-1)floor =lfloor jsfloor .}$

Точно так же позиция ${displaystyle k/s}$ в списке ${displaystyle lfloor krfloor }$.

Вывод: каждое положительное целое число (то есть каждая позиция в списке) имеет вид ${displaystyle lfloor nrfloor }$ или формы ${displaystyle lfloor nsfloor }$, но не то и другое одновременно. Верно и обратное утверждение: если п и q два действительные числа так что каждое положительное целое число встречается ровно один раз в приведенном выше списке, то п и q иррациональны, и сумма их обратных величин равна 1.

Второе доказательство

Столкновения: Предположим, что вопреки теореме есть целые числа j > 0 и k и м такой, что

${displaystyle j=leftlfloor {kcdot r}ightfloor =leftlfloor {mcdot s}ightfloor ,.}$

Это эквивалентно неравенствам

${displaystyle jleq kcdot r<j+1{ ext{ and }}jleq mcdot s<j+1.}$

Для ненулевого j, иррациональность р и s несовместимо с равенством, поэтому

${displaystyle j<kcdot r<j+1{ ext{ and }}j<mcdot s<j+1}$

которые приводят к

${displaystyle {j over r}<k<{j+1 over r}{ ext{ and }}{j over s}<m<{j+1 over s}.}$

Сложив их вместе и используя гипотезу, мы получаем

${displaystyle j<k+m<j+1}$

что невозможно (нельзя иметь целое число между двумя соседними целыми числами). Таким образом, предположение должно быть ложным.

Анти-столкновения: Предположим, что вопреки теореме есть целые числа j > 0 и k и м такой, что

${displaystyle kcdot r<j{ ext{ and }}j+1leq (k+1)cdot r{ ext{ and }}mcdot s<j{ ext{ and }}j+1leq (m+1)cdot s,.}$

С j +1 не равно нулю и р и s иррациональны, мы можем исключить равенство, поэтому

${displaystyle kcdot r<j{ ext{ and }}j+1<(k+1)cdot r{ ext{ and }}mcdot s<j{ ext{ and }}j+1<(m+1)cdot s.}$

Тогда получаем

${displaystyle k<{j over r}{ ext{ and }}{j+1 over r}<k+1{ ext{ and }}m<{j over s}{ ext{ and }}{j+1 over s}<m+1}$

Добавляя соответствующие неравенства, получаем

${displaystyle k+m<j{ ext{ and }}j+1<k+m+2}$

${displaystyle k+m<j<k+m+1}$

что тоже невозможно. Таким образом, предположение неверно.

Характеристики

${displaystyle min {mathcal {B}}_{r}}$ если и только если

${displaystyle 1-{frac {1}{r}}<left[{frac {m}{r}}ight]_{1}}$

куда ${displaystyle [x]_{1}}$ обозначает дробную часть ${displaystyle x}$ т.е. ${displaystyle [x]_{1}=x-lfloor xfloor }$.

Доказательство:${displaystyle min B_{r}}$${displaystyle Leftrightarrow exists n,m=lfloor nrfloor }$${displaystyle Leftrightarrow m<nr<m+1}$ ${displaystyle Leftrightarrow {frac {m}{r}}<n<{frac {m}{r}}+{frac {1}{r}}}$ ${displaystyle Leftrightarrow n-{frac {1}{r}}<{frac {m}{r}}<n}$ ${displaystyle Leftrightarrow 1-{frac {1}{r}}<left[{frac {m}{r}}ight]_{1}}$

Более того, ${displaystyle m=leftlfloor left(leftlfloor {frac {m}{r}}ightfloor +1ight)rightfloor }$.

Доказательство: ${displaystyle m=leftlfloor left(leftlfloor {frac {m}{r}}ightfloor +1ight)rightfloor }$${displaystyle Leftrightarrow m<left(leftlfloor {frac {m}{r}}ightfloor +1ight)r<m+1}$${displaystyle Leftrightarrow {frac {m}{r}}<leftlfloor {frac {m}{r}}ightfloor +1<{frac {m+1}{r}}}$${displaystyle Leftrightarrow leftlfloor {frac {m}{r}}ightfloor +1-{frac {1}{r}}<{frac {m}{r}}<leftlfloor {frac {m}{r}}ightfloor +1}$${displaystyle Leftrightarrow 1-{frac {1}{r}}<{frac {m}{r}}-leftlfloor {frac {m}{r}}ightfloor =left[{frac {m}{r}}ight]_{1}}$

Связь со штурмовскими последовательностями

В первая разница

${displaystyle lfloor (n+1)rfloor -lfloor nrfloor }$

последовательности Битти, связанной с иррациональным числом ${displaystyle r}$ это характеристика Штурмское слово по алфавиту ${displaystyle {lfloor rfloor ,lfloor rfloor +1}}$.

Обобщения

Если немного изменить теорему Рэлея, ее можно обобщить на положительные действительные числа (не обязательно иррациональные), а также на отрицательные целые числа: если положительные действительные числа ${displaystyle r}$ и ${displaystyle s}$ удовлетворить ${displaystyle 1/r+1/s=1}$, последовательности ${displaystyle (lfloor mrfloor )_{min mathbb {Z} }}$ и ${displaystyle (lceil nsceil -1)_{nin mathbb {Z} }}$ образуют разбиение целых чисел.

В Теорема Ламбека – Мозера. обобщает теорему Рэлея и показывает, что более общие пары последовательностей, определенные из целочисленной функции и ее обратной функции, обладают одинаковым свойством разбиения целых чисел.

Успенского Теорема утверждает, что если ${displaystyle alpha _{1},ldots ,alpha _{n}}$ положительные действительные числа такие, что ${displaystyle (lfloor kalpha _{i}floor )_{k,igeq 1}}$ содержит все положительные целые числа ровно один раз, то ${displaystyle nleq 2.}$ То есть не существует эквивалента теоремы Рэлея для трех или более последовательностей Битти.^[4][5]

Рекомендации

1. Битти, Сэмюэл (1926). «Проблема 3173». Американский математический ежемесячный журнал. 33 (3): 159. Дои:10.2307/2300153.
2. С. Битти; А. Островский; Дж. Хислоп; А. К. Эйткен (1927). «Решения проблемы 3173». Американский математический ежемесячный журнал. 34 (3): 159–160. Дои:10.2307/2298716. JSTOR  2298716.
3. Джон Уильям Стратт, третий барон Рэлей (1894). Теория звука. 1 (Второе изд.). Макмиллан. п. 123.
4. Успенский Ю. В. О проблеме, вытекающей из теории одной игры. Амер. Математика. Ежемесячно 34 (1927), стр. 516–521.
5. Р. Л. Грэм, К теореме Успенского, Амер. Математика. Ежемесячно 70 (1963), стр. 407–409.

дальнейшее чтение

• Holshouser, Артур; Райтер, Гарольд (2001). «Обобщение теоремы Битти». Юго-западный журнал чистой и прикладной математики. 2: 24–29. Архивировано из оригинал 2014-04-19.
• Столярский, Кеннет (1976). «Последовательности Битти, непрерывные дроби и некоторые операторы сдвига». Канадский математический бюллетень. 19 (4): 473–482. Дои:10.4153 / CMB-1976-071-6. МИСТЕР  0444558. Включает много ссылок.

внешняя ссылка

• Вайсштейн, Эрик В. "Битти Последовательность". MathWorld.
• Александр Богомольный, Битти последовательности, Разрезать узел