뽀대 하나는 확실한 경우의 수 풀이 (예제 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를 선물하세요.
-
1명 모집 낮공인데... 안되겠죠?ㅜ
-
시대인재 서바이벌 2 0
서바 시즌에는 가서 풀셤보고 문풀하는거 보고 끝인가요? 라이브반도 있는 지 궁금합니다.
-
리버스 나르키소스임 1 1
나도 비춰진 내 모습을 보면 강물에 뛰어들고 싶어짐
-
이번 수특 계산 왜이럼 3 0
절레절레
-
학생들을 뭔가 굉장히 능동적이고 주체적이고 열정적으로 자신의 꿈을 찾고 꿈을 이루기...
-
요즘 독서실문제임 1 0
제대로된1인실독서실이없음 다스카,관리형독서실행중
-
평백 91이에요 화확사탐 89 85 99 97 평균 2등급은 나왔어요 3 3 1 1 2 1
-
열품타 들어가고싶은데 2 0
잇나요 댓글로 저 받아주실 열품타 구해요..
-
34만전자·170만닉스 전망…맥쿼리 "메모리 공급부족 심화" 4 1
[이데일리 박순엽 기자] 외국계 증권사들이 메모리 반도체 업황을 바라보는 눈높이를...
-
공부 어플 ㄱㅊ은거 있나여? 2 0
공부 어플 적당한거 찾고 있음 약간 플래너 처럼 하루 공부한거 정리하는 용도로...
-
뭐할까 추천좀 해봐 2 0
-
현역 사탐확통런 1 1
고2모고 과탐쳐서 모든과목 전부다 3정도 뜨는데 정시로 대학가려면 미적 과탐보다는...
-
아니면 제가 싸게 가져갑니다~
-
기하 1 0
응 수식
-
바보 1 0
바보야
-
하닉 120 갔으면 4 1
ㄱㄱㄱㄱㄱ
-
시발점 강의 다 들었는데 강의 다시 들어야 할까요? 아니면 그냥 책 읽으면서 문제 풀까요?
-
에에 2 0
3월 1일이 일요일이라고? 아..이건아니지예
-
투과목 안에선 인원수가 생2가 가장 많을텐데 작수가 몇명 차로 1컷이 45였네
-
헤겔지믄 볼때마다 질내4바를인가 그사람 글 떠오름 1 4
아직까지도 충격으로 남은 그의 게시물...
확통의 신 ㄷㄷ
라기엔..재미로만 공부...
뛰어난 발상이네요.더 나아가서 중복조합 수열의 generating function을 0 근방에서 maclaurin series로 근사전개한 후 이항정리로 계수를 추출하는 방법도 생각해볼 수 있죠. 교육청 30번 중에 이거 한방으로 뚫리는 것도 있더라구요
좋게 봐주셔서 감사합니다! 헉 이산 수학을 공부해본 적이 있으신가 보군용 메클로린 급수... 저 풀이를 배우려고 아등바등할 때 테일러 급수 테일러 전개랑 같이 딸려있었던 것 같은 기억이 나네요! 재밌어보여요 아직 본글의 풀이도 제대로 마스터를 못했지만 한번 수능 공부하면서 지루할 때 그것도 한번 배워봐야겠어요