빈 그래프는 수형도인가

트위터에서 empty graph가 tree가 아닌 forest로 분류되어야하는지에 대한 이야기가 있었는데 (원본 트윗은 쓰신 분이 플텍 걸어놔서 보이지 않는다) 여러모로 봤을 때 forest로 보는 것이 타당하다. 이게 문제가 된 이유는 tree의 정의들을 생각해보면 ‘임의의 두 점이 정확히 한 개의 경로로 연결되는 그래프’, ‘연결되고 cycle이 없는 그래프’ 등이 있는데 전자 같은 경우 뽑을 두 점이 애초에 없으니 […]

Read More 빈 그래프는 수형도인가

사상 최악의 일본 입시 수학 문제

구독중인 ‘타마키의 수학’ 유튜브 채널에 올라온 한 영상. 1998년 도쿄대 후기 이과 입시 문제로 나왔던 한 수학문제를 다루고 있는데, 그 악명높은 난이도로 인해 전설이 된 문제라고. 문제는 다음과 같다. 먼저 흰 점 한 개만 있는 그래프가 주어져있다. 여기서 말하는 그래프는 각각의 점에 흑과 백 두 색 중 하나를 칠한 단순그래프를 뜻한다. 이 때, 다음과 같은 […]

Read More 사상 최악의 일본 입시 수학 문제

스즈미야 하루히의 증명

TVA “스즈미야 하루히의 우울”은 방영 에피소드 순서와 원반 매체에 수록된 순서가 달랐다. 후자는 원작의 순서를 따라 시계열에 따른 진행이었지만 전자는 그 순서를 셔플해버린 것. 이에 착안해 2011년 9월 13일 4chan의 한 유저가 과학과 수학을 다루는 /sci/ 게시판에 다음과 같은 질문을 던졌다. “「스즈미야 하루히의 우울」 1기 총 14화의 모든 가능한 순서가 각각 연속적으로 등장하도록 에피소드들을 배치한다면 […]

Read More 스즈미야 하루히의 증명

평면의 채색수

평면을 색 몇 개를 이용해 칠하되, 거리가 1인 어떤 두 점도 서로 다른 색이 되도록 칠하려고 할 때 필요한 색의 개수의 최솟값은? Hadwiger-Nelson problem으로 알려진 조합기하 문제이다. 여기서 따지고 있는 필요한 색의 개수의 최솟값 는 평면의 채색수(chromatic number)라 불린다. 평면을 위 그림처럼 7개의 색을 가진 육각형들로 타일링함으로써, 7개의 색만으로 조건을 만족시키게 하는 것이 가능함을 보일 […]

Read More 평면의 채색수