투-모스 수열

수학에서, Thue-Morse sequence 또는 Prouhet-thue-Morse sequence 또는 패리티 sequence는^[1] 0으로 시작하여 지금까지 얻은 sequence의 Boolean complement를 연속적으로 추가하여 얻은 이진 sequence(0과 1의 무한 sequence)입니다. 이 절차의 처음 몇 단계에서는 Thue-Morse 시퀀스의 접두사인 문자열 0, 01, 0110, 01101001, 01101100110 등을 생성합니다. 전체 시퀀스가 시작됩니다.

01101001100101101001011001101001.... ^[1]

이 순서는 악셀 튜와 마스턴 모스의 이름을 따서 지어졌습니다.

정의.

Thue-Morse 수열을 정의하는 데에는 몇 가지 동등한 방법이 있습니다.

직접정의

n번째 원소 t를_n 계산하려면 숫자 n을 이진법으로 적습니다. 이 이진 전개에서 하나의 수가 홀수이면 t = 1이고 짝수이면 t = 0입니다. 즉, t는 n에 대한 짝수 패리티 비트입니다. John H. Conway et al. 에서는 n을 만족시키는 숫자 n을 1개의 음험한(홀수의 경우) 숫자와 t = 0개의 음험한(짝수의 경우) 숫자라고 불렀습니다. 즉, n이 사악한 수이면 t = 0, n이 사악한 수이면 t = 1입니다.

빠른 시퀀스 생성

이 방법은 Thue-Morse 수열을 빠르게 계산하는 방법으로 이어집니다: t = 0으로 시작한 다음, n 각각에 대해 n - 1의 표현에서 같은 비트와 다른 n의 이진법에서 가장 높은 차수의 비트를 찾으십시오. 이 비트가 짝수 인덱스에 있으면 t와 다르며, 그렇지 않으면 t와 같습니다.

의사 코드 형식:

디프 generate_sequence(seq_length: 인트의):     """Thue-Morse sequence."""     가치 = 0     위해서 n = 0 로. seq_length-1 타고 1:         # 참고: n == 0일 때 x가 홀수(예: 31 또는 63)가 되도록 워드 크기의 짝수 비트와 2의 상보 산술을 가정합니다.         x = index_of_highest_one_bit(n ^ (n - 1))                                 한다면 ((x & 1) == 0):             # 비트 인덱스는 짝수이므로 토글 값             가치 = 1 - 가치         양보 가치 

결과적인 알고리즘은 각 시퀀스 요소를 생성하는 데 일정한 시간이 소요되며, 오직 로그 수의 비트(일정한 수의 단어) 메모리를 사용합니다.^[3]

재발관계

Thue-Morse 시퀀스는 순환 관계를 만족시키는 시퀀스 t입니다_n.

${\displaystyle {\begin{aligned}t_{0}&=0,\\t_{2n}&=t_{n},\\t_{2n+1}&=1-t_{n},\end{aligned}}}$

음이 아닌 모든 정수 n에 대하여.^[2]

엘계

Thue-Morse 수열은 ^[4]다음과 같은 린덴마이어 시스템의 출력입니다.

비트 단위 부정을 이용한 특성화

비트 수열로서, 위에 주어진 형태의 Thue-Morse 수열은 비트 수열의 연산을 이용하여 재귀적으로 정의될 수 있습니다. 그래서 첫 번째 요소는 0입니다. 그런 다음 처음 2개의ⁿ 요소가 지정되어 문자열이 형성되면 다음 2개의ⁿ 요소는 s의 비트 단위 음을 형성해야 합니다. 이제 우리는 처음 2개의ⁿ⁺¹ 요소를 정의하고 반복합니다.

처음 몇 단계의 스펠링을 자세히 설명합니다.

• 0부터 시작합니다.
• 0의 비트 단위 음은 1입니다.
• 이것들을 합하면, 처음 2개의 원소는 01입니다.
• 01의 비트 단위 음은 10입니다.
• 이것들을 합하면 처음 4개의 원소는 0110입니다.
• 0110의 비트 단위 음은 1001입니다.
• 이들을 합하면 처음 8개의 원소는 01101001입니다.
• 등등.

그렇게

• T = 0.
• T = 01.
• T = 0110.
• T₃ = 01101001.
• T₄ = 0110100110010110.
• T₅ = 01101001100101101001011001101001.
• T₆ = 0110100110010110100101100110100110010110011010010110100110010110.
• 등등.

