| [ QuizWit ] in KIDS 글 쓴 이(By): constell (호이~!) 날 짜 (Date): 2001년 2월 8일 목요일 오후 01시 13분 29초 제 목(Title): Re: 악수문제 사람들을 A1, A2, B1, B2, C1, C2라고 하면요(같은 영문자끼리 부부) 아 그 주인공 이름이 뭐지 암튼 A1이라고 하죠. 나머지 다섯명이 악수한 사람수가 다 다르다고 했는데 문제 규칙에 의해 5명과 악수할 수는 없으니 각각 0,1,2,3,4가 되겠죠. 그래프에서 디그리와 같으니 deg()으로 표시하기로 하고.. deg(A2)=4일 순 없죠. 그렇게 되면 주인공 외에 deg 0인 사람이 없게 되니까. 그럼 B1,B2,C1,C2 네명 중 하나가 deg 4가 될거고.. WLOG deg(B1)=4라고 하죠. 그럼 deg 0인 사람은 B2일수밖에 없고. A2, C1, C2의 디그리가 각각 1,2,3이어야 하는데, 디그리 3인 사람이 누가 되는지 보면.. deg(A2)=3이라면 A2는 C1, C2와 모두 연결이 되니까 deg 1인 사람이 있을수 없죠. 그러니 A2는 아니고 그러면 C1,C2 중 하나. WLOG deg(C1)=3이라고 하죠. 그럼 C1는 A1,A2와 연결이 돼야만 합니다. (그림 그려보면 간단..) 그럼 deg(A2)=2, deg(C2)=1이 되어서 끝. A2,B1,B2,C1,C2의 디그리가 각각 2,4,0,3,1이 되지요. 그럼 A1는 B1,C1과 연결이 되어 디그리가 2가 되구요. 그래서 deg(주인공)=2. 그림 그리면 간단한데.. |