책 이야기

항아리에 일곱 가지 무지개 색의 공이 각각 10개씩, 총 70개의 공이 항아리에 있다.

랜덤하게 20개의 공을 선택할 경우 몇 가지의 색이 있겠는가?

소숫점 9자리까지 답을 구하시오(a.bcdefghij형태).

--------------------------------------------------------------------------

처음에는 조합(combination)을 이용해서 나오는 각 경우의 수에 대한 색상 종류를 구해서 전체 평균을 구하는 형태로 접근했는데, 가능한 조합인 ₇₀C₂₀의 값이 161,884,603,662,658,000이어서 코딩을 정확하게 한 것은 자신있지만 시간 내에 답을 구하리라는 장담을 할 수 없는 상황이었다.

그래서 다른 형태의 접근이 필요한 상황이었는데, 구글의 도움을 받아 해결할 수 있었다. 특정 색이 있지 않을 확률은 70개 중 60개에서 20개의 공을 꺼내는 경우이므로(₆₀C₂₀/₇₀C₂₀), 특정 색이 있을 확률은 정반대가(1-₆₀C₂₀/₇₀C₂₀) 되며, 7개 공 각각에 대해 구하면(7*(1-₆₀C₂₀/₇₀C₂₀)) 된다.

이렇게 접근하는 논리를 생각해 내는 것이 쉽지 않은 문제이지, 이 논리를 구현하는 것은 정말 간단하다.

피터는 (피라미드 모양) 4면 주사위 9개를 가지고 있고, 각 주사위 면에는 1,2,3,4가 적혀 있다.

콜린은 (정육면체 모양) 6면 주사위 6개를 가지고 있고, 각 주사위 면에는 1,2,3,4,5,6이 적혀 있다.

피터와 콜린이 주사위를 굴려 합계를 비교해서 합계가 큰 사람이 이긴다. 둘의 합계가 같으면 무승부이다.

4면 주사위를 가진 피터가 콜린을 이길 확률은 얼마인가? 정답을 소숫점 7자리까지 반올림으로 나타내어 0.abcdefg 형태로 제시하시오.

--------------------------------------------------------------------------

처음에 랜덤 함수를 이용하여 둘의 주사위를 생성하고, 합계를 비교하는 몬테카를로 시뮬레이션 방법을 활용하여 천만번 게임을 운영한 승패를 구했는데 답이 맞지 않았다.

그래서 어쩔수 없이 단순하게 전체 경우를 구하는 형태로 접근을 바꿨다. 파이썬 라이브러리의 중복순열(from itertools import production)을 이용하여 피터와 콜린의 경우의 수를 각각 구하고, 그것을 합계로 바꿔 반복문을 통해 두 사람의 모든 경우를 비교하는 형태로 구현했다. 이렇게 설명하면 간단하지만 두 사람의 경우를 곱하면 122억이 넘기 때문에 보기보다 많은 시간이 걸리는 문제였다(몬테카를로 시뮬레이션을 활용하더라도 100억 번은 넘어야 결과에 가까운 답이 나올 수 있다는 뜻으로 이해되었다).

다시 생각해보니, 피터는 9~36, 콜린은 6~36의 합계가 나올 수 있지만 경우의 수는 각각 262,144, 46,656이므로 많은 경우 중복되어 나온다. 앞의 방식처름 122억 회 이상 비교하는 것 보다는 각 값에 대한 발생횟수를 가중치 형태로 만들어서 계산하니 2초 내외에 답을 구할 수 있었다.

문제를 잘못 이해해서 답을 abcdefg 형태로 구했는데 계속 틀리게 나와 알고리즘을 다시 검토하는 등 시간을 많이 소모했는데, 답은 이미 맞게 구했고 '0.abcdefg' 형태로 답을 쓰면 되는 것이었다.

가방에 붉은 색 원반 1장과 푸른 색 원반 1장이 있다. 게임에서 원반 1장을 랜덤하게 꺼내고 색을 기록한다. 각 회차가 끝나고 나면 원반을 다시 가방에 넣고 붉은 색 원반 1장을 추가한 후, 원반 1장을 랜덤하게 꺼낸다.

참가자는 1파운드를 내고 경기에 참가하고, 게임이 끝났을 때 푸른 색 원반이 붉은 색 원반보다 많은 경우 승리한다.

게임이 4회차로 구성된 경우, 참가자가 승리할 확률은 정확하게 11/120이고, 주최측이 손실을 입지 않으려면 할당해야 하는 최대 상금은 10파운드가 되어야 한다. 모든 상금은 파운드 단위로만 되어야 하고 참가비 1파운드가 포함되므로, 예시에서 참가자가 획득하는 돈은 9파운드가 된다.

게임이 15회차로 구성되는 경우 할당해야 하는 최대 상금을 구하시오.

--------------------------------------------------------------------------

확률과 조합을 이용하여 해결하는 문제이다.

예시를 조금 설명하면, 참가자가 승리하는 경우는 파란색 4장을 꺼낸 경우와 3장을 꺼낸 경우이다. 그러면 전체 가능한 경우 120(2*3*4*5) 중 파란색 4장을 꺼낸 경우는 1회이며(1/2*1/3*1/4*1/5), 3장을 꺼낸 경우는 10회(처음 나올 경우 1회, 2번째 2회, 3번째 3회, 4번째 4회)가 된다.

