투에-모스 수열
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
투에-모스 수열은 여러 가지 방법으로 정의할 수 있는 비트(0과 1)의 무한 수열이다. 이 수열은 이진법으로 표현된 숫자의 1의 개수가 홀수인지 짝수인지에 따라 결정되며, 점화식, L-시스템, 비트 단위 NOT 연산을 통해서도 정의할 수 있다. 투에-모스 수열은 제곱 반복은 많이 포함하지만, 세제곱 반복이나 겹치는 제곱 반복은 포함하지 않는 특성을 가지며, 조합론적 게임 이론, 프랙탈, 공정한 분배, 해시 충돌, 리만 제타 함수 등 다양한 분야에 응용된다. 이 수열은 1851년 외젠 프루에에 의해 처음 연구되었고, 악셀 투에와 마스턴 모스에 의해 널리 알려지게 되었다.
더 읽어볼만한 페이지
- 이진 수열 - 비트스트림 (컴퓨터 과학)
비트스트림은 일련의 비트로 구성된 데이터 스트림을 의미하며, FPGA 구성 데이터 설명, 수학적 특성 연구, 압축 알고리즘 코딩 등에 활용되고, 운영 체제는 바이트스트림 패러다임으로 변환하며, 흐름 제어를 통해 데이터 생성 속도와 소비 속도를 조절한다. - 홀짝성 - 패리티 비트
패리티 비트는 이진 데이터에서 1의 개수가 짝수인지 홀수인지 나타내는 비트로서, 오류 감지 및 수정에 사용되며, 통신 프로토콜과 RAID 시스템 등 다양한 분야에서 활용된다. - 홀짝성 - 반정수
반정수는 정수에 1/2을 더한 수로 표현되며, 정수와 함께 덧셈 연산에 대해 군을 형성하지만 환은 형성하지 않고, 양자역학, 페르미온의 스핀, 4차원 격자 포장 등 다양한 분야에 응용된다. - 고정점 - 도메인 이론
도메인 이론은 정보 조각과 부분 계산 결과로 해석되는 부분 순서 집합을 연구하여 정보 확장, 일관성 분석, 계산 과정의 수렴성 및 연속성을 형식화하는 분야로, 람다 대수 의미론 연구에서 동기를 얻어 컴퓨터 과학에 응용된다. - 고정점 - 브라우어르 고정점 정리
브라우어르 고정점 정리는 콤팩트 볼록 집합에서 자기 자신으로 가는 연속 함수는 반드시 고정점을 가진다는 정리로, 다양한 공간에서 여러 형태로 표현되며 함수해석학에서 중요한 역할을 한다.
투에-모스 수열 | |
---|---|
개요 | |
이름 | 투에-모스 수열 |
영어 이름 | Thue–Morse sequence |
별칭 | 프루헤-투에-모스 수열(Prouhet-Thue-Morse sequence) |
성질 | |
종류 | 무한 이진 수열 |
생성 규칙 | 보수화 및 연결 반복 |
OEIS | A010060 |
2. 정의
투에-모스 수열은 여러 가지 동등한 방법으로 정의할 수 있다.
2. 1. 직접 정의
''n''번째 원소 ''tn''을 계산하려면 ''n''을 이진수로 써야 한다. 이 이진 표현에서 1의 개수가 홀수라면 ''tn'' = 1이고, 짝수면 ''tn'' = 0이다.[20] 따라서 존 호턴 콘웨이는 ''tn'' = 1을 만족하는 수 ''n''을 ''불쾌한'' 수(''odious'' number영어, 홀수를 뜻하는 ''odd''에서 나왔다)라고 부르고 ''tn'' = 0일 때는 ''악한'' 수(''evil'' number영어, 짝수 ''even''때문)라고 불렀다. 다시 말해, ''n''이 악한 수일 때는 tn = 0이고 ''n''이 불쾌한 수일 경우에는 tn = 1이다.이 방법은 투에-모스 수열을 계산하는 빠른 방법이다. 먼저 ''t0'' = 0에서 시작하고, 각각의 ''n''에 대해 ''n''의 이진 표기에서 ''n'' - 1의 이진 표기와 다른 최상위 비트를 찾는다. 이 비트가 짝수 인덱스에 있다면, ''tn''은 ''t''''n'' - 1과 다르고, 아니면 ''t''''n'' - 1과 같다.
2. 2. 점화식
''n''번째 원소 ''tn''을 계산하려면 ''n''을 이진수로 써야 한다. 이 이진 표현에서 1의 개수가 홀수라면 ''tn'' = 1이고, 짝수면 ''tn'' = 0이다.[20] 따라서 존 호턴 콘웨이는 ''tn'' = 1을 만족하는 수 ''n''을 ''불쾌한'' 수(odious number|오디어스 수영어, 홀수를 뜻하는 ''odd''에서 나왔다)라고 부르고, ''tn'' = 0일 때는 ''악한'' 수(evil number|이블 수영어, 짝수 ''even''때문)라고 불렀다. 다시 말해, ''n''이 악한 수일 때는 tn = 0이고 ''n''이 불쾌한 수일 경우에는 tn = 1이다.투에-모스 수열은 모든 음이 아닌 정수 ''n''에 대하여 다음 점화식을 만족시키는 수열 ''tn''이다.[20]
t0 | = 0 |
t2n | = tn |
t2n+1 | = 1 − tn |
2. 3. L-시스템
투에-모스 수열은 모픽 단어이며,[21] 다음의 린덴마이어 시스템으로 표현할 수 있다.변수 | 0, 1 |
---|---|
상수 | 없음 |
시작 | 0 |
규칙 | (0 → 01), (1 → 10) |
2. 4. 비트 단위 NOT을 사용한 특성화
투에-모스 수열은 첫 번째 원소는 0이고, 처음 2n개의 원소가 결정되면, 다음 2n개의 원소는 이전 원소들의 비트 단위 NOT 연산으로 생성되는 재귀적인 수열이다.처음 몇 단계를 자세히 설명하면 다음과 같다.
- ''T''0 = 0에서 시작한다.
- 0의 비트 단위 NOT을 취하면 1이다.
- 이를 연결하면 ''T''1 = 01이다.
- 01의 비트 단위 NOT을 취하면 10이다.
- 이를 연결하면 ''T''2 = 0110이다.
- 0110의 비트 단위 NOT을 취하면 1001이다.
- 이를 연결하면 ''T''3 = 01101001이다.
- 이와 같은 방식으로 계속 진행된다.
''T''n의 값은 다음과 같다.
n | Tn |
---|---|
0 | 0 |
1 | 01 |
2 | 0110 |
3 | 01101001 |
4 | 0110100110010110 |
5 | 01101001100101101001011001101001 |
6 | 0110100110010110100101100110100110010110011010010110100110010110 |
2. 5. 무한 곱
:이때, t|티영어j는 j = 0에서 시작했을 때 j번째 원소이다.
3. 특성
투에-모스 수열은 여러 가지 흥미로운 특성을 갖는다.
투에-모스 수열은 새로운 부분을 이전 부분에 비트 단위 NOT 연산을 취해 만들어지고, 이 과정이 반복되므로, 수열은 ''이중 반복''(반복되는 연속적인 수열)으로 가득하다. 즉, 특정 문자열 ''X''에 대해 ''XX'' 형태의 반복이 많이 나타난다. 그러나 ''XXX'' 형태의 ''삼중 반복''이나 0''X''0''X''0 또는 1''X''1''X''1 형태의 ''겹치는 이중 반복''은 나타나지 않는다.[22][23] 임계 지수는 2이다.[22]
투에-모스 수열은 고른 재귀 단어이다. 즉, 어떤 유한한 문자열 ''X''가 주어지면, 그 문자열이 특정 길이 ''nX''인 모든 블록에 나타나는 ''nX''가 존재한다.[24] 그러나 투에-모스 수열은 주기 수열이 아니고, 부분적 주기 수열(일부 비주기적인 초기값 이후 주기적이 되는 수열)도 아니다.[25]
3. 1. 제곱 반복과 비주기성
투에-모스 수열은 ''XX'' 형태의 제곱 반복(square영어)은 많이 포함하지만, ''XXX'' 형태의 세제곱 반복(cube영어)이나 겹치는 제곱 반복은 포함하지 않는다.[22][23] 여기서 ''X''는 임의의 문자열을 의미한다. 예를 들어, 일 때, 제곱 반복 는 에서 16번째 비트부터 나타난다. 에 있는 제곱 반복의 길이는 또는 형태이다.투에-모스 수열은 주기 수열이 아니면서도 균등하게 반복되는 특성을 가지고 있다.[25] 어떤 유한한 문자열 ''X''가 주어지면, ''X''가 길이 ''nX''인 모든 블록에 나타나는 어떤 길이 ''nX''가 존재한다.[24]
모든 ''n'' > 1에 대해서 ''T''2''n''은 회문이다. 또한, ''q''''n''을 ''T''2''n''에서 연속적인 0사이의 1을 세어 얻은 단어라고 할 때, 이 단어는 회문이면서 제곱 반복이 없는 단어이다.
3. 2. 회문 구조
모든 ''n'' > 1에 대해 ''T''2''n''은 회문이다. 예를 들어 T2 = 0110, T4 = 0110100110010110 과 같이, n의 값이 커져도 앞부분과 뒷부분이 같은 회문 형태가 유지된다.나아가, q''n''을 ''T''2''n''에서 연속적인 0 사이의 1을 세어 얻어지는 단어로 정의한다. 예를 들어, ''q''1 = 2이고, ''q''2 = 2102012 등과 같이 나타낼 수 있다.
Tn 자체는 겹치는 반복이 없기 때문에, qn 역시 회문이면서 이중 반복 없는 단어가 된다.[22][23]
3. 3. 투에-모스 사상
투에-모스 사상(Thue–Morse morphism영어)은 이진 수열의 집합에서 모든 0을 01로, 모든 1을 10으로 바꾸어 자기 자신에게로 보내는 함수 ''f''로 정의된다.[26] ''T''가 투에-모스 수열이라면, ''f''(''T'')는 다시 ''T''가 된다. 즉, ''T''는 ''f''의 고정점이다. ''f''는 자유 모노이드 {0,1}∗에서 ''T''를 고정점으로 갖는 연장 가능 사상이다. ''T''는 ''f''의 유일한 고정점이며, 유일한 다른 고정점은 ''T''의 비트 단위 NOT을 취한 것으로, (1,0)에서 시작하는 투에-모스 수열이다. 이 성질은 오토마타 수열의 개념으로 일반화할 수 있다.3. 4. 생성 함수
이진체에서의 ''T''의 ''생성 급수''는 형식적 멱급수이다.:
이 멱급수는 다음 방정식을 만족하는 유리 함수의 체에 대한 대수적이다.[9]
:
4. 응용
투에-모스 수열은 다양한 분야에서 응용되고 있다.
- 조합론적 게임 이론: 님 덧셈과 케일스 게임에서 투에-모스 수열의 악한 수(''t''''n''=0인 수 ''n'')가 중요한 역할을 한다.[1]
- 프로헷-테리-에스콧 문제: 이 문제는 거듭제곱의 합이 같은 두 서로소 부분집합을 찾는 문제인데, 투에-모스 수열을 이용하여 해를 구할 수 있다.[28]
- 프랙탈과 거북이 그래픽: 거북이 그래픽에서 투에-모스 수열을 이용하면 코흐 눈송이와 같은 프랙탈 곡선을 만들 수 있다.[10]
- 공평한 분배: 스티븐 브람스와 앨런 테일러는 논쟁이 되는 아이템을 공정하게 분배하는 방법으로 투에-모스 수열을 활용한 "균형 교대" 방식을 제안했다.[11] 라이오넬 레빈과 캐서린 E. 스탱은 에티오피아 식사와 같이 함께 먹는 음식을 공정하게 분배하는 데 투에-모스 수열을 제안했다.[12] 조슈아 쿠퍼와 애런 더틀은 투에-모스 순서가 이산 사건에서 공정한 결과를 제공하는 이유를 밝혔다.[12]
- 스포츠 경기: 이그나시오 팔라시오스-우에르타는 축구 승부차기 순서를 투에-모스 수열로 변경할 것을 제안했으며, 이는 실제로 FIFA(유럽 및 세계 선수권 대회) 등에서 시험되고 있다.[13][14] 경쟁 조정에서도 투에-모스 수열을 활용하여 횡력을 제거하거나 흔들림을 방지한다.
- 선수 드래프트: 선수 드래프트에서 약팀에게 먼저 선택권을 주는 방식의 공정성을 높이기 위해 투에-모스 수열을 활용할 수 있다.[13][14][11]
- 해시 충돌: 투에-모스 수열의 초기 비트는 특정 다항식 해시 함수에서 해시 충돌을 유발할 수 있다.[15]
- 리만 제타 함수: 투에-모스 수열의 항을 계수로 하는 디리클레 급수의 특정 선형 결합은 리만 제타 함수와 관련된 항등식을 생성한다.[16]
4. 1. 조합론적 게임 이론
악한 수(''t''''n''=0인 수 ''n'')의 집합은 님 덧셈(비트 단위 배타적 논리합) 하에서 음이 아닌 정수들의 부분 공간을 형성한다. 케일스 게임에서, 악한 수 님 값은 게임에서 몇몇(유한 개) 위치에서 나타나고, 나머지 모든 위치는 불쾌한 님 값을 갖는다.[1]4. 2. 프로헷-테리-에스콧 문제
프로헷-테리-에스콧 문제(Prouhet–Tarry–Escott problem영어)는 양의 정수 ''N''과 음이 아닌 정수 ''k''가 주어졌을 때, 집합 ''S'' = { 0, 1, ..., ''N''-1 }를 ''k''까지 거듭제곱의 합이 같은 두 서로소 부분집합 ''S''0와 ''S''1으로 분할하는 문제이다. 이때 ''i''는 1에서 ''k''까지의 모든 정수를 의미한다.:
이 문제는 ''N''이 2''k''+1의 배수일 때 다음과 같은 해를 가진다.
- ''S''0은 ''S''에서 ''tn'' = 0인 정수 ''n''으로 이루어져 있다.
- ''S''1은 ''S''에서 ''tn'' = 1인 정수 ''n''으로 이루어져 있다.
예를 들어, ''N'' = 8이고 ''k'' = 2일 때, 다음과 같다.
: 0 + 3 + 5 + 6 = 1 + 2 + 4 + 7
: 02 + 32 + 52 + 62 = 12 + 22 + 42 + 72
''N''이 2''k''+1의 배수여야 한다는 조건은 반드시 필요한 것은 아니다. 해가 존재하는 다른 경우가 일부 존재하지만, 이 조건은 더 강한 특성을 보장한다. 조건을 만족한다면, 등차 수열의 수 ''N''개의 ''k''제곱을 한 집합은 합이 같은 두 집합으로 분할 할 수 있다. 이것은 등차 수열의 ''n''번째 원소를 나타내는 이항에 적용된 이항 정리에 의해 주어진 확장에서 직접적으로 따른다.
투에-모스 수열의 일반화와 두 부분 이상으로 분할하는 프로헷-테리-에스콧 문제에 대해서는 Bolker, Offner, Richman 그리고 Zara의 "The Prouhet–Tarry–Escott problem and generalized Thue–Morse sequences"을 보라.[28]
4. 3. 프랙탈과 거북이 그래픽
거북이 그래픽을 사용할 때, 오토마톤이 수열로 프로그래밍 되어있다면 곡선이 만들어진다. 투에-모스 수열의 요소는 프로그램 상태를 만들기 위해 사용된다.[10]- ''t''(''n'') = 0일 때, 한 단위 앞으로 이동한다.
- ''t''(''n'') = 1일 때, 반시계 방향으로 π/3 라디안(60°)만큼 회전한다.
나타나는 곡선은 유한한 면적을 가지면서 곡선의 길이가 무한한 프랙탈 곡선인 코흐 눈송이로 수렴한다. 이것은 투에-모스 수열의 프랙탈 성질을 나타낸다.[10]
다음 지침을 사용하여 곡선을 정확하게 그리는 것도 가능하다.[10]
- ''t''(''n'') = 0이면, π 라디안(180°) 각도로 회전한다.
- ''t''(''n'') = 1이면, 한 단위 앞으로 이동한 다음, π/3 라디안 각도로 회전한다.
4. 4. 공평한 분배
스티븐 브람스와 앨런 테일러는 공정한 분배 문제에 대한 저서에서, 논쟁이 되는 아이템을 분배할 때 먼저 선택하는 쪽이 유리한 문제를 해결하기 위해 "균형 교대" 방식을 제안했다. 이 방식은 투에-모스 수열을 명시적으로 언급하지는 않았지만, 앤과 벤이 번갈아 가며 선택하되, 앤-벤-벤-앤 순서로 선택하는 방식을 예시로 들었다.[11]라이오넬 레빈과 캐서린 E. 스탱은 에티오피아 식사와 같이 함께 먹는 음식을 공정하게 분배하는 방법에 대해 논의하면서, 먼저 선택하는 것의 이점을 줄이기 위해 투에-모스 수열을 제안했다. 그들은 투에-모스 순서가 공정한 결과를 낳는 경향이 있다는 직관을 정량화하는 것이 흥미로울 것이라고 언급했다.[12]
로버트 리치먼은 투에-모스 수열을 [0,1] 구간의 계단 함수로 제시하고, 왈쉬 함수 및 라데마허 함수와의 관계를 설명했다. 그는 자원의 가치가 단조롭게 감소하는 연속 함수로 표현될 때, 함수가 더 평평해질수록 투에-모스 수열을 사용하는 것이 가장 공정하게 자원을 할당하는 방법임을 보였다. 예를 들어, 커피의 농도 구배가 비선형인 커피 통에서 동일한 농도의 커피 잔을 따르는 방법을 제시했다.[11]
조슈아 쿠퍼와 애런 더틀은 투에-모스 순서가 이산 사건에 대해 공정한 결과를 제공하는 이유를 밝혔다.[12] 그들은 갈루아 결투에서 각 결투자들의 명중 확률이 0에 가까워질수록 발사 순서가 투에-모스 수열로 수렴한다는 것을 증명했다. 이를 통해 투에-모스 순서가 임의의 길이의 수열에 대해서도 공정한 결과를 생성한다는 것을 입증했다.[12]
이러한 연구 결과는, 먼저 하는 턴이 나중에 하는 턴보다 유리하고 그 유리함이 연속적이든[11] 이산적이든 상관없이 변한다면, 투에-모스 수열을 사용하는 것이 공정성을 보장하는 수학적으로 뒷받침되는 방법임을 보여준다.[12]
스포츠 경기에서는 엄격한 교대가 한 팀에게 불공정한 이점을 주는 경우가 많기 때문에, 공정한 순서 결정이 중요하다. 이그나시오 팔라시오스-우에르타는 축구 승부차기 순서를 투에-모스 수열로 변경할 것을 제안했다.[13] 그는 프로 선수들을 대상으로 한 실험에서 ABAB(또는 ''T''1) 방식에서는 첫 번째 팀이 60%, ABBA(또는 ''T''2) 방식에서는 54%, 전체 투에-모스 수열(또는 ''T''n) 방식에서는 51%의 승률을 보였다는 것을 발견했다. ABBA 방식은 FIFA(유럽 및 세계 선수권 대회)와 잉글리시 축구 연맹 프로 축구(EFL 컵)에서 광범위한 시험을 거치고 있다.[14] ABBA 패턴은 테니스 타이브레이크의 공정성도 향상시키는 것으로 나타났다.[14] 경쟁 조정에서 ''T''2는 네 명의 무타수 경주용 보트에서 횡력을 제거하는 유일한 배열이며, ''T''3는 여덟 명의 보트에서 흔들림을 방지하는 네 가지 리그 중 하나이다.
선수 드래프트에서도 공정성이 중요하다. 많은 프로 스포츠 리그는 약팀에게 먼저 선택권을 주는 방식으로 경쟁적 패리티를 달성하려 한다. 판타지 풋볼 리그는 "뱀" 드래프트(''T''1)를 사용하는 경우가 많지만,[13] 이안 앨런은 "3라운드 반전"(''T''2)이 더 공정하다고 주장했다.[14] 리치먼은 길거리 농구 팀을 선택할 때 ''T''3를 반영하는 것이 가장 공정하다고 제안했다.[11]
4. 5. 해시 충돌
투에-모스 수열의 초기 2k 비트는 광범위한 클래스의 다항식 해시 함수에 의해 0으로 매핑되는데, 이는 해시 충돌을 유발할 수 있다.[15]4. 6. 리만 제타 함수
투에-모스 수열의 항을 계수로 하는 디리클레 급수의 특정 선형 결합은 리만 제타 함수와 관련된 항등식을 생성한다.[16] 예를 들어 다음과 같다.:
여기서 는 투에-모스 수열의 항이다. 실제로 실수부가 보다 큰 모든 에 대해 다음이 성립한다.
:
5. 역사
1851년 외젠 프루에(Eugène Prouhet)가 정수론에 적용시키면서 처음으로 연구를 시작하였다.[17] 그러나 프루에는 이 수열을 명시적으로 언급하지 않았다. 1906년 악셀 투에가 이를 단어의 조합론 연구의 기초를 세우는 데 사용하였다. 1921년 마스턴 모스가 미분기하학에 적용하면서 전 세계적으로 주목을 받게 되었다.
이 수열은 종종 동시 발견되었으며, 항상 전문 연구 수학자에 의해서 발견된 것은 아니다. 예를 들어, 체스 그랜드마스터이자 수학 교사인 막스 오이베는 1929년 체스에 적용하면서 이 수열을 발견했다. 그는 이 수열의 큐브-프리(cube-free) 속성을 사용하여 무한히 지속되는 게임을 방지하기 위한 세 번 반복 규칙을 어떻게 우회할 수 있는지 보여주었다. 당시에는 동일한 보드 상태가 연속으로 나타나야 규칙이 발동되었지만, 수열은 연속적인 기준을 영원히 피할 수 있음을 보여주면서, 이후 규칙은 동일한 보드 위치가 세 번 나타나면 규칙이 발동되도록 개정되었다.
참조
[1]
OEIS
Thue-Morse sequence
[2]
harvtxt
[3]
harvtxt
[4]
harvtxt
[5]
harvtxt
[6]
harvtxt
[7]
harvtxt
[8]
harvtxt
[9]
harvtxt
[10]
웹사이트
Thue-Morse Navigating Turtles
http://blog.zacharya[...]
2012-01-23
[11]
harvtxt
[12]
harvtxt
[13]
웹사이트
Fantasy Draft Types
http://www.nfl.com/f[...]
[14]
웹사이트
Third-Round Reversal Drafts
https://www.fantasyi[...]
2020-09-01
[15]
간행물
Where to Use and How not to Use Polynomial String Hashing
https://ioinformatic[...]
2013
[16]
간행물
Linear Combinations of Dirichlet Series Associated with the Thue-Morse Sequence
[17]
문서
The ubiquitous Prouhet-Thue-Morse sequence by Jean-Paul Allouche and Jeffrey Shallit
https://cs.uwaterloo[...]
[18]
간행물
Gray codes and the Thue-Morse-Hedlund sequence
1992
[19]
웹사이트
On the Asymptotic Relative Change for Sequences of Permutations
https://www.research[...]
2021-01-31
[20]
harvtxt
[21]
harvtxt
[22]
harvtxt
[23]
harvtxt
[24]
harvtxt
[25]
harvtxt
[26]
harvtxt
[27]
harvtxt
[28]
저널 인용
The Prouhet –Tarry –Escott problem and generalized Thue –Morse sequences
2016
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com