UPO/4회: 두 판 사이의 차이

2019년 12월 18일 (수) 22:19 판

1일차 문제

f(x)를 다음과 같이 정의하자.

f(0)=0, f(1)=1
f(2n)=f(n), f(2n+1)=f(n)+1 (단, n은 자연수)

한 사람이 수직선의 원점(0의 점) 위에 있다. 1부터 n까지의 수를 임의로 배치한 다음, 앞에 있는 수부터 차례대로 다음 과정을 반복한다.

1) 수가 짝수일 경우: 오른쪽(양의 방향)으로 f(x)만큼 움직인다.
2) 수가 홀수일 경우: 왼쪽(음의 방향)으로 f(x)만큼 움직인다.

이 과정을 완료한 뒤 사람이 서 있는 위치를 g(n)이라 하자. 단, g(0)=0이라고 하자.

이때, 아래 문제들을 풀어라.

f(1048574)의 각 자리 수의 합을 구하시오.
~~임의의 자연수 n에 대해, g(n)이 유일함을 증명하시오.~~
g(15), g(16)을 구하시오.
n이 자연수일 때, g(n)의 최댓값과 그때의 n을 구하시오.
g(2019)를 구하고, n이 홀수일 때 g(n)을 구하시오.
k(x)=g(x-4)-g(x-3)-g(x-2)+g(x-1)라 하자. n이 4의 배수일 때 ${\frac {k(4)+k(8)+\cdots +k(n)}{n}}$ 을 구하여라.

p.s. 2번 문제의 경우 너무 당연한 사실을 증명하는 것이 매우 어려워 보이므로 삭제합니다. 제가 원했던 답은 "수를 배치한 순서와 g(n)은 아무 상관이 없다"였습니다.

1번 (해결)

2 --Rika14369(토론)(기여:회) 2019년 4월 1일 (월) 21:45 (KST)
오답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 18:24 (KST)
28 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 19:58 (KST)
오답입니다... -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 20:25 (KST)
10 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 20:57 (KST)
정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 21:03 (KST)

3번 (해결)

-4, 1 --Rika14369(토론)(기여:회) 2019년 4월 1일 (월) 21:50 (KST)
오답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 18:24 (KST)
~~8, -8 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 20:00 (KST)~~
오답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 20:25 (KST)
~~19, 15 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 21:09 (KST)~~
오답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 21:21 (KST)
-8, -7 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 22:12 (KST)
정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 22:14 (KST)

4번 (해결)

n=2 Sleep (토론) 2019년 12월 18일 (수) 17:30 (KST)

문제를 다시 한번 잘 읽어주세요. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 12월 18일 (수) 19:50 (KST)

n=2,g(n)=0 Sleep (토론) 2019년 12월 18일 (수) 21:41 (KST)

정답입니다. 조금 덧붙이자면, 4번 소문항이 아마도 여기 있는 문제들 중 증명의 난이도가 가장 높습니다. (증명이 가능하긴 합니다.) 일단 문제는 해결된 것으로 하겠지만, 혹시 증명 과정을 알아내셨다면 올려 주실 수 있나요? -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 12월 18일 (수) 22:02 (KST)

제가 위키 문법에 미성숙해서 가독성이 떨어질 수 있는데 양해바랍니다. 유익한 수학문제 감사합니다! Sleep (토론) 2019년 12월 18일 (수) 22:13 (KST)

소정리 0

문제를 풀면서 아셨을 테지만, f(n)은 n을 2진수로 나타낸 뒤 자릿수를 모두 합산한 값입니다.

귀납법으로 자명히 증명이 되니 따로 쓰지는 않겠습니다.

소정리 1

g(2^k-1)=-2^(k-1)

이는 귀납법으로 증명이 가능합니다. k=1,2 일때 g(1)=-1, g(3)=-2로 성립합니다.

이제 k일때 성립을 가정하고 k+1일때 성립함을 증명하겠습니다. (단, k는 2이상입니다.)

f(x)를 문제에 제시한 대로 합산하여 g(n)을 구하는 경우, 그 부호가 뒤바뀌기 때문에 (g(n)=-f(1)+f(2)+.....)

편의상 부호까지 생각한 함수 h(x)=(-1)^x * f(x)를 정의하겠습니다. 이렇게 하면 g(n)=h(1)+h(2)+...가 됩니다.

자 그러면, 2^k 이상, 2^(k+1)-1 이하인 정수 t를 생각해봅시다.

t를 2진수로 표현하면 1 a1 a2 a3.... ak (2) 꼴로 나타낼 수 있으므로,

h(t)는 기우성에 따라서 h(t-2^k)값에 1을 더하거나 뺀 값이 됩니다.

더 정확하게 말하면, t가 홀수이면 1을 빼주고, t가 짝수이면 1을 더해줘야겠죠.

수식으로 정리하면

h(t) = h(t-2^k) + (-1) ^ t 가 됩니다.

