뽀대 하나는 확실한 경우의 수 풀이 (예제 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를 선물하세요.
-
대학 가기가 무서움 3 0
-
현타오네 7 0
우으..
-
국어물이어라 3 1
2311 재림!!
-
언어에 대한 한계를 보여주는 지문였음 결국 논리란거도 서술의 반복에 불과하다는...
-
근데 와이파이 어디감 1 2
저번에 UI바뀔때 없어졌나
-
심찬우 들으면 좋은점 4 4
국어 끝나기 직전 "문학 심상전개" 사용해서 같은 반 사람들의 뇌를 정지시켜서...
-
정신병올거같다 6 1
왜 나는 수학이 안되냐 수학이 2만 나와줬어도 이렇게 힘들필요 없는데
-
인문은 강한데 법에 약함 3 1
원칙이랑 예외랑 따로따로 머릿속에 집어넣는걸 잘 못함 약간 머릿속에서 스까진달까
-
본인 최애 지문은 3 1
점유소유...긴합니다 예전에 내 힘으로 처음으로 뚫어낸 지문이 이거임
-
오르비팔로워/인스타팔로워 2 1
성립하지않아요…
-
아 심심해 1 1
너무 심심해서 공지글 댓글 좋아요 누르고옴
-
일찍 자겠습니다 2 0
그동안의 나태를 반성합니다
-
23수능은 77점 (5등급) 23 6모 83점 (1등급) 나옴 원래 이럴 수 있냐...
-
. 2 0
.
-
뽀대 하나는 확실한 경우의 수 풀이 (예제 2개 포함) 2 0
들어가기에 앞서, 필자는 확통은 재미로만 일부 공부했고 수능과 내신에도 선택안했기에...
-
사회인 정도까지는 배워보고 싶은데
-
저는얼마전에1돌파했음 2 1
오르비 팔로워/인스타 본계 팔로워 수치...
-
강원도 출신 걸그룹 멤버 6 1
-
죽으면 회귀함 6 4
내가 믿는 종교인 회귀교에서 그렇게 말함 ㅋ
-
하관을 아그팔트에 갈았네 5 0
이거 어케 못하나 ㄹㅇ
확통의 신 ㄷㄷ
라기엔..재미로만 공부...