무한곱

시퀀스는 다음과 같이 정의할 수도 있습니다.

${\displaystyle \prod _{i=0}^{\infty }\left(1-x^{2^{i}}\right)=\sum _{j=0}^{\infty }(-1)^{t_{j}}x^{j},}$

여기서 우리가 j = 0에서 시작한다면 j번째 원소입니다.

특성.

The Thue–Morse sequence contains many squares: instances of the string ${\displaystyle XX}$, where ${\displaystyle X}$ denotes the string ${\displaystyle A}$, ${\displaystyle {\overline {A}}}$, ${\displaystyle A{\overline {A}}A}$, or ${\displaystyle {\overline {A}}$$A{\overline {A}}}$, where ${\displaystyle A=T_{k}}$ for some ${\displaystyle k\geq 0}$ and ${\displaystyle {\overline {A}}}$ is the bitwise negation of ${\displaystyle A}$.^[5] For instance, if ${\displaystyle k=0}$, then ${\displaystyle A=$$T_{0$}$=$0}. ${\displaystyle 사각형}$ ${\displaystyle AA\stackrel{}{}}$¯ ${\displaystyle AA}$ ¯ $A$= $010010 {\displaystyle$ A{\overline {A}}$AA{\overline {A}}A=010010$}은(는) 16번째 비트부터 $T$ ${\displaystyle$ T$}$에 표시됩니다. $T$ ${\displaystyle T}$의 모든 정사각형은 이 4개의 문자열 중 하나를 반복하여 $얻어지기$ 때문에${\displaystyle ,}$ $n개$의 ≥ 0${\displaystyle$ $2^{n}$ 또는 ${\displaystyle {3개}^{}}$의 ⋅ 2 $n$ {\$displaystyle 3\cdot$ 2^{n}}를 갖습니다$.$ ${\displaystyle T}$ contains no cubes: instances of ${\displaystyle XXX}$. There are also no overlapping squares: instances of ${\displaystyle 0X0X0}$ or ${\displaystyle 1X1X1}$.^[6][7] $T {\displaystyle$ T$}$의 임계 지수는 2입니다$$.^[8]

Thue-Morse 수열은 균일하게 반복되는 단어입니다.^[9][10] 수열 내의 임의의 유한한 문자열 X가 주어졌을 때, X가_X 길이 n의_X 모든 블록에 나타날 정도로 길이 n이 있습니다. 특히, Thue-Morse 시퀀스는 주기적이거나 결국 주기적(즉, 일부 초기 비주기적 세그먼트 이후에 주기적)이지 않고 균일하게 반복됩니다.^[11]

수열 T는_2n 임의의 n에 대한 회문입니다. 또한 q를 T의 연속된 0 사이의 것을 세어 얻은 단어라고 하자. 예를 들어 q = 2와 q = 2102012. T는_n 겹침 사각형을 포함하지 않으므로 단어 q는_n 회문 사각형 자유 단어입니다.

Thue-Morse 형태론 μ는 알파벳 {0,1}에서 치환 맵 μ(0) = 01, μ(1) = 10으로 정의됩니다: 시퀀스의 0마다 01로, 1마다 10으로 대체됩니다. T가 Thue-Morse 수열이면 μ(T)도 T입니다. 따라서 T는 μ의 고정점입니다. 모피즘 μ는 T를 고정점으로 하는 자유 모노이드 {0,1}^∗에서 연장 가능한 모피즘입니다. 이것은 본질적으로 μ의 유일한 고정점이며, 유일한 다른 고정점은 T의 비트 단위 음으로, (0,1)이 아닌 (1,0)의 Thue-Morse 시퀀스일 뿐입니다. 이 속성은 자동 시퀀스의 개념으로 일반화될 수 있습니다.

이진 필드 위에서 T의 생성 급수는 형식적 멱급수입니다.

${\displaystyle t(Z)=\sum _{n=0}^{\infty }T(n)Z^{n}\ .}$

이 멱급수는 유리함수의 분야에 걸쳐 대수적이며, 방정식을^[13] 만족합니다.

${\displaystyle Z+(1+Z)^{2}t+(1+Z)^{3}t^{2}=0}$

조합적 게임이론에서

${\displaystyle n}$ = $0 {\$displaystyle t_{n}=0}인 악수 집합(numbers n$${\$displaystyle$n})은 nim-addition(bitwise exclusive or)에서 음이 아닌 정수의 부분 공간을 형성합니다. 카일 게임의 경우 게임에서 소수의(확실히 많은) 포지션에 대해 사악한 님 값이 발생하며, 나머지 모든 포지션은 끔찍한 님 값을 가집니다.

프루엣-태리-에스카트 문제

프루엣-태리-에스콧 문제는 양의 정수 N과 음이 아닌 정수 k가 주어졌을 때 집합 S = {0, 1, ..., N-1}을 k까지 같은 거듭제곱의 합을 갖는 두 개의 서로소 부분집합 S와 S로 분할하는 것으로 정의할 수 있습니다. 즉,

${\displaystyle \sum _{}}{\displaystyle \underset{}{}\underset{}{}}$x $∈$ S 0${\displaystyle \underset{}{}}$x${\displaystyle \underset{}{}\underset{}{{}_{}}}$ ${\displaystyle \underset{}{=}\underset{}{}}$∑ x ∈ S 1 x$i {\displaystyle$\sum _{x\in S_{0}}${\displaystyle \underset{}{x}}$^{i}=\sum _{x\in S_{1}}x^{i}}.

N이 2의^k+1 배수이면 다음과 같은 해가 나옵니다.

• S는 t = 0인 S의 정수 n으로 구성됩니다.
• S는 t = 1인 S의 정수 n으로 구성됩니다.

예를 들어, N = 8과 k = 2의 경우,

0 + 3 + 5 + 6 = 1 + 2 + 4 + 7,

0² + 3² + 5² + 6² = 1² + 2² + 4² + 7².

N이 2의^k+1 배수여야 한다는 조건은 엄격하게 필요하지 않습니다. 해가 존재하는 몇 가지 경우가 더 있습니다. 그러나 조건이 만족되면 산술 진행에서 N개 숫자로 이루어진 임의의 집합의 k번째 거듭제곱들의 집합은 같은 합으로 두 집합으로 분할될 수 있습니다. 이것은 산술 진행의 n번째 요소를 나타내는 이항에 적용된 이항 정리에 의해 주어진 확장으로부터 직접적으로 이어집니다.

튀-모르 수열과 프루엣-타리-에스콧 문제를 두 부분 이상으로 분할하는 일반화에 대해서는 볼커, 오프너, 리치먼, 자라, "프루엣-타리-에스콧 문제와 튀-모르 수열을 일반화"를 참조하십시오.^[14]

프랙탈과 거북이 그래픽

거북이 그래픽을 사용하여 오토마톤을 시퀀스로 프로그래밍하면 곡선을 생성할 수 있습니다. 프로그램 상태를 선택하기 위해 Thue-Morse 시퀀스 멤버를 사용하는 경우:

• t(n) = 0인 경우 한 단위씩 이동합니다.
• t(n) = 1인 경우, π/3 라디안(60°) 각도만큼 회전합니다.

결과적인 곡선은 유한한 영역을 포함하는 무한한 길이의 프랙털 곡선인 코흐 곡선으로 수렴합니다. 이것은 Thue-Morse Sequence의 프랙탈 특성을 보여줍니다.^[15]

다음 지침을 사용하여 정확하게 곡선을 그릴 수도 있습니다.^[16]

• t(n) = 0인 경우, π 라디안(180°) 각도만큼 회전,
• t(n) = 1인 경우 한 단위씩 이동한 다음 π/3 라디안의 각도만큼 회전합니다.

공평한 순서

공정한 나눗셈에 관한 그들의 책에서 스티븐 브람스와 앨런 테일러는 Thue-Morse 수열을 언급했지만, 그것을 그렇게 식별하지는 않았습니다. 브람스와 테일러는 아이템의 상대적 가치에 동의하는 두 당사자 사이에 경쟁적인 아이템 더미를 할당할 때, 한 당사자가 다른 당사자보다 먼저 선택할 때 내재하는 편애를 피하기 위한 방법으로 균형적인 교대 또는 교대라는 방법을 제안했습니다. 이혼한 부부가 공동소유 물건의 분배에 있어서 어떻게 공정한 해결을 할 수 있는지를 보여준 사례가 있습니다. 각 당사자는 교대로 선택 과정의 서로 다른 지점에서 첫 번째 선택자가 됩니다. 앤은 한 가지 물건을 고르고, 벤은 한 가지 물건을 고르고,^[17] 앤은 한 가지 물건을 고릅니다.

라이오넬 레빈과 캐서린 E. 에티오피아 만찬과 같은 공동 식사를 공정하게 할당하는 방법에 대한 논의에서 Stange는 먼저 이동하는 이점을 줄이기 위한 방법으로 Thue-Morse 시퀀스를 제안했습니다. 그들은 "Thue-Morse 순서가 공정한 결과를 낳는 경향이 있다는 직관을 정량화하는 것이 흥미로울 것"이라고 제안했습니다.^[18]

Robert Richman은 이 문제를 해결했지만, 그 역시 Thue-Morse 시퀀스가 출판 당시에 그렇게 확인되지 않았습니다.^[19] 그는 시퀀스 T를_n 간격 [0,1]의 단계 함수로 제시하고 Walsh 및 Rademacher 함수와의 관계를 설명했습니다. 그는 n번째 도함수가 T로_n 표현될 수 있음을 보여주었습니다. 결과적으로_n T에서 발생하는 스텝 함수는 n - 1차 다항식과 직교합니다. 이 결과는 함수가 평탄해짐에 따라 Tue-Morse로 수렴하는 수열을 사용하여 값이 단조적으로 감소하는 연속 함수로 표현되는 자원을 가장 공정하게 할당하는 것입니다. 비선형 농도 구배를 가진 카페에서 같은 강도의 커피를 따르는 방법을 보여준 예가 있어 대중 언론에 기발한 기사가 나왔습니다.^[20]

Joshua Cooper와 Aaron Dutle은 왜 Thue-Morse 순서가 이산형 사건에 대해 공정한 결과를 제공하는지를 보여주었습니다.^[21] 그들은 갈루아 결투를 하는 가장 공정한 방법을 생각했습니다. 그들은 각 사격 선수들이 똑같이 형편없는 사격 기술을 가지고 있습니다. 쿠퍼와 더틀은 각 결투 선수가 상대방의 우선적인 승리 확률이 자신의 승리 확률을 초과하는 즉시 사격 기회를 요구할 것이라고 가정했습니다. 그들은 결투 선수들의 타격 확률이 0에 가까워질수록 사격 시퀀스가 Thue-Morse 시퀀스로 수렴한다는 것을 증명했습니다. 그렇게 함으로써, 그들은 Thue-Morse 순서가 길이가ⁿ 2인 시퀀스 T뿐만_n 아니라 어떤 길이의 시퀀스에 대해서도 공정한 결과를 낳는다는 것을 증명했습니다.

따라서 수학은 목표가 공정성일 때 교대로 교대하는 대신 Thue-Morse 시퀀스를 사용하는 것을 지원하지만 이전의 턴은 나중의 턴과 단조적으로 다른 일부 의미 있는 품질(품질이 연속적으로^[19] 변하든 이산적으로 변하든)을 사용합니다.^[21]

스포츠 경기는 공평한 순서 문제의 중요한 부류를 형성하는데, 왜냐하면 엄격한 대체는 종종 한 팀에게 불공평한 이점을 주기 때문입니다. 이그나시오 팔라시오스-후에르타는 축구에서 승부차기 순서와 같은 다양한 토너먼트 대회의 사후 공정성을 향상시키기 위해 순차 순서를 Tue-Morse로 변경할 것을 제안했습니다.^[22] 그는 프로 선수들과 함께 일련의 현장 실험을 한 결과, 먼저 차는 팀이 ABAB(또는 T₁)를 사용하여 60%, ABBA(또는 T₂)를 사용하여 54%, 완전한 Thue-Morse(또는 T_n)를 사용하여 51%의 게임을 이겼다는 것을 발견했습니다. 결과적으로 ABBA는 FIFA(유럽 및 세계 선수권 대회)와 잉글랜드 연맹 프로 축구(EFL 컵)에서 광범위한 시험을 거치고 있습니다.^[23] ABBA 서브 패턴은 또한 테니스 타이브레이크의 공정성을 향상시키는 것으로 밝혀졌습니다.^[24] 경쟁 조정에서 T는₂ 4인승 콕스리스 경주용 보트에서 횡력(따라서 옆으로 움직이는 것)을 제거하는 유일한 좌현 및 우현 조정 승무원 배치이며, T는₃ 8인승 보트에서 움직이는 것을 피할 수 있는 4개의 장비 중 하나입니다.^[25]

선수 드래프트에서 공정성은 특히 중요합니다. 많은 프로 스포츠 리그들은 매 라운드마다 더 약한 팀들에게 더 이른 선택을 줌으로써 경쟁력 있는 동등성을 달성하려고 시도합니다. 반면 판타지 풋볼 리그는 수정해야 할 기존 불균형이 없기 때문에 종종 "뱀" 드래프트(포워드, 백워드 등)를 사용합니다₁.^[26] 이안 앨런(Ian Allan)은 "3라운드 역전"(전방, 후방, 후방, 전방₂ 등)이 더 공정할 것이라고 주장했습니다.^[27] 리치먼은 "캡틴 A"와 "캡틴 B"가 농구 거울 픽업 게임을 위해 편을 선택하는 가장 공정한 방법을₃ 제안했습니다. 주장 A는 첫 번째, 네 번째, 여섯 번째, 일곱 번째 선택을 하고 주장 B는 두 번째, 세 번째, 다섯 번째, 여덟 번째 선택을 합니다.^[19]

해시 충돌

Thue-Morse 시퀀스의 초기 2비트는^k 광범위한 클래스의 다항식 해시 함수 모듈로 2의 거듭제곱에 의해 0으로 매핑되며, 이는 해시 충돌로 이어질 수 있습니다.^[28]

역사

튜-모르 수열은 1851년 외젠 프루엣(Eugène Prouhet[fr])에 의해 처음 연구되었고,^[29] 그는 수론에 적용했습니다. 그러나 프루엣은 수열을 명시적으로 언급하지 않았습니다; 이것은 1906년 단어에 대한 조합론 연구를 발견하는 데 사용된 악셀 투에게 맡겼습니다. 이 수열은 1921년 마스턴 모스가 미분기하학에 적용하면서 세계적인 주목을 받기 시작했습니다. 이 수열은 전문적인 연구를 하는 수학자들에 의해서가 아니라 여러 번 독립적으로 발견되어 왔습니다. 예를 들어, 체스 그랜드 마스터이자 수학 선생님인 Max Euwe는 1929년에 체스에 적용된 응용 프로그램에서 이 수열을 발견했습니다: 정육면체가 없는 속성을 사용함으로써, 무브 반복을 무승부로 선언함으로써 무한히 길어지는 게임을 막기 위한 3중 반복 규칙을 피하는 방법을 보여주었습니다. 당시 규칙을 실행하려면 연속적인 동일한 이사회 상태가 필요했습니다. 연속적인 기준을 영원히 피할 수 있다는 것을 보여주기 때문에 규칙은 나중에 어느 시점에서든 세 번 반복되는 동일한 이사회 위치로 수정되었습니다.

참고 항목

• 데장 정리
• 파비우스 함수
• Thue-Morse 수열의 첫 번째 차이
• 회색코드^[30][31][32]
• 코모르니크–로레티 상수
• 프루엣-튜-모르상수

메모들

참고문헌

더보기

• Bugeaud, Yann (2012). Distribution modulo one and Diophantine approximation. Cambridge Tracts in Mathematics. Vol. 193. Cambridge: Cambridge University Press. ISBN 978-0-521-11169-0. Zbl 1260.11001.
• Lothaire, M. (2005). Applied combinatorics on words. Encyclopedia of Mathematics and Its Applications. Vol. 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. Cambridge: Cambridge University Press. ISBN 978-0-521-84802-2. Zbl 1133.68067.

외부 링크

Wikimedia Commons에는 Thue-Morse 시퀀스와 관련된 미디어가 있습니다.

• "Thue-Morse sequence", Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Weisstein, Eric W. "Thue-Morse Sequence". MathWorld.
• 알루슈, J.-P.; 샬릿, J.O. 유비쿼터스 프루엣-투에-모스 수열. (많은 응용프로그램 및 일부 이력 contains)
• Tue-Morse Sequence over (1,2) (OEIS에서 서열 A001285)
• OEIS 수열 A000069 (이상한 수: 이진 전개에서 홀수가 1인 수)
• OEIS 수열 A001969 (이음수: 이진 전개에서 1의 짝수를 갖는 수)
• Thue-Morse Sequence를 사용하여 아날로그 IP에서 DC 오프셋 드리프트의 영향을 줄입니다. Tue-Morse Sequence 의 기술적 응용
• MusiNum - The Music in the Numbers. Thue-Morse Sequence 및 관련 번호 시퀀스를 기반으로 자체 유사 음악을 생성할 수 있는 프리웨어.
• Parker, Matt. "The Fairest Sharing Sequence Ever" (video). standupmaths. Retrieved 20 January 2016.