의외의 계산 문제 2025 KJMO 조합 20번 해설 (feat. 반복 시행, 수학적 센스)
지난 주말 9월6일(토) 에 치뤄진 KJMO 의
마지막 문제(조합)를 살펴보겠습니다.
2025 KJMO 는 올해로 7회차에 해당되는데,
KJMO 는 회차 표시는 하지 않고
연도만 표시하는것 같네요.
기존 올림피아드들이 회차와 연도를 섞어쓰다보니
매번 헷갈렸는데,
연도 표기로 단순화하는것도 좋아보입니다.
출제된 문제는 아래와 같습니다.
1. 반복 시행?
종종 반복 시행이 포함된 문제들은
불변성(invariance)을 찾고
그것을 활용해서 해결하는 유형이 많습니다.
이 문제를 보고 불변성을 찾아보려고
여러가지 궁리를 해봤는데,
딱히 괜찮은것이 안보이네요. 기껏
매 시행마다 수의 갯수가 2배로 늘어난다.
이것밖에 안보이네요.
혹시, 좋은 것이 보이시면
저에게도 좀 알려주세요..
2. 눈치껏 (수학적 센스)
그러면 설마 직접 계산하라는 말인가?
일단, 문제를 읽고 떠오르는
눈치를 모아보겠습니다.
(1)
허접하지만 찾아낸 불변성
→ 매 시행마다 각 수가 2개가 됨
64개는 금방 도달함.
(2)
문제에서 6회 시행하면 종료되는데,
의외로 시행횟수가 적다.
→ 설마 직접 계산하라는 암시인가?
(3)
초기값 10000이 의외로 상당히 크다.
x+1 은 고만고만한 크기의 숫자이고
1/x 는 0에 근접한 양수를 만든다..
→ 평균을 낼 때, 작은 수는 역할이 미미할듯
(4)
저학년용 경시대회 문제이다.
아마, 6학년도 풀 수 있게 해놨을것이다.
(5)
가장 가까운 정수를 구하라고?
이것도 직접 계산하라는 암시인것 같다.
(6)
답을 숫자로 요구하고 있다.
→ 어차피 어느정도 계산은 해야할 것 같다.
(7)
엘레강트한 불변성은 보이지를 않고
제한시간 내에 답은 내야한다.
출제자는 나한테 왜이러심?
3. NGD 를 결심하기
여러 정황과 촉에 따라 어쩔수 없으니
일단, NGD(노가다)를 해야 할것 같네요.
진흙탕에서 구르는 계산도
막상 해보면 꽤 재미있습니다.
64개를 끝까지 다 적는것은 좀 아닌것 같고,
일단 3번 정도만 해볼께요.
4. 분석하기(1)
ngd 를 좀 뛰어보니 새로 떠오르는
눈치는 아래와 같습니다.
(1)
10000 근처의 수를 '큰 수'
0 근처의 수를 '작은 수' 라 하고,
앞 단계 수에 1 을 더해주는 시행을 A
앞 단계 수를 역수 취해주는 시행을 B
라 두고 생각해보면 좋을 것 같다.
(2)
시행의 결과는 아래 네 가지 중에 하나
① 큰 수에 A 를 취하면 큰 수가 됨.
② 큰 수에 B 를 취하면 작은 수가 됨.
③ 작은 수에 A 를 취하면 1 근처의 수가 생김.
④ 작은 수에 B 를 취하면 큰 수가 됨.
여기서, 중요한것이 ③ 인데,
이렇게 생겨난 1 근처의 수를 '어중간한 수'
라고 이름을 지어주자.
(3)
즉, 초기값 10000 에서 시작해서
시행을 하면 만들어지는 수는
큰 수, 작은 수, 어중간한 수의
세 종류가 생긴다.
(4)
6단계에서 생기는 64개의 수가
① 모두 작은 수라 해도 그 합은 1 보다 작다.
② 모두 어중간한 수라 해도 그 합은
(넉넉하게 고려해도) 400 보다 작다.
위의 ①, ② 는 쉽게 증명 가능합니다.
(심심할때 각자 해보세요~)
(5)
문제에서 요구하는 값은
64개의 수의 합을 6400 으로 나눈 수에
가장 가까운 정수이므로,
작은 수와 어중간한 수는 총합에 기여도가
무의미하므로 그냥 없다고 봐도 된다.
아마, 이거 하라고 초기값을 10000으로
매우 큰 값을 준 것으로 예상됨.
(6)
그러면 6회 시행하는 동안
큰 수가 몇 개 만들어지는지만
확인하면 된다.
(7)
어중간한 수는 A, B 를 아무리 적용해도
어중간한 수만 만들어낸다.
(8)
최초 10000 에서 시작해서
생성되는 수가 큰 수가 되려면 적어도
역수를 취하는 B 시행은 짝수번이어야 한다.
(필요조건 #1)
(9)
큰 수에서 B 를 시행한 후 A 를 시행하면
어중간한 수가 되어 버린다.
(10)
따라서, B 시행은 존재한다면
반드시 두 번 연속 일어나야 한다.
(필요조건 #2)
5. 분석하기(2)
이제, 4 에서 찾은 필요조건 두 개를 적용해서
6회 시행 후에 생기는
큰 수의 개수를 구하면 됩니다.
즉, 6회 시행으로 가능한 것은
아래 네 가지만 가능합니다.
① AAAAAA 꼴
② A + A + A + A + BB 꼴
③ A + A + BB + BB 꼴
④ BBBBBB 꼴
6. 계산하기
앞의 네 경우를 계산해봅시다.
① AAAAAA 꼴
1가지
② A + A + A + A + BB 꼴
(같은것이 있는 순열입니다.)
③ A + A + BB + BB 꼴
④ BBBBBB 꼴
1가지
따라서, 큰 수는 총 13개가 나옵니다.
(초등학생은 직접 나열하면 됩니다.)
그러므로 6단계에서
64개의 수의 합 S 는
이고, 6400으로 나누면
이므로 답은 20 입니다.
7. 리뷰
수의 감각이 좋은 학생이라면
더 잘 풀었을것 같은 재미있는 문제였습니다.
저는 실제로는 단위원에서의 반전(inversion)과
비슷한 느낌이라 NGD 를 결심한 뒤에는
금방 풀었답니다. 잠시 설명을 드리자면,
1/10000이라는 점은 원점에 거의 붙어있기 때문에,
반전하면 저 멀리 날아갈 '힘'을 가진 상태인데,
+1 평행이동을 시키면 원의 경계인 '1' 근처로
옮겨버리므로 이후에는 힘을 잃게 되죠. 그래서
BB 는 반드시 두 개 연속으로 있어야 합니다.
8. code
심심해서 64개를 생성시켜봤습니다.
결과는 아래와 같아요.
1: 10006
2: 10004
3: 10004
4: 10004
5: 10004
6: 10004
7: 10002
8: 10002
9: 10002
10: 10002
11: 10002
12: 10002
13: 10000
14: 5.00010
15: 4.00010
16: 3.99990
17: 3.00010
18: 3.00010
19: 3.00010
20: 3.00010
21: 3.00010
22: 2.99990
23: 2.49998
24: 2.00010
25: 2.00010
26: 2.00010
27: 2.00010
28: 2.00010
29: 1.99990
30: 1.99990
31: 1.99990
32: 1.99990
33: 1.50002
34: 1.49998
35: 1.33332
36: 1.00010
37: 1.00010
38: 1.00010
39: 1.00010
40: 1.00010
41: 1.00010
42: 1.00010
43: 1.00010
44: 0.99990
45: 0.99990
46: 0.99990
47: 0.99990
48: 0.66668
49: 0.50002
50: 0.49998
51: 0.49998
52: 0.49998
53: 0.49998
54: 0.33334
55: 0.33332
56: 0.24999
57: 9.99900e-5
58: 9.99900e-5
59: 9.99900e-5
60: 9.99700e-5
61: 9.99700e-5
62: 9.99700e-5
63: 9.99700e-5
64: 9.99500e-5
생성된 64개 숫자의 꽤 정확한 총합: 130109.9183601977
이것을 6400으로 나누면 근사값으로
20.329674743780892
가 나옵니다.