00:07 <@JongMan> 25명의 사람이 있어
00:08 <@JongMan> 이 사람들이 모자를 쓰고 있다가
00:08 <@JongMan> 바구니에 집어넣고
00:08 <@JongMan> 랜덤하게 redist. 해줬다?
00:08 <@JongMan> 이제 게임을 하는데
00:08 <@JongMan> 한 사람이 자기 모자를 썼을 때마다 5 씩을 내가 너한테 주는거야.
00:08 <@JongMan> 그러면 이 게임을 하는 댓가로 얼마를 낼래?
라는 문제였습니다.
물론 0$5 씩을 내가 너한테 주는거야.<br> 00:08 <@JongMan> 그러면 이 게임을 하는 댓가로 얼마를 낼래? <br> 라는 문제였습니다.<br> 물론 0$..... 내고 할 수 있다면 좋겠지만 이게 의도가 아니라는 건 다들 알고 계시겠지요? ;ㅁ;
우선 정답을 먼저 말하자면 5가 됩니다. 이 문제를 푸는 방법은 매우 다양합니다만,
간단한 한 가지 풀이를 소개하자면 25! 가지의 수열을 쭉 쓴다고 가정해 봅시다.
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25)
(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 24)
...
(25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1) : 총 25!가지 경우
여기서 1이 첫번째 위치에 있는 경우는 몇 가지가 될까요? 아마 처음 나오는 24!개의 경우가 될 것입니다.
그러면 2가 두번째 위치에 있는 경우는? 마찬가지로 24!개의 경우가 될 것입니다.
[카운트 하기 힘들다면, 첫번째 위치와 두번째 위치를 바꾼 수열을 생각해 보세요! 2가 첫번째 위치에 있는 경우는 명백하게
24!개의 경우가 있으니까요]
그러면 1, 2, ..., 25가 자기 자리를 지키는 경우는 모두 24!가지 경우가 되는겁니다 !
따라서 5$가 됩니다. 이 문제를 푸는 방법은 매우 다양합니다만,<br> 간단한 한 가지 풀이를 소개하자면 25! 가지의 수열을 쭉 쓴다고 가정해 봅시다.<br> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25)<br> (1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 25 24)<br> ...<br> (25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1) : 총 25!가지 경우<br> 여기서 1이 첫번째 위치에 있는 경우는 몇 가지가 될까요? 아마 처음 나오는 24!개의 경우가 될 것입니다.<br> 그러면 2가 두번째 위치에 있는 경우는? 마찬가지로 24!개의 경우가 될 것입니다. <br> [카운트 하기 힘들다면, 첫번째 위치와 두번째 위치를 바꾼 수열을 생각해 보세요! 2가 첫번째 위치에 있는 경우는 명백하게<br> 24!개의 경우가 있으니까요]<br> 그러면 1, 2, ..., 25가 자기 자리를 지키는 경우는 모두 24!가지 경우가 되는겁니다 !<br> 따라서 5$ * (24! / 25!) * 25 = 5 가 됩니다. [우리가 얻는 돈(5$가 됩니다. [우리가 얻는 돈(5$) * ( i 가 자기 자리를 지킬 확률 ) * (i는 1 ~ 25) 가 되는거지요]

그럼 응용문제로, Derangement에 대하여 알아봅시다.
wikipedia에서 찾아보면 잡다한 설명이 많~이 나오는데요 =.=
위의 문제와 비슷한 설정인데요. "n명의 사람이 있을때 모든 사람이 자기의 모자를 쓰지 않는 경우의 수!" 가 Derangement가 됩니다.
D(n)의 점화식을 구할 수 있는데요 ! 숙제입니다 !
[spoiler="해답입니다?!"]D(n) = n 명의 사람이 있을 때 모든 사람이 자기의 모자를 쓰지 않는 경우의 수. 라고 정의했지요?
일단 n번째 위치에는 n이 절대로 올 수 없습니다. (당연하겠죠?)
따라서 n은 1 ~ n-1번째 위치중에 하나에 있다는 말이 되겠군요 'ㅁ'
case 1 -- n이 i번째 위치에 있고, n번째 위치에 i가 있는 경우와
case 2 -- n이 i번째 위치에 있고, n번째 위치에 i가 있지 않는 경우로 나눠서 생각을 해 봅시다.
case 1 과 case 2는 교집합이 없고, 모든 영역을 포함합니다.
따라서 D(n) = (n - 1) * { (case 1) + (case 2) } 가 되겠네요. 앞에 n - 1이 붙은건 n이 1 ~ n-1번째 위치중에 하나에 있으니까요.
(case 1)은, n과 i를 제외하고 생각해 보면 D(n - 2)일 때의 정의와 일치한다는 것을 알 수 있습니다. 즉 (case 1) = D(n - 2)
(case 2)는, i번째 위치에 있는 n은 없애고, n번째 위치에 있는 숫자를 i번째 위치로 가져온다고 가정을 해 봅시다.
우리는 위에서 (case 2)를 정의할 때 n번째 위치에 i가 있지 않는 경우라고 했으니, n번째 위치에 있는 숫자를
i번째 위치로 가져온다고 해서, 자기의 모자를 쓰는 사람은 생기지 않습니다. 즉 n-1명이 모두 자기의 모자를 쓰지 않았네요.
따라서 (case 2) = D(n - 1)입니다.
정리하면 D(n) = (n - 1) * (D(n - 1) + D(n - 2))가 되겠군요.
[/spoiler]