증명 힌트 좀 주세요!!
글쓴이: urmajest / 작성시간: 목, 2004/09/02 - 2:30오후
Quote:
1. 수업을 듣는 학생들이 있습니다.
2. 4명씩 팀을 구성하게 되는데 한 학생은 0개 이상의 팀에 속할 수 있습니다.
3. 하지만, 서로 다른 팀이 2명 이상의 학생을 동시에 가질 수 없습니다.
4. 선생님은 학생들에게 자기가 몇 개의 팀에 속해 있는지 갯수를 세게합니다.
5. 전체 학생 수 중 적어도 1/3이상의 학생이 다른 학생들과는 다른 수(팀의 갯수)를 가지고 있다면 선생님은 모든 학생에게 A를 주기로 약속합니다.
하지만, 학생들은 모두 A를 받을 수 없답니다.
이걸 어떻게 증명할 수 있을까요?
몇일 째 씨름 중인데 정말 모르겠군요 -_-
Forums:
대충 보고 대충 생각해서 쓰는 trivial 한 답입니다. 틀릴지도 ;;
대충 보고 대충 생각해서 쓰는 trivial 한 답입니다. 틀릴지도 ;;
문제를 "아이들이 말한 숫자가 다른 가짓수" 에 초점을 맞춰서
보면,
n가지의 경우가 나타났을때,
아이가 말하는 수는 1이상의 양수여야 하므로,
n경우일때, 아이가 말한 값중 최대의 값이 최소가 되는 경우에 그 값이 n이 된다. (최소값에 최대경우)
다시 말하자면, n을 말한 아이는 n개의 그룹에 속하는 것이고,
"서로 다른 그룹에 2명 이상의 아이가 중복되지 않는다" 는 조건에 의해서
n을 말한 아이가 속한 n개의 그룹은 n을 말한 아이 외에 중복되는 아이를 한명도 포함해서는 안된다.
이때 이 n개의 그룹은 각각 4명의 멤버를 가지고,
n개의 그룹의 인원 총 합은 1 + 3n 이 된다.
n은 (3n + 1) / 3 = n + 1/3 보다 클 수 없기 때문에
교수님의 말은 맞다.
** 개강 기념 교수님의 숙제인가요? -_-;
오토마타 시간인가 ㅎㅎ
-------------------------
The universe is run by the complex interweaving of three elements: matter, energy, and enlightened self-interest.
- G'kar, Babylon 5
[quote="futari"]대충 보고 대충 생각해서 쓰는 trivial
팀을 만드는데 필요한정확한 인원은 아니라도 위의문제를 증명하는데는 충분하군요
마지막에 팀을 구성하는데 필요한인력 3n+1 이 전체 인원 3n 을 초과하게 되어 발생할수 없는경우라고 하는게 더 좋을듯.
----------------------------------------------------------------------------