15회차 게임에서 승리할 경우는 전체 경우 20,922,789,888,000(2*3*4*5*6*7*8*9*10*11*12*13*14*15*16) 중 파란색을 8장 이상 꺼낸 경우를 계산하면 된다. 위 예시 설명에서 나오듯이 파란색을 꺼내는 경우는 1, 붉은색을 꺼내는 경우는 '해당 차수 원반 전체-1'이 된다.

붉은 색인 경우를 대상으로 계산을 하면 되므로, 붉은 색이 0장에서 7장인 경우를 계산하는 반복문을 만들고, 각 반복에서 가능한 조합을 생성해서 조합의 갯수를 합하는 형태로 구성하였다. 참고로, 붉은색 공이 2개인 경우 2개를 곱하는 방식을 통해 조합의 전체 갯수를 구하고, 조합의 갯수를 합해야 한다.

그리고, 참가자가 우승할 조합 갯수에 상금을 곱해서 전체 경우보다 작으면서 가장 큰 상금을 구하면 된다.

조합이나 확률을 잘 이해하면 좀 더 짧은 코드로 구현 가능했을 것 같은데, 기초만 이해하는 상황에서는 이 구성이 최선이었고 빠른 시간 내에 답을 구할 수 있었다. 난이도는 35%였지만 적성에 맞는 문제인지 어렵지 않게 해결 가능했다.

If a box contains twenty-one coloured discs, composed of fifteen blue discs and six red discs, and two discs were taken at random, it can be seen that the probability of taking two blue discs, P(BB) = (15/21)×(14/20) = 1/2.

The next such arrangement, for which there is exactly 50% chance of taking two blue discs at random, is a box containing eighty-five blue discs and thirty-five red discs.

By finding the first arrangement to contain over 10¹² = 1,000,000,000,000 discs in total, determine the number of blue discs that the box would contain.

파란색 디스크 15장, 빨간색 디스크 6장으로 구성된 21장의 디스크가 있는 박스에서, 디스크 2장을 랜덤하게 선택하는 경우 2장의 파란색 디스크를 선택할 확률은 P(BB)=(15/21)x(14/20)=1/2이다.

동일한 구성으로 2장의 파란색 디스크를 랜덤하게 선택할 확률이 50%인 경우는 85장의 파란색 디스크와 35장의 붉은색 디스크로 구성된 경우이다.

총 10¹² = 1,000,000,000,000장 이상 디스크가 있을 때 동일한 구성으로 2장의 파란색 디스크를 랜덤하게 선택할 확률이 50%가 되는 경우는, 파란색 디스크가 몇 장 있을 때인가?

--------------------------------------------------------------------------

(중학생 이하 수준이지만) 갈수록 수학문제가 되고 있는 상황인데, 근의 공식을 이용하여 해결하기로 결정했다. 이전에 √를 바로 사용하면서 소숫점이 이하 자리 숫자가 있음에도 값이 너무 작아 정수로 판정되는 오류를 겪었기 때문에, 큰 수이지만 일단 제곱수인 상태에서 적용해 보기로 했다.

확률이 1/2일 때 총 디스크 수를 c, 파란색 디스크 수를 x라고 하면, P(BB)=(x/c)*((x-1)/(c-1))=1/2이며, 이것을 전개하면 2x²-2x=c(c-1), 2x²-2x-c(c-1)=0이 된다. 여기에 근의 공식을 적용하면 x=(2+(4+4*2*c(c-1))**0.5)/2*2가 되고, 루트 기호 부분 기준으로 정리하면 (4+8c(c-1))**0.5=4x-2이 되고, 양쪽을 제곱하여 루트를 없애면 1+2c(c-1)=(2x-1)²가 된다. 수학 기호를 html로 표기하는 방법이 익숙하지 않아 가독성이 나쁘게 적었지만 이와 같은 형태로 방정식을 구할 수 있다.

여기에서 c는 1조에서 시작하고, x는 좌변의 값보다 조금 작은 값이 나올 값에서 시작해서 양 변이 같을 때까지 c와 x값을 계속 키우면서 찾는 작업을 했다. 양변을 크게 보면 8*c^2와 16*x^2가 있어서 x의 시작값을 1부터 하지 않고 c/√2부터 시작해서 추적했다. 실행이 생각보다 오래 걸려서 상황을 보니 이 방법으로는 답을 구할 수 없을 것 같았다.

먼저 방법으로는 해결되지 않아 인터넷을 검색해 보니, 연분수와 비슷하게 x, c의 이전값을 통해 새 값을 찾을 수 있다고 되어 있었다. 문제에서는 (x, c) 값이 (15, 21), (85, 120)인 경우가 있었는데, (3, 4)인 경우에도 확률이 파란색 2개가 연속으로 나올 확률은 1/2가 된다.

이 (x,c)값 3쌍을 이용하여 x, c값의 다음 항에 대한 일차방정식을 유추해봤고(xn=3x+2c-2, cn=4x+3c-3), 그 공식으로 만든 숫자로 다음 값인 (493, 697) 또한 파란색 2개가 나올 확률이 1/2임을 확인해서 해당 공식을 통해 빠른 시간 내에 답을 구할 수 있었다.

일차방정식을 빨리 유추하기 위해 엑셀을 사용했는데, 엑셀로는 12자리 이상 숫자를 확인할 수 없다는 것 또한 알게 되었다.