내가 생각한 중요문제들만 담겠다. #1.100개의 A1,...,A100, |Ai|=10 이 주어져 있는데, 임의의 두 집합의 공통 원소의 개수는 정확히 하나이다. A1∩A2∩...∩An≠∮ 임을 증명하시오. 귀류법:A1∩A2∩...∩An=∮ 우선 왼쪽의 그림부터 보도록 하자. a∈S, a∈A1,A2,...,Ad(a는 Ad+1에서 A100에는 속하지 않는다.) |Ai∩Aj|=1이기 때문에 A1,Ad에서 K집합으로 선을 1개씩은 그어야 한다. 그리고 선들이 같은 K집합의 원소로 향하면 |Ai∩Aj|≠1이 되어 모순이기 때문에 각 선은 다 다른 원소를 가리킨다. |Ai|=10이라 d≤10을 만족, S의 임의 원소는 최대 10개의 Ai에 포함된다. 이제 오른쪽 그림이다. |Ai∩Aj|=1로 인해 F'에서 S'로..

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

불변량이 좀 더 심화된 문제들을 알아보자. #5.칠판에 9999...99(9가 2002개) 가 쓰여 있다. 첫 번째 학생이 그 수를 ab(a,b>1)로 인수분해하여 칠판에 원래의 수를 지우고 |a-a'|=2, |b-b'|=2인 수 a',b'을 적는다. 그리고 두 번째 학생도 나와 첫번째 학생이 한 것처럼 반복한다. 유한명의 학생이 위의 방법으로 새로운 수를 계속 써갈 때, 칠판에 쓰여 있는 모든 수가 9와 같아질 수 있겠는가? mod 4로 봤을때, 3->1,3이므로 3을 지우면 1,3이 써진다. 이때, 9999...99≡3(mod 4)이므로, mod 4로 3인 수를 지우고 다른 수를 써도 항상 mod 4로 3인 수가 존재하는데 9는 mod 4에 대해 3과 합동이 아니라서 모두 9가 될 수 없다. #6.이..

자, 우리가 level 1에서는 정말 "기본적인" 대입을 배웠다. 이제 조금 더 심화된 대입의 테크닉들에 대해서 알아보자. 1.반대부호 대입 예시문제) f(x²+y)=f(xⁿ+2y)+f(x⁴) (n은 홀수) P(x,0) : f(x²)=f(xⁿ)+f(x⁴) P(-x,0) : f(x²)=f(-xⁿ)+f(x⁴) 이때, 두 식을 비교하면 f(xⁿ)=f(-xⁿ)이다. 이때, xⁿ과 -xⁿ 모두 전체 실수를 표현할 수 있기 때문에 f는 상수함수임을 알 수 있고, f(x)=k라 두자. 이때, 이것을 원식에 대입하면 f(x)=0을 알 수 있다. 이렇게 반대부호를 사용함으로써 문제를 더 쉽게 풀 수 있다. 2.내부를 0으로 만들기 & 같게 만들기 이런 경우는 x,y에 수 또는 식을 맟춰서 넣어서 소거시키는 기술이다. 나..

불변량에는 번쩍이는 아이디어가 필요한 것 같다. 불변량 문제는 보통 어떠한 시행을 계속 진행하여 그 과정에서 변하지 않는 것을 잡는다.(반불변량도 있는데 그것은 나중에 다루도록 하겠다.) 아래의 문제를 보도록 하자. #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에 대해 불변임을 보여주는..

1-? 조합에서 사용되는 다양한 테크닉(한대 묶기 곤란) 체스판 문제 포함과 배제의 원리 2-? 비둘기집의 원리와 램지의 정리 비둘기집의 원리1 비둘기집의 원리2 램지의 정리 비둘기집의 원리3 3-? 불변량1 불변량2 4-? 그래프차수 5-? 심화문제 심화1 심화2