예전에 올라온 도쿄대 그래프 문제입니다. <figure 1>같은 규칙을 사용하여 흰돌 1개부터 시작하여 오직 흰돌로만 이루어지고 edge로 일렬로 이어진 봉모양의 그래프를 만들었을 때 이 때의 n값(흰돌의 총개수)의 필요충분 조건을 묻는 문제였습니다.
<figure 1>
어떤분께서 흰돌 2개의 원배열에서 시작하여 규칙2만 적용하는 것이 원문제의 흰돌 1개로 시작하여 규칙 1,2를 적용하는 것과 동치임을 보여 주셨습니다.
<figure 2>는 규칙의 가능한 경우를 모두 적어 놓았는데 보시면 V자로 체크한 돌을 제거하여 나온 파란색 박스 부분이 기존의 문제와 동일하게 배열됨을 보실 수 있습니다. 따라서 이 문제는 흰색으로만 이루어진 원배열을 만들 수 있느냐로 환원됩니다. (원래 없어야 될 돌을 맨아래로 놓아 경우의 수를 파악하기 쉽게 하였습니다.)
<figure 2>
우선 <figure 3>와 같이 돌 2개 3번의 규칙의 적용하여 흰색돌 3개를 집어 넣을 수 있습니다. 기본적으로 흰돌 3개로나 4개로 일렬로 이루어진 봉모양은 쉽게 만들 수 있고 이를 원배열로 바꾸면 각각 흰돌 4개나 5개로 이루어진 모양으로 바뀝니다. 그리고 <figure 3>를 이용하면 3k+1 or 3k+2 for k=1,2,.개의 원배열 모양은 흰돌로 이루어짐을 알 수 있습니다. 따라서 3k for k=1,2,..개의 원배열 모양의 그래프가 흰돌로만 이루어지는 경우가 있는지 확인하면 됩니다.
<figure 3>
우선 흰돌 2개의 원배열에서 시작한 것과 검은돌 2개의 원배열에서 시작한것을 각각 an,bn으로 놓겠습니다. <figure 4>와 <figure 5>에서 보듯이 b4에서 빨간색 박스 부분이 a3와 1대일 대응을 보이고 b5는 a4와 b6는 a5와 1대1 대응이 보임을 알 수 있었습니다. 파란색 박스안에 맨 왼쪽만 빼고 빨간색 박스를 그리어 놓았는데 맨 오른쪽만 빼고 그려도 마찬가지로 1대1 대응이 됩니다. 왜냐하면 대칭으로 시작했기 때문에 ak와 bk의 원소들의 대칭은 ak와 bk안에 있기 때문에 맨 오른쪽을 빼고 빨간색 다시 그려도 1대1 대응이 됩니다. 그리고 <figure 5>에서 박스 밑에 숫자를 적어 놓았는데 이는 박스안의 돌을 흑을 1 백을 0으로 보아 이진법으로 계산한 값입니다. 예를 들어 <figure 4>의 a3에서 2개의 모양은 1과 2를 나타내고 b2는 0을 나타냅니다. 이로 추측해보았을 때 a3 U b3은 0부터 2까지 a4 U b4는 0부터 6까지 a5 U b5 는 0부터 14까지 표현함을 볼 수 있으면 즉 ak U bk은 0부터 2^(k-1)-2까지 즉 모두 흰색인 돌부터 가장 오른쪽 돌이 흰색인 나머지 돌이 모두 흑색돌인 거까지로 표현됨을 추측할 수 있었습니다. 마지막으로 a3에서 a4로 규칙을 적용해나갈 때 a3에서 b4의 경우로 가는 것을 보지 못하엿고 이는 b3도 마찬가지였습니다. 즉 ak 교지합 bk는 공집합입니다 라는 것을 추측하였습니다.
<figure 4>
<figure 5>
추측들을 정리하면 다음과 같습니다.
1. ak U bk =0부터 2^(k-1)-2까지의 숫자로 표현된다.
2. bk의 파란색박스안에서 맨 오른쪽 or 맨 왼쪽 돌 한개를 제외하고 빨간색 박스를 쳤을 때 이는 ak-1의 빨간색 박스와 1대1 대응이다.
3. ak ∩ bk = 공집합
이를 증명하기 위해 수학적 귀납법을 사용하겠습니다. n=2부터 k까지 위 3가직 추측이 성립한다 가정하고 k+1일 때도 성립함을 보이겠습니다.
추측1
먼저, '추측1'은 <figure 6>와 같이 증명됩니다. 우선 n=k+1인 경우 0부터 2^k-2로 배열 표현은 흰돌이 그안에 있음으로 역방향으로 규칙이 가능합니다. 역방향을 하면 n=k일 때의 이진법이 나오고 n=k일 때는 0부터 2^(k-1)-2까지의 2진수로 모두 표현됨으로 n=k+1경우의 0부터 2^k-1의 배열 표현은 ak U bk에서 규칙 1번을 적용하여 모두 표현이 가능합니다. 따라서 an U bn은 모든 2^(n-1)-1을 제외한 모든 2진수로 표현이 됩니다.
<figure 6>
너무 길어 추측2부터 이어서 쓰겠습니다.
잘읽어보겠습니다.