| [ QuizWit ] in KIDS 글 쓴 이(By): outsider (하얀까마귀) 날 짜 (Date): 2001년 2월 22일 목요일 오후 10시 44분 46초 제 목(Title): 왕따 면하기(?) 게임하다 생각난 문제인데, 생각보다 쉽게 풀리지 않고 있군요..; 역시 A,B,C,D 네 사람이 경쟁을 합니다. 경쟁하는 사람 머릿수만큼 1점, 2점, ..., 4점짜리까지 '자리'가 있습니다. 네 사람은 자기가 원하는 자리를 1지망부터 4지망까지 (원칙적으로) 비공개로 정합니다. 그 뒤 다음의 규칙에 따릅니다. 1) 각자의 1지망을 비교합니다. 2) 어떤 자리를 한 사람만 원한다면 그 사람에게 줍니다. (누군가가 1지망에 '3점'을 적고 다른사람이 아무도 3점을 택하지 않았다면 그 사람은 3점을 가집니다.) 3) 어떤 자리를 여러 사람이 원한다면 그중에 한 사람에게 제비뽑기로 줍니다. 4) 자리를 얻은 사람들은 빼고 남은 사람들의 2지망을 비교합니다. 5) 2지망을 이미 누군가 가져간 자리로 쓴 사람은 아무것도 얻지 못합니다. 6) 2)-3)과 마찬가지로 자리를 줍니다. 7) 모두 자리를 얻을 때까지 4)-6)을 3지망, 4지망..에 대해 반복합니다. 근데, 이번에도 역시 B,C,D는 공모를 하고 있습니다. A로서 다행인 점은, 이번엔 A도 자신이 속고 있다는 점을 알고 있다는 사실이고, A한테 나쁜 점은, B,C,D들도 A가 자신들의 공모를 눈치챘음을 알고 있습니다. 양쪽의 최선의 전략은...? 물론 A의 목표는 전의 문제와 마찬가지로 최대한 얻는 자리의 점수의 기대값을 높이는 것이고 공모자들은 그것을 깎아먹는 것입니다. 그리고 공모자가 n명일 경우에도 풀 수 있을까요? ps. 이거 minimax문제인 듯 한데 어렵더군요. -- @< //) `//<_ 하얀까마귀 |