KMO/조합(11)
-
조합[램지의 정리] 2-3
램지의 정리를 처음 보는 분들이라면 고든 램지를 떠올렸을 수도 있을 것 같다. 하지만 이번에 배울 램지의 정리는 고든 램지에 당연히 아무 관련없는 정리이다. 램지의 정리에 대해 설명하기에 앞서, 완전그래프 Kn에 대해 먼저 알고 있어야 한다. Kn은 n개의 점이 존재하고 어떤 2개의 점을 잡아도 점과 점이 연결되어 있는 상태를 말한다. 위에 보이는 사진이 바로 K4 완전그래프이다. 4개의 점이 존재하고 어떤 2개의 점을 잡아도 직접적으로 이어져 있는 것이 확인된다. R(a,b)=n이라면 Kn의 각 선분을 2가지 색으로 임의로 색칠시 항상 Ka나 Kb가 존재하게 된다는 뜻이다. 백문이불여일견이라고 아래의 예시로 이해를 도와보겠다. ※주의사항:램지이론은 완전그래프에서만 사용할 수 있다. #1.9명의 사람 가..
2021.11.07 -
조합[비둘기집의 원리2] 2-2
비둘기집의 원리1에 이어서 비둘기집의 원리2를 적게 되었습니다. 비둘기집의 원리를 파트를 나눠서 진행하는 이유는 없고 단지 양이 많기 때문입니다. 비둘기집의 원리1을 아직 보지 못했다면 여기로 들어가서 보고 와주세요. #5.a1
2021.11.07 -
조합[비둘기집의 원리1] 2-1
비둘기집의 원리에 대해 알아보자. 비둘기집의 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다는 원리이다. 보다시피 이 원리를 도대체 어떻게 문제에 적용할지를 궁금해할 것 같다. 이제부터 비둘기집의 원리에 대한 문제들을 살펴보도록 하자. #1.n명의 사람이 모임을 가지고 있다. 모든 사람은 다른 사람과 악수를 한다. 모임 동안에 같은 수만큼 악수한 사람 두 명이 항상 존재함을 증명하여라. 사람당 가질 수 있는 악수의 숫자는 1~n-1인데 사람은 총 n명이니 모임 동안 같은 수만큼 악수한 사람이 존재한다. 이 #1은 비둘기집의 원리의 기초라고 볼 수 있을 정도로 쉬운 축에 속한다. #2.공간상에 어느 세 점도 일직선상에 있지 않은 9개의 격자점 P1....
2021.11.06 -
조합[체스판] 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 -
그래프이론
그래프의 정의 가장 일반적인 의미에서 그래프(graph)는 순서쌍 G = (V, E)으로 볼 수 있으며, 여기에서 집합 V는 꼭짓점, E는 변 을 의미한다. 혼동을 피하기 위해, 방향이 없는 단순한 그래프 만을 다루겠다. 복잡하게 생각하지 말고, 가장 대표적인 예시로는 10명의 사람들이 인사를 주고받을 때, 10명을 점으로 하고 인사를 주고받았다면 선으로 연결, 주고 받지 않았더라면 연결하지 않았을 때, 나오는 모양을 의미한다. 점들의 배치는 중요하지 않다. 그래프 용어 1. n-정규그래프 n-정규그래프는 모든 점들의 차수가 n 으로 동일한 것을 의미한다. 위 예시로는 각 10명이 모두 인사를 7명에게 하였을 때, 나오는 그래프 이다. 2. 이분할그래프 이분할 그래프는, 두 그룹으로 나누어진 점에 의해 ..
2021.10.09