퀴즈 445 동전던지기

---

A,B 가 동전던지기를 한다. A 는 6개의 동전을 B는 5개의 동전을 던진다. A 가 B 보다 앞면이 많이 나올 확률은?

c.f) 참고로 (A : n+1, B: n) 의 경우에도 답은 같다.

풀이

사실 직관적으로 답이 1/2 인 것을 얻어 낼 수도 있다.

아니면 다음과 같은 표를 생각해보자 A 는 n+1 개 B 는 n 개가 있고 A 가 B 보다 앞면이 나올 경우의 수를 직접 세어보자.

옆에 숫자는 A 가 몇개의 앞면의 갯수가 나오느냐를 말해주고, A 줄에는 A 가 나올 수 있는 경우의 수를 B 경우에는 그럴 때 B 가 가질 수 있는 경우의 수 [예를 들어 A 가 앞면이 2개가 나왔다면, B 는 앞면이 0개 또는 1개가 나올 경우 전체를 기입한다. 이 때 전체 경우의 수는 [곱사건이기에] A 의 경우의 수 x B의 경우의 수가 된다.]

가장 극단적인 0인 경우와 n+1 개인 경우를 채워보자

그리고 k 인 경우를 생각해보자

즉 원하는 답은

을 전체 경우의 수인 2^{2n+1} 로 나눈 값이 되겠다.

즉 저 조합 곱의 합을 구해야 한다. 일반화를 생각했지만 문제에 주어진 특정 경우의 수에는 저 합을 직접 구하는 것은 크게 문제가 없다. 그러면 답은 1/2 이 나온다.

여러가지 방법으로 저 값이 2^{2n} 인 것을 보일 수 있다. [explicit 하게 구하려면 좀 많이 까다롭다. 한가지 방법은 nCr = nC_{n-r} 인 것을 이용하는 것이다.

Double counting 을 이용하면 비교적 쉽게 증명할 수 있다는데 좀 생소하다. 확실한 것은 변수를 이리 저리 바꾸고 파스칼 삼각형과 Vandermonde identity 들을 사용하는 건데.... 흠..

이전에 리만 제타 관련 되어서 등장했던 double sum 테크닉을 쓰면 구할 수는 있는데.... 흠.. 일단 풀이 과정을 올리긴 한다.

일반화된 정보는 퀴즈라고 하기에는 좀 선을 넘은듯...

퀴즈 446 크리스마스 선물

---

A,B,C,D 는 각각 다른 색깔의 선물상자에 조그만 피규어 인형을 받았다.

1 . 상자 안에 들어있는 인형의 수는 모두 다르고, 가장 많이 가지고 있는 아이와 가장 적게 가지고 있는 아이는 8개 차이가 났다.
2 . 상자 안에 인형을 홀수개 가지고 있던 아이는 한명 뿐이었지만, 두번째로 많이 가진 아이는 아니었다.
3 . B 는 녹색 선물 상자의 아이보다 4개를 더 가지고 있다.
4 . 회색 선물 상자의 아이는 A 보다 5개를 더 가지고 있다.

A 는 가장 적게 받은 아이일까? 아니라면 A 는 가장 적게 받은 아이보다 몇개 더 선물을 받았을까?

풀이

가장 적게 받은 아이를 n 이라 하자 1 번 조건으로 부터 가장 많이 가지고 있는 아이는 n+ 8 개를 가졌다. 2번 조건으로 홀수 개의 인형을 가진 아이가 한명이라는 것에서 n 은 짝수 라는 것을 알 수 있다. [n 과 n+8 이 등장하니 n 이 홀수여야 한다.] 그리고 홀수개가 두번째로 많이 가진 아이가 아니라고 하니 홀수개는 n보다 큰 3번째 아이가 된다.

자 이제 3번째 조건을 보자 B는 녹색 선물 상자보다 4개를 더 가지고 있다. 여기서 녹색 선물 상자가 홀수개가 될 수 없다. [홀수개가 되면 +4 하면 홀수], 그러니 여기서 생각할 수 있는 것은 두가지이다. 녹색 선물 상자를 가장 적은 n 개와 묶을 경우와 아닌 경우이다. 이를 표로 나타내면

그 다음 마지막 조건을 생각해보자 회색 선물 상자는 A 보다 5개를 더 가지고 있다. (i) 의 경우를 먼저 생각해보자 n이 A 라고 가정하자. 그러면 회색 상자의 주인은 A 보다 5개 많은 n+5 개를 가지는데 이는 홀수다. 이 경우 순서가 뒤집어져서[2번 조건] 모순이 생긴다. 즉 A 는 n 이 아니다. 이 말은 A 는 홀수개를 가진 사람이 된다. 그리고 회색 상자를 가진 주인은 B 로 n+8 개를 가진 사람이 된다. 4 조건에서 두 차이가 5개라고 했으니 A 는 n+3 개를 가진다.

(ii) 의 경우 역시 자연스럽게 B 가 회색 상자를 가졌다는 것을 알 수 있고 A 가 n+8-5=n+3 개를 가졌다는 것을 알 수 있다.

즉 가장 적게 받은 아이를 n 이라 하면 A는 n+3개를 가지고 있다.