‘폴리매스 회원이여 모여라!’ 수학 멘토 군단 ‘폴리매스 어셈블’이 결성되었습니다.
국제수학올림피아드(IMO) 출신 대학생 멘토 6명이 재미있게 생각해 볼 만한 ‘창의 수학’ 문제를 내 주고
수학 공부법과 진로 등에 대한 상담도 해 줄 계획이에요.
2022년, 세 번째 폴리매스 어셈블 문제를 내 준 멘토는 김준수 멘토입니다.
안녕하세요! 저는 폴리매스 어셈블 멘토인 김준수입니다.
2020년 국제수학올림피 아드(IMO)에서 은메달을 땄고,
현재 서울대학교 수리과학부에서 수학 공부를 계속 이어 나가고 있습니다.
현재 2학년이 되어 기하학의 문제를 미적분을 이용해 푸는 ‘미분기하학’을 배우고 있는데,
늘 기하학을 어려워하는 저라 쉽지 않네요.
저는 고등학생 때부터 새로운 문제를 만드는 것을 좋아했어요.
더 어릴 때는 에 실린 신기한 문제들을 재미있게 풀곤 했지요.
여러분도 저처럼 문제를 내 고 푸는 것에 흥미를 가지면 좋겠습니다.
제가 이번에 출제할 문제는 수학과 퍼즐을 좋아하는 친구라면 많이 접해 봤을 ‘네 모네모 로직’과 관련한 문제예요.
‘네모네모 로직’은 각 행과 열마다 숫자가 주어진 격자판에서 각 줄에 적힌 숫자에 맞게 칸을 칠하는 퍼즐이에요.
이 퍼즐을 풀 때마다 늘 ‘답이 딱 하나로만 결정될까?’ 하는 의문이 들었습니다.
실제로 그렇지 않은데요, 그렇다면 과연 어떤 경우에 답이 유일하게 존재할까요?
다음 문제를 풀어 보 면서 그 답을 알아봅시다.
김준수 멘토의 폴리매스 어셈블 문제
문제1 색칠해 보기
4 × 4 표에서 각 행과 열에는 그 줄에 색칠할 칸의 수가 적혀 있을 때, 가능한 색칠을 모두 그 려 보세요. 예를 들어 아래 예시는 조건을 만족하는 하나의 색칠이에요.
문제2 조건 발견하기
사각형 격자판에 몇 개의 칸이 색칠되어 있고, 각 행과 열마다 각 줄에 색칠할 칸의 수가 적혀 있을 때, 현재의 색칠이 이를 만족하는 유일한 색칠이 되기 위한 조건을 찾아보세요.
문제3 증명하기
문제2의 조건이 필요충분조건임을 보이고, 이때 어떤 형태로 색칠해야 하는지를 구체적으로 증명해 보세요.
끝.
-
-
다시 도전
3번이 주 문제인 것 같아서 3번 증명을 올리겠습니다.
그전에 증명해야 하는 것이 있는데, 색칠이 존재하게 만드는 필요충분조건(동치 조건)은 행의 숫자들의 합과 열의 숫자들의 합이 같다는 것입니다.
행에 써져있는 숫자의 합=직사각형 안의 색칠된 칸의 수=열에 써져있는 숫자들의 합 이기 때문입니다. 이는 색칠이 존재하기 위한 동치 조건이죠. (거의 공리에 가까움)
조건으로, 행의 개수를 n, 열의 개수를 k라 하고, 무작위 열(행이어도 되지만 그냥함)에 써져 있는 숫자를 m이라 합시다.
m이 써져있는 열에서는 n칸에 m개의 색칠을 채워넣어야 합니다. 고로, nCm개의 색칠하는 가짓수가 나옵니다. (사실상 0이 있는 행은 제외하므로, 달라질 수 있음, 0의 가짓수까지 고려를 하면, 0의 숫자를 포함하는 행의 개수를 p라 하면 n-pCm이 됨.) 그럼, 우선 그 열은 채워넣었으미, 그 열을 삭제합시다. 직사각형에서 지우는 것이죠. 그저 확실한 걸 지웠으므로 별 영향은 없습니다. 대신, 그 채워넣었던 행들의 숫자들을 각각 -1 해야 하는 것이죠. (이미 하나 채워넣었으므로)
하지만, 직사각형은 여전히 유지됩니다. 고로, 이번에도 행의 숫자들의 합과 열의 숫자들의 합이 같으며, 새로운 로직판(?)이 생기게 되는 것이죠.
근데, 여기서 중요한 것은, 이 로직판에서도 색칠은 존재합니다. 각각의 모든 경우에서요. 즉, nCm 개의 로직판이 생긴 것이죠.
이를 반복하면, 조합들의 곱의 가짓수로, 색칠의 가짓수가 생겨납니다. 유일한 가짓수가 되기 위해선, 이 모든 조합들이 1이 되야 합니다. 이 1은, xCx꼴에서만 존재하게 되는 것입니다.
즉, 임의의 한 열(행)에 써져있는 수와 색칠할 수 있는 행의 수가 같아야 한다는 것입니다. 이를 바꿔말하면, 숫자가 써져있는 행과 열(0이 안써져있는 행,열)의 개수가 같다는 것입니다. (행의 개수=열의 개수) 근데, 우리는 앞에서 "임의의"라고 썼습니다. 먼저 어떤 걸 지우느냐에 따라 가짓수가 달라지는 건 아니니까요.
임의의 행(열)에 써져있는 수는 반대되는 열(행)의 숫자가 써져있는 열(행)의 개수와 같으므로, 또한 그것은 열(행)의 개수와 같게 됩니다. 이는, 그냥 모든 써져있는 숫자가 같다는 말과 동치입니다!
고로, 유일하게 로직판을 만들 수 있는 필요충분조건(동치 조건)은 써져있는(0제외) 숫자가 모두 같으며, 그 숫자만큼 열과 행에 숫자가 써져있는 열과 행의 개수가 같다. (써져있는 숫자=숫자가 써져있는 행의 개수=숫자가 써져있는 열의 개수)
-
