수학동아 - 폴리매스

폴리매스 문제

세상에 없던 문제에 도전하세요!

[대한수학회] 대49. 제 33회 한국수학올림피아드 변형 문제

수학동아 2020.12.30 11:43 조회 1702

페이스북 트위터 카카오톡 카카오스토리 네이버블로그 네이버밴드

문제 0. 제 33회 한국수학올림피아드 최종시험 4번 문제

모든 양의 정수가 다음 수열에 정확 히 한 번 등장하도록 하는 양의 실수의 순서쌍 (α, β)가 존재하는가? 존재한다면 순서쌍을 모두 구하고, 그렇지 않다면 순서쌍이 존재하지 않음을 보여라.

2020, $[\alpha ]$ , $[\beta ]$ , 4040, $[2\alpha ]$ , $[2\beta]$ , 6060, $[3\alpha ]$ , $[3\beta ]$ , 8080, $[4\alpha ]$ , $[4\beta ]$ , . . .

(단, $[x]$ 는 $x$ 를 넘지 않는 최대 정수)

-------------------------------------------------------------------------------------------------------------------------------------

두 실수 $\alpha(\geq 1)$ 와 $\beta$ 에 대하여 $S(\alpha ,\beta )$ 를 다음과 같이 정의하자.

$S(\alpha ,\beta )$ = { $[\alpha +\beta ]$ , $[2\alpha +\beta ]$ , $[3\alpha +\beta ]$ , $[4\alpha +\beta ]$ , . . .}

변형 문제 1.

두 집합 $S(\alpha _{1}, 0)$ 과 $S(\alpha _{2}, 0)$ 이 자연수 집합의 분할이 되는 두 실수의 쌍 $(\alpha _{1}, \alpha _{2})$ 이 존재하 는가? 존재한다면 순서쌍을 모두 구하고, 그렇지 않다면 순서쌍이 존재하지 않음을 보여라.

변형 문제 2.

세 집합 $S(\alpha _{1}, 0)$ , $S(\alpha _{2}, 0)$ , $S(\alpha _{3}, 0)$ 이 자연수 집합의 분할이 되는 세 실수의 쌍 $(\alpha _{1}, \alpha_{2}, \alpha _{3})$ 이 존재하는가? 존재한다면 순서쌍을 모두 구하고, 그렇지 않다면 순서쌍이 존재하지 않음을 보여라.

변형 문제 3.

자연수 $m\geq 3$ 일 때, 집합 $S(\alpha _{1}, \beta _{1})$ , $S(\alpha _{2}, \beta _{2})$ , . . ., $S(\alpha _{m}, \beta _{m})$ 이 자연수 집합의 분할이 되는 경우가 존재하는가? 존재한다면 순서쌍을 모두 구하고, 그렇지 않다면 순서쌍이 존재하지 않음을 보여라.

변형 문제 4.

자연수 $m\geq 3$ 이고 $\alpha _{1}\leq \alpha _{2}\leq ...\leq \alpha _{m}$ 이 모두 유리수일 때, 집합 $S(\alpha _{1}, \beta _{1})$ , $S(\alpha _{2}, \beta _{2})$ , . . ., $S(\alpha _{m}, \beta _{m})$ 이 자연수 집합의 분할이 되는 경우가 존재하는가? 존재한다면 순서쌍을 모두 구하고, 그렇지 않다면 순서쌍이 존재하지 않음을 보여라.

이전글 대48. 개미집 속의 개미

다음글 대50. 짝수 치환과 홀수 치환

문제 찜하기 목록보기

댓글 작성하기

수좋학 Lv.5 2021.01.04 17:33

아.........

어떤 문제인지 설명해 주실수 있나요?(제가 이해가 안되서요.....)

댓글 작성하기 좋아요1 댓글수0
파스칼 Lv.7 2021.01.08 11:25

1번 문제를 풀려고 했는데 생각보다 진전이 없어서 아이디어로 공유합니다.

기본적으로 4문제 모두 충분히 큰 n에 대해 1부터 n까지에서 집합들이 갖는 밀도를 생각해 보면 $\frac{1}{\alpha _1}+\frac{1}{\alpha _2}+...=1$ 입니다.

또한 1,2번 문제에서 모든 a_i는 1보다 크며, 1 이상 2 미만의 a_i가 존재해야 합니다.

1. 위 2가지 성질에 의해 0 이상 1이하의 a에 대해 $\alpha _1=1+a$ , $\alpha _2=1+\frac{1}{a}$ 로 놓을 수 있습니다.

이때 a가 유리수일 경우 간단히 a=p/q로 놓으면 $q\alpha_1=p\alpha_2$ 에서 조건을 만족할 수 없습니다.

a가 무리수일 경우를 보겠습니다. 임의의 1이 아니고 서로소인 두 자연수 p,q(p<q)에 대하여, 베주 항등식에 의해 qy-px=1을 만족하며 x<q, y<p인 자연수 x,y가 존재합니다. 이때 p,q에 대해 $\epsilon<\frac{1}{p}$ 를 만족하며 a= $\frac{p}{q-\epsilon }$ 또는 $\frac{1}{a}$ = $\frac{p}{q-\epsilon }$ 가 되는 p,q, $\epsilon$ 이 존재할 것이라고 생각합니다.

일반성을 잃지 않고, $\alpha _1=$ $\frac{p+q-\epsilon }{p}$ , $\alpha _2=\frac{p+q-\epsilon }{q-\epsilon }$ 라 놓겠습니다. 또한 위 조건에 의해 x,y를 잡으면, $\epsilon<\frac{1}{p}$ 에서 $\epsilon<\frac{q}{px+1}$ 이며 즉 $\frac{x}{q-\epsilon}-\frac{x}{q}<\frac{1}{pq}$ 입니다.

