구독상품안내
문제
1. 한 원의 두 현 AB,CD가 원의 내부의 점E에서 만나고 있다.M을 선분 EB위의 양끝점이 아닌 점이라 하자. 세점 D,E,M을 지나는 원에 E에서 그은 접선이 직선BC,AC와 만나는 점을 각각 F,G라 한다.
$\frac{AM}{AB}$=t라 할때 $\frac{EG}{EF}$를 t의 식으로 나타내라. ●인도 출제
2. n은 n≧3인 정수다. 한 원둘레 위의 서로 다른 2n-1개 점으로 이루어진 집합을 E라 하자.E의 점 중에서 꼭 k개의 점에 검은 칠을 할 때, 검은 칠을 한 것 중 적어도 한 쌍의 점이 있어서, 이 두 점을 제외한 두개의 호 중에서 어느 하나의 호위에 E의 점이 꼭n개 있으면 'k개가 색칠이 잘 되었다'라고 한다.
모든k개가 색칠이 잘된 석이 되기 위한 k의 최소값을 구해라. ●체코 출제
3. $\frac{{2}^{n}+1}{{n}^{2}}$이 정수가 되는 1보다 큰 모든 정수 n을 구해라. ●루마니아 출제
4. ${Q}^{+}$를 양의 유리수 전체의 집합이라 하자. 모든 양의 유리수 x,y에 대해 f(xf(y))=$\frac{f(x)}{y}$를 만족시키는 함수 f:${Q}^{+}$→${Q}^{+}$를 만들어라. ●터키 출제
5. 처음에 1보다 큰 정수${n}_{0}$가 주어져 있고, 두 경기자 A,B가 다음 규칙에 따라서 정수 ${n}_{1}$,${n}_{2}$,${n}_{3}$…을 번갈아 뽑고 있다.
${n}_{2k}$를 알았을 때,A는 ${n}_{2k}$≦${n}_{2k+1}$을 알았을 때, B는 $\frac{{n}_{2k+1}}{{n}_{2k+2}}$이 소수의 자연수 거듭제곱이 되는 정수 ${n}_{2k+2}$를 뽑는다. A는 1990을 뽑으면 이기고,B는 1을 뽑으면 이긴다고 한다.
다음 각각을 만족시키는 ${n}_{0}$을 모두 구하고 그 이유를 설명해라. ●서독 출제
(a) A가 이길 수 있는${n}_{0}$
(b) B가 이길 수 있는${n}_{0}$
(c) A도 B도 이길 수 없는${n}_{0}$
6. 다음 두 성질을 가지는 볼록1990각형이 존재함을 증명하여라.
(a) 모든 내각의 크기는 같다.
(b) 변의 길이는 ${1}^{2}$, ${2}^{2}$, ${3}^{2}$,…. ${1989} ^{2}$, ${1990} ^{2}$을 적당한 순서로 나열한 것이다. ●네덜란드 출제
풀이 및 해답
1. D와 A,B,M를 잇는다.∠CEF=∠DEG=∠EMD'=∠ECF=∠MAD이므로 △CEF∾△AMD 따라서 CE·MD=AM·EF 한편 ∠ECG=∠MBD(AD 위의 원주각) ∠CGE=∠CEF-∠GCE=∠EMD-∠MBD=∠BDM이므로 △CGE∾△BDM 따라서 GE·MB=CE·MD GE·MB=AM·EF 즉 $\frac{GE}{EF}$=$\frac{AM}{MB}$=$\frac{AM}{AB-AM}$=$\frac{tAB}{(1-t)AB}$=$\frac{t}{1-t}$…(답)
2. 주어진 2n-1개의 점에 차례로 0,1,2,…2n-2의 번호를 붙이고 S={0,1,2,…2n-2}하 하자.
정수 ℓ∈Z에 대해 ℓ≡i(mod 2n-1)이면 ℓ과i∈S는 같은 것으로 생각한다. ｜i-j｜=n+1 또는 ｜i-j｜=n-2이면 S의 원소 i와 j는 '서로 관련된 원소'라고 부르기로 하자.
i와 j가 서로 관련된 원소이면 이들 두 원소에 해당하는 점을 제외한 어느 한쪽의 호위에 주어진 2n-1개의 점 중에서 꼭 n개의 점이 있게 되고 역도 성립한다(위의 그림 창조).
모든 k개의 색칠이 잘 된 것이 될 필요충분조건은 k개의 원소를 가진 S의 어떠한 부분집합A에 대해서도 A에는 두 개의 서로 관련된 원소가 존재하는 것이다.
(1) n개의 색칠은 항상 잘된 색칠이다. A⊂S,#A=n(#A는 A의 원소의 개수)라 하자.
A에는 서로 관련된 원소가 없다고 가정하자.
j∈A에 대하여 S(j)를 j와 서로 관련된 S의 모든 원소의 집합이라 하면 가정에 의해 모든 j∈A에 대해 S(j)와 A는 서로 소이다 각 원소는 많아야 두 개의 S(j)에 나타나고, 모든 j∈A에 대해 S(j)의 합집합은 적어도 n개의 원소를 가지므로 이것은 #A=n에 모순이다.
귀류법에 의하여 A에는 서로 관련된 원소의 짝이 반드시 존재한다. 즉 n개의 색칠은 잘된 색칠이다.
(2) 3∤2n-1이면 n-1개의 색칠은 잘된 색칠이 아니다.
B⊂S,#B=n-1인 B에는 서로 관련된 원소가 없는 경우를 만들면 된다.
B={3k｜k=0,1,2,…'n-2}
C={3k+n-2｜k=0,1,2,…'n-1}라 하자. C에서 k대신에 n-1-k를 대입하면
C={3(n-1-k)+n-2｜k=0,1,2,…'n-1}={2(2n-1)-3-3k｜k=0,1,2,…'n-1}={3(-1-K)｜k=0,1,2,…'n-1}3∤2n-1이므로
B∪C={3k｜k=-n, -n+1,…,-1,0,1,2,…, n-2}=S #B=n-1,#C=n이므로 B∩C=∅ j∈B,j=3k(0≦k≦n-2)라 하면
S(j)={3k+n-2, 3k+n+1}={3k+n-2,3(k+1)+n-2}⊂C 이므로 S(j)∩B=∅다. 이것은 B에는 서로 관련된 원소의 짝이 없다는 것을 뜻한다.
(주) a∤b는 'b는 a로 나누어지지 않는다'는 기호고 a｜b는 'b는 a로 나누어진다'는 기호다.
(3) 3｜2n-1인 경우를 생각하자. 이 경우에는 n≡(mod 3)이다.
n=3m-1(m≧2)라 하면 2n-1=3(2m-1),n-2=3(m-1),n+1=3m이다. 따라서 S의 원소i와 j가 서로 관련된 원소면 i≡j(mod 3)이다.
r=0,1,2에 대해 ${S}_{r}$={3k+r｜k=0,1,2,…,2m-2}라 하면 S는 서로 소인 부분집합 ${S}_{0}$,${S}_{1}$,${S}_{2}$로 나누어진다.
그리고 S의 각원소 i에 대해 i∈${S}_{r}$이면i와 서로 관련된 두 개의 원소는 모두 ${S}_{r}$에 속함을 알 수 있다.
여기서 3m-2(=n-1) 개의 색칠이 잘된 색칠임을 증명하고자 한다.
A⊂S,#A=3m-2이면 비둘기구멍(pigeonhole)원리에 따라 A∩${S}_{r}$인 꼴의 한 부분집합은 적어도 m개의 원소를 갖는다.
(1)에서 사용한 방법에 의하면 A∩${S}_{r}$(⊂A)에는 서로 관련된 원소의 짝이 존재함을 밝힐 수 있다.
끝으로 3(m-1)(=n-2)개의 색칠은 잘된 색칠이 될 수 없음을 보이고자 한다. 서로 관련된 원소를 갖지 않는 ${S}_{r}$의 m-1개의 원소로 된 부분집합을 구성해 보이면 된다.
${B}_{r}$={3k+r｜k=0,1,2,…,m-2}(r=0,1,2)라 하자.
i와 j가 서로 관련된 원소일 필요충분조건은 ｜i-j｜=3(m-1) 또는 ｜i-j｜=3m 이므로 ${B}_{0}$,${B}_{1}$,${B}_{2}$의 각각에는 서로 관련괸 원소가 없음을 알 수 있다.
이상을 종합하면 다음과 같다.
k의 최소값 n-1,2n-1이 3의 배수 일때 n,2n-1이 3의 배수가 아닐때
3. ${2}^{n}$+1이 홀수이므로 ${n}^{2}$｜${2}^{n}$+1이면 n은 홀수다.
(주:b｜a는 'a가 b로 나누어진다'는 뜻이다.) 따라서 n≧3이다. 지금 n의 최소의 소인수를 p라 하자. 그러면 p≧3이고 p｜${2}^{n}$+1, 즉 ${2}^{n}$=-1(mod p)이다. i를 ${2}^{i}$1(mod p)인 최소의 자연수라 하면 ${2}^{p-1}$=-1(mod p)로 부터 i＜p-1이다.
n=ki+r(0≦r≦i-1)라 하면 다음 결과를 얻는다.
${2}^{n}$=${2}^{ki}$×${2}^{r}$≡${(-1)} ^{k}$${2}^{r}$ (mod p). k를 짝수라 하면 ${2}^{r}$≡${2}^{n}$≡-1(mod p)이고 이것은 i의 선택에 모순. 따라서 k는 홀수이다. 이때 ${2}^{r}$≡1(mod p)이다.
여기서 r>;0라 하고 i=r+d(1≦d＜i)라 하면 ${2}^{d}$≡${2}^{r}$×${2}^{d}$=${2}^{r+d}$ ${2}^{i}$≡-1(mod p) 역시 i의 선택에 모순이다.
r=0 따라서 n=ki이고 i｜n. i＜p이고 p는 최소의 소인수이므로 i=1. 따라서 p｜2+1 ∴ p=3.
n=${3}^{k}$d(k≧1),(d,3)=1라 하자.
k≧2라 하면 ${n}^{2}$｜${2}^{n}$+1,${3}^{2k}$｜${(3-1)} ^{n}$+1이므로 ${(3-1)} ^{n}$을 전개하여
${3}^{k+2}$｜(${3}^{k+1}$ d-${(-1)}^{h}$ (∵ n은 홀수)
를 얻는다. hi의 소인수분해의 3의 지수는 $\frac{h}{2}$보다 작고 ${3}^{h}$의 소인수분해의 3의 지수는 k+$\frac{h}{2}$보다 크므로 h≧2일때 ${3}^{k+2}$｜${3}^{h}$, 즉 ${3}^{k+2}$｜${3}^{k+1}$d를 얻는다.
이것은 모순이다. ∴ k=1이고 n=3d이다.
d=1 즉 n=3 이면 성립한다.
q를 d의 최소의 소인수라 하면 d는 홀수이고 (d,3)=1 이므로 q≧5,q｜${2}^{n}$+1.
j를 ${2}^{j}$≡-1(mod q)인 최초의 자연수라 하면 페르마(Fermat)의 정리에 의하여 j＜q-1.
앞에서와 같은 방법을 되풀이하면 j｜n이다.
n=3d, (3,d)=1, j＜q-1,q는 d의 소인수이므로 j=1 또는 3이다.
${2}^{j}$≡1(mod q)로 부터 q｜3 또는 q｜9 ∴ q=3.
이것은 q≧5에 모순이다.
이상을 종합하면 $\frac{{2}^{n+1}}{{n}^{2}}$ 이 정수가 되는 1보다 큰 정수는 n=3 뿐이다.
(답) n=3
4. f(${y}_{1}$=f(${y}_{2}$)라 하면 f(xf${y}_{1}$))=f(xf(${y}_{2}$))=$\frac{f(x)}{{y}_{1}}$=$\frac{f(x)}{{y}_{2}}$ 이므로 ${y}_{1}$=${y}_{2}$ 이다.
즉 f(x)는 1:1 함수이다.y=1이라하면 모든 y∈${Q}^{+}$ 에 대하여 f(f(y))=$\frac{1}{y}$이므로 f($\frac{1}{y}$)=f{f(f(y))}=$\frac{1}{f(y)}$이 모든 y∈${Q}^{+}$ 에 대하여 성립한다. 끝으로 y=f($\frac{1}{t}$) 이라 하면 f(xf(f($\frac{1}{t}$)))=f(xt),$\frac{f(x)}{y}$=f(x)f(f(f($\frac{1}{t}$)))=f(x)f(t)
f(xt)=f(x)f(t)가 모든 x,t∈${Q}^{+}$에 대하여 성립한다.
역으로, 모든 x,t∈${Q}^{+}$에 대하여 두개의 함수방정식
(a) f(xt)=f(x)f(t)
(b) f(f(x))=$\frac{1}{x}$
을 만족시키는 함수 f는 주어진 조건을 만족시킴을 쉽게 알 수 있다.
조건 (a)를 만족시키는 함수 f:${Q}^{+}$→${Q}^{+}$를 우선 소인수분해된 정수에 대해서 생각한다. ${p}_{j}$를 j번째의 소수라 하고 x=${{p}_{1}}^{{n}_{1}}$${{p}_{2}}^{{n}_{2}}$…${{p}_{k}}^{{n}_{k}}$ 라 하면 (a)에 의해
f(${{p}_{1}}^{{n}_{1}}$${{p}_{2}}^{{n}_{2}}$…${{p}_{k}}^{{n}_{k}}$)=${(f({p}_{1}))} ^{{n}_{1}}$${(f({p}_{2}))} ^{{n}_{2}}$…${(f({p}_{k}))} ^{{n}_{k}}$ 이다. 따라서 소수 ${p}_{j}$에 대하여f(${p}_{j}$)를 정하면 된다.
이것은 다음과 같이 구성된다.
(F):f(${p}_{j}$)=${P}_{j+1}$,j가 홀수일 때 $\frac{1}{{P}_{j-1}}$,j가 짝수일 때
이렇게 하면
j가 홀수일 때 f(f(${p}_{j}$))=f(${P}_{j+1}$)=$\frac{1}{{p}_{j}}$
j가 짝수일 때f(f(${p}_{j}$))=f($\frac{1}{{P}_{j-1}}$)=$\frac{1}{f({P}_{j-1})}$=$\frac{1}{{p}_{j}}$
이므로 임의의 소수 p에 대해서f(f(p))=$\frac{1}{p}$. 즉 성질 (b)가 성립한다.
유리수 $\frac{b}{a}$에 대해서는 f($\frac{b}{a}$)=f(b)f($\frac{1}{a}$)=$\frac{f(b)}{f(a)}$ 로 된다.
즉 (F)가 구하고자 하는 한 함수이다.
(주) 여기서는 소수를 차례대로 나열해놓고 정의했으므로 이 나열방법을 바꾸면 얼마든지 많은 함수를 구성할 수 있다.
5. ${n}_{0}$으로부터 시작하여 경기자 A가 이길 수 있는 술책을 구사할 수 있는 모든 자연수 ${n}_{0}$의 집합을 W라 하자.
<;보조정리>; {m, m+1,…,1990}⊂W,s≦1990, $\frac{s}{pr}$≧m 라 하자. 여기서 p는 소수이고 r∈N이며 ${p}^{r}$은 s의 최대인수이다.
그러면 $\sqrt{s}$≦${n}_{0}$＜m인 모든 자연수 ${n}_{0}$은 W의 원소이다.
<;증명>; 이러한 한 ${n}_{0}$로 부터 시작하면 A는 ${n}_{1}$=s를 잡는다.
그러면 B는 m≦$\frac{s}{pr}$≦${n}_{2}$≦s≦1990인 ${n}_{0}$을 취할 수 밖에 없다.
${n}_{2}$∈W이므로 A는 이길 수 있다. 따라서 보조정리는 증명되었다.
(a) ${45}^{2}$=2025>;1990 이므로 45≦${n}_{0}$＜1990 인 모든 ${n}_{0}$은 ${n}_{0}$∈W이다.
m=45 이므로 s=420=${2}^{2}$×3×5×7은 위의 보조정리의 조건을 만족하고 $\sqrt{420}$＜21≦45 이므로 {21,22,…,44}⊂W이다.
m=21,s=168=${2}^{3}$×3×7을 이용하면 보조정리로 부터 {13,14,…,20}⊂W.
m=13,s=105=3×5×7을 이용하면 보조정리로 부터 {11,12}⊂W.
m=11,s=60=${2}^{2}$×3×5라 하면 {8,9,10}⊂W이다.
따라서 {8,9,…,1990}⊂W이다.
${n}_{0}$>;1990일 때는 A는 ${2}^{r}$×${3}^{2}$＜${n}_{0}$≦${2}^{r+1}$×${3}^{2}$＜²₀인 자연수 r을 찾아서 ${n}_{1}$=${2}^{r+1}$×${3}^{2}$을 취한다. 그러면 B는 8≦${n}_{2}$＜${n}_{0}$인 ${n}_{2}$를 취할 수 밖에 없고, 이것을 유한번 되풀이 하면 8≦${n}_{2k}$≦1990인 상태로 되며 결국은 A가 이기게 된다.
즉 ${n}_{0}$≧8이면 A가 이기도록 할 수 있다.
(b) ${n}_{0}$≦5인 경우를 생각하자.
세개의 서로 다른 곱의 세개의 서로 다른 소수의 곱의 최소값은 2×3×5=30>;${5}^{2}$이므로 A는 ${n}_{1}$=${p}^{r}$×${q}^{s}$인 ,${n}_{1}$을 취할 수 밖에 없다. 여기서 p는 소수이고 q는 소수 또는 1.${p}^{r}$>;${q}^{s}$,r,s≧1이다. 그러면 B는 ${n}_{2}$=${q}^{s}$≦$\frac{{n}_{1}}{pr}$＜$\sqrt{{n}_{1}}$≦${n}_{0}$를 취한다.
따라서 이 과정을 유한번 반복하면 B는 ${n}_{2k}$=1을 택할 수 있고, B가 이긴다. B가 (c)끝으로 ${n}_{0}$=6 또는 ${n}_{0}$=7이면 A는 ${n}_{1}$=30=2×3×5 또는 ${n}_{1}$=42=2×3×7을 취할 수 밖에 없고 이때 B는 ${n}_{2}$=6을 택할 수 있다. 이 이후에는 A와 B는 30,6,30,6,…
을 반복해서 택할 수 밖에 없고 둘은 비긴다.
(답)(a) ${n}_{0}$≦8
(b) ${n}_{0}$≦5
(c) ${n}_{0}$≦6,7
6. 내각의 크기가 같으므로 한 외각의 크기는 α=$\frac{2π}{1990}$이다.
구하는 1990각형을 ${A}_{0}$${A}_{1}$${A}_{2}$…${A}_{1989}$라 하고 벡터$\overrightarrow{ArAr+1}$을 복소수 ${n}_{r}$${e}^{irα}$,r=0,1,…,1989로 나타내기로 하자. 여기서 A1990=${A}_{0}$라 한다. 여기서 ${n}_{0}$,${n}_{1}$,…,${n}_{1989}$는 ${1}^{2}$,${2}^{2}$…,${1990} ^{2}$의 순열이다. 그러면 문제는 다음과 같이 나타낼 수 있다.
"$\sum_{r=0}^{1989}$nγ${e}^{ira}$=0 을 만족시키는 ${1}^{2}$,${2}^{2}$…,${1990} ^{2}$의 적당한 순열 (${n}_{0}$,${n}_{1}$…,${n}_{1989}$을 구하여라". 이것은 다음과 같이 나타낼 수 있다.
(1) "단위 원판의 둘레를 1990개의 무게 ${1}^{2}$,${2}^{2}$,…,${1990} ^{2}$을 달아서 원점0가 평형의 중심이 되게 할 수 있음을 보이면 된다".
먼저 1990개의 무게를 995개의 짝 (${1}^{2}$,${2}^{2}$),(${3}^{2}$,${4}^{2}$),…,(${1989} ^{2}$,${1990} ^{2}$)으로 나누고 단위원의 지름의 양끝이 서로의 짝을 놓으면 문제를 다음과 같이 단순화 시킬 수 있다.
(2) "단위 원의 둘레를 995 등분하고 각 호에 995개의 무게 ${2}^{2}$-${1}^{2}$=3, ${4}^{2}$-${3}^{2}$=7,…,${1990} ^{2}$-${1989} ^{2}$=3979 를 어떻게 배치하면 평형상태로 만들 수 있는가?"라는 문제로 고칠 수 있다.
다음에는 995=5×199 이므로 995개의 무게를 199개의 짝(*) (3,7,11,15,19),(23,27,31,35,39),…,(3963,3967,3971,3975,3979)로 분할한다.
β=$\frac{2π}{199}$,γ=$\frac{2π}{5}$라 하자.
꼭지점이 1,${e}^{iγ}$,${e}^{2iγ}$,${e}^{3iγ}$,${e}^{4iγ}$인 5각형을 ${F}_{1}$이라 하고, 5각형 ${e}^{1kβ}$${F}_{1}$을 ${F}_{k+1}$(k=0,1,…,198)라 하자.
(*)에서의 (k+1)번째의 5개의 무게를 5각형 ${F}_{k+1}$의 꼭지점에 놓으면 복소수의 k+1번재의 짝(2k+3)${e}^{ikβ}$,(2k+7)${e}^{i(kβ+γ)}$,(2k+11)${e}^{i(kβ+2γ)}$,(2k+15)${e}^{i(kβ+3γ)}$,(2k+19)${e}^{i(kβ+4γ)}$ k=0,1,2,…,198을 얻는다.
1+${e}^{iγ}$+${e}^{2iγ}$+${e}^{3iγ}$+${e}^{4iγ}$=0 이므로 위의 (k=1)번째 짝의 복소수의 합은
n=3+7${e}^{iγ}$+11${e}^{2iγ}$+15${e}^{3iγ}$+19${e}^{fiγ}$라 할때 ${ne}^{1kβ}$로 나타낼 수 있다.
199개의 모든 짝의 복소수의 합은 n(1+${e}^{iβ}$+…+${e}^{1989iβ}$ =0 이다.
따라서 주어진 조건을 만족시키는 1990각형이 존재함을 알 수 있다.
끝으로 $\sum_{γ=0}^{1989}$nγ${e}^{ira}$=0을 구체적으로 나타내면 다음과 같다.
0=$\sum_{k=0}^{198}$ $\sum_{l=0}^{4}$ (20k+4ℓ+3)${e}^{i(kβ+ιγ)}$
=$\sum_{k=0}^{198}$ $\sum_{l=0}^{4}$${(10k+2ℓ+2)} ^{2}$-${(10k+2ℓ+1)} ^{2}$${e}^{i(kβ+ιγ)}$
=$\sum_{k=0}^{198}$ $\sum_{l=0}^{4}$ $\sum_{m=1}^{2}$ ${(10k+2ℓ+m)} ^{2}$${e}^{i(kβ+ιγ+mπ)}$
여기서 k가 0,1,2,…,198,ℓ이 0,1,2,3,4, m이 1,2를 움직이면 10k+2ℓ+m은 1,2,…,1990을 꼭 한번씩 취하고 ${e}^{i(kβ+ιγ+mπ)}$ =는 1,${e}^{iα}$,…,${e}^{1990iα}$ 를 꼭한번 취한다.
1. 한 원의 두 현 AB,CD가 원의 내부의 점E에서 만나고 있다.M을 선분 EB위의 양끝점이 아닌 점이라 하자. 세점 D,E,M을 지나는 원에 E에서 그은 접선이 직선BC,AC와 만나는 점을 각각 F,G라 한다.
$\frac{AM}{AB}$=t라 할때 $\frac{EG}{EF}$를 t의 식으로 나타내라. ●인도 출제
2. n은 n≧3인 정수다. 한 원둘레 위의 서로 다른 2n-1개 점으로 이루어진 집합을 E라 하자.E의 점 중에서 꼭 k개의 점에 검은 칠을 할 때, 검은 칠을 한 것 중 적어도 한 쌍의 점이 있어서, 이 두 점을 제외한 두개의 호 중에서 어느 하나의 호위에 E의 점이 꼭n개 있으면 'k개가 색칠이 잘 되었다'라고 한다.
모든k개가 색칠이 잘된 석이 되기 위한 k의 최소값을 구해라. ●체코 출제
3. $\frac{{2}^{n}+1}{{n}^{2}}$이 정수가 되는 1보다 큰 모든 정수 n을 구해라. ●루마니아 출제
4. ${Q}^{+}$를 양의 유리수 전체의 집합이라 하자. 모든 양의 유리수 x,y에 대해 f(xf(y))=$\frac{f(x)}{y}$를 만족시키는 함수 f:${Q}^{+}$→${Q}^{+}$를 만들어라. ●터키 출제
5. 처음에 1보다 큰 정수${n}_{0}$가 주어져 있고, 두 경기자 A,B가 다음 규칙에 따라서 정수 ${n}_{1}$,${n}_{2}$,${n}_{3}$…을 번갈아 뽑고 있다.
${n}_{2k}$를 알았을 때,A는 ${n}_{2k}$≦${n}_{2k+1}$을 알았을 때, B는 $\frac{{n}_{2k+1}}{{n}_{2k+2}}$이 소수의 자연수 거듭제곱이 되는 정수 ${n}_{2k+2}$를 뽑는다. A는 1990을 뽑으면 이기고,B는 1을 뽑으면 이긴다고 한다.
다음 각각을 만족시키는 ${n}_{0}$을 모두 구하고 그 이유를 설명해라. ●서독 출제
(a) A가 이길 수 있는${n}_{0}$
(b) B가 이길 수 있는${n}_{0}$
(c) A도 B도 이길 수 없는${n}_{0}$
6. 다음 두 성질을 가지는 볼록1990각형이 존재함을 증명하여라.
(a) 모든 내각의 크기는 같다.
(b) 변의 길이는 ${1}^{2}$, ${2}^{2}$, ${3}^{2}$,…. ${1989} ^{2}$, ${1990} ^{2}$을 적당한 순서로 나열한 것이다. ●네덜란드 출제
풀이 및 해답
1. D와 A,B,M를 잇는다.∠CEF=∠DEG=∠EMD'=∠ECF=∠MAD이므로 △CEF∾△AMD 따라서 CE·MD=AM·EF 한편 ∠ECG=∠MBD(AD 위의 원주각) ∠CGE=∠CEF-∠GCE=∠EMD-∠MBD=∠BDM이므로 △CGE∾△BDM 따라서 GE·MB=CE·MD GE·MB=AM·EF 즉 $\frac{GE}{EF}$=$\frac{AM}{MB}$=$\frac{AM}{AB-AM}$=$\frac{tAB}{(1-t)AB}$=$\frac{t}{1-t}$…(답)
정수 ℓ∈Z에 대해 ℓ≡i(mod 2n-1)이면 ℓ과i∈S는 같은 것으로 생각한다. ｜i-j｜=n+1 또는 ｜i-j｜=n-2이면 S의 원소 i와 j는 '서로 관련된 원소'라고 부르기로 하자.
i와 j가 서로 관련된 원소이면 이들 두 원소에 해당하는 점을 제외한 어느 한쪽의 호위에 주어진 2n-1개의 점 중에서 꼭 n개의 점이 있게 되고 역도 성립한다(위의 그림 창조).
모든 k개의 색칠이 잘 된 것이 될 필요충분조건은 k개의 원소를 가진 S의 어떠한 부분집합A에 대해서도 A에는 두 개의 서로 관련된 원소가 존재하는 것이다.
A에는 서로 관련된 원소가 없다고 가정하자.
j∈A에 대하여 S(j)를 j와 서로 관련된 S의 모든 원소의 집합이라 하면 가정에 의해 모든 j∈A에 대해 S(j)와 A는 서로 소이다 각 원소는 많아야 두 개의 S(j)에 나타나고, 모든 j∈A에 대해 S(j)의 합집합은 적어도 n개의 원소를 가지므로 이것은 #A=n에 모순이다.
귀류법에 의하여 A에는 서로 관련된 원소의 짝이 반드시 존재한다. 즉 n개의 색칠은 잘된 색칠이다.
(2) 3∤2n-1이면 n-1개의 색칠은 잘된 색칠이 아니다.
B⊂S,#B=n-1인 B에는 서로 관련된 원소가 없는 경우를 만들면 된다.
B={3k｜k=0,1,2,…'n-2}
C={3k+n-2｜k=0,1,2,…'n-1}라 하자. C에서 k대신에 n-1-k를 대입하면
C={3(n-1-k)+n-2｜k=0,1,2,…'n-1}={2(2n-1)-3-3k｜k=0,1,2,…'n-1}={3(-1-K)｜k=0,1,2,…'n-1}3∤2n-1이므로
B∪C={3k｜k=-n, -n+1,…,-1,0,1,2,…, n-2}=S #B=n-1,#C=n이므로 B∩C=∅ j∈B,j=3k(0≦k≦n-2)라 하면
S(j)={3k+n-2, 3k+n+1}={3k+n-2,3(k+1)+n-2}⊂C 이므로 S(j)∩B=∅다. 이것은 B에는 서로 관련된 원소의 짝이 없다는 것을 뜻한다.
(주) a∤b는 'b는 a로 나누어지지 않는다'는 기호고 a｜b는 'b는 a로 나누어진다'는 기호다.
(3) 3｜2n-1인 경우를 생각하자. 이 경우에는 n≡(mod 3)이다.
n=3m-1(m≧2)라 하면 2n-1=3(2m-1),n-2=3(m-1),n+1=3m이다. 따라서 S의 원소i와 j가 서로 관련된 원소면 i≡j(mod 3)이다.
r=0,1,2에 대해 ${S}_{r}$={3k+r｜k=0,1,2,…,2m-2}라 하면 S는 서로 소인 부분집합 ${S}_{0}$,${S}_{1}$,${S}_{2}$로 나누어진다.
그리고 S의 각원소 i에 대해 i∈${S}_{r}$이면i와 서로 관련된 두 개의 원소는 모두 ${S}_{r}$에 속함을 알 수 있다.
여기서 3m-2(=n-1) 개의 색칠이 잘된 색칠임을 증명하고자 한다.
A⊂S,#A=3m-2이면 비둘기구멍(pigeonhole)원리에 따라 A∩${S}_{r}$인 꼴의 한 부분집합은 적어도 m개의 원소를 갖는다.
(1)에서 사용한 방법에 의하면 A∩${S}_{r}$(⊂A)에는 서로 관련된 원소의 짝이 존재함을 밝힐 수 있다.
끝으로 3(m-1)(=n-2)개의 색칠은 잘된 색칠이 될 수 없음을 보이고자 한다. 서로 관련된 원소를 갖지 않는 ${S}_{r}$의 m-1개의 원소로 된 부분집합을 구성해 보이면 된다.
${B}_{r}$={3k+r｜k=0,1,2,…,m-2}(r=0,1,2)라 하자.
i와 j가 서로 관련된 원소일 필요충분조건은 ｜i-j｜=3(m-1) 또는 ｜i-j｜=3m 이므로 ${B}_{0}$,${B}_{1}$,${B}_{2}$의 각각에는 서로 관련괸 원소가 없음을 알 수 있다.
이상을 종합하면 다음과 같다.
k의 최소값 n-1,2n-1이 3의 배수 일때 n,2n-1이 3의 배수가 아닐때
3. ${2}^{n}$+1이 홀수이므로 ${n}^{2}$｜${2}^{n}$+1이면 n은 홀수다.
(주:b｜a는 'a가 b로 나누어진다'는 뜻이다.) 따라서 n≧3이다. 지금 n의 최소의 소인수를 p라 하자. 그러면 p≧3이고 p｜${2}^{n}$+1, 즉 ${2}^{n}$=-1(mod p)이다. i를 ${2}^{i}$1(mod p)인 최소의 자연수라 하면 ${2}^{p-1}$=-1(mod p)로 부터 i＜p-1이다.
n=ki+r(0≦r≦i-1)라 하면 다음 결과를 얻는다.
${2}^{n}$=${2}^{ki}$×${2}^{r}$≡${(-1)} ^{k}$${2}^{r}$ (mod p). k를 짝수라 하면 ${2}^{r}$≡${2}^{n}$≡-1(mod p)이고 이것은 i의 선택에 모순. 따라서 k는 홀수이다. 이때 ${2}^{r}$≡1(mod p)이다.
여기서 r>;0라 하고 i=r+d(1≦d＜i)라 하면 ${2}^{d}$≡${2}^{r}$×${2}^{d}$=${2}^{r+d}$ ${2}^{i}$≡-1(mod p) 역시 i의 선택에 모순이다.
r=0 따라서 n=ki이고 i｜n. i＜p이고 p는 최소의 소인수이므로 i=1. 따라서 p｜2+1 ∴ p=3.
n=${3}^{k}$d(k≧1),(d,3)=1라 하자.
k≧2라 하면 ${n}^{2}$｜${2}^{n}$+1,${3}^{2k}$｜${(3-1)} ^{n}$+1이므로 ${(3-1)} ^{n}$을 전개하여
${3}^{k+2}$｜(${3}^{k+1}$ d-${(-1)}^{h}$ (∵ n은 홀수)
를 얻는다. hi의 소인수분해의 3의 지수는 $\frac{h}{2}$보다 작고 ${3}^{h}$의 소인수분해의 3의 지수는 k+$\frac{h}{2}$보다 크므로 h≧2일때 ${3}^{k+2}$｜${3}^{h}$, 즉 ${3}^{k+2}$｜${3}^{k+1}$d를 얻는다.
이것은 모순이다. ∴ k=1이고 n=3d이다.
d=1 즉 n=3 이면 성립한다.
q를 d의 최소의 소인수라 하면 d는 홀수이고 (d,3)=1 이므로 q≧5,q｜${2}^{n}$+1.
j를 ${2}^{j}$≡-1(mod q)인 최초의 자연수라 하면 페르마(Fermat)의 정리에 의하여 j＜q-1.
앞에서와 같은 방법을 되풀이하면 j｜n이다.
n=3d, (3,d)=1, j＜q-1,q는 d의 소인수이므로 j=1 또는 3이다.
${2}^{j}$≡1(mod q)로 부터 q｜3 또는 q｜9 ∴ q=3.
이것은 q≧5에 모순이다.
이상을 종합하면 $\frac{{2}^{n+1}}{{n}^{2}}$ 이 정수가 되는 1보다 큰 정수는 n=3 뿐이다.
(답) n=3
4. f(${y}_{1}$=f(${y}_{2}$)라 하면 f(xf${y}_{1}$))=f(xf(${y}_{2}$))=$\frac{f(x)}{{y}_{1}}$=$\frac{f(x)}{{y}_{2}}$ 이므로 ${y}_{1}$=${y}_{2}$ 이다.
즉 f(x)는 1:1 함수이다.y=1이라하면 모든 y∈${Q}^{+}$ 에 대하여 f(f(y))=$\frac{1}{y}$이므로 f($\frac{1}{y}$)=f{f(f(y))}=$\frac{1}{f(y)}$이 모든 y∈${Q}^{+}$ 에 대하여 성립한다. 끝으로 y=f($\frac{1}{t}$) 이라 하면 f(xf(f($\frac{1}{t}$)))=f(xt),$\frac{f(x)}{y}$=f(x)f(f(f($\frac{1}{t}$)))=f(x)f(t)
f(xt)=f(x)f(t)가 모든 x,t∈${Q}^{+}$에 대하여 성립한다.
역으로, 모든 x,t∈${Q}^{+}$에 대하여 두개의 함수방정식
(a) f(xt)=f(x)f(t)
(b) f(f(x))=$\frac{1}{x}$
을 만족시키는 함수 f는 주어진 조건을 만족시킴을 쉽게 알 수 있다.
조건 (a)를 만족시키는 함수 f:${Q}^{+}$→${Q}^{+}$를 우선 소인수분해된 정수에 대해서 생각한다. ${p}_{j}$를 j번째의 소수라 하고 x=${{p}_{1}}^{{n}_{1}}$${{p}_{2}}^{{n}_{2}}$…${{p}_{k}}^{{n}_{k}}$ 라 하면 (a)에 의해
f(${{p}_{1}}^{{n}_{1}}$${{p}_{2}}^{{n}_{2}}$…${{p}_{k}}^{{n}_{k}}$)=${(f({p}_{1}))} ^{{n}_{1}}$${(f({p}_{2}))} ^{{n}_{2}}$…${(f({p}_{k}))} ^{{n}_{k}}$ 이다. 따라서 소수 ${p}_{j}$에 대하여f(${p}_{j}$)를 정하면 된다.
이것은 다음과 같이 구성된다.
(F):f(${p}_{j}$)=${P}_{j+1}$,j가 홀수일 때 $\frac{1}{{P}_{j-1}}$,j가 짝수일 때
이렇게 하면
j가 홀수일 때 f(f(${p}_{j}$))=f(${P}_{j+1}$)=$\frac{1}{{p}_{j}}$
j가 짝수일 때f(f(${p}_{j}$))=f($\frac{1}{{P}_{j-1}}$)=$\frac{1}{f({P}_{j-1})}$=$\frac{1}{{p}_{j}}$
이므로 임의의 소수 p에 대해서f(f(p))=$\frac{1}{p}$. 즉 성질 (b)가 성립한다.
유리수 $\frac{b}{a}$에 대해서는 f($\frac{b}{a}$)=f(b)f($\frac{1}{a}$)=$\frac{f(b)}{f(a)}$ 로 된다.
즉 (F)가 구하고자 하는 한 함수이다.
(주) 여기서는 소수를 차례대로 나열해놓고 정의했으므로 이 나열방법을 바꾸면 얼마든지 많은 함수를 구성할 수 있다.
5. ${n}_{0}$으로부터 시작하여 경기자 A가 이길 수 있는 술책을 구사할 수 있는 모든 자연수 ${n}_{0}$의 집합을 W라 하자.
<;보조정리>; {m, m+1,…,1990}⊂W,s≦1990, $\frac{s}{pr}$≧m 라 하자. 여기서 p는 소수이고 r∈N이며 ${p}^{r}$은 s의 최대인수이다.
그러면 $\sqrt{s}$≦${n}_{0}$＜m인 모든 자연수 ${n}_{0}$은 W의 원소이다.
<;증명>; 이러한 한 ${n}_{0}$로 부터 시작하면 A는 ${n}_{1}$=s를 잡는다.
그러면 B는 m≦$\frac{s}{pr}$≦${n}_{2}$≦s≦1990인 ${n}_{0}$을 취할 수 밖에 없다.
${n}_{2}$∈W이므로 A는 이길 수 있다. 따라서 보조정리는 증명되었다.
(a) ${45}^{2}$=2025>;1990 이므로 45≦${n}_{0}$＜1990 인 모든 ${n}_{0}$은 ${n}_{0}$∈W이다.
m=45 이므로 s=420=${2}^{2}$×3×5×7은 위의 보조정리의 조건을 만족하고 $\sqrt{420}$＜21≦45 이므로 {21,22,…,44}⊂W이다.
m=21,s=168=${2}^{3}$×3×7을 이용하면 보조정리로 부터 {13,14,…,20}⊂W.
m=13,s=105=3×5×7을 이용하면 보조정리로 부터 {11,12}⊂W.
m=11,s=60=${2}^{2}$×3×5라 하면 {8,9,10}⊂W이다.
따라서 {8,9,…,1990}⊂W이다.
${n}_{0}$>;1990일 때는 A는 ${2}^{r}$×${3}^{2}$＜${n}_{0}$≦${2}^{r+1}$×${3}^{2}$＜²₀인 자연수 r을 찾아서 ${n}_{1}$=${2}^{r+1}$×${3}^{2}$을 취한다. 그러면 B는 8≦${n}_{2}$＜${n}_{0}$인 ${n}_{2}$를 취할 수 밖에 없고, 이것을 유한번 되풀이 하면 8≦${n}_{2k}$≦1990인 상태로 되며 결국은 A가 이기게 된다.
즉 ${n}_{0}$≧8이면 A가 이기도록 할 수 있다.
(b) ${n}_{0}$≦5인 경우를 생각하자.
세개의 서로 다른 곱의 세개의 서로 다른 소수의 곱의 최소값은 2×3×5=30>;${5}^{2}$이므로 A는 ${n}_{1}$=${p}^{r}$×${q}^{s}$인 ,${n}_{1}$을 취할 수 밖에 없다. 여기서 p는 소수이고 q는 소수 또는 1.${p}^{r}$>;${q}^{s}$,r,s≧1이다. 그러면 B는 ${n}_{2}$=${q}^{s}$≦$\frac{{n}_{1}}{pr}$＜$\sqrt{{n}_{1}}$≦${n}_{0}$를 취한다.
따라서 이 과정을 유한번 반복하면 B는 ${n}_{2k}$=1을 택할 수 있고, B가 이긴다. B가 (c)끝으로 ${n}_{0}$=6 또는 ${n}_{0}$=7이면 A는 ${n}_{1}$=30=2×3×5 또는 ${n}_{1}$=42=2×3×7을 취할 수 밖에 없고 이때 B는 ${n}_{2}$=6을 택할 수 있다. 이 이후에는 A와 B는 30,6,30,6,…
을 반복해서 택할 수 밖에 없고 둘은 비긴다.
(답)(a) ${n}_{0}$≦8
(b) ${n}_{0}$≦5
(c) ${n}_{0}$≦6,7
6. 내각의 크기가 같으므로 한 외각의 크기는 α=$\frac{2π}{1990}$이다.
구하는 1990각형을 ${A}_{0}$${A}_{1}$${A}_{2}$…${A}_{1989}$라 하고 벡터$\overrightarrow{ArAr+1}$을 복소수 ${n}_{r}$${e}^{irα}$,r=0,1,…,1989로 나타내기로 하자. 여기서 A1990=${A}_{0}$라 한다. 여기서 ${n}_{0}$,${n}_{1}$,…,${n}_{1989}$는 ${1}^{2}$,${2}^{2}$…,${1990} ^{2}$의 순열이다. 그러면 문제는 다음과 같이 나타낼 수 있다.
"$\sum_{r=0}^{1989}$nγ${e}^{ira}$=0 을 만족시키는 ${1}^{2}$,${2}^{2}$…,${1990} ^{2}$의 적당한 순열 (${n}_{0}$,${n}_{1}$…,${n}_{1989}$을 구하여라". 이것은 다음과 같이 나타낼 수 있다.
(1) "단위 원판의 둘레를 1990개의 무게 ${1}^{2}$,${2}^{2}$,…,${1990} ^{2}$을 달아서 원점0가 평형의 중심이 되게 할 수 있음을 보이면 된다".
먼저 1990개의 무게를 995개의 짝 (${1}^{2}$,${2}^{2}$),(${3}^{2}$,${4}^{2}$),…,(${1989} ^{2}$,${1990} ^{2}$)으로 나누고 단위원의 지름의 양끝이 서로의 짝을 놓으면 문제를 다음과 같이 단순화 시킬 수 있다.
(2) "단위 원의 둘레를 995 등분하고 각 호에 995개의 무게 ${2}^{2}$-${1}^{2}$=3, ${4}^{2}$-${3}^{2}$=7,…,${1990} ^{2}$-${1989} ^{2}$=3979 를 어떻게 배치하면 평형상태로 만들 수 있는가?"라는 문제로 고칠 수 있다.
다음에는 995=5×199 이므로 995개의 무게를 199개의 짝(*) (3,7,11,15,19),(23,27,31,35,39),…,(3963,3967,3971,3975,3979)로 분할한다.
β=$\frac{2π}{199}$,γ=$\frac{2π}{5}$라 하자.
꼭지점이 1,${e}^{iγ}$,${e}^{2iγ}$,${e}^{3iγ}$,${e}^{4iγ}$인 5각형을 ${F}_{1}$이라 하고, 5각형 ${e}^{1kβ}$${F}_{1}$을 ${F}_{k+1}$(k=0,1,…,198)라 하자.
(*)에서의 (k+1)번째의 5개의 무게를 5각형 ${F}_{k+1}$의 꼭지점에 놓으면 복소수의 k+1번재의 짝(2k+3)${e}^{ikβ}$,(2k+7)${e}^{i(kβ+γ)}$,(2k+11)${e}^{i(kβ+2γ)}$,(2k+15)${e}^{i(kβ+3γ)}$,(2k+19)${e}^{i(kβ+4γ)}$ k=0,1,2,…,198을 얻는다.
1+${e}^{iγ}$+${e}^{2iγ}$+${e}^{3iγ}$+${e}^{4iγ}$=0 이므로 위의 (k=1)번째 짝의 복소수의 합은
n=3+7${e}^{iγ}$+11${e}^{2iγ}$+15${e}^{3iγ}$+19${e}^{fiγ}$라 할때 ${ne}^{1kβ}$로 나타낼 수 있다.
199개의 모든 짝의 복소수의 합은 n(1+${e}^{iβ}$+…+${e}^{1989iβ}$ =0 이다.
따라서 주어진 조건을 만족시키는 1990각형이 존재함을 알 수 있다.
끝으로 $\sum_{γ=0}^{1989}$nγ${e}^{ira}$=0을 구체적으로 나타내면 다음과 같다.
0=$\sum_{k=0}^{198}$ $\sum_{l=0}^{4}$ (20k+4ℓ+3)${e}^{i(kβ+ιγ)}$
=$\sum_{k=0}^{198}$ $\sum_{l=0}^{4}$${(10k+2ℓ+2)} ^{2}$-${(10k+2ℓ+1)} ^{2}$${e}^{i(kβ+ιγ)}$
=$\sum_{k=0}^{198}$ $\sum_{l=0}^{4}$ $\sum_{m=1}^{2}$ ${(10k+2ℓ+m)} ^{2}$${e}^{i(kβ+ιγ+mπ)}$
여기서 k가 0,1,2,…,198,ℓ이 0,1,2,3,4, m이 1,2를 움직이면 10k+2ℓ+m은 1,2,…,1990을 꼭 한번씩 취하고 ${e}^{i(kβ+ιγ+mπ)}$ =는 1,${e}^{iα}$,…,${e}^{1990iα}$ 를 꼭한번 취한다.
