원탁에 덜 혼란

Question

이것은 원탁에서 Super-derangement 의 더 어려운 변형입니다 .

---

16 개의 좌석이있는 원형 테이블이 있으며, 각 좌석은 시계 방향으로 1 ~ 16으로 표시됩니다. 또한 16 명의 사람이 있으며 각 사람은 1에서 16까지의 고유 한 정수가 지정됩니다.

이제 16 명이 테이블에 둘러 앉아

1. 정확히 한 사람이 자신의 레이블에 앉고
2. 테이블이 회전되면 위의 조건은 가능한 모든 테이블 회전에 대해 참으로 유지됩니다.

예를 들어 테이블은 다음과 같이 레이블이 지정됩니다.

    16 1    
  15     2  
 14       3 
13         4
12         5
 11       6 
  10     7  
    9  8    

사람들은 다음과 같이 앉을 수 있습니다.

    2  1    
  4      3  
 6        5 
8          7
10         9
 12       11 
  14     13  
    16 15    

조건 1을 충족하지만 조건 2를 충족하지 않는 경우 테이블을 시계 반대 방향으로 한 단계 회전하면 3과 12가 모두 올바르게 장착됩니다.

이게 가능해? 다른 가치에 대해 가능합니까?$n$,와 함께 $n$ 사람과 $n$-좌석 테이블?

Answer 1

n이 홀수이면 가능합니다.
n이 홀수이면 사람 1을 좌석 1, p2 @ s3, p3 @ s5 등에 배치 할 수 있습니다.이 배열이 원하는 속성을 갖는 것은 분명합니다.
n이 짝수이면 필요한 속성이있는 배열에서 각 쌍 pi @ sj에 대한 오프셋 ij 집합이 집합이어야합니다.$\{0,1,2,...,n-1\}$모듈로 n. 하지만 합계,$n(n-1)/2$,이 중 n이 짝수이면 n의 배수가 아닙니다. 동시에 n 명의 순열에 대해이 합계는 0 mod n, 모순이라는 것을 쉽게 알 수 있습니다.

Answer 2

@PaulPanzer의 간결한 대답은 모든 두드러진 점을 언급하지만 실제 퍼즐 풀기 (재미있는 부분)는 "보기 쉽다"안에 숨겨져있는 것 같습니다. :-) 그래서, 여기에 덜 정교한 접근 방식이 있습니다. (물론 최종 결과는 동일합니다.)

우리는 사람들의 좌석과의 거리에 대해 이야기하고 있으므로 자신의 좌석에서 사람의 시계 방향 거리를 측정 값으로 사용합시다.

또한 테이블을 여러 번 돌아다녀도 아무 것도 변경되지 않으므로 모든 수학 "모듈로 16"을 수행해야합니다. 즉, 어떤 숫자가 주어지면 0 사이의 값을 얻을 때까지 16을 더하거나 뺄 것입니다. 및 15.

이제 한 사람이 다른 사람과 자리를 바꾸면 반대 방향으로 이동하므로 한 사람의 시계 방향 거리는 다른 사람의 시계 방향 거리가 감소하는 것과 정확히 같은 양 (모듈로 16)만큼 증가합니다.

이것은

2 인 좌석 교환은 전체 그룹의 시계 방향 총 거리 (모듈로 인원수)를 변경하지 않습니다.

그러나 우리는 2 인 스왑을 사용하여 가능한 모든 좌석 주문을 구성 할 수 있습니다! 이것은

가능한 모든 좌석 순서에서, 좌석에서 시계 방향으로 결합 된 사람의 거리는 항상 동일합니다 (모듈로 인원 수).

또한 모든 사람을 각자의 자리에 앉힐 수 있기 때문에

그 숫자는 0입니다.

이를 통해 우리는 첫 번째 질문을 쉽게 해결할 수 있습니다. 16 명과 같은 좌석 배치는

불가능한. 좌석에서 사람들의 시계 방향 총 거리는$\sum_{n=0}^{15}n = 120$, 이는 8 (0이 아님) 모듈로 16입니다.

N 명의보다 일반적인 솔루션을 위해 우리는 정체성을 사용할 수 있습니다. $\sum_{n=0}^{N-1}n = \frac{N(N-1)}{2}$ N :

"Half N"에 N-1 (홀수)을 곱하면 N으로 나눌 때 항상 N / 2의 0이 아닌 나머지가 남습니다.

홀수 N의 경우 상황이 다릅니다.

N-1은 짝수이므로 $\frac{N-1}{2}$ 는 정수이고 따라서 합계는 항상 N의 배수, 즉 0 모듈로 N입니다.

이것은

홀수 N의 경우 이러한 좌석 순서는 항상 존재합니다.

이러한 좌석 순서를 구성하려면

모든 사람을 다음과 같은 자리에 앉히십시오. $2\times$ 그들의 "이름", 모듈로 N.

예를 들어 N = 5를 선택하면 다음과 같은 순서가됩니다.

    1 3
  5 2-> 5 1
   4 3 2 4

물론이 좌석 순서를 회전 및 / 또는 미러링하면 가능한 해결책이 제공됩니다.