quiz 200, 0203 풀이
3
풀이는 라마누잔의 식에서!
이 식은 아주 쉽게 증명 가능하다.
루트 안에 {, } 여기에 또 같은 방법을 사용하면 된다.
일반적으로 정원수 m명에 투표자 n 명의 경우, 후보자가 m 명보다 많은 경우 어떤 사람이 당선 확실이라고 할 수 있는 득표수는
여기서 [] 는 가우스 기호로 [x] 는 x 를 초과하지 않는 최대 정수를 나타낸다.
일반화된 식을 증명하기 위해서는 귀류법을 사용해야 한다.
문제로 돌아가서 한번 귀류법을 적용해 보자.
우리 아파트 101동은 총 45개의 가구로 이루어져 있다. 여기서 3명의 아파트 위원을 선출해야 하는데 총 8명의 후보자가 나왔다. 각 가구별로 1개의 표를 투표할 수 있다. 개표 도중에 후보자 1명의 당선 확실을 말할 수 있으려면 그 사람에게 몇 표가 나왔을 때인가.
12표.
어떤 사람이 12표를 얻었는데도 당선이 확실하지 않다고 가정하자. 즉 이 말은 그 사람 이외에 12개 이상의 득표를 한 사람이 적어도 3명이 있어야 한다. 즉 이 경우 전체 투표수는
12+12x3 = 48 이상이 되어야 한다.
이는 전체 투표자(총 45가구)의 조건에 어긋난다.
참고로 11표는 왜 안될까? 11표를 얻었을 경우, 12표 11표 11표 를 득표하는 경우가 존재하기 때문에 당선가능성이 확실하지 않다. (11+12+11+11=45)