오늘은 미국 수학 경시대회 문제입니다.
공간 풀이법 : 그림, 도형, 도표를 이용하자
Let K be the number of sequences A_1, A_2, … , A_n such that n is a positive integer less than or equal to 10, each A_i is a subset of {1,2,3,…,10}, and A_i-1 is a subset of A_i for each i between 2 and n, inclusive. For example, {}, {5,7}, {2,5,7},{2,5,7}, {2,5,6,7,9} is one such sequence, with n=5. What is the remainder when K is divided by 10?
(Combinatorics, Number Theory, Source : 2023 AMC 12)
번역을 하고 시작해야겠죠?
10이하의 자연수 n에 대하여 n개의 집합 A_1, A_2, … , A_n을 배열한다. 각각의 집합 A_i는 {1,2,3,…,10}의 부분집합이며, 직전의 집합 A_i-1을 포함한다. 예를 들면 다음과 같은 배열은 n=5인 한 예이다.
{}, {5,7}, {2,5,7},{2,5,7}, {2,5,6,7,9}
이러한 전체 배열의 갯수를 K라 할 때, K를 10으로 나눈 나머지를 구하라.
그림(=도표)을 이용하자.
길이가 2인 경우에 다음과 같은 도표를 그릴 수 있습니다. 집합을 그림과 같이 표현하니 그들 사이의 포함관계는 이미 이 그림에 다 표현되어 있습니다. 전체 경우의 수는 몇 가지일까요? 각각의 원소를 세 영역중 어디에 넣을 것인가만 결정하면 됩니다. 모두 3^10가지입니다.
이제 K = 2^10+3^10+…+11^10입니다. 첫 번째 풀이 공간의 결론을 얻었습니다. 간단한 계산은 아닌 듯하니 두 번째 풀이 공간을 열겠습니다. 나머지의 계산으로 이름 붙이죠. 복잡한 이론을 쓰지 않아도 해결할 수 있는 방법이 있습니다. 왜냐 하면 목표공간에 이미 K의 일의 자릿수 구하기라고 써놓았기 때문입니다. 반복되는 규칙성을 찾습니다.
공간 학습법 : 서로 다른 내용이면 분리하자.
오늘 이야기하고 싶은 학습법은 ‘서로 다른 내용을 나누자’입니다. 이 문제는 앞 부분 경우의 수 부분과 뒷 부분 수열의 계산 부분이 서로 관련이 없습니다. 이론적인 접점이 전혀 없어서 별개로 풀이하면 되는 상황이네요. 그래서 풀이 공간을 두 개로 나누어서 풀 수 있었습니다.
그래서 전체적인 풀이의 공간들을 다음과 같이 배열해 볼 수 있답니다. 도형이나 도표를 찾아서 아주 쉽게 풀 수 있는 문제였네요. 미국 경시 문제 별거 아니죠?
오늘은 여기까지 입니다. 다음에 더 재미있는 문제로 만나요!~