UPO/4회

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이라고 하자.

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

1. f(1048574)의 각 자리 수의 합을 구하시오.
2. 임의의 자연수 n에 대해, g(n)이 유일함을 증명하시오.
3. g(15), g(16)을 구하시오.
4. n이 자연수일 때, g(n)의 최댓값과 그때의 n을 구하시오.
5. g(2019)를 구하고, n이 홀수일 때 g(n)을 구하시오.
6. 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번 (해결)

1. 2 --Rika14369(토론)(기여:회) 2019년 4월 1일 (월) 21:45 (KST)

   오답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 18:24 (KST)

2. 28 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 19:58 (KST)

   오답입니다... -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 20:25 (KST)

3. 10 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 20:57 (KST)

   정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 21:03 (KST)

3번 (해결)

1. -4, 1 --Rika14369(토론)(기여:회) 2019년 4월 1일 (월) 21:50 (KST)

   오답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 18:24 (KST)

2. 8, -8 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 20:00 (KST)

   오답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 20:25 (KST)

3. 19, 15 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 21:09 (KST)

   오답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 21:21 (KST)

4. -8, -7 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 22:12 (KST)

   정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 22:14 (KST)

4번 (해결)

1. 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)

덧붙여서 아마 5번 문제와 연계된 풀이를 원하시는 것 같으셔서 긴 풀이로 아래 적겠습니다.

소정리 0

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

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

소정리 0을 이용하면 바로 문제가 끝납니다.

인접한 두 수의 f(x)값을 생각했을 때

홀수에서 짝수로 넘어갈때는 2진수상의 받아올림이 발생하지만, 그 반대는 받아올림이 없으므로

무조건 홀수가 짝수보다 f(x)의 값이 같거나 더 큽니다.

따라서 (-1)^(n+1) * f(n+1) + (-1)^(n+2) * f(n+2)=<0이므로

g(n+2)=<g(n)이 성립합니다.

고로 g(2), g(1) 값만 비교하면 되는데, g(2) = 0 이고 g(1) = -1 이므로 정답은 n=2, g(n) = 0 입니다.

소정리 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)=-2^(k-1)+1

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

본 증명

이제 어떤 홀수 n을 생각해 봅시다.

우리는 귀납적으로 홀수 n에 대해 g(n) = -(n+1) / 2임을 보일 것입니다.

자. 이번에는 변형된 귀납법입니다.

명제 p(k) : 2^k 이상 2^(k+1) 미만 홀수 n 에 대해 g(n) = -(n+1) / 2 이다.

라고 놓은 뒤 p(0) 가 성립합과, p(k) -> p(k+1) 임을 증명할 것입니다.

1. p(0)은 참이다.

g(1) = -1 이므로 성립

2. p(k) -> p(k+1)

2^(k+1) 이상 2^(k+2) 미만인 홀수 n을 생각하자.

같은 범위내의 자연수 x는 2진수로 나타냈을 때 k+2번째 자릿수가 1이다.

그러므로 h(x) = h(x - 2^(k+1)) + (-1)^x 가 성립한다.

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

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

뒤에 +1, -1 번갈아 나오는 것은 서로 개수가 같아 상쇄된다.

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

= -2^k - (n-2^(k+1) + 1)/2 = - (n+1)/2

따라서 모든 홀수 n 에 대해 g(n) = -(n+1)/2 입니다.

짝수는 g(n) = -n/2 + f(n) 이 됩니다.

고로 홀수 n 에 대해 g(n)이 최대가 될 조건은 n=1일때 입니다.

짝수의 경우 g(2k) = -k + f(2k) = -k + f(k) 인데 g(k) = -k/2 + f(k)or -1/2 가 됩니다.

f(k)가 아무리 커봤자 k를 2진수로 썼을 때 자릿수 까지이므로

넉넉잡아 k>=4부터는 g(2k) < g(k)가 됩니다.

