증명 힌트 좀 주세요!!

urmajest의 이미지

Quote:
1. 수업을 듣는 학생들이 있습니다.
2. 4명씩 팀을 구성하게 되는데 한 학생은 0개 이상의 팀에 속할 수 있습니다.
3. 하지만, 서로 다른 팀이 2명 이상의 학생을 동시에 가질 수 없습니다.
4. 선생님은 학생들에게 자기가 몇 개의 팀에 속해 있는지 갯수를 세게합니다.
5. 전체 학생 수 중 적어도 1/3이상의 학생이 다른 학생들과는 다른 수(팀의 갯수)를 가지고 있다면 선생님은 모든 학생에게 A를 주기로 약속합니다.
하지만, 학생들은 모두 A를 받을 수 없답니다.

이걸 어떻게 증명할 수 있을까요?
몇일 째 씨름 중인데 정말 모르겠군요 -_-
futari의 이미지

대충 보고 대충 생각해서 쓰는 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

ㅡ,.ㅡ;;의 이미지

futari wrote:
대충 보고 대충 생각해서 쓰는 trivial 한 답입니다. 틀릴지도 ;;

문제를 "아이들이 말한 숫자가 다른 가짓수" 에 초점을 맞춰서

보면,

n가지의 경우가 나타났을때,

아이가 말하는 수는 1이상의 양수여야 하므로,

n경우일때, 아이가 말한 값중 최대의 값이 최소가 되는 경우에 그 값이 n이 된다. (최소값에 최대경우)

다시 말하자면, n을 말한 아이는 n개의 그룹에 속하는 것이고,

"서로 다른 그룹에 2명 이상의 아이가 중복되지 않는다" 는 조건에 의해서

n을 말한 아이가 속한 n개의 그룹은 n을 말한 아이 외에 중복되는 아이를 한명도 포함해서는 안된다.

이때 이 n개의 그룹은 각각 4명의 멤버를 가지고,

n개의 그룹의 인원 총 합은 1 + 3n 이 된다.

n은 (3n + 1) / 3 = n + 1/3 보다 클 수 없기 때문에

교수님의 말은 맞다.

** 개강 기념 교수님의 숙제인가요? -_-;

오토마타 시간인가 ㅎㅎ

팀을 만드는데 필요한정확한 인원은 아니라도 위의문제를 증명하는데는 충분하군요
마지막에 팀을 구성하는데 필요한인력 3n+1 이 전체 인원 3n 을 초과하게 되어 발생할수 없는경우라고 하는게 더 좋을듯.


----------------------------------------------------------------------------