[Algorithm] HW1

The Birthday Problem (The Birthday Paradox)

문제

• n명으로 이루어진 모임에서 생일이 같은 두 명의 사람이 있을 확률을 구하는 문제이다.

• 이 문제가 갖는 의의는 아래와 같다:

"꽤 많은 사람이 모여야 생일이 같은 한 쌍이 나올 것 같지만,
23명의 사람만 모여도 생일이 같은 한 쌍이 나올 확률이 50%가 넘어가며,
57명의 사람이 모이면 생일이 같은 한 쌍이 나올 확률이 99%가 넘어간다."

문제 분석

• 여사건의 개념을 통해 문제에 접근한다.
• 전체 K 명의 학급에서 모든 생일의 수가 전체가 되고, 여집합에 해당되는 것은 K명의 사람들이 모두 생일이 일치하지 않을 경우이다.

Calculation Probability (확률 계산)

n : 사람 수 n≤365

p(n) : n 명의 사람이 모였을 때, 생일이 같은 사람이 둘 이상 있을 확률

~p(n) : n 명의 사람이 모였을 때, 모든 사람의 생일이 다를 확률 (~p(n)=1−p(n))

• 1년은 365일이므로, n≥366이면 Pigeonhole Principle 에 의해, 생일이 같은 두 사람이 무조건 존재하게 된다.

그러므로 n≤365인 경우로 제한하여 확률을 계산한다.

최종 구하고자 하는 사건 = 1-(365 Cn*n!)/365^n

위의 확률을 보면 50% 이상의 확률을 가지기 위해선 23명의 인원만 모여도 가능함을 볼 수 있다.

증명

귀납정 증명을 통해 정확성을 증명해본다.

• p(1)이 참이다.
• p(n)이 참이면 p(n+1)이 참이다.
  위를 모두 만족하면 모든 n에 대해서 참이 된다.

코드

def condination(x,y):
	result = 1
    underresult = fact(y)
    while y > 0:
   	return (1-(combination(365,n)/undernumber))