| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 1995년10월20일(금) 01시46분09초 KST 제 목(Title): Re: 정신병자 다섯 절대로 놓일 수 없습니다. 이제 슬슬 증명해볼까요? 차곡차곡 생각해봅시다. (좌표체계는 보통의 극좌표입니다.) Lemma 1. 다섯 명 중 적어도 두 명은 같은 row에 놓인다. ======= 모든 사람이 서로 다른 row에 놓여 있다고 가정해보자. 그러면 pigeonhole principle에 의해, 적어도 세 사람은 짝수번째(혹은 홀수번째) row에 놓인다. 이때, 이 셋이 각각 (X1, Y1), (X2, Y2), (X3, Y3)에 있다고 하면.. 모든 i,j 쌍에 대해, Yi-Yj는 짝수이므로, Xi-Xj는 홀수여야 한다. (Xi-Xj도 짝수이면, ((Xi+Xj)/2, (Yi+Yj)/2)에 의해 가리므로..) 따라서, 모순이다. (세 숫자 간의 차이가 모두 홀수일 수는 없다.) 따라서, 다섯 명 중 적어도 두 명은 같은 row에 놓인다. Corollary 2. 다섯 명 중 적어도 두 명은 같은 column에 놓인다. =========== 위와 마찬가지로... 위의 Lem 1과 Cor 2에 의해, 세 명의 좌표는 정해진다. (이 셋을 A, B, C라고 하고, 각각의 좌표를 (0,0), (1,0), (0,1)이라 하자.) 나머지 두 정신병자를 D와 E라고 하자. Lemma 3. D의 좌표를 (X, Y)라고 했을 때, X와 Y는 모두 홀수이다. ======= D는 (0,0)과 (1,0)을 모두 볼 수 있어야 하므로, Y는 홀수여야 한다. D는 (0,0)과 (0,1)을 모두 볼 수 있어야 하므로, X도 홀수이다. Corollary 4. E의 X, Y 좌표도 모두 홀수이다. =========== Theorem. 다섯 명의 죄수를 서로 보이는 곳에 배치할 수 없다. ======= 위에서 D와 E는 서로 가린다. -- 씨디팍 박종대 |