문제 : https://arca.live/b/math/48072156
귤 16개가 탁자 위에 올려져 있는데 이중 3개는 당도가 높은 특별한 귤이라고 한다. 이 특별한 귤을 구별하기 위해 탐지기를 가져왔는데, 이 탐지기는 2개의 귤을 검사해서 2개의 귤이 모두 특별한 귤일 때에만 울린다고 한다. 16개의 귤들 중에서 특별한 귤 하나를 찾아내기 위해 적어도 필요한 탐지기 시행의 횟수는?
sw1wswq님이 문제에 해당하는 리퍼런스를 가져오셨고
cc 님이 맞추셨습니다.
사실 저도 왜 그렇게 되는지 모르는 문제였는데 댓글로 금방 풀이를 달으셔서 놀랐습니다.
이 문제는 작년 2월 아카라이브 냥드립채널에 올라왔던 것을 수정한 것입니다. (https://arca.live/b/dogdrip/21300604)
귤이 아니라 사과였고 16개가 아니라 14개였습니다. 이 경우 최소 횟수는 39회가 됩니다.
우여곡절이 있는 문제였는데 처음 공개된 문제가 수정되었고 이에 따라 출제자가 다시 공개한 답은 42회였습니다.
하지만 누군가가 프로그래밍을 동원한 노가다로 이보다 적은 39회를 기어코 찾아냈습니다.(https://arca.live/b/dogdrip/21305598)
제가 공개하려던 방법이 이것이었습니다.
최소 49번의 탐지로 특별한 귤을 찾는 방법은 다음과 같습니다.
16개의 귤을 8개, 7개, 1개씩 나누어둡니다.
8개에 대해서 모든 조합으로 탐지기를 시행합니다. (8C2)
7개에 대해서도 모든 조합으로 탐지기를 가져다댑니다. (7C2)
중간에 탐지기가 울린다면 특별한 귤을 찾았으니 끝.
만약 탐지기가 울리지 않았다면 8개 중에 1개의 귤이 특별하고, 7개의 귤 중에서 1개의 귤이 특별하다는 의미이므로 탐지하지 않은 나머지 귤 하나가 반드시 특별합니다.
이때 탐지한 횟수는 8C2 + 7C2 = 49가 됩니다.
cc님의 풀이는 Turan의 정리를 활용한 것인데 제가 감으로 조사한 것에 따르면 위의 풀이는 튜란 그래프 중 하나인 완전 이분 그래프에 해당합니다.
이때 서로 마주보는 점의 갯수는 가능한 동등해야하며, 이것이 15개의 귤을 8, 7개로 나눈 이유가 됩니다.
튜란 그래프가 그 외에 뭐가 있는지 저는 잘 모르기에 이 풀이가 유일한지 아닌지 또한 저는 모릅니다.
이제 49가 최소임을 증명합니다. (cc님 풀이를 다시 풀어 써봤습니다.)
Turan의 정리에서 유도되는 결론은 n 개의 점에 대해서 삼각형을 이루는 세 점이 존재하지 않을 때 가능한 변의 최대 갯수가 (n^2)/4 보다 같거나 작다는 것입니다.(이걸 Mantel의 정리라고도 합니다.)
귤을 점이라고 하고 탐지기를 사용했을 때 소리가 울리지 않는 두 귤 사이를 선으로 잇는다고 생각합시다. 시행한 횟수 만큼 변이 있는 그래프가 그려질 것입니다.
이때 반전 그래프를 생각합시다. 특별한 귤 세개는 삼각형을 이룹니다. 탐지기가 아직 울리지 않은 한 이 삼각형은 반전 그래프에 속할 것입니다.
반전 그래프에서 특별한 귤이 확정되는 상황은 1)가능한 모든 삼각형이 하나의 점을 꼭지점으로 공유하고 있을 때가 이상적입니다.
2)가능한 모든 삼각형이 변을 공유하고 있는 경우도 생각할 수 있지만 이는 1)보다 효율적이지 못합니다.
2)의 경우 두개의 점을 뺀 나머지 14개 점에 대해서 모두 탐지를 시행해야하며 이는 14*13/2=91번이 됩니다.
1)을 취한다면 점 하나와 그와 연결된 모든 선분을 지운 나머지 그래프가 삼각형을 이루어서는 안됩니다.
따라서 변의 최대 갯수는 15^2/4 = 56.25보다 같거나 작은 56이 됩니다.
그리고 15개 점에서 가능한 모든 변의 숫자는 15*14/2=105입니다.
따라서 반전 그래프가 56 이하가 되려면 탐지기를 105-56=49번 사용해야 합니다.
