| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark () 날 짜 (Date): 1996년01월16일(화) 18시51분00초 KST 제 목(Title): [답] 케이크 자르기(간단한 방법도 있네요. 쩝... 원래 문제에 너무 충실하려다 보니 위의 답이 너무 복잡했네요. 제일 간단한 답은 다음과 같습니다. (경매식 방법이라고 이름붙이죠..) 단순화시켜서 생각합시다. (아예 N명짜리 문제로..) 1번째 사람이 케이크에서 1/N 크기의 조각을 잘라냅니다. 나머지 N-1 명이 이 케이크 조각에 대한 우선권을 가집니다. 이들은 이 케이크 조각에 대한 우선권을 버릴 수도 있고, 주장할 수도 있습니다. (1) 만약 우선권을 주장하는 사람이 아무도 없다면, 이 조각은 자동으로 1번째 사람에게 낙찰됩니다. 이제 남은 케이크를 N-1 명이 나눠 가지면 되죠.. :) (2) 이 조각에 대한 우선권을 주장하는 사람이 1명만 있다면, 이 조각은 그 사람이 가지면 되죠. :) 남은 케이크를 N-1명(1번째 사람 포함해서..)이 나누고... (3) 이 조각에 대한 우선권을 주장하는 사람이 2명 이상이 있다면.... (N-1명 이하!) 우선권을 주장하는 사람 중에서 1명이 나와서 케이크를 조금 잘라내어 그 크기가 전체의 1/N이 되도록 조정합니다. 이때, 우선권을 가진 사람들은 계속 우선권을 주장하거나, 포기를 합니다. 모두 포기하면, 방금 짤라낸 사람이 케이크를 가지고... 우선권을 주장하는 사람이 많다면 그 사람들끼리 계속 이 케이크 크기를 줄여갑니다. 자르는 사람은 자동으로 우선권이 사라지므로, 언젠가는 이 케이크 조각이 누군가의 손에 넘어가겠죠? 그럼 나머지 조각(+많은 빵가루(?)들..)을 나머지 N-1 명이 나눠가지게 됩니다. 어때요? 간단하죠? 불만도 없을테고... 빵을 자르는 사람의 입장: case 1: 자른 사람이 빵조각을 못 가졌을 경우: 자신이 너무 크게 잘라서죠.. case 2: 자른 사람이 빵조각을 가졌을 경우: 자신이 너무 작게(?) 잘라서죠.. 빵을 자르지 않는 사람의 입장: case 1: 결국 우선권을 통해 빵을 얻어낸 경우: 자기가 먹고 싶은 조각을 얻어냈으니 성공.. case 2: 빵을 결국 못 얻어낸 경우: 자기가 그 조각에 대한 권리를 스스로 포기했으니 불만없음.. (이 방법의 단점!) 맨 첫 조각을 뺀 나머지 조각은 빵에 많은 흠이 가게 된다. -- 박종대 |