수학동아 - 폴리매스

폴리매스 문제

아직 아무도 답을 모르는 문제에 도전하세요!

[슬기로운 수학생활] 슬9. 행렬 채우기 문제

수학동아 2021.01.04 22:17 조회 1746

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

슬기로운 수학생활 9번

행렬 채우기 문제

문제 출제자 : 백진언 미시간 대학교 수학과 박사과정생

자연수 $n$ , $m$ 에 대해, $n imes m$ 짜리 행렬을 1부터 $nm$ 까지의 자연수를 각각 정확히 한번씩만 써서 채웠다.

성질 "숫자 $x$ 는 $x$ 가 속해있는 행에서도 최소값이고, $x$ 가 속해있는 열에서도 최소값이다" 를 만족하는 숫자 $x$ 가 1밖에 없도록 자연수들을 배치할 수 있는 가짓수가 $\frac{(nm)!n!m!}{(n+m-1)!}$ 임을 보여라.

이전글 슬8. 볼록다각형을 세보자!

다음글 슬10. 속이 빈 단색 삼각형

문제 찜하기 목록보기

댓글 작성하기

퍼즐-Scratch Lv.5 2021.03.02 07:52

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/e920c3b26b32f6b51d5aa76b7d5b288a.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

흠, 댓글이 없군요. 아이디어를 공유해 주신다면 정말 감사하겠습니다~ ^^

n이나 m 둘 중 하나가 1이면 자명한데, 2만 되어도 어떻게 해야 할지 감이 오지 않네요... $n+m-1=nm-(n-1)(m-1)$ 을 이용하면 각 변의 길이가 1씩 작은 직사각형과도 어떻게든 연관시킬 수 있을 것 같았는데 어렵네요 ㅎㅎ

댓글 작성하기 좋아요0 댓글수0
파스칼 Lv.7 2021.03.03 04:39

저도 이 문제는 감이 안 오네요

행렬이므로 행렬로 다루어 봅시다

행이나 열을 서로 바꾸는 변환만을 통해 1을 맨 왼쪽 위에 놓습니다

그리고 다시 행이나 열을 바꾸어 1이 포함된 행 또는 열에 속하지 않는 최소의 수를 끌어다 놓습니다

이 과정을 반복하여 정리하면 행렬사다리꼴처럼 바꿀 수 있으며 이때 행렬의 위치 사이에 존재하는 order로 먼저 식을 만든 다음, 이 order를 모두 더하면 좀 더 쉬울 것 같습니다

(아이디어이며 매우 추상적인 상태입니다.. 좀 시간이 나면 더 손대보겠습니다)

댓글 작성하기 좋아요0 댓글수0
피카파이 Lv.8 2021.04.26 23:35

우선 모든 수는 자신보다 작은 수와 x축 또는y축에서 같이 있어야 한다는 것은 자명해요.

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