| [ QuizWit ] in KIDS 글 쓴 이(By): cdpark (박종대) 날 짜 (Date): 2000년 8월 3일 목요일 오후 07시 14분 08초 제 목(Title): 상금이 걸린 미해결 문제(포항공대) http://com2mac.postech.ac.kr/ 에 올라와 있습니다. Ramsey Number에 관련된 문제 둘과 Random Graph에 관련된 문제 하나군요. 첫번째 문제를 조금 읽기 쉽게 고쳐봤습니다. 파티장에 6명 이상이 있다면 (1) 서로 아는 세 명이 있거나 (2) 서로 모르는 세 명이 있습니다. (1)이나 (2) 둘 중의 하나는 반드시 성립합니다. 5명이 있을 때는 이게 성립하지 않죠. a, b, c, d, e의 5명이 있을 때, a-b, b-c, c-d, d-e, e-a가 서로 안다고 하면, 이 중에 어떻게 세 명을 뽑더라도 서로 알거나 서로 모르는 상황은 발생하지 않습니다. 마찬가지로 파티장에 18명 이상이 있다면 (1) 서로 아는 네 명이 있거나 (2) 서로 모르는 네 명이 있습니다. 문제 1. 파티장에 몇 명 이상이 있다면 (1) 서로 아는 다섯 명이 있거나 (2) 서로 모르는 다섯 명이 있을까요? 현재까지 알고 있는 건 이 값이 43 이상이고 (42명이면 위처럼 안 되는 예를 만들 수 있습니다.), 49 이하라는 겁니다. (49명일 때는 반드시 존재합니다.) 이 43 <= X <= 49인 X 값을 찾는 건 300 달러짜리 문제이고, 43이나 49 값을 좀 줄이는 건 100 달러짜리 문제입니다. 그리고 더 중요한 건(!) 확실한 논문감이란 겁니다. ^^ -- 박.. |