g(2)와 g(4) 값을 구하면 각각 0과 -1입니다. g(3)과 g(6) 값을 비교해도 같은 결론이 납니다.(계산은 직접해주시면 감사하겠습니다.)

고로 우리는 n=2일 때와 1일때만 비교하면 됩니다.

그러므로 정답은 n=2, g(2)=0 입니다. 끝!

할 말을 잃었습니다. 고작 문제 하나를 위해 이렇게 힘들게... 게다가 5번 소문제와 연관지어서... 훌륭합니다. 소정리 0이 바로 제가 의도한 풀이였습니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
만든 게임: Bd3076의 게임 2019년 12월 19일 (목) 17:06 (KST)

풀이과정에 오류가 발견되어서 수정하였습니다. p(1)이 아니라 p(0)부터 시작해야 합니다. 또한 g(3), g(6) 값 역시도 비교해줘야 하는데 귀차니즘으로 생략해도...되겠져? Sleep (토론) 2019년 12월 19일 (목) 21:23 (KST)

5번 (해결)

1. 2027, 2036 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 21:13 (KST)

   오답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 21:21 (KST)

2. -1010, g(n)=-(n+1)/2 — Malgok1 (토론·기여) 2019년 4월 2일 (화) 23:19 (KST)

   정답입니다. -- Bd3076 (토론) (둘러보기)기여 횟수:
   만든 게임: Bd3076의 게임 2019년 4월 2일 (화) 23:39 (KST)

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

1. $-{\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)라 하자.

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

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

1번 (해결)

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

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

2번 (해결)

1. 문제에 제시된 조건에 따라 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번 (해결)

1. 요거이 글로 설명하기 거시기하다만은... 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번 (해결)

1. 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번 (해결)

1. 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)

• 돌아가기

2일차 정해

1번

f(x, y), f(rx, ry)의 두 삼각형은 SAS 닮음을 이룬다. 따라서 f(x, y)=f(rx, ry).

2번

특수각의 삼각비에서 f(1, 1)=45도이므로 f(1, a)=60도여야 한다. 이를 만족하는 $a={\sqrt {3}}$.

3번

각 ABD=f(2, 1)이고, 각 DBC=f(3, 1)이다. 즉 각 ABC=f(2, 1)+f(3, 1).

그런데 삼각형 ABC는 AB=BC인 직각이등변삼각형이므로, f(2, 1)+f(3, 1)=f(1, 1)이다.

4번

각 ABC=f(5, 1)+f(8, 1), 각 EFG=f(3, 1)+f(7, 1)은 위의 그림을 통해 알 수 있다.

그런데 AB=${\sqrt {65}}$, BC=${\sqrt {26}}$, CA=${\sqrt {13}}$

EF=${\sqrt {50}}$, FG=${\sqrt {10}}$, GE=${\sqrt {20}}$

즉 삼각형 ABC와 EGF는 SSS 닮음이다.

즉 우리가 구해야 할 것은 각 ABC+EFG인데, ABC=EGF이므로 EFG+EGF를 구하면 된다.

I를 그림과 같이 잡으면, EFG+EGF=EGI이다.

그런데, GI=IE, GIE=90도이므로 EGI는 직각이등변삼각형이다.

따라서 EGI=45도이고, 답은 f(b, 1)=45도를 만족하는 b인 1이다.

5번

BOA=f(x, 1), COB=f(y, 1)이라고 하고 위 그림과 같이 그림을 그리자. 그럼 위와 같은 길이를 알아낼 수 있다. (힌트: CBE와 BOA는 닮았다.)

DE=k라고 놓자.

DEC와 DAO는 닮음이므로, k:1/y=k+x/y+1:x이다.

이 비례식을 풀면 k=${\frac {x+y}{xy^{2}-y}}$이다. 따라서 tan DOA = ${\frac {x+y}{xy-1}}$이다.

즉 z는 k의 역수인 ${\frac {xy-1}{x+y}}$이다.

• 돌아가기