익스트림 스우 in 100에 포함되지 않는 직업이 존재할 확률은 1이다
작성 완료
- 전제 조건: 모든 직업에게 공평한 상황이라 익스우 in 100에 포함될 확률이 동일하다고 가정
- 익스우 in 100에 포함되지 않은 직업이 적어도 하나 이상 존재할 사건을 $A$라 하자
- $A$의 여집합은 익스우 in 100에 모든 직업이 포함되는 것이다
- 이때 $P(A) = 1 - P(A^c)$
- 따라서 $P(A^c)$를 계산하면 $P(A)$를 알 수 있다
- 간단하게 직업별로 10명씩 총 460명이 도전한다고 가정해보자
- 사건 $A^c$의 경우 직업별로 적어도 한 명 이상 포함되야 하므로 직업별로 1명씩 총 46명을 뽑고 나머지 54명은 남은 414명에서 아무나 뽑으면 된다
- 이제 414명에서 54명을 뽑는 방법에 대해 생각해보자
- 동일 직업이면 동일 원소이므로 414명이란 수치는 46개 직업에 대하여 각 직업의 원소가 9개가 존재하여 도출된 값이다
- 이러한 집합에서 원소를 뽑을 땐 중복 조합을 사용하면 된다
- 즉, 46개의 직업에 대해 중복을 포함하여 54명을 뽑는 것이다
- 여기서 문제가 발생하는데 각 직업에 대해서 최대로 뽑을 수 있는 인원이 9명으로 이는 54명 보다 작다
- 따라서 하나의 직업에서만 뽑는 경우처럼 최대로 뽑을 수 있는 인원을 초과하는 방법은 제외해야 된다
- 일단 뽑을 수 있는 최대 인원 수를 생각하지 말아보자
- 46개의 직업에 대해 중복을 포함하여 54명을 뽑는 방법의 경우의 수는 $x_1 + x_2 + \cdots + x_{46} = 54$를 만족하는 음이 아닌 정수 해의 개수와 동일하다
- 뽑을 수 있는 최대 인원 수를 고려하는 것은 조건식 $0 \le x_1, x_2, \cdots ,x_{46} \le 9$를 추가하는 것과 동일하다
- 이 문제를 이론적으로 해결하기는 어려우니 일단 더 쉬운 조건을 고려하자
- 처음 가정에서 직업별로 10명씩 총 460명이 도전한다고 했는데 10명이 아닌 100명으로 변경하자
- 그러면 방정식은 $x_1 + x_2 + \cdots + x_{46} = 54$로 동일하나 조건식이 $0 \le x_1, x_2, \cdots ,x_{46} \le 99$로 변경된다
- 해당 방정식을 만족하는 음이 아닌 정수 해의 개수는 $ _{46}H_{54} =\, _{99}C_{54}$이다
- 같은 방법으로 46개 직업에서 중복을 포함하여 100명을 뽑는 경우의 수는 $ _{46}H_{100} =\, _{145}C_{100}$이다
import math
denominator = math.comb(145, 100)
numerator = math.comb(99, 54)
result = numerator / denominator
print(result)
- $P(A^c) \approx 0$이므로 $P(A) \approx 1$이다
- 참고로 위와 같이 계산하게 되면 각 직업별로 인원 수가 동일하면서 100명 이상이기만 하면 $P(A)$는 동일하게 계산된다
- 즉, 각 직업별 인원 수가 동일하면서 100명 이상이면 전체 인원 수와 $P(A)$는 상관이 없다
- 각 직업별로 인원 수가 100명보다 적어 충분하지 않은 경우를 마저 생각하자
- 최댓값이 제한되어 있는 조건식을 고려해야 되기 때문에 이론적으로 구하기는 복잡하다
- 동적계획법 알고리즘을 통해 이를 해결해보자
- i + 1개의 직업에서 최댓값 p를 고려하여 j명을 중복을 허용해 뽑는 것을 생각해보자
- i + 1개의 직업은 i개의 직업과 새로 추가된 직업 x로 이루어졌다고 하자
- i개의 직업으로 구성된 경우에 x를 추가한다면 최소 0개부터 최대 p개까지 가능하다
- 만약 p보다 j가 더 작다면 최대 j개 까지 가능하다
- 이제 dp[i][j]를 i개의 직업에서 최댓값 p를 고려하여 j명을 중복을 허용해 뽑는 가짓수라고 정의하자
- 그러면 정의에 따라 dp[i + 1][j] = dp[i][j] + dp[i][j - 1] + ... + dp[i][j - min(j, p)]가 성립한다
- 더 쉽게 생각해보면 x를 포함한 i + 1개의 직업이 p를 고려해 j명을 중복을 허용해 뽑혔다고 가정하자
- 모든 경우에 대하여 x를 제거해보자
- 그러면 남은 경우는 i개의 직업에서 p를 고려해 j - min(j, p)명부터 j명까지 각각에 대해 중복을 허용해 뽑은 것과 동일하다
def reset_dp(target_sum, job_count):
dp = [[0] * (target_sum + 1) for _ in range(job_count + 1)]
dp[0][0] = 1
return dp
def solution(target_sum, job_count, max_value):
dp = reset_dp(target_sum, job_count)
for i in range(job_count):
for j in range(target_sum + 1):
for k in range(min(j, max_value) + 1):
dp[i + 1][j] += dp[i][j - k]
return dp[job_count][target_sum]
# 주어진 등식의 해의 개수 계산
target_sum = 54
job_count = 46
max_value = 9
result = solution(target_sum, job_count, max_value)
print("음이 아닌 정수 해의 개수:", result)
target_sum = 100
job_count = 46
max_value = 10
result2 = solution(target_sum, job_count, max_value)
print("음이 아닌 정수 해의 개수:", result2)
result / result2
- 결론: 충분하지 않은 인원이 도전해도 결과는 동일하다 (확률이 동일하지는 않다)
def compute_p(max_value):
result = solution(54, 46, max_value - 1)
result2 = solution(100, 46, max_value)
return result / result2
compute_p(100)
compute_p(73)
- 소수점 아래 15번째 자리까지밖에 보여주지 않아서 최댓값이 73일 때와 100일 때의 확률이 동일해보인다
- 하지만 완전히 동일한 값은 아님
compute_p(3)
compute_p(4)
- 최댓값이 3일 때가 확률이 가장 크다 (최댓값인 2인 경우는 100명을 뽑을 수 없어서 불가능)
- 최댓값이 커질수록 확률이 작아지다가 100명부터는 동일해진다