방학을 맞아 영준이는 한 가지 재미있는 실험을 하게되었다. 그것은 베이징 시내에 나가서 아무 사람이나 무작위로 6명을 골랐을 때, 이 6명 중 적어도 3명이 서로 다 알거나, 서로 다 모르는 경우 가 있을 확률을 구해보기로 하였다. 그런데, 영준이의 친구인 재영이가 실험을 할 필요없이 당연히 확률은 1 이라고 하였다. 이 말은 사실일까? 아니면 재영이가 실수를 한것일까? 단,A가 B를 알면 B도 A를 아는 것으로 한다.
Ramsey 이론이 비롯된 역사적인 문제. 상당히 의미있는 문제이나 초등적인 지식으로도 풀수있는 재밌는 문제임. 풀이는 원하는 사람 있으면 올려봄
해당 댓글은 삭제되었습니다.
적어도 3명이 서로 다 모르는 경우임
재영이 ㄷㄷ
6명 중 A 하나 고정하면 나머지 5명과의 관계를 생각했을 때 서로 모르거나 서로 아는 관계 둘 중 하나는 3개 이상 있음. WLOG 3명 이상과 서로 아는 관계이며, 얘들을 BCD라 하자. BCD 삼각형을 생각했을 때 얘들 중 아는 관계가 하나라고 있으면 (예를 들면 BC) ABC는 서로 알게 됨. 그렇지 않다면 BCD가 서로를 모르니 확률은 1임
오 잘 풀었음. 내가 푼거랑 본질적으로 같은거네