KMO(23)
-
조합[비둘기집의 원리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 -
함수방정식-전단사 함수(level 2)
오늘은 어제에 이어서 전단사 함수에 대해서 알아보자. 먼저 전사함수를 보자. 전사함수란 공역과 치역이 같은 함수를 말한다. 예를 들어 y=x,y=x^3은 전사함수이지만, y=x^2과 같은 함수는 음수부분이 나타나지 않기 때문에 전사함수가 아니다. 전사함수를 증명하는 방법은 f(상수가 아닌 어떤 식)=(모든 실수를 표현할 수 있는 식)인 꼴이 나오게 된다면 (대입으로) 전사함수이다. 예를 들어 f(f(x)+f(y))+f(f(x))=2f(x)+y라는 식에서 P(0,x)를 대입하면 f(f(0)+f(x))+f(f(0))=2f(0)+x가 된다. 즉, f(f(x)+f(0))=x+2f(0)-f(f(0))이 되므로 f는 전사함수이다.( f(0), f(f(0))은 상수이다. ) 그런데, 전사함수이면 뭐가 좋길래 증명하는..
2021.11.04 -
함수방정식-대입의 기본(level 1)
함수방정식, 대수의 꽃이라고 해도 될 정도로 풀었을 때 엄청난 희열을 느낄 수 있는 문제들이다. 함수방정식에서 가장 중요한 것은 무엇일까? 그렇다. 말할 것도 없이 대입이다. 그러나 우리는 문제를 더 빨리 풀기 위해서는 더 효과적이고, 문제에 도움이 되는 대입을 해야한다. 자, 이제 예시문제를 보고 대입을 하여 문제를 풀어보자. 아, 그리고 이제 문제에서 명시를 하지 않으면 R=>R, 즉 실수가 정의역이고 공역도 실수인 함수로 한다. f(x)f(y)-f(xy)=x+y 먼저 위 식을 P(x,y)라고 하자. (만약 P(1,2)라면 x=1,y=2를 대입한 것을 의미한다. 물론 f(x)등의 식을 대입해도 가능하다.) P(x,0):f(x)f(0)-f(0)=x 이를 1번 식이라고 하자. =>f(x)=(x/f(0))..
2021.11.04 -
정수 #4.정수조건 부정방정식의 전략들
인수분해 -크기비교 -홀짝성 및 나머지 관찰 대수적 접근법 -이차방정식 이론-D≥0, D=k2 -일차인 변수에 대해 정리 -a/b∈Z일 때, a와 b가 어떤 문자에 관한 다항식일 경우, a의 차수가 b보다 낮도록 만들어보고 a≠0이면 /a/≥/b/(/ /은 절댓값 기호) 부등식 -식의 대칭성 -정수의 이산성 -양수 조건을 보고 크기를 비교하여 문자를 치환(차이치환) mod 관찰 -지수함수, !이 등장하는 형태 등에서 적당한 mod로 관찰해본다. -mod에 관한 다양한 이론들을 적용해본다. 최대공약수와 서로소 관찰 -소인수분배 -a/bc, gcd(a,b)=1 → a/c -ab=ck (a,b∈N), gcd(a,b)=1 → a=xk, b=yk +) 1≡n(mod n-1)
2021.10.29 -
정수 #3.위수와 원시근
위수란? 2 이상의 정수 m 에 대해서 m 과 서로소인 정수 a일때, an 이 m으로 나눈 나머지가 1이 되는 가장 작은 n 을 mod m에 대한 a의 위수 라고 한다. ordm(a)=r이다. 원시근이란? 원시근에 대해서 설명하기 전에, 오일러 함수에 대해서 알아야 한다. 자연수 n에 대한 오일러 함수 Φ(n) = (n보다 작거나 같은 자연수 중, n과 서로소인 수의 개수)로서 정의 되는데, aΦ(m) 을 m으로 나눈 나머지가 1이 되지만, Φ(m)보다 작은 n에 대해서는 an 을 m으로 나눈 나머지가 1이 되지 않도록 하는 a가 존재할 때, a를 법 m(mod m)에 대한 원시근이라고 한다.
2021.10.26