본문 바로가기

조합론 퍼즐14

띄어 앉을 수 있는 경우의 수는? 이 글을 쓰는 지금은 코로나 시국, 사회적 거리두기 캠페인이 한창이다. 이번 글에서는 거리두기와 관련있는 경우의 수 문제를 준비해보았다. 좀 어려운 경우의 수 문제를 자주 접해본 고등학생들이라면 이미 풀어봤을 법한, 그런 잘 알려진 문제이다. 1. 세 명의 사람과 일렬로 나열된 8개의 좌석이 있다. 이 중 세 좌석을 골라 앉되 어떤 두 사람 사이에도 최소 한 좌석은 비어있어야 할 때, 세 사람이 앉을 수 있는 경우의 수는 모두 몇인가? 2. 세 명의 사람과 원탁에 배치된 8개의 돠석이 있다. 이 중 세 좌석을 골라 앉되 어떤 두 사람 사이에도 최소 한 좌석은 비어있어야 할 때, 세 사람이 앉을 수 있는 경우의 수는 모두 몇인가? (주의! 원탁에 앉는 경우의 수를 구할 땐 회전에서 같아지면 모두 하나로 센.. 2020. 9. 6.
3×1 조각으로 체스판 채우기(feat.소사이어티게임2 10화) 소사이어티 게임은 tvn에서 방영중인 서바이버류 프로그램이며, 두 마을이 신체와 두뇌를 이용해 게임에서 격돌하는 것이 주 내용이다. 여기서 두뇌를 이용한 게임엔 주로 기억력 테스트, 아이큐 테스트나 퍼즐이 쓰이는데 특별히 어제(2017.10.27) 등장한 퍼즐이 마음에 들어 이렇게 글을 쓴다. 문제를 푸는 아이디어는 '수학의 모자이크'(라비 바킬 지음)에서 가지고왔다. 주어진 타일들을 이용해 8×8 체스판을 완성하라. 언뜻 쉬워보이나 이상하게도 잘 풀리지 않는 듯 하다. 바로 이 문제에 대해 설명한다. 더보기 이 문제를 주먹구구를 쓰지않고 풀기 위해서는 흑백이 아닌 다른 색구성이 필요하다. 다음 그림과 같이 체스판을 새로 칠했다고 가정하자. 3x1 크기의 조각은 가로든 세로든 어떻게 배치해도 정확하게 세.. 2017. 10. 28.
이항정리의 따름정리들과 조합적 증명 이항정리는 (x+y)^n을 전개시키면 어떻게 되는지 설명하는 정리이다. 여기엔 조합론에서 매우 중요한 C(n,r)이 사용된다.(C(n,r)이 n개의 물체중에서 r개를 선택하는 조합의 수임을 기억하라.) 이항정리로 말미암아 이 C(n,r)은 로 쓰고 이항계수라고도 부르기도한다. 본 글에서는 필자가 이항계수의 기호입력이 좀 익숙치 않은 관계로 모두 C(n,r)로 통일하여 쓰도록 하겠다. 이항정리의 증명은 여러가지가 있을 수 있다. 수학적 귀납법을 이용할 수도 있고 조합적 증명을 이용할 수도 있다. 하지만 이번 글에서는 이항정리 자체에 주목하지 않고 정리로 부터 나오는 따름정리(corollary)들의 조합적 증명에 더 주목하기로 한다.(조합적 증명에 대해선 다음 글을 참고하라.http://puzzleresea.. 2017. 10. 15.
보안을 위한 자물쇠의 개수는? 가, 나, 다, 세 명의 경비원이 보안을 위해 3개의 자물쇠를 구입했다. 문에 이 세 개의 자물쇠를 설치하고 해당 복제열쇠들을 나눠 갖는데, 오직 과반 이상이 참석할 때만 문을 열 수 있도록 2개씩 복사열쇠를 만들고 각자 아래 표와 같이 열쇠를 나눠가졌다. 표에서 알 수 있듯 1명은 세 자물쇠를 열 수 없지만, 2명만 모이면 모든 자물쇠를 풀 수 있다. 즉 과반이 모여야만 문을 열 수 있다. 어느날 보안업무에 라, 마, 두 명의 경비원이 추가로 배정되었다. 이제 가, 나, 다, 라, 마, 다섯 명의 경비원은 오직 과반 이상이 있을 때만 문을 열 수 있도록 추가 자물쇠와 추가 복사열쇠를 구입하려한다. 이들에게 필요한 최소 자물쇠 개수는 몇 개인가? 또 추가 복사열쇠는 어떻게 나눠가져야 하는가? (다른 사람.. 2017. 4. 16.
아이코시안 게임(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.

티스토리툴바