본문 바로가기

조합론 퍼즐/그래프 퍼즐6

아이코시안 게임(Icosian game) 아이코시안 게임은 1857년 천문학자이자 수학자였던 W.해밀턴(William Rowan Hamilton)에 의해 만들어진 퍼즐이다. 퍼즐의 내용은 다음과 같다. 정십이면체의 모서리를 따라 움직이며 모든 꼭짓점을 밟고 제자리로 돌아오는 경로를 찾아라. 단 한번 지나간 길은 다시 지나갈 수 없다. 해밀턴은 이 퍼즐의 권리를 25파운드에 팔았는데, 당시 상업적으로 팔렸던 퍼즐의 사진을 다음 사이트에서 볼 수 있다(http://puzzlemuseum.com/month/picm02/200207icosian.htm) 정십이면체의 모서리와 꼭짓점을 그래프로 간주해 평면에 놓으면 위 그림과 같은 모양이 나온다.(이와같이 고차원 물체를 저차원에 옮기는 것을 슐레겔 도표(Schlegel Diagram)이라 부른다.) 고로.. 2016. 10. 16.
숫자 넣기 퍼즐 누가 고안한 것인지 모르는 옛 퍼즐 문제를 소개한다. 빈 칸들이 여러 선에 의해 연결되어 있다. 연속하는 두 자연수(1과 2, 2와 3, 3과 4, ...)가 선에 의해 연결되지 않도록 1부터 8까지의 숫자들을 빈 칸에 채워보아라. 그림의 중앙의 두 빈 칸에 주목하자 . 왼쪽과 오른쪽 빈 칸은 모두 무려 다섯개의 다른 빈칸과 연결되어있는 상태이다. 만약 왼쪽의 빈칸에 5가 들어갔다면 4와 6은 5와 이어진 다섯개의 빈 칸에 들어갈 수 없고, 따라서 하나 남은 오른쪽 빈 칸에 두 숫자가 다 들어가야 한다는 말인데, 이는 모순이다. 비슷한 원리로 2부터 7까지 항상 모순이 일어나므로 중앙의 빈 칸에 들어갈 수 있는 수는 1과 8밖에 없다. 대칭성을 생각하여 왼쪽에 8, 오른쪽에 1을 집어넣자. 그러면 8과 .. 2014. 6. 10.
램지 수(Ramsey Number) 퍼즐 또다른 파티 문제이다. 어떤 두 사람이건 서로 한 번은 만나보았거나(빨간 선), 혹은 단 한 번도 만난 적이 없을 것이다(파란 선). 그림 왼쪽은 아무나 6명을 모았을 때 일어날 수 있는 관계도 중 하나를 그린 것이다. 이런 상황에서, 파티에 사람들을 초대하여 서로 한 번은 만나본 사람들 3명(빨간 삼각형)이 생기거나, 혹은 서로 전혀 만나본 적 없는 사람들 3명(파란 삼각형)이 생기도록 하고싶다.(동시에 두 그룹이 생기지 않아도 좋다.) 최악의 경우까지 고려할 때 최소한 몇 명이 파티에 모여야 할까? 설명 그 최소 인원은 6명이다.우선 6명이 모이면 언제나 조건을 만족함을 증명하자. 모인 사람들 중 한 명을 임의로 생각하면 그(철수)는 나머지 다섯 사람들 중 3명 이상과 만나보았거나 그렇지 않을 것이다.. 2013. 12. 8.
물, 가스, 전기 공급의 문제 그림과 같이 가,나,다, 이렇게 세 집이 있고, 물 공급원, 가스 공급원, 그리고 전기 공급원이 아래에 순서대로 있다. 교차하지 않게 선을 그어 물, 가스, 전기 모두를 세 집에 다 공급하려면 어떻게 해야할까? 듀드니의 문제이다.(http://en.wikipedia.org/wiki/Water,_gas,_and_electricity) 해답. 이런 경우에는 용어에서 속임수나 트릭을 찾아야한다고 듀드니는 설명했다.[1] 위 그림 처럼 물의 관을 가 집 지하에 만들어 다 집으로 보내면 해결이라는 것이다. (근데 지하 매설이 가능하면 그냥 다 지하에 파묻어버리면 그만 아닌가?) 만약 위와 같은 꼼수를 부리지 않는다면 이 문제는 풀 방법이 없다. 이는 그래프 이론에 의거한 것으로 3, 3의 이분그래프(Biparti.. 2013. 5. 13.
리그전 대진표짜기 문제 잠깐 토막상식. 토너먼트(tournament)란 경기 때마다 1:1로 싸워 승자는 올라가고, 패자를 제외시켜서 마지막에 남은 두 편으로 우승을 결정하게 하는 시합을 말하고, 리그전(league戰)은 여러 팀이 일정한 기간에 서로 같은 횟수만큼 시합하여 그 성적에 따라 순위를 결정하는 경기 방식을 말한다. 그런데 여기서 리그전이라는 말은 실은 콩글리쉬이다. 영어에서 리그전에 해당하는 말은 Round-robin tournament이다. 첫 번째 문제 어느 도시에 아마추어 야구 팀이 5팀 생겼다고 한다. 이 야구팀들은 하루에 2번씩 총 5일동안 경기를 열어서 리그 순위를 매기고자 한다. (리그 총 경기수는 5C2=10이고, 하루에 할 수 있는 최대 경기 수는 [n/2]=2이므로, 이는 타당한 설정이다.) 당연.. 2012. 11. 18.
우연히 모인 파티의 법칙 파티에는 참 많은 사람들이 온다. 가장 잘 생각할 수 있는 것이 결혼식. 외국이고 우리나라고 할 것 없이 결혼식만 되면 아는 사람 모르는 사람 전부 와서 신랑신부 두 사람의 영원할 행복을 축하해준다. 어쩌면 그런 의미에서 파티(party) 에는 사교모임이라는 뜻에 단체, 동아리라는 뜻도 있는 듯 하다. 여기 어떤 일로 몇명의 사람들이 모였다고 하자. 개중에는 아는 사람도 있고 모르는 사람도 있을 것이다. 애매한 구석을 없애기 위해, 내가 알면 상대방도 나를 알아서 우리는 친구인거고, 내가 모르면 상대방와 나는 완전히 남남이라고 하자. 그렇다면 그 파티에는 각자 일종의 친구수를 가지게 된다. 이제 이야기가 재미있어진다. 놀랍게도, 그 어떤 파티에도 친구수가 똑같은 그런 두 사람을 늘 찾을 수 있다고 한다... 2012. 4. 7.

티스토리툴바