본문 바로가기

조합론 퍼즐14

램지 수(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.
체스판 위에 도미노 깔기 2 도미노 깔기 1에서, 체스판의 같은 색깔을 없앴을 경우 절대로 도미노들을 덮을 수 없음을 알았다. 그렇다면, 다른 색깔 두 개를 제거하였다면 어떻게 될까? 두개의 칸은 그야말로 완전히 무작위하게 제거됨을 명심하자. 이 때, 이 조각난 체스판을 항상 덮을 수 있을까, 아니면 덮을 수 없는 반례가 존재할까? 설명 매우 깔끔한 증명이다. 이제 남은 일은 무작위로 제거된 칸을 두고 기차놀이하는 것 뿐이다. IBM의 랄프 고모리(Ralph Gomory)의 증명이다. 2013. 4. 14.
귀퉁이 잘린 체스판에 도미노 깔기 그림과 같이 두 귀퉁이가 없어진 체스판이 있다. 체스판은 총 64칸이므로 지금은 62칸이다. 이 62칸을 도미노조각(두 사각형이 붙어있는 조각) 31개로 모두 덮으려 한다. 그런데, 막상 해보니 쉽지 않을 것 같다. 어떻게 해야할까? 해설 딱 잘라 말하면, 불가능하다. 그림과 같이 한 도미노 조각은 반드시 밝은 칸과 어두운 칸을 동시에 덮게 된다. 그렇기에 서른 한개의 도미노를 올리면 뒤덮힌 62칸중 정확히 반이 밝은 칸이고 나머지 반이 어두운 칸이게 된다. 지금의 체스판은 어두운 칸이 밝은 칸보다 2개 많으므로 이 체스판을 도미노로 덮는 것은 불가능하다. 이 문제는 마틴 가드너(Martin Gardner)에 의해 소개되었습니다. 2013. 4. 1.
리그전 대진표짜기 문제 잠깐 토막상식. 토너먼트(tournament)란 경기 때마다 1:1로 싸워 승자는 올라가고, 패자를 제외시켜서 마지막에 남은 두 편으로 우승을 결정하게 하는 시합을 말하고, 리그전(league戰)은 여러 팀이 일정한 기간에 서로 같은 횟수만큼 시합하여 그 성적에 따라 순위를 결정하는 경기 방식을 말한다. 그런데 여기서 리그전이라는 말은 실은 콩글리쉬이다. 영어에서 리그전에 해당하는 말은 Round-robin tournament이다. 첫 번째 문제 어느 도시에 아마추어 야구 팀이 5팀 생겼다고 한다. 이 야구팀들은 하루에 2번씩 총 5일동안 경기를 열어서 리그 순위를 매기고자 한다. (리그 총 경기수는 5C2=10이고, 하루에 할 수 있는 최대 경기 수는 [n/2]=2이므로, 이는 타당한 설정이다.) 당연.. 2012. 11. 18.
우연히 모인 파티의 법칙 파티에는 참 많은 사람들이 온다. 가장 잘 생각할 수 있는 것이 결혼식. 외국이고 우리나라고 할 것 없이 결혼식만 되면 아는 사람 모르는 사람 전부 와서 신랑신부 두 사람의 영원할 행복을 축하해준다. 어쩌면 그런 의미에서 파티(party) 에는 사교모임이라는 뜻에 단체, 동아리라는 뜻도 있는 듯 하다. 여기 어떤 일로 몇명의 사람들이 모였다고 하자. 개중에는 아는 사람도 있고 모르는 사람도 있을 것이다. 애매한 구석을 없애기 위해, 내가 알면 상대방도 나를 알아서 우리는 친구인거고, 내가 모르면 상대방와 나는 완전히 남남이라고 하자. 그렇다면 그 파티에는 각자 일종의 친구수를 가지게 된다. 이제 이야기가 재미있어진다. 놀랍게도, 그 어떤 파티에도 친구수가 똑같은 그런 두 사람을 늘 찾을 수 있다고 한다... 2012. 4. 7.

티스토리툴바