수학동아 - 폴리매스

주니어 폴리매스 문제

수학 문제를 푸는 매력에 빠져 보세요!

[KAIST 과학영재교육연구원] k8. 조금 특별한 집합

수학동아 2019.03.04 18:59 조회 2088

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

임의의 음이 아닌 정수 n에 대하여, 각 n에 대해 다음과 같이 정의된 두 집합이 있다.

$\large A_{n}=\left \{f:\left \{ 0, 1, \cdots, n \right \}\rightarrow \left \{ 0, 1, \cdots, n \right \}\left\mid f(0)=f(n)=0, \left \left | f(i)-f(i-1) \right \right | \leqslant 1 \right \}$

$\large B_{n}=\left \{f:\left \{ 0, 1, \cdots, 2n \right \}\rightarrow \left \{ 0, 1, \cdots, 2n \right \}\left\mid f(0)=f(2n)=0, \left \left | f(i)-f(i-1) \right \right | = 1 \right \}$

문제1

n=5일 때 두 집합의 원소의 개수 $\large \left | A_{5} \right |, \left | B_{5} \right |$ 를 구하시오.

문제2

문제1을 바탕으로 $\large A_{n}$ 과 $\large B_{n}$ 집합의 원소의 개수를 비교하시오.

이전글 k7. 거울 속 빛의 여행

다음글 k9. 신경 쓰이는 루빅스 큐브

문제 찜하기 목록보기

댓글 작성하기

퍼즐-Scratch Lv.5 2019.03.06 04:10

앗싸 첫번째 댓글이다 ^^

|A₅| = (₅C₁* C₂) + (₅C₃* C₁) + (₅C₅* C₀) = 21

|B₅| = C₅= 42

여기서 C_n은 카탈란 수입니다. |A_n|은 |B_n|의 절반일것 같군요.

댓글 작성하기 좋아요2 댓글수1
- 디듀우 Lv.7 2019.03.07 07:52
  
  좀 더 구체적인 설명 부탁드려요.
  
  좋아요2
퍼즐-Scratch Lv.5 2019.03.06 04:43

A PHP Error was encountered

Severity: Warning

Message: mkdir(): Permission denied

Filename: libraries/Common.php

Line Number: 202

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 202
Function: mkdir

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 236
Function: getLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
Line: 90
Function: parseLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
Line: 343
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 558
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: Warning

Message: file_put_contents(/DATA/upload/polymath/latex/9599ce4ee580ddcb4c0bbdc3c7fb7490.gif): failed to open stream: No such file or directory

Filename: libraries/Common.php

Line Number: 213

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 213
Function: file_put_contents

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 236
Function: getLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
Line: 90
Function: parseLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
Line: 343
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 558
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: Warning

Message: mkdir(): Permission denied

Filename: libraries/Common.php

Line Number: 202

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 202
Function: mkdir

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 236
Function: getLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
Line: 90
Function: parseLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
Line: 343
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 558
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

A PHP Error was encountered

Severity: Warning

Message: file_put_contents(/DATA/upload/polymath/latex/11b4d7d30d568bba516031d3abc0e6f4.gif): failed to open stream: No such file or directory

Filename: libraries/Common.php

Line Number: 213

Backtrace:

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 213
Function: file_put_contents

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/libraries/Common.php
Line: 236
Function: getLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view_comment_list.php
Line: 90
Function: parseLatexImg

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/views/ver3/inc/view.php
Line: 343
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/application/controllers/ver3/Contents.php
Line: 558
Function: view

File: /volume1/web/PhpstormProjects/www_polymath_co_kr/index.php
Line: 315
Function: require_once

$|A_{n}| = \sum_{k=0}^{[\frac{n}{2}]} C_{k} \binom{n}{n-2k}= {\color{Red} \sum_{k=0}^{[\frac{n}{2}]} C_{k} \binom{n}{2k}}$

$|B_{n}| = {\color{Red} C_n}$

인 것 같습니다.

댓글 작성하기 좋아요2 댓글수0
주니어멘토 Lv.1 2019.03.15 07:42

안녕하세요!

주니어 폴리매스 멘토입니다.

답글 달아주신 퍼즐&Scratch 님 감사합니다! 디듀우 님의 댓글처럼 좀 더 자세한 설명이 있다면 좋을 것 같습니다!

힌트를 드리자면 첫번째 문제는 좌표평면에서 (0,0)이라는 점에서 (5,0)으로 가는 경로의 수를 적절한 제한 조건아래에서 생각하는 문제로 치환하여 풀면 좀 더 눈에 보일 것 입니다!

두번째 문제는 A와 B의 상황 중에 어떤 한 가지 상황이 다른 한 가지 상황을 포함하여 더 원소가 많게 된다는 식의 이야기를 할 수 있을 것입니다.

감사합니다!

댓글 작성하기 좋아요0 댓글수0
닐스보어gs Lv.2 2019.04.23 06:38

댓글 작성하기 좋아요0 댓글수0
code Lv.5 2019.08.09 04:55

질문입니다.

|A₅|의 원소의 갯수는 달라질 수 있는것이 아닌가요? 조건에 의하면 집합이 하나만 존재하는 것이 아니기 때문에 각 집합마다 원소의 갯수는 다를 것같은데..

댓글 작성하기 좋아요0 댓글수3
- 주니어멘토 Lv.1 2019.08.09 08:33
  
  안녕하세요!
  
  주니어 폴리매스 멘토입니다.
  
  A_n의 정의에서, f에 대한 조건이 조건제시법으로 | 뒤에 제시되어 있고, 그것을 만족하는 모든 함수 f의 집합이기 때문에 가장 커다란 집합을 생각하면, A_n은 유일하게 결정됩니다. 감사합니다.
  
  좋아요0
- code Lv.5 2019.08.09 21:03
  
  함수가 저 집합에서 원소가 되기에, 그 함수의 갯수를 세면 되는건가요?
  
  좋아요1
- 주니어멘토 Lv.1 2019.08.10 02:28
  
  네 정확합니다. 집합의 원소가 함수이고, 함수의 개수를 세면 됩니다!
  
  좋아요0
code Lv.5 2019.08.10 06:32

이 원리를 사용하면 됩니다.

A집합 두 번째 조건에 의해, 좌표계상에서 이웃해 있는 x좌표끼리의 차는 최대 1이며

다음과 같은 그림을 생각할 수 있습니다.

(숫자는 쓰기 귀찮아서 생략)

답은 21이 나옵니다.

같은 원리로

B집합 두번째 조건에 의해, 좌표계상에서 이웃해 있는 x좌표끼리의 차는 1이며,

45도 기울인 정사각형이 피라미드 식으로 연결되어 있는 모형을 확인할 수 있습니다.

답은 42가 나옵니다.

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