| [ QuizWit ] in KIDS 글 쓴 이(By): iLUSiON (수버미엄마�`) 날 짜 (Date): 1994년05월24일(화) 16시06분28초 KDT 제 목(Title): [환상정답] 고봉균님의 아이디어가 맞습니다. 정확히 답을 말하면 upper bound뿐만아니라 exact form이 나옵니다. 전에 정의한대로 strongly connected chain을 vertically or horizontally connected two stone이라고 하면 다음의 정리에 도달합니다. 환상 제일 막시말 커버정리 iLUSiON's maximal cover theorem I. n개의 흑돌로 최대의 백돌을 먹는 configuration은 2개의 strongly connected chain을 갇던가 0개의 strongly connected chain을 갇는다. 증명: XXX일경우 (2개의 s.c.c. 가 연속배열) 이면 중앙의 것을 올림 X XOX 이러면 한개의 백돌을 더 먹을수있음 XX일경우 오목 볼록 몇가지 생각해보면 오직 귀퉁이에만 갈수있음 마름모꼴의 귀퉁이에만 갈수있다는 소리. 만약 홀수개의 s.c.c.개가 귀퉁이에 가면(4귀퉁이중에) 결코 마름모꼴을 형성할수없음( 음 대략 평형사변형식임) 결론은 0개나 2개의 s.c.c.만이 마름모꼴의 귀퉁이에 붙을수있음. (여기서 빠진것은 4개의 s.c.c.가 마름모꼴의 귀퉁이를 차지하는경우인데 아주극소(겨우 백돌1개인것으로 계산되는데) 의 차이로 같은 숫자의 흑돌 configuration중 no s.c.c.인것보다 백돌한개를 덜먹음. 증명 끝. 0개의 s.c.c.인경우는 n이 4의 배수인경우 2개인 경우는 (대각선방향 혹은 같은쪽 귀퉁이) n이 4의 배수가 아닌경우로 직접해보면 규칙발견할수있음. (rotational) ~~~~~~~~~~~~~~~~~~~~~ iLUSiON 2002 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 비둘기들이 나에게 속삭인다. "우리 모이주어 먹으러 가쟈...." 환상 비둘기가 꾸벅 꾸벅 졸면서 "난 꿈을 먹을꺼야.." 그러다가 환상 비둘기는 굶어죽었다. |