이제 g(2^(k+1)-1)을 계산할 차례입니다.

g(2^(k+1)-1)=h(1) + h(2) + ..... + h(2^k-1) + h(2^k) + .... + h(2^(k+1)-1)

= g(2^k-1) + h(2^k) + .... + h(2^(k+1)-1)

= g(2^k-1) + h(0) + 1 + h(1) - 1 +.....+ h(2^k-1) - 1

그런데 부가적으로 나오는 +1, -1 항은 서로 반복되어 나타나고, 각각 나타나는 횟수가 동일하므로 모두 상쇄됩니다. 따라서

g(2^(k+1)-1) = g(2^k-1) + h(0) + h(1) +.....+ h(2^k-1) = 2*g(2^k-1) = -2^k 가 성립합니다.

귀납적으로 원 명제가 증명되었습니다!

소정리 3

g(2^k-1)=-2^(k-1)+1

h(2^k) = 1 이므로 소정리 2에 의해 성립.

5번 (해결)

~~2027, 2036 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 21:13 (KST)~~
오답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 21:21 (KST)
-1010, g(n)=-(n+1)/2 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 23:19 (KST)
정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 23:39 (KST)

6번 (해결) <명예의 전당 문항>

$-{\frac {1}{4}}$ QuantumGravity, 완성되지 않은 이론 (토론) 2019년 4월 14일 (일) 13:50 (KST)
정답이긴 합니다만은, 혹시 풀이를 알 수 있을까요? -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 15일 (월) 08:16 (KST)
2번을 풀면 $g\left(x\right)=\sum _{i=1}^{n}{\left(-1\right)^{i}f\left(i\right)}$ 임을 알 수 있습니다. 따라서 $k\left(x\right)=\left(-1\right)^{x-1}f\left(x-1\right)-\left(-1\right)^{x-3}f\left(x-3\right)$ 입니다. $x$ 가 4의 배수라면 $4s+4$ (단, $s$ 는 음수가 아닌 정수) 꼴로 쓸 수 있어서

{\begin{aligned}k\left(x\right)&=\left(-1\right)^{x-1}f\left(x-1\right)-\left(-1\right)^{x-1}f\left(x-3\right)\\&=\left(-1\right)^{4s+3}f\left(4s+3\right)-\left(-1\right)^{4s+3}f\left(4s+1\right)\\&=-\left(f\left(2s+1\right)+1\right)+\left(f\left(2s\right)+1\right)\\&=-f\left(2s+1\right)+f\left(2s\right)\\&=-f\left(2s+1\right)+f\left(2s\right)\\&=-\left(f\left(s\right)+1\right)+f\left(s\right)\\&=-1\end{aligned}}

이므로

{\frac {k(4)+k(8)+\cdots +k(n)}{n}}={\frac {-n/4}{n}}=-{\frac {1}{4}}

입니다(?!). 이제 보니 부호가 반대였다 카더라. ~~QuantumGravity, 완성되지 않은 이론 (토론) 2019년 4월 16일 (화) 09:41 (KST)~~ QuantumGravity, 완성되지 않은 이론 (토론) 2019년 4월 16일 (화) 15:17 (KST)

죄송합니다. 부호가 잘못된 걸 못 봤네요. 정답 맞습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 19일 (금) 17:46 (KST)

2일차 문제

f(x, y)를 다음과 같이 정의한다. 삼각형 ABC에서 각 B는 직각이고, AB=x, BC=y이다. 이때 각 A를 f(x, y)라 하자.

이때, 아래 문제들을 풀어라. 단, 중학교 수준 이내에서 풀어야 한다.

임의의 실수 x, y, r에 대해, f(x, y)=f(rx, ry)임을 증명하여라.
f(1, 1) = 3/4 f(1, a)를 만족하는 양의 실수 a를 구하여라.
f(2, 1)+f(3, 1)=f(b, 1)을 만족하는 양의 실수 b를 구하여라.
f(3, 1)+f(5, 1)+f(7, 1)+f(8, 1)=f(c, 1)을 만족하는 양의 실수 c를 구하여라.
임의의 양의 실수 x, y에 대해 f(x, 1)+f(y, 1)=f(z, 1)인 양의 실수 z를 x, y에 대해 나타내어라.

1번 (해결)

두 변에 각각 같은 수를 곱하면 자연히 삼각형은 모든 변의 길이가 일정하게 변화하면서 이전의 삼각형보다 커지거나 작아지겠죠. 여기서 이전의 삼각헝과 새로 만든 삼각형은 변의 길이만 조정되었을 뿐 모든 각은 그대로인 닮음꼴이라 할 수 있습니다. 따라서 f(x,y)와 f(rx, ry)는 같지요. — Malgok1 (토론·기여) 2019년 4월 16일 (화) 23:42 (KST)
정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 17일 (수) 08:08 (KST)

2번 (해결)

문제에 제시된 조건에 따라 f(1, 1)은 직각이등변삼각형임을 알 수 있으며, 동시에 45도의 값을 가지고 있단 것도 확인이 가능합니다.

