#5.28팀이 참가하는 축구대회가 열렸다. 각 팀은 다른 팀과 꼭 한 번씩 경기하였고, 매 경기마다 이기면 승점 2, 비기면 1, 지면 0점씩을 받는다. 75%를 넘는 경기가 무승부였다. 그럼 같은 승점의 두 팀이 존재함을 보여라. 이김=2 비김=1 짐=0->이김=1 비김=0 짐=-1 로 바꾼다. 귀류법:임의 두 팀은 승점이 다르다. (승패가 정해진 경기수)0: k번 팀은 적어도 Xk번을 이겼다. Xk

내가 생각한 중요문제들만 담겠다. #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.이..

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