원 안에 동전 뒤집기

Question

우리는 모두 원 안에 놓인 N 개의 동전 세트를 가지고 있습니다. 그들은 모두 "꼬리"를 앞면으로 가지고 있습니다. 동전은 모두 구별되며 숫자 (1,2,3 ... N)가 적혀 있습니다.

움직일 때마다 3 개의 연속 동전을 뒤집습니다. 즉, 다음을 고려하십시오.

HHHTT

동전 3,4, 5를 뒤집기로 결정하면 HHTHH

이제 N 개의 고유 한 동전의 2 ^ N 개의 고유 한 헤드-테일 순열이있을 수 있습니다.

1. 초기 모든 꼬리 순열에서이 N 코인의 (2 ^ N) 앞면 순열 중 하나에 도달 할 수있는 유한 한 이동 집합이 있음을 증명 / 반증합니다.

또한 순열에 도달하는 것이 실제로 가능하다면 초기 모든 꼬리 순열에서 순열에 도달하는 데 필요한 최대 이동 횟수는 얼마입니까?

더 명확히하기 위해, 예를 들어 N이 3이면이 3 개의 동전의 2 ^ 3 개의 고유 한 순열은 다음과 같습니다.

TTT

TTH

THT

THH

HHH

HHT

HTH

HTT

Answer 1

가정하자 $N \geq 3$그렇지 않으면 문제가 잘 정의되지 않았습니다.

파트 1 :

동전의 끝 위치는 동전이 얼마나 많이 뒤집 혔는지에 따라 달라집니다 (짝수 뒤집기, T, 홀수, H).

따라서 동작 (3 번의 플립으로 구성)은 교환 적입니다. 또한 움직임은 분명히 자기 반전이므로 같은 움직임을 두 번 할 필요가 없습니다. 따라서 우리는 (순서가없는) 이동 위치 세트에만 관심이 필요합니다.$2^N$).

모든 위치에 도달 할 수없는 경우 두 개의 다른 이동 세트가 동일한 결과를 제공해야합니다. 그러나 이는 이러한 이동 세트 간의 대칭 차이 (XOR)가 모든 T로 구성을 제공해야 함을 의미합니다. 따라서 우리는 대신 모든 T

를 제공하는 비어 있지 않은 이동 세트가 있는지 물어볼 수 있습니다. 모든 이동 세트에 대해 각 동전이 뒤집힐 것입니다. 0 ~ 3 회. 또한 인접한 동전의 뒤집기 횟수는 0 또는 1만큼만 달라야합니다.$x$ 그리고 아닙니다 $x + 1$그 반대의 경우도 마찬가지입니다.) 따라서 모든 T를 얻으려면 뒤집기 횟수가 모두 0이거나 모두 2 여야합니다. 모두 0은 빈 이동 세트에서만 가능합니다. 2는 어떻습니까?

각 이동은 3 개의 동전을 뒤집기 때문에 총 뒤집기 횟수는 3의 배수 여야합니다. 따라서 2 개를 모두 얻는 것은 불가능합니다.$N$ 3의 배수입니다. $N$3의 배수입니다. 모든 동전은 세 번째 위치마다 움직여서 뒤집을 수 있습니다. 그런 다음 동일한 작업을 다시 수행 할 수 있지만 1만큼 이동하여 다시 뒤집습니다.

따라서 모든 종료 위치는 다음과 같은 경우에만 도달 할 수 있습니다.$N$3으로 나눌 수 없습니다.

파트 2 :

모든 위치에 도달 할 수 있으면 모든 이동 세트가 다른 위치에 도달합니다. 특히 모든 이동 위치 집합은 다음에서 특정 종료 위치에 도달합니다.$N$다른 위치는 그보다 더 많은 움직임이 필요하지 않습니다. 이 특정 위치는 실제로 각 동전을 3 번 뒤집기 때문에 모두 H입니다.

주어진 종료 위치에 대한 이동 세트를 빠르게 계산하려면 먼저 동전 1을 뒤집는 이동 세트를 계산하는 것이 좋습니다. 그런 다음이 이동 세트를 이동하여 단일 동전을 뒤집는 방법을 알고 있습니다. 그런 다음 단일 동전 이동 세트 (대칭 차이 / XOR 포함)를 결합하여 결과를 계산할 수 있습니다.

Answer 2

덜 "수학적"접근 방식 :

임의의 구성에 도달하는 문제는 정확히 하나의 동전을 뒤집는 일련의 움직임과 동일하다는 것이 분명합니다.

이제 그것을 찾는 방법 :

시퀀스 1,2,4,5,7, ...을 사용하여 필요한 플립 시퀀스를 쉽게 구성 할 수 있습니다 (숫자는 시작 동전에 해당하고 1은 동전 1,2,3을 뒤집는 것을 의미합니다). 이것은 동전 2 (N = 3k + 1) 또는 N (N = 3k + 2)을 뒤집을 것입니다. 구성은 분명합니다. 첫 번째 이동으로 앞면으로 설정하는 동전 1로 시작하고 나머지는 계속 뒤집어서 원의 "끝"을 향해 전파되는 앞면이 1-2 개뿐입니다. 이 머리가 (거의) 첫 번째 머리를 만나면 마지막 뒤집기를 수행하십시오. N = 3k + 1을 사용하면 끝에 1 개의 앞면을 얻고 결국 동전 2를 뒤집습니다. N = 3k + 2이면 끝 전에 앞면 1 개를 얻고 동전 N 만 뒤집습니다. N = 3k에서는 동전 2 개를 얻습니다. 끝과 모든 꼬리에 도달합니다. 단일 "헤드"로 남겨두기 위해 이러한 동전을 "압착"할 수 없기 때문에 모든 구성에 도달 할 수는 없습니다.

이제 최악의 경우 :

모든 머리를 얻으려면 모든 동전을 1 ~ 3 번 뒤집어 야합니다. N = 3k + 1 또는 2로 모든 동전을 1 번 뒤집을 수는 없습니다. 동전 X가 3 번 뒤집혔다면, 동전 X + 1은 이미 2 번 뒤집 혔고 한 번 더 뒤집어 야합니다. 이니셜의 모든 꼬리에서 모든 앞면을 얻으려면 모든 동전을 3 번 뒤집어 야합니다.