3-regular graph의 세계일주

도시들이 주어져 있고, 각각의 도시에 대해 정확히 세 개의 서로 다른 도시로 갈 수 있는 비행기편이 있다고 한다. 어떤 사람이 이 편로들을 이용해 이 사람의 고향에서 출발해 모든 도시들을 한 번씩만 거쳐 다시 원래 도시로 돌아왔다면 이 루트를 세계 일주라 부른다. 만약 이 도시들에서 세계 일주가 가능했다면, 그 여정과 다른 방법으로 세계 일주가 가능하다. (단, […]

Read More 3-regular graph의 세계일주

볼록다면체의 외각의 합

볼록다면체의 번째 변 에서 만나는 두 면이 이루는 각 중 외각에 해당하는 각을 라 하면, 이다. 볼록다각형의 외각의 합이 란 결과를 3차원으로 확장한 결과물이다. 2007년 일본 수학 올림피아드 하계 세미나 문제 코너에 출제된 문제. 문제를 공개하면 학생들이 답안을 제출해 점수를 받는 프로그램이었는데 이 문제는 제출된 답안이 없었을 정도로 쉽지 않은 문제였다. 여기서는 이리에 케이(入江慶)가 작성한 […]

Read More 볼록다면체의 외각의 합

테스트 문제들에 대한 테스트 문제

James Propp이 만든 Self-referential Aptitude Test. 미국 대입 테스트인 SAT의 형태를 빌었는데 말 그대로 self-referential이라 모든 문제가 테스트지 내의 문제의 답에 대한 정보로만 이루어져있는 일종의 논리 퍼즐 문제이다. 예컨대 1. 답이 B인 첫 번째 문제는? (A) 1번 (B) 2번 (C) 3번 (D) 4번 (E) 5번 2. 유일하게 답이 같은 연속한 두 문제는? (A) 6번과 7번 […]

Read More 테스트 문제들에 대한 테스트 문제

도서관에서의 변의

예전에 스펀지에서 “도서관이나 서점 같이 책들로 둘러싸인 곳에서 변의를 느끼는 현상”을 다뤘던 적이 있었는데 찾아보니 아오키 마리코 현상이라고 불리고 있었다. 아직 그 메커니즘이나 더 나아가 현상이 실재하는지조차도 학문적으로 규명되지 않았는데 위키피디아 문서의 분량이 엄청남… 1980년대에 비슷한 경험담들이 조금씩 일본 미디어에 드러나기 시작했었는데 본격적으로 유명하게 된 기폭제는 잡지 “책의 잡지”(本の雑誌) 40호(1985년 2월)에 실린 사연이라고 한다. 당시 […]

Read More 도서관에서의 변의

NP-complete한 펜슬 퍼즐들

노노그램(네모네모로직)같이 주어진 보드에서 연역적으로 푸는 펜슬 퍼즐들이 있다. 많은 펜슬 퍼즐들은 일본의 계간지 니코리에서 등장하는데, 팬층이 두터워서 팬들이 새로운 퍼즐 포맷을 창안해 투고하고 몇 호씩 창작 문제들을 실으면서 인기가 있을지 없을지 검증하기도 함. 2012년 나고야에 갔을 때 서점에서 처음 알게된 이후로 계속 사서 즐기고 있다. 니코리 홈페이지에서 매월 일정 금액 결제해서 온라인으로도 몇 문제씩 정해진 […]

Read More NP-complete한 펜슬 퍼즐들

석방을 위한 카드 선택 문제

A, B가 감옥에 따로따로 갇혀있다. 어느 날 간수가 52장의 카드를 앞면이 위를 향하도록 일렬로 늘어놓고 A를 불러들여 이 카드들 중 원한다면 두 장의 위치를 바꿀 수 있게끔 했다. 그리고 A를 돌려보낸 후 모든 카드들을 각각 뒤집은 뒤, B를 불러들였다. (A와 대화를 못하도록 막아두었다)간수는 이 카드들 중 어느 특정한 카드를 랜덤하게 지정해, B가 만약 이 카드를 […]

Read More 석방을 위한 카드 선택 문제

Chomp 게임과 힐베르트의 정리

두 좌표가 0 이상인 정수인 모든 점들을 생각한다. 남아있는 점들 중 한 점을 잡아, 이 점보다 두 좌표가 크거나 같은 (즉 상대적으로 우상단에 있는) 모든 점들을 없애는 스텝을 되풀이할 때, 어떻게 해도 유한번 안에 모든 점을 없애게 된다. Fibonacci Freak에서 소개된 문제. Chomp란 이름의 게임이 있는데, 유한한 직사각형 모양의 점들에서 위에서 묘사한 시행을 되풀이하여 마지막으로 […]

Read More Chomp 게임과 힐베르트의 정리