| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2003년 12월 18일 목요일 오후 04시 20분 01초 제 목(Title): Re: [문제] 6명의 정치인 답: 있다. 증명은 좀 아래........ 정치인 6명이 있다. 악수한 정치인 둘을 골라 a, b라고 하자. (악수한 정치인이 아무도 없다면 당연히 아무나 셋을 뽑으면 된다.) 나머지 정치인 4명을 a와만 악수한 정치인 그룹을 A, (b와는 악수하지 않았다.) b와만 악수한 정치인 그룹을 B, (a와는 악수하지 않았다.) a,b 모두와 악수하지 않은 정치인의 그룹을 C라고 하자. (정의에 의해 a,b 모두와 악수한 정치인은 없다.) |A| + |B| + |C| = 4. A 그룹 내(와 B 그룹 내)에선 서로 악수를 하지 않았다. 만약 A 그룹 내의 사람끼리 악수를 했다면 A와 a는 악수를 한 세 명이 된다. 만약 |A| >= 2라면 A와 b를 고르면 조건을 만족. 역시 |B| >= 2라면 B와 a를 고르면 조건을 만족. C에 속한 정치인 사에에 악수를 하지 않았다면 C에서 두 명을 고르고, a를 포함하면 이 셋은 서로 악수를 하지 않은 정치인 셋이 된다. 따라서 C에 속한 정치인끼리는 모두 악수를 했다. 조건에 의해 |C| <= 2 따라서 |A| <= 1, |B| <= 1. |C| >= 2 결국 |A| = 1, |B| = 1, |C| = 2 만이 가능하다. A = {a'} B = {b'} C = {c, c'} 이라고 하자. b'이 c와 c' 둘 다와 악수를 하지는 않았다. (b'/c/c'이 서로 악수를 하지는 않았으므로). WLOG b'이 c와 악수를 하지 않았다고 하자. 결국 a, b', c가 주어진 조건을 만족하는 악수하지 않은 정치인 세 명이 된다. @ 더 깔금하게 정리될 듯도 싶지만 귀차니즘 때문에... @@ 증명하고보니 Ramsey's Number... 그거랑 다른 거라고 왜 착각했지? -_- -- 박.. |