조합[체스판] 1-1
조합문제를 풀때 등장하는 체스판문제의 예시와 테크닉을 알아보자. 다음의 예시문제를 보도록 하자. #1.다음과 같은 10×10 그래프 G가 있다. G에 포함된 어떤 격자 회로 P가 다음을 만족한다. P는 점 a를 정확히 한 번 지난다. P는 a,b가 아닌 각 점을 정확히 10번씩 지난다. 이 때, P는 점 b를 정확히 몇 번 지나는가? 이 판의 점을 체스판처럼 검정 흰색을 칠하면(a,b가 있는 자리가 흰색이 되도록) 격자회로 P는 검정점과 흰 점이 교대로 반복된다. 조금만 어떤 회로를 그려서 관찰해볼 경우, P가 지나는 검정점개수=P가 지나는 흰점개수이다. P가 지나는 검정점개수=50×10 P가 지나는 흰점개수=48×10+1+b를 지나가는 횟수 따라서 P는 점 b를 19번 지난다. 이 문제에서 우리가 알 ..
2021.11.06