주메뉴바로가기.. 본문바로가기

Problems

폴리매스 문제 보기

문제

[국가수리과학연구소] 국31. 자연수 집합의 연결 고리

2019.07.01

같이 풀어볼까?

네이버밴드 구글플러스

 

국가수리과학연구소의 31번째 문제입니다

 

 

0을 포함하는 자연수의 집합을 \large \mathbb{N}이라 하자.

 

 

 

문제1

집합 \large \mathbb{N}에서 집합 \large \mathbb{N}으로 가는 일대일 대응을 만드는 다항식을 모두 찾아라.

 

 

 

문제2

집합 \large \mathbb{N}^{2}에서 집합 \large \mathbb{N}으로 가는 일대일 대응을 만드는 다항식은 뭐가 있을까? 찾은 다항식 외에 다른 다항식이 없다는 걸 어떻게 밝힐 수 있을까?

 

 

문제3

임의의 양의 자연수 \large k에 대해, 집합 \large \mathbb{N}^{k}에서 집합 \large \mathbb{N}으로 가는 일대일 대응을 만드는 다항식은 뭐가 있을까?

 

 

 

-끝-

 

 

댓글 35

  • 수학장 2019.07.01 16:29:07

    1. 다음 조건을 만족하는 다항식 f(x)는 집합 N 에서 집합 N으로 가는 일대일 대응을 만드는 다항식이 됩니다.

    1) f(0)=0

    2) 양수 x에 대하여 f'(x)>0

    좋아요0 댓글수7
    • Simon 2019.07.01 16:33:32

      정의역이 음이아닌 자연수로 연속하지 않기 때문에 미분 불가능합니다

      좋아요0
    • 수학장 2019.07.01 16:36:19

      제가 x가 양수라고 했기에 미분가능합니다.

      좋아요0
    • 수학장 2019.07.01 16:37:29

      다항식이 임의의 구간에서 연속하는 건 자명하고, 따라서 x>0에서 연속하는 것도 자명합니다.

      좋아요0
    • Simon 2019.07.01 16:42:55

      y=2x는 수학장님이 말씀하신 조건을 만족합니다.

      f^{-1}(1)은 0.5로 음이아닌 정수에 포함되니 않으므로 정의되지 않습니다

      좋아요0
    • 수학장 2019.07.01 16:43:49

      수정합니다. 조건 2번에 \large x\geq 0에 대해 \large f'(x)\geq 0이네요.

      좋아요0
    • 수학장 2019.07.01 16:44:26

      아 잠만 자연수였네요... 크흠...

      좋아요0
    • Simon 2019.07.01 16:46:33

      따라서 미분 불가능합니다;;

      가장 강력한 도구를 못쓰게 됬네요

      좋아요0
  • 수학장 2019.07.01 16:50:35

    그런데 치역하고 공역이 같지 않아도 되는 건가요?

    좋아요0 댓글수1
    • Undefined 2019.07.01 19:54:10

      정의역과 공역이 집합의 크기가 같기 때문에 일대일 대응이 됩니다.

      이 문제의 경우 둘 다 가부번하므로 \aleph_0로 같습니다.

      (물론 이렇게 표현하면 순환정의가 되긴 하지만요)

      일대일 대응은 치역과 공역이 같은 전사 함수입니다.

      좋아요1
  • Undefined 2019.07.01 19:51:15

    (1) 풀이

    f(x)=\sum_{k=0}^{n}a_k x^k를 다항식이라고 가정하자.

    lemma) \lim_{x\rightarrow\infty}\sum_{k=0}^{n}a_k x^k =\infty when a_n >0 

    proof:자명

     

    a_n <0이라면 -\infty로 발산하므로 음수가 되는 x가 존재한다.

    따라서 a_n >0

     

    \Delta f(x)=f(x+1)-f(x)라고 하자.

    만약 모든 0<y<1에 대해 f''(x+y)>0이라면 f'(x)<\Delta f(x)

    그러나 n\geq2일 때 어떤 x_c가 존재해 x_c 이상의 모든 x에 대해 f''(x)>0와 f'(x)>1를 만족한다.

    즉, x_c 이후 무한히 많은 자연수를 뛰어넘게 되며, x_c 이전의 자연수는 유한하므로 자연수 전체를 대응시킬 수 없다.

    그러므로 n=1

     

    f'(x)=a_n >0이므로 증가함수, 그러므로 차례대로 대응되어야 하며 f(x)=x

    좋아요0 댓글수1
    • 출제자(국) 2019.07.02 13:33:33 비밀댓글
      비밀댓글 입니다.
  • Undefined 2019.07.02 15:28:52

    (2) 실례: f_2(x_1,x_2)=\frac{(x_1+x_2)(x_1+x_2+1)}{2}+x_1

    증명: 

    첫번째 항은 1+2+...+(x_1+x_2)이므로 두번째 항이 x_2=0이여도 x_1+x_2+1을 넘지 못한다.

    역함수를 예시로 들어 보이겠다.

    f_2^{-1}(58):~ 58=55+3=(1+2+...+10)+3 ,~x_1+x_2=10,~x_1=3

    \therefore f_2^{-1}(58)=(7,3)

     

    (3) 실례: f_n (x_1,x_2,...,x_n)=\sum_{k=1}^{\sum_{i=1}^{n}x_i}f_{n-1}(k,0,0,...,0)+f_{n-1}(x_1,...,x_{n-1})

    ((2)의 확장)

    ex) f_3(x_1,x_2,x_3)=\frac{(x_1+x_2+x_3)(x_1+x_2+x_3+1)(x_1+x_2+x_3+5)}{6}+f_2(x_1,x_2)

    유일성 증명은 어떻게 할지 모르겠습니다.

    좋아요0 댓글수3
    • 수학장 2019.07.02 18:28:58

      2번 문제 풀이인가요?

      좋아요0
    • 출제자(국) 2019.07.03 11:27:47

      잘 하셨어요! 유일성 증명도 같이 생각해봐요 ㅎㅎ

      좋아요0
    • Undefined 2019.07.03 13:34:06

      여기서 (3)이나 (2)의 경우 x_1,x_2,...,x_n의 순서를 바꾸어도 됩니다.

      즉, A:{1,2,3,...,n}일 때 어떤 일대일 함수 g:A\rightarrow A에 대해

      f^1_{n}(x_1,x_2,...,x_n)=f_n(x_{g(1)},x_{g(2)},...,x_{g(n)})이면

      f^1_{n}도 조건을 만족하는 함수가 된다.

      좋아요0
  • cube120 2019.07.02 17:37:50

    집합 N^2에서 간다는건 무엇을 뜻하는 건가요?

    f(x,y)같은걸 말하는 건가요???

    좋아요0 댓글수1
    • 수학장 2019.07.02 18:29:55

      네 2개 변수를 가진 다항식에서 나온 결과가 (x,y)랑 일대일대응 해야 하는 거죠.

      좋아요0
  • 퍼즐&Scratch 2019.07.02 20:40:57

    문제 2를, 변수가 2개인 다항식이 있어 모든 (x, y)쌍(x\in \mathbb{N}, y\in \mathbb{N})과 \mathbb{N}의 모든 원소가 일대일 대응된다고 해석하였습니다. 

    그러면 아래의 다항식이 조건을 만족하는 것 같습니다. 

    f(x, y) =\frac{1}{2}(x^2 + 2xy + y^2 + 3x + y)

    여기서 x와 y의 위치를 바꾼 다항식도 조건을 만족합니다. 

    풀이는 아래의 그림과 같습니다. 숫자를 사선으로 배치하고 (x, y)에 해당하는 수를 다항식으로 나타낸 것입니다. 

    혹시 문제의 해석이 잘못되었거나, 풀이에 오류가 있으면 말씀해 주세요. 

    좋아요0 댓글수7
    • 퍼즐&Scratch 2019.07.02 20:48:39

      만약 이 풀이가 맞으면, \mathbb{N}^k의 경우는 (수학적으로 정의되는) k차원을 생각하면 될 것 같아요. 

      좋아요0
    • 출제자(국) 2019.07.03 11:28:45

      잘 해석하셨습니다! 2번에 해당하는 실례를 잘 찾아주셨어요 yes

      좋아요0
    • 출제자(국) 2019.07.03 11:28:47

      잘 해석하셨습니다! 2번에 해당하는 실례를 잘 찾아주셨어요 yes

      좋아요0
    • 퍼즐&Scratch 2019.07.03 15:23:29

      제 풀이를 잘 읽어주셔서 감사합니다. 앞으로도 열심히 하겠습니다! 그런데 위에서부터 댓글을 다시 살펴보니 Undefined님께서 이미 똑같은 다항식을 찾으셨네요. 안 보고 했는데, 혹시 따라했다고 오해하셨으면 죄송합니다;;

      좋아요0
    • Undefined 2019.07.04 03:22:59

      저는 대수적으로만 해석해서 풀었는데, 기하적 해석을 이용한 풀이를 보니까 더 이해가 잘 되네요.

      좋아요0
    • 출제자(국) 2019.07.04 17:55:08 비밀댓글
      비밀댓글 입니다.
    • 퍼즐&Scratch 2019.07.04 21:48:36 비밀댓글
      비밀댓글 입니다.
  • 수학잘하고싶다 2019.07.02 23:07:14

    다항식이면 유한개의 항만을 가지고 있어야 하나요?

    좋아요0 댓글수1
    • Undefined 2019.07.03 23:31:44

      무한개의 항을 가지는 '다항식'을 형식적 멱급수(Formal power series)라고 합니다.

      이에 대해 찾아보시면 다음과 같은 사실을 알 수 있을 겁니다.

      1. 이들은 함수가 아닙니다. 형식적으로 나타낸 문자열에 불과합니다.

      2. 이들 중 x>=0 일때 발산하지 않는 (즉, 값이 존재하는) 것의 극한을 함수라고 정의할 수 있으나,

      그러면 대부분의 x=0에서 유한한 값을 가지는 미분가능한 함수를 포함하기 때문에 문제의 의도와 다르게 e^x나 sin(x), x! 등의 함수를 고려해야 하며, 문제의 답도 여러개가 됩니다.

      즉, g:\mathbb{N}\rightarrow\mathbb{N}인 임의의 함수 g(n)에 대해 모든 점 (n,g(n)) 을 지나도록 형식적 멱급수를 만들 수 있습니다.

       

      이를 만족하는 g(n)의 개수는 형식적으로 |\mathbb{N}|!=\aleph_0 !개라 할 수 있으며, 그런 g(n)들의 집합이 존재한다고 가정한다면 그 cardinal(기수)은 large cardinal(큰 기수) 가 되겠네요. 

      좋아요1
  • 수학잘하고싶다 2019.07.03 12:59:56

    3번 이렇게 하면 되지않을까요?

    좋아요1 댓글수3
    • 퍼즐&Scratch 2019.07.03 15:25:27

      오호, 좋은 아이디어인데요? 맞는 것 같아요. 

      좋아요0
    • 김우현 기자 2019.07.10 13:37:33

      검토 요청드렸으니 조금만 기다려주세요!!!smiley

      좋아요0
    • 김우현 기자 2019.07.15 18:06:42

      연구원님께서 답변을 준비 중입니다.

      생각보다 시간이 걸린다고 하네요. 조금만 더 기다려주세요!crying

      좋아요0
  • 모두다같이 2019.07.10 19:08:22

    삼차식, 이차식 흔히 생각하는 식에서 절대값 기호가 들어가도

    다항식이라 하죠..?!

    좋아요0 댓글수2
    • 수학장 2019.07.10 21:38:26

      절대값 기호가 들어가면 그건 다항식이라고 하지 않습니다.

      좋아요0
    • 모두다같이 2019.07.11 18:34:40

      고마워요

      좋아요0