15명의 여학생 문제와 Steiner system의 존재성

15명의 여학생 문제라는게 있다. 이게 뭔고 하니, 여학생 15명이 매일 3명씩 다섯 조를 짜서 7일동안 등교하는데, 모든 학생들이 한 번 같은 조였던 사람과는 두 번 다시 조가 되지 않도록 하라는 문제이다. 정답은 위키피디아 링크에 나와 있으니, 퍼즐 좋아하면 먼저 풀어보시라. ㅎ

이를 일반화하여 이런 질문을 해 볼 수 있다.

n개의 원소로 이루어진 집합이 있다. 모든 r개로 된 부분집합들이 딱 \lambda개만 포함되는 q개로 된 부분집합들의 모임 S를 항상 만들 수 있는가?

그러한 q-subsets collection을 design이라 부르는 모양인데, 특히 \lambda=1일 때, Steiner system이라 부르는 듯. 위 15명의 여학생 문제는 n=15, q=3, r=2인 경우 Steiner system을 찾는 문제이다.

여하간 Steiner system의 존재성 문제는 combinatorics분야에서 꽤 오래되고 중요한 문제인 모양인데, 이 문제가 Peter Keevash 라는 수학자에 의해 얼마전에 풀렸다는 소문이 있다.

Amazing: Peter Keevash Constructed General Steiner Systems and Designs in Combinatorics and more

특정한 n에 대해 모든 q, r에서 Steiner system이 존재한다는 것을 증명한 듯. Randomised Algebraic Constructions이라는 새로운 method를 창안한 모양인데 뭐 본인은 뭔지 모른다 ㅋ

역사가 깊은 많은 문제가 그러하듯 문제 자체는 쉽게 이해되는 편인데, 풀이는 어떨지 모르겠다. 본인은 논문을 안 읽어봐서… ㅋㅋㅋ

그나저나 15명의 여학생 문제에서 왜 하필 여학생(schoolgirl)일까? 뭐 모르긴해도 여고생이 좋긴 좋다-_-

 


2015.6.21
와이어드 ANSWER TO A 150-YEAR-OLD MATH CONUNDRUM BRINGS MORE MYSTERY DATE OF PUBLICATION: 06.20.15. 7:00 AM

2 thoughts on “15명의 여학생 문제와 Steiner system의 존재성

  1. 남학생들은 떼지어 등교하지는 않는 경향이 있는데 비해서 여학생들은 많이들 같이 등교하는것 같아요 ㅋㅋ
    이것도 편견일까…

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중