Последовательность Битти

Целые числа, образованные путем округления вниз целых кратных положительного иррационального числа.

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

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

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

Определение

Любое иррациональное число , большее единицы, порождает последовательность Битти . Два иррациональных числа и естественным образом удовлетворяют уравнению . Две последовательности Битти и , которые они порождают, образуют пару дополнительных последовательностей Битти . Здесь «дополнительный» означает, что каждое положительное целое число принадлежит ровно одной из этих двух последовательностей. ${\displaystyle r}$ $${\displaystyle {\mathcal {B}}_{r}={\bigl \{}\lfloor r\rfloor ,\lfloor 2r\rfloor ,\lfloor 3r\rfloor ,\ldots {\bigr \}}}$$ ${\displaystyle r}$ ${\displaystyle s=r/(r-1)}$ ${\displaystyle 1/r+1/s=1}$ ${\displaystyle {\mathcal {B}}_{r}}$ ${\displaystyle {\mathcal {B}}_{s}}$

Примеры

Когда есть золотое сечение , дополнительная последовательность Битти генерируется с помощью . В этом случае последовательность , известная как нижняя последовательность Витхоффа , есть ${\displaystyle r}$ ${\displaystyle r=(1+{\sqrt {5}})/2\approx 1.618}$ ${\displaystyle s=r+1=(3+{\sqrt {5}})/2\approx 2.618}$ ${\displaystyle (\lfloor nr\rfloor )}$

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

и дополнительная последовательность , верхняя последовательность Витхоффа , равна ${\displaystyle (\lfloor ns\rfloor )}$

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

Эти последовательности определяют оптимальную стратегию для игры Витхоффа и используются в определении массива Витхоффа .

В качестве другого примера, для квадратного корня из 2 , , . В этом случае последовательности имеют вид ${\displaystyle r={\sqrt {2}}\approx 1.414}$ ${\displaystyle s=2+{\sqrt {2}}\approx 3.414}$

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 ).

Для и последовательности имеют вид ${\displaystyle r=\pi \approx 3.142}$ ${\displaystyle s=\pi /(\pi -1)\approx 1.467}$

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 ).

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

История

Последовательности Битти получили свое название от проблемы, поставленной в The American Mathematical Monthly Сэмюэлем Битти в 1926 году. ^{[1] [2]} Это, вероятно, одна из наиболее часто цитируемых проблем, когда-либо поставленных в Monthly . Однако еще раньше, в 1894 году, такие последовательности были кратко упомянуты лордом Рэлеем во втором издании его книги The Theory of Sound . ^[3]

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

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

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

Пусть . Мы должны показать , что каждое положительное целое число лежит в одной и только одной из двух последовательностей и . Мы сделаем это, рассмотрев порядковые позиции, занимаемые всеми дробями , и когда они совместно перечислены в неубывающем порядке для положительных целых чисел j и k . ${\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}$ ${\displaystyle r/s}$ ${\displaystyle j/k}$ ${\displaystyle r/s=r(1-1/r)=r-1,}$

Для любого существуют положительные целые числа такие, что и положительные целые числа такие, что , так что позиция в списке равна . Уравнение подразумевает ${\displaystyle j/r}$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle i/r\leq j/r}$ ${\displaystyle \lfloor js/r\rfloor }$ ${\displaystyle k}$ ${\displaystyle k/s\leq j/r}$ ${\displaystyle j/r}$ ${\displaystyle j+\lfloor js/r\rfloor }$ ${\displaystyle 1/r+1/s=1}$ $${\displaystyle j+\lfloor js/r\rfloor =j+\lfloor j(s-1)\rfloor =\lfloor js\rfloor .}$$

Аналогично, позиция в списке — . ${\displaystyle k/s}$ ${\displaystyle \lfloor kr\rfloor }$

Вывод: каждое положительное целое число (то есть каждая позиция в списке) имеет вид  или вид , но не оба. Обратное утверждение также верно: если p и q — два действительных числа , такие, что каждое положительное целое число встречается ровно один раз в приведенном выше списке, то p и q иррациональны, а сумма их обратных чисел равна 1. ${\displaystyle \lfloor nr\rfloor }$ ${\displaystyle \lfloor ns\rfloor }$

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

Столкновения : Предположим, что, вопреки теореме, существуют целые числа j  > 0, а также k и m, такие, что Это эквивалентно неравенствам $${\displaystyle j=\left\lfloor {k\cdot r}\right\rfloor =\left\lfloor {m\cdot s}\right\rfloor \,.}$$ $${\displaystyle j\leq k\cdot r<j+1{\text{ and }}j\leq m\cdot s<j+1.}$$

Для ненулевого j иррациональность r и s несовместима с равенством, поэтому, что приводит к $${\displaystyle j<k\cdot r<j+1{\text{ and }}j<m\cdot s<j+1,}$$ $${\displaystyle {j \over r}<k<{j+1 \over r}{\text{ and }}{j \over s}<m<{j+1 \over s}.}$$

