[일:] 2019 1월 24

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한 펜슬 퍼즐들