포함과 배제의 원리, 조합에서 자주 사용되는 원리이다. 포함과 배제의 원리는 유한 집합의 합집합의 원소 개수를 세는 기법이라고 구글에 나와있는데 이렇게 들으면 뭔 소린지 도통 모르겠으므로 다음의 예시문제로 설명을 시작할까 한다. #*.한 변의 길이가 2인 정사각형의 내부에 각각의 넓이가 1 이상인 일곱개의 다각형들이 주어져 있다. 이 때, 이 다각형들 중에서 어떤 두 개의 다각형은 공통 부분의 넓이가 1/7 이상임을 증명하여라. 위의 문제의 결론을 부정하는 문장은 '임의 두 개의 다각형의 공통 부분의 넓이가 1/7 미만'이라고 볼 수 있다. 우리가 이제부터 해야할 행동이 무엇인지 알겠는가? 바로 귀류법을 사용하여 최선을 다해도 모순이 나온다는 것을 보이는 것이다. 귀류법:임의 두 개의 다각형의 공통 부분..

불변량에는 번쩍이는 아이디어가 필요한 것 같다. 불변량 문제는 보통 어떠한 시행을 계속 진행하여 그 과정에서 변하지 않는 것을 잡는다.(반불변량도 있는데 그것은 나중에 다루도록 하겠다.) 아래의 문제를 보도록 하자. #1.한 번의 시행에서 정수의 순서쌍 (p,q,r)을 (r+5q,3r-5p,2q-3p)으로 바꾼다. (1,3,7)로부터 유한번의 시행 후에 (k,k+1,k+2)가 얻어지는 정수 k가 존재하는가? 문제에서 시행을 할 때에 변하지 않는 것을 찾아야 한다. (r+5q)+(3r-5p)+(2q-3p)≡p+q+r(mod 3) 시행을 할때 순서쌍 원소들의 합은 mod 3에 대해 불변이다. 1+3+7은 3m+2꼴인데 k+(k+1)+(k+2)은 3m꼴이라 모순 이 문제처럼 mod e에 대해 불변임을 보여주는..

어느덧 비둘기집의 원리 마지막을 다루게 되었다. 열심히 해보자. 비둘기집의 원리는 무엇이 비둘기이고, 비둘기집인지에 대해 잘 파악해야 한다. #8.반지름 16인 원의 내부에 650개의 점이 있다. 그러면 내부 반지름이 2이고 외부 반지름이 3인 반지모양(링 C)으로 이 점들 중 10개를 덮을 수 있음을 증명하여라. 점 P가 중심이 Q인 링 C에 덮이는 것은 점Q가 중심이 P인 링 C에 덮이는 것과 같다. 650개의 각 점 P를 중심으로 내부반지름:2 외부반지름:3인 링을 그린다. 이 링중 어떤 10개가 어떤 점을 동시에 덮는다는 것을 보이자. 귀류법:평면상의 임의의 점은 최대 9개의 링이 덮는다. S=링의 넓이의 합=5π×650=3250π 650개의 링은 반지름이 19인 원에 덮인다. S는 최대 361π..

비둘기집의 원리1에 이어서 비둘기집의 원리2를 적게 되었습니다. 비둘기집의 원리를 파트를 나눠서 진행하는 이유는 없고 단지 양이 많기 때문입니다. 비둘기집의 원리1을 아직 보지 못했다면 여기로 들어가서 보고 와주세요. #5.a1

비둘기집의 원리에 대해 알아보자. 비둘기집의 원리는 n+1개의 물건을 n개의 상자에 넣을 때 적어도 어느 한 상자에는 두 개 이상의 물건이 들어있다는 원리이다. 보다시피 이 원리를 도대체 어떻게 문제에 적용할지를 궁금해할 것 같다. 이제부터 비둘기집의 원리에 대한 문제들을 살펴보도록 하자. #1.n명의 사람이 모임을 가지고 있다. 모든 사람은 다른 사람과 악수를 한다. 모임 동안에 같은 수만큼 악수한 사람 두 명이 항상 존재함을 증명하여라. 사람당 가질 수 있는 악수의 숫자는 1~n-1인데 사람은 총 n명이니 모임 동안 같은 수만큼 악수한 사람이 존재한다. 이 #1은 비둘기집의 원리의 기초라고 볼 수 있을 정도로 쉬운 축에 속한다. #2.공간상에 어느 세 점도 일직선상에 있지 않은 9개의 격자점 P1....

조합문제를 풀때 등장하는 체스판문제의 예시와 테크닉을 알아보자. 다음의 예시문제를 보도록 하자. #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번 지난다. 이 문제에서 우리가 알 ..