따라서 이 식과 x,y의 조건식 $\frac{y}{p}-\frac{x}{q}=\frac{1}{pq}$ 로부터 $0<\frac{y}{p}-\frac{x}{q-\epsilon }<\frac{1}{pq}$ 이며, $0<y\alpha _1-x\alpha _2<\frac{p+q-\epsilon }{pq}$ 입니다.

이때 $\left \lfloor y\alpha _1 \right \rfloor \neq \left \lfloor x\alpha _2 \right \rfloor$ 이기 위해서는 $y\alpha _1 -\left \lfloor y\alpha _1 \right \rfloor <\frac{p+q-\epsilon }{pq}$ 가 되어야 하는데, 저는 여기에서 모순을 찾아 ya1과 xa2의 정수부분이 같음을 보이고자 했습니다.

너무 풀이가 문제에 짜 맞추는 느낌이 있는데.. 아이디어가 더 필요할 듯합니다

댓글 작성하기 좋아요1 댓글수2
- 구머 Lv.5 2021.02.26 19:14
  
  (진짜 오랜만에 온 폴리매스)
  
  아랫분 댓글에서 $\frac{1}{\alpha _{1}} + \frac{1}{\alpha _{2}}=1$ 식이 어떤 의미인가 싶었는데, 숫자의 밀도로 생각을 하니 딱 맞아떨어지네요 ㄷㄷ. Sait2000님이 주신 링크를 보면 해당 정수부분이 놀랍게도 하나도 안겹치는게 증명이 되어있는 것 같습니다. 참고 바랍니당
  
  좋아요0
- 파스칼 Lv.7 2021.02.27 15:17
  
  확인했습니다!
  
  처음에 답 자체를 잘못 추정했네요
  
  좋아요0
Sait2000 Lv.3 2021.02.17 12:18

1번 문제는 ~~웰노운~~ Beatty sequence입니다. \alpha_1과 \alpha_2가 무리수이고 1 / \alpha_1 + 1 / \alpha_2 = 1일 때 성립함이 잘 알려져 있다고 개인적으로 생각합니다. 증명은 영문 위키백과에 간단한 증명이 있는 것 같습니다. https://en.wikipedia.org/wiki/Beatty_sequence

2번 문제는 \alpha가 3개 이상일 때 불가능함이 알려져 있다고 합니다. 증명은 영문 위키백과에 링크되어있는 것 같습니다. http://www.math.ucsd.edu/~fan/ron/papers/63_01_uspensky.pdf

증명을 적당히 요약하면, 일반성을 잃지 않고 \alpha_1 < \alpha_2 < ... 라고 할 때, \lfloor \alpha_1 \rfloor = 1이어야 합니다.

이때 S(\alpha_1, 0)에서 처음으로 빠진 수를 m이라고 하면, 빠진 수가 그 뒤로 m 또는 m + 1마다 하나씩 나옴을 보입니다.

그리고 그 m은 S(\alpha_2, 0)이 채우게 되는데, 이렇게 되면 S(\alpha_2, 0)가 채우는 수도 역시 m이나 m + 1마다 하나씩 나오게 됩니다.

이때 S(\alpha_1, 0)과 S(\alpha_2, 0)이 겹치지 않으려면 1의 빈칸에 2가 들어가야만 하는데, 그러면 자연수가 꽉 차게 되고 \alpha가 3개 이상이 될 수가 없습니다.

3, 4번 문제는 모르겠습니다. 존재함은 간단히 보일 수 있습니다. 그냥 S(3, -2) S(3, -1) S(3, 0) 하면 됩니다. 다 구하는 건 간단하지 않을 것 같습니다.

댓글 작성하기 좋아요0 댓글수3
- Sait2000 Lv.3 2021.02.17 12:43
  
  4번에 대해서, 모든 \alpha들의 공배수 중 가장 작은 자연수를 생각합니다. 말이 좀 이상하지만 정의를 안 해도 뭔지는 다 아실 거라고 생각합니다. 이 자연수를 주기이니까 T라고 합시다. 그러면 a \in S(\alpha_i, \beta_i)에 대해 a + T \in S(\alpha_i, \beta_i)입니다. 따라서 T를 고정하면 문제를 T로 나눈 나머지에서 풀 수 있습니다. 뭔가 등차수열로 정수 덮기 문제랑 비슷한 거 같은데 \alpha가 정수가 아닐 때가 좀 그렇네요.
  
  좋아요0
- 파스칼 Lv.7 2021.02.27 15:16
  
  1번이 당연히 불가능할 거라고 생각하고 유리수에서는 쉬운데 무리수에서는 왜 증명이 어려운지 한달간 고민했어요
  
  풀리지 않는 이유가 있었네요^^
  
  좋아요0
- 파스칼 Lv.7 2021.02.27 22:08
  
  3,4 번 저도 그 생각을 했는데, 잘은 모르지만 아마 출제하신 분이 beta가 양수라는 조건을 빠트리신 게 아닌가 싶습니다!
  
  아니라면 실수이고 유리수이고의 조건이 별로 차이가 없기 때문에..
  
  좋아요0
퍼즐-Scratch Lv.5 2021.03.02 09:49

Sait2000님이 소개해 주신 것과 같은 증명을 Problem-Solving Strategies에서 찾아서 공유해봅니다 ㅎㅎ

정수를 무리수에 곱했을 때 정수가 되지 않으므로, 오히려 자연수 집합을 분할 할 수 있다는 것이 신기하네요~

댓글 작성하기 좋아요0 댓글수0