뽀대 하나는 확실한 경우의 수 풀이 (예제 2개 포함)
게시글 주소: https://orbi.kr/00077717201
들어가기에 앞서, 필자는 확통은 재미로만 일부 공부했고 수능과 내신에도 선택안했기에 이러한 내용이 확통에 있는지 없는지 모른다. 다만 경우의 수 문제들을 풀면서 재밌는 풀이를 찾아서 끄적여본다.
(실용성 없고 개억지인 거 알고 있으니까 재미로만 보셈 본인 수학 개허수임)
다항식 Q(x)를 생각해보자.
Q(x)는 우리가 숫자 하나를 뽑을 때, 발생하는 상황을 하나의 다항식 항(a*xn)으로 나타낸 것이다.(머리 속에 그려지나용) 이 때 지수 n은 내가 뽑은 숫자이며, 계수 a는 그 수가 나올 수 있는 경우의 수이다.
그렇다면 (Q(x))^z를 생각해보자. 다항식이 곱해졌으니 지수 법칙(x^a * x^b = x^(a+b))에 의해 각 항들이 알아서 더해질 것이다. 그러니까 단순하게 다항식만 전개하면 합의 분포가 나오는 것이다!
조금 머릴 굴려보면 z는 뽑는 횟수이고, 다항식의 곱셈은 연속적인 선택이라는 생각이 든다.
1. 서로 다른 주사위 3개를 굴려 합이 7이 나올 경우의 수를 구하시오.(서다주3 ㄷㄷ)
풀이 :
쒀론:
먼저, 이 문제는 미적분 쪽 개념도 약간 필요하다. 간단해서 딱히 비중을 차지하지는 않는다.
뽄론:
문항에 따르면 각 항의 지수가 주사위에서 나올 수 있는 숫자(1~6)이고, 각각 경우의 수는 1개일 것이다.
Q(x) = x+x2+x3+x4+x5+x6
서다주 3개니까 총 3번 던진걸로 생각을 해보면, (Q(x))^3이 문제의 답을 구할 수 있는 다항식이라는 것이 자명하다.
(Q(x))^3의 x7의 계수가 정답인 것을 구했다! 그럼 이제 다 전개해서 풀면 끝이다!
만약 그런다면 직접 노가다하는 게 더 빠르겠다.
그런데 제목에서 미적분 개념이 쓰인다고 하지 않았는가? 단지 어그로였을까?
여기서 미적분 개념과 등비수열의 합 공식이 한 스푼 들어간다.
Q(x)는 초항이 x고 공비도 x인 등비수열을 제6항까지 더한 것으로 볼 수 있다.
(Q(x))^3 = {x(1-x^6)/(1-x)}^3...이다.
x^3을 일단 빼내면 나머지 괄호에서 x^4이 나와야만 할 것 같다.
그런데 1-x6에서 x6이 들어가면 벌써 x4를 초과하므로, 1만 고려해줘야한다.
1/(1-x)의 세제곱에서 x^4를 빼내야 한다. 도무지 안 보이고 말도 안 되는 것 같다.
여기서 미적분 개념이 쓰인다.
1/(1-x)가 무한급수라서, 1+x+x^2+....이다.
즉 1+x+x^2+....의 세제곱에서 x^4을 빼내야하는데, 위에서 언급한 다항식과 경우의 수의 관점에서 바라본다면
x^4의 계수는 3H4라는 것을 이끌어낼 수 있다.
답 : 3H4 = 15
2. 집합 X = {1,2,3,4}에서
집합 y = {1,2,3,5,6,7}로의 함수 중에서
f(1)+f(2)+f(3)-f(4) = 4m (m은 정수)를 만족시키는 f의 개수를 구하시오.
이 문제도 앞서 언급한 방법으로 풀면 도움이 된다고 말할 수는 없지만 뽀대가 난다.
문제에서 우리가 숫자 하나를 뽑을 때, 중요한 것은 그 숫자를 4로 나눈 나머지가 무엇인가..이다.
공역의 원소들이 1,2,3,5,6,7은 각각 4의 나머지로 분류하면
나머지 1,2,3이 경우의 수가 각각 2개 씩나온다.
즉 Q(x) = 2x + 2x^2 +2x^3으로 생각해볼 수 있다.
문제의 조건은 f(1)+f(2)+f(3)-f(4) = 4m, 즉 나머지가 0이라는 소리다.
나머지는 다 더하기지만 f(4)는 빼기이다. 지수에서 뺀다는 것은?
x^(-f(4))를 곱한다는 것과 같다!
즉 문제에서 우리가 찾을 수 있는 조합의 분포는 (Q(x))^3 * Q(x^-1) -> p(x)라고 치겠다. 으로 나타낼 수 있다.
이제 이 식들을 다 전개해서 x^0 , x^4, x^-4 같이 지수가 4의 배수인 항들의 계수만 다 더하면 그게 정답이다.
여기서 또 이상한 테크닉?이 들어가는데, 다항식에서 지수가 4의 배수인 계수들만 쏙 뽑아내는 마법공식이다.
바로 복소수 i를 사용하는 것이다!
바로 답부터 말하자면, P(1) + P(i) + P(-1) + P(-i)를 4로 나눈 값이 정답이다.
왜?
i의 n제곱은 n이 4의 배수일 때만 1이 되고, 나머지는 i,-1,-i로 변하면서 "상쇄"되어 사라지기 때문이다.
여기서 주의해야 할 점이 있다.
우리는 x값으로 1, i, -1, -i만 대입할 것이다. 이 숫자들은 전부 다 x^4 = 1을 만족한다.
x^4 = 1이라면, x^-1은 x^3과 같고, x^-3은 x^1과 같다.
그렇다면 직접 대입해본다면, Q(x-1 ) = Q(x)를 만족하게 된다. 그래서 계산 편의 상 P(x) = Q(x)^4로 두고 풀어도 된다.
만약 그렇지 않다면, Q(x)^3 * Q(x^-1)를 계산해야 한다.
문제에서 기가 막히는 대칭성을 제공해준 덕분에, 계산이 편리해진 셈이다.
최종 계산이다. P(1) + P(i) + P(-1) + P(-i)를 4로 나눈 값이 정답이라고 앞서 말했으니,
Q(1) = 6 -> 64 = 1296
Q(i) = -2 -> 16
Q(-1) = -2 -> 16
Q(-i) = -2 -> 16
1344/4 = 366이 답이 된다.
풀이3줄정리
1. 공역의 나머지들의 구성을 다항식으로 바꾼 뒤
2. 조건식을 지수법칙으로 연결
3. 복소수의 주기성을 이용해 4의 배수항만 필터링
마치며
이 풀이방식은 합이 n의 배수가 되는 경우의 수를 묻는 모든 문제에 적용할 수 있긴 하다. 쓸모가 있나? 모르겠다.
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
인하대는 열등감 덩어리들이 많음? 57 20
당연 곽에도 홀리가 있긴 하지만 에타에 타 대학 비방글이나 계획적인 훌리짓을...
-
잠이 안오ㅓ ㅠㅠㅠㅠㅠ 0 0
자기시러러 ㅠㅠ
-
수학 작년 20번 문항 2 0
작수 20번 같은 빈칸추론 문항 풀이법 같은게 따로있을까요? 21번은 풀리는데...
-
근데 과외 어디서 구함 0 1
김과외랑 숨고 알아봤는데 거기는 너무 과외를 업으로 삼는 사람들밖에 없는고 같음...
-
더프 담날에 서프보는데 0 1
채점하면서 ㄹㅇ 도파민 터지겠다 요새 실모 중독 걸린거 같음 어싸는 뭔가 풀 맛이 안나요
-
기숙학원 반수반 장학이 0 0
당해년도 6모 성적으로 장학 받을 수 있나요? (시대인재나 강대 등)
-
기숙 or 독재 0 1
삼수생이고 재수 때는 언미물지로 6,9는 영어 빼고 다 1인데 수능 때 수학 탐구를...
-
-
솔텍하면 수특 안해도댐? 0 0
솔텍에 연계교재 반영이라고 써있는데.. 100프로 반영이 아닌가요?
-
아노네에에에 헨지오쵸오다이 0 0
-
땅콩 그릇에서 남은 땅콩 주워먹으려다가 텅 빈 껍데기를 집은 그런 기분이야
-
이를 시도한 사람들은 하나같이 무언가에 의해 제거되었다
-
현역 수학 커리 0 0
뉴런 3모 전에 한바퀴 돌리고 틀린거 복습 빠르게 하고 수분감 스텝2랑 입문 n제...
-
오르비 열품타 초대 0 0
오르비 열품타 초대해주실 분 잇나요...... 저 열심히 할게요
-
하 나만 1 0
현대,고전 소설보다 시가 어렵나 도대체 어케 읽어야하는 건지 모라고 이야기하는 건지를 모르겠네
-
오르비 첫글 처녀때기 2 0
드디어 가입한지 일주일이네 감사합니다 감사합니다
-
생기부 질문이요 0 0
동아리 만들려는데 생기부에 동아리 내용 몇바이트 제한 있잖아요. 동아리 이름도...
-
아나타와 이마 도코데 0 1
나니오시테 이마스까
확통의 신 ㄷㄷ
라기엔..재미로만 공부...
뛰어난 발상이네요.더 나아가서 중복조합 수열의 generating function을 0 근방에서 maclaurin series로 근사전개한 후 이항정리로 계수를 추출하는 방법도 생각해볼 수 있죠. 교육청 30번 중에 이거 한방으로 뚫리는 것도 있더라구요
좋게 봐주셔서 감사합니다! 헉 이산 수학을 공부해본 적이 있으신가 보군용 메클로린 급수... 저 풀이를 배우려고 아등바등할 때 테일러 급수 테일러 전개랑 같이 딸려있었던 것 같은 기억이 나네요! 재밌어보여요 아직 본글의 풀이도 제대로 마스터를 못했지만 한번 수능 공부하면서 지루할 때 그것도 한번 배워봐야겠어요