그렇다면 계산을 했을 때 f(1, a)는 당연히 60도가 되어야 하겠죠? f(1, a)=60도를 만족하는 삼각형 ABC에서 BC는 삼각비 정리에 의해 √3임을 알 수 있습니다. 휴대폰으로 작성해서 수식 표현이 부실한 점 양해 부탁드립니다. — Malgok1 (토론·기여) 2019년 4월 18일 (목) 15:32 (KST)

정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 4월 18일 (목) 16:40 (KST)

3번 (해결)

요거이 글로 설명하기 거시기하다만은... f(2, 1)을 만족하는 삼각형을 $\bigtriangleup ABC$ 라고 하고, f(3, 1)을 만족하는 삼각형을 $\bigtriangleup A'B'C'$ 라고 합니다. 그리고, 점 A와 점 A'를 일치시키고 ${\overline {AB}}$ 와 ${\overline {A'B'}}$ 를 겹치게해서 그린 뒤에, 점 C와 점 C'를 잇는 선분을 그리면 $\bigtriangleup ACC'$ 는 각 C가 직각이며 ${\overline {AC}}={\overline {CC'}}={\sqrt {5}}$ 인 직각이등변삼각형이 되므로 f(1, 1). 즉, b=1. 사용자:뺶꾀싸쩐/서명 2019년 5월 13일 (월) 20:07 (KST)
정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 5월 14일 (화) 17:09 (KST)

4번 (해결)

f(3, 1)을 만족하는 삼각형을 $\bigtriangleup ABC$ 라고 하고, f(7, 1)을 만족하는 삼각형을 $\bigtriangleup A'B'C'$ 라고 하여 점 A와 점 A'를 일치시키고 ${\overline {AB}}$ 와 ${\overline {A'B'}}$ 를 겹치게해서 그린 뒤에 반직선 AC를 그립니다. C'에서 반직선 AC에 수선을 내리고 그 수선의 발을 D라고 두면 각 D는 당연히 직각이고 ${\overline {AD}}=2{\sqrt {10}},{\overline {C'D}}={\sqrt {10}}$ 으로 $\angle DAC'$ 는 f( $2{\sqrt {10}}$ , ${\sqrt {10}}$ ) = f(2, 1)이다.
같은 방법으로 f(5, 1) + f(8, 1)을 계산하면 f(3, 1)이 나옵니다. 그러면 f(3, 1) + f(5, 1) + f(7, 1) + f(8, 1) = f(2, 1) + f(3, 1) = f(1, 1)입니다. 즉, c=1.사용자:뺶꾀싸쩐/서명 2019년 5월 13일 (월) 20:47 (KST)
정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 5월 14일 (화) 17:09 (KST)

참고로 저는 다른 풀이로 풀었는데, 답은 같고 풀이 과정도 올바르니 정답 처리합니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 5월 14일 (화) 17:15 (KST)

5번 (해결)

f(x, 1)을 만족하는 삼각형을 $\bigtriangleup ABC$ 라고 하고, f(y, 1)을 만족하는 삼각형을 $\bigtriangleup A'B'C'$ 라고 하여 점 A와 점 A'를 일치시키고 ${\overline {AB}}$ 와 ${\overline {A'B'}}$ 를 겹치게해서 그립니다. 그러면 두 도형의 넓이의 합은 ${x+y \over 2}$ 입니다. 점 C와 점 C'을 이어서 만든 $\bigtriangleup ACC'$ 의 넓이는 등적 변형에 의해 ${x+y \over 2}$ 입니다. 이때, 반직선 AC를 그립니다. C'에서 반직선 AC에 수선을 내리고 그 수선의 발을 D라고 두면 각 D는 당연히 직각이고, ${\overline {C'D}}$ 는 ${\overline {AC}}$ 에 대한 높이입니다. ${\overline {AC}}$ 의 길이는 피타고라스 정리에 의해 ${\sqrt {x^{2}+1}}$ 이므로, ${\overline {C'D}}$ 의 길이는 ${x+y \over {\sqrt {x^{2}+1}}}$ 입니다. 또한, ${\overline {A'C'}}$ 의 길이는 ${\sqrt {y^{2}+1}}$ 이니 ${\overline {AD}}$ 는 피타고라스 정리에 의해 ${xy-1 \over {\sqrt {x^{2}+1}}}$ 입니다. 각 A를 f(x, y)라고 한다면 tan A는 ${y \over x}$ 입니다. 여기서 각 DAC'에 대한 tan 값은 ${x+y \over xy-1}$ 입니다. z의 값은 이 수의 역수이니, 즉 z= ${xy-1 \over x+y}$ 입니다.~~아, 쓰기 복잡하다~~~사용자:뺶꾀싸쩐/서명 2019년 5월 14일 (화) 13:08 (KST)
정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 5월 14일 (화) 17:18 (KST)