이런 그래프 G가 있을 때 인접하는 꼭짓점이 같은 색을 갖지 않도록 m가지 색으로 그래프의 꼭짓점을 칠하는 방법이 문제입니다.
원문:
주어진 문제가 모든 edge의 양 끝이 서로 다른 색을 가져야 되는 거하고 같으니 set Ai 를 i번째 edge의 양 끝이 같은 색을 가지도록 색칠하는 방법이라 두고 Inclusion-exclusion formula를 사용하면(교수님이 사용하라고 하셔서..)
N(모든 Ai의 여집합의 교집합) = N - S1 + S2 - S3 + S4 - S5 + S6 - S7이 문제의 정답이 되고 N = m^7, Si 는 9Ci * m^(7-i) 와 비슷한 형태가 되야한다는 것 까지는 이해했습니다. 그런데 S4부터는 어느 edge를 선택하느냐에 따라 edge를 선택하며 색칠되는 꼭짓점의 갯수가 달라져서 너무 복잡해 집니다ㅠㅠ... S3의 경우에는 edge 3개를 선택한게 삼각형인 경우에만 선택되는 꼭짓점이 세개여서 (9C3 -2)m^4 + 2m^5 인것 같은데 이 다음부터는 너무 복잡해져서 어떻게 해야될지를 모르겠습니다.. 뭔가 풀 방법이 있을까요
두번 째 문제는 반에 37명이 있을 때
1명은 190cm보다 크고
4명은 180cm~190cm (180, 190포함)
11명은 170cm~180cm (170 180미포함)
21한명은 170 이하
원문은 이거고
문제는 대충 190cm보다 큰 1명이 180~190 사이에 있는 4명 중 최소 한 명 보다는 다음에 오도록 37명을 줄세우는 걸로 이해했습니다. 이 조건의 complement는 그 큰 한 명이 180~190 사이에 있는 4명 전부 보다 앞에 와야한다는 걸로 생각하고 set A 를 이 조건 하에서 줄세우는 경우로 잡았습니다. N(complement of A) = N - N(A) 일때 N은 37! 이고 N(A) = 37C5 * 4! * 32! 따라서 37! - 37C5*4!*32!로 답을 구했는데 정답지도 없고 체그에 올라온 풀이도 이상해서 이게 맞는 건지 모르겠습니다.. 배점이 큰 문제여서 Inclusion Exclusion formula를 복잡하게 사용해야 할 줄 알았는데 이렇게 쉽게 답이 나오는 것도 이상하고 의미가 없어보이는 조건들도 있어서 잘못푼거 같아 올려봅니다ㅠㅠ
