| [ QuizWit ] in KIDS 글 쓴 이(By): guest (sol) <maggie.kaist.ac.> 날 짜 (Date): 2002년 11월 23일 토요일 오후 11시 54분 30초 제 목(Title): Re: 보석 상자 보석칸의 수 n 보석의 종류 K 한 종류당 보석 개수 k then 3n=Kk 각 칸을 vertex, 각 칸사이에 edge를 공통인 보석이 존재하는 것으로 생각하면 C(n,2) <= C(k,2)*K <--- 최대 생길 수 있는 edge개수 위 식은 그래프가 complete해야 하므로 성립 참고로 C(a,b)는 a combination b를 의미 위 식에 의해 k => (n+2)/3 고로 K=3n/k <= 9-18/(n+2) That is, K는 기껏해야 8이다.. 8이 되는 경우는 누군가가 보일 것이므로 저는 7이 되는 경우를 보입니다. a,b,c,d,e,f,g의 보석이 각각 3개씩 있습니다. 즉 총21개의 보석이 있습니다. 그럼 각가의 칸에 다음과 같이 넣으면 원하는 조건을 만족합니다. abc, ade, afg, bdf, beg, cef, cdg 고로 K의 최대값은 최소 7이상이며 최대 8이하입니다. 위와 같이 보석들을 칸에 넣을 때 determinitic하게 넣을 수 있는 방법이 있을 것 같습니다. 근데 제 생각이 또 틀렸음 쪽 팔립니다^^. |