수업시간에 쓰려고 만든건데 적당히 쉽고 재밌어서 여기에 씀. 


제시문) 사람이 10명 있고, 2명이 나와 1:1로 게임을 한다. 빠짐없이 한 번씩 게임을 해야하고, 이기면 1점을 얻고, 지면 점수가 그대로이다. 비기는 경우는 없다.


문제1) 열 사람이 하는 게임의 총 횟수는?


문제2) 점수가 9점인 사람은 많아야 1명이다. 왜 그럴까?


문제3) 점수가 8점이상인 사람은 많아야 3명이다. 왜 그럴까?



문제1 풀이) 


10C2 = 45


문제2 풀이) 


9점인 사람이 2명일때 모순임을 보이면 충분하다. 9점인 사람을 a, b라고 하자. a와 b는 9번 이겨야한다. 따라서 a는 b를 이겨야한다. 그러면 b의 점수는 8점이하가 되므로 모순. 9점인 사람은 많아야 1명이다.


문제3 풀이) 


8점 이상인 사람이 4명일때 모순임을 보이면 충분하다. 8점이상인 사람을 a, b, c, d라고 하자. a ~ d내의 게임은 총 6회(완전그래프 K_4)이며 a ~ d는 1번의 패배만이 허용되는 상황이다. 따라서 a, b, c, d는 서로 간의 게임에서 2점을 확보해야한다. 2점을 확보하지 못했다는 것은 2회 이상의 패배를 의미하는 것이기 때문이다. 그러나 a ~ d간의 게임에서 얻게 되는 점수의 총 합은 6점(게임횟수가 6회 이므로)이고, 네 사람이 얻어야 하는 점수의 총합은 8점이상이므로 이는 모순이다.


따라서 8점이상인 사람은 많아야 3명이다. 3명이 되는 경우는 사례가 존재함을 보이면 충분하다.