Сложив их вместе и используя гипотезу, мы получаем, что невозможно (не может быть целого числа между двумя соседними целыми числами). Таким образом, предположение должно быть ложным. $${\displaystyle j<k+m<j+1}$$

Антистолкновения : Предположим, что, вопреки теореме, существуют целые числа j  > 0, а также k и m, такие, что $${\displaystyle k\cdot r<j{\text{ and }}j+1\leq (k+1)\cdot r{\text{ and }}m\cdot s<j{\text{ and }}j+1\leq (m+1)\cdot s\,.}$$

Поскольку j  + 1 не равно нулю, а r и s иррациональны, мы можем исключить равенство, поэтому $${\displaystyle k\cdot r<j{\text{ and }}j+1<(k+1)\cdot r{\text{ and }}m\cdot s<j{\text{ and }}j+1<(m+1)\cdot s.}$$

Тогда мы получаем $${\displaystyle k<{j \over r}{\text{ and }}{j+1 \over r}<k+1{\text{ and }}m<{j \over s}{\text{ and }}{j+1 \over s}<m+1}$$

Сложив соответствующие неравенства, получаем $${\displaystyle k+m<j{\text{ and }}j+1<k+m+2}$$ $${\displaystyle k+m<j<k+m+1}$$

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

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

Число принадлежит последовательности Битти тогда и только тогда , когда обозначает дробную часть числа , т.е. . ${\displaystyle m}$ ${\displaystyle {\mathcal {B}}_{r}}$ $${\displaystyle 1-{\frac {1}{r}}<\left[{\frac {m}{r}}\right]_{1}}$$ ${\displaystyle [x]_{1}}$ ${\displaystyle x}$ ${\displaystyle [x]_{1}=x-\lfloor x\rfloor }$

Доказательство: ${\displaystyle m\in B_{r}}$ ${\displaystyle \Leftrightarrow \exists n,m=\lfloor nr\rfloor }$ ${\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}}\right]_{1}}$

Более того, . ${\displaystyle m=\left\lfloor \left(\left\lfloor {\frac {m}{r}}\right\rfloor +1\right)r\right\rfloor }$

Доказательство: ${\displaystyle m=\left\lfloor \left(\left\lfloor {\frac {m}{r}}\right\rfloor +1\right)r\right\rfloor }$ ${\displaystyle \Leftrightarrow m<\left(\left\lfloor {\frac {m}{r}}\right\rfloor +1\right)r<m+1}$ ${\displaystyle \Leftrightarrow {\frac {m}{r}}<\left\lfloor {\frac {m}{r}}\right\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}}\right\rfloor +1}$ ${\displaystyle \Leftrightarrow 1-{\frac {1}{r}}<{\frac {m}{r}}-\left\lfloor {\frac {m}{r}}\right\rfloor =\left[{\frac {m}{r}}\right]_{1}}$

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

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

Обобщения

Если немного изменить теорему Рэлея, ее можно обобщить на положительные действительные числа (не обязательно иррациональные) и отрицательные целые числа: если положительные действительные числа и удовлетворяют , то последовательности и образуют разбиение целых чисел. Например, белые и черные клавиши фортепианной клавиатуры распределены как такие последовательности для и . ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle 1/r+1/s=1}$ ${\displaystyle (\lfloor mr\rfloor )_{m\in \mathbb {Z} }}$ ${\displaystyle (\lceil ns\rceil -1)_{n\in \mathbb {Z} }}$ ${\displaystyle r=12/7}$ ${\displaystyle s=12/5}$

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

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

Ссылки

1. Битти, Сэмюэл (1926). «Проблема 3173». American Mathematical Monthly . 33 (3): 159. doi :10.2307/2300153. JSTOR  2300153.
2. S. Beatty; A. Ostrowski; J. Hyslop; AC Aitken (1927). «Решения задачи 3173». American Mathematical Monthly . 34 (3): 159–160. doi :10.2307/2298716. JSTOR  2298716.
3. Джон Уильям Страт, 3-й барон Рэлей (1894). Теория звука. Т. 1 (Второе изд.). Macmillan. стр. 123.{{cite book}}: CS1 maint: numeric names: authors list (link)
4. Дж. В. Успенский, Об одной задаче, вытекающей из теории одной игры, Amer. Math. Monthly 34 (1927), стр. 516–521.
5. Р. Л. Грэм, О теореме Успенского, Amer. Math. Monthly 70 (1963), стр. 407–409.

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

• Holshouser, Arthur; Reiter, Harold (2001). «Обобщение теоремы Битти». Southwest Journal of Pure and Applied Mathematics . 2 : 24–29. Архивировано из оригинала 2014-04-19.
• Столярский, Кеннет (1976). «Последовательности Битти, непрерывные дроби и некоторые операторы сдвига». Канадский математический бюллетень . 19 (4): 473–482. doi : 10.4153/CMB-1976-071-6 . MR  0444558.Включает множество ссылок.

Внешние ссылки

• Вайсштейн, Эрик В. «Последовательность Битти». MathWorld .
• Александр Богомольный , Битти Секвенции, Cut-the-knot