KMO(23)
-
조합[불변량2] 3-2
불변량이 좀 더 심화된 문제들을 알아보자. #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.이..
2021.11.07 -
함수방정식-대입의 테크닉(level 3)
자, 우리가 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에 수 또는 식을 맟춰서 넣어서 소거시키는 기술이다. 나..
2021.11.07 -
조합[불변량1] 3-1
불변량에는 번쩍이는 아이디어가 필요한 것 같다. 불변량 문제는 보통 어떠한 시행을 계속 진행하여 그 과정에서 변하지 않는 것을 잡는다.(반불변량도 있는데 그것은 나중에 다루도록 하겠다.) 아래의 문제를 보도록 하자. #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에 대해 불변임을 보여주는..
2021.11.07 -
조합[비둘기집의 원리3] 2-4
어느덧 비둘기집의 원리 마지막을 다루게 되었다. 열심히 해보자. 비둘기집의 원리는 무엇이 비둘기이고, 비둘기집인지에 대해 잘 파악해야 한다. #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π..
2021.11.07 -
조합[램지의 정리] 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