| [ QuizWit ] in KIDS 글 쓴 이(By): jhshin (신 준 호) 날 짜 (Date): 2001년 1월 14일 일요일 오전 02시 38분 21초 제 목(Title): 오래 전 문제 4937번, wshin님이 내신 문제에 대한 해를 예전에 구해 본건데요, 혹, 반례가 있다면 찾아 주시기 바랍니다. --------------------------------------------------------------------- ======================<wshin님의 문제>======================== 주어진 m에 대하여, 다음 성질을 만족하는 집합M의 원소의 최대 개수는? (1) S가 M의 원소이면, S는 {1,2,...,m}의 부분집합이고, 원소의 개수가 3개이다. (2) 임의의 서로 다른 M의 두 원소 S,T의 교집합의 원소의 개수는 1개이하이다. 좀 더 일반적으로, (1)의 조건 중 원소의 개수가 k이고, (2)의 조건을 만족하는 집합 M의 원소의 최대 개수는? ============================================================= --------------------------------------------------------------------- 1) k=0 일 때 G=1 2) k=1 일 때 G=m 3) k>=2 일 때 ㄱ) k =2 이면 A_n = (m-1-(k-1)(n-1))/(k-1)^n ㄴ) k>=3 이면 A_n = ((m-1)(k-2)-(k-1)^n+k-1))/((k-1)^n(k-2)) (n은 양의 정수) 라 하고, [A_n]=0를 만족하는 최소의 n을 q+1, m-1-[A_1](k-1)=r, (A_q-[A_q])(k-1)^q=p 라 하면 G = Sigma[A_n](k-1)^(2n-2) + R 1<=n<=q 단, [A_q] = k-1 일 때 R=p(k-1)^q [A_q] = k-2 일 때 R=max(r(p-r), [r/(k-[A_q])]) [A_q]<= k-3 일 때 R=[r/(k-[A_q]+[(r-p)/(k-1)^q])] * [x]는 x를 넘지 않는 최대의 정수, max(a,b) 는 a, b 중에 작지 않은 수 가끔 지나가는, jhshin |