Problem Analysis #probability_30

문제 모델링

10개 주머니에 공 8개(구별 없음), 각 주머니 최대 2개. 조건:

• (가) 정확히 1개인 주머니 수 = 4 또는 6
• (나) 2개인 주머니의 양옆 주머니는 0개

공 개수 계산으로 경우가 제한됩니다:

• 1개 주머니가 4개면: 4 + 2k = 8 → 2개 주머니 k=2, 0개 주머니 4개
• 1개 주머니가 6개면: 6 + 2k = 8 → 2개 주머니 k=1, 0개 주머니 3개

전수 조사로 경우의 수를 셉니다.

Recorded Python call:

from itertools import product

count = {4: 0, 6: 0}
examples = {}
for a in product(range(3), repeat=10):  # each bag: 0,1,2 balls
    if sum(a) != 8:
        continue
    ones = a.count(1)
    if ones not in (4, 6):
        continue
    ok = True
    for i, v in enumerate(a):
        if v == 2:
            if i > 0 and a[i-1] != 0: ok = False; break
            if i < 9 and a[i+1] != 0: ok = False; break
    if ok:
        count[ones] += 1
        if ones not in examples:
            examples[ones] = a

print("count with 4 ones (2 twos, 4 zeros):", count[4], "e.g.", examples[4])
print("count with 6 ones (1 two, 3 zeros):", count[6], "e.g.", examples[6])
print("total:", count[4] + count[6])

전수 조사 결과 4-1개 경우 150, 6-1개 경우 112, 총 262가 나왔습니다. 이제 조합 공식으로 두 경우를 각각 교차 검증하겠습니다.

Recorded Python call:

from math import comb
from itertools import combinations

# Case A: 2 twos (T), 4 ones (O), 4 zeros (Z). T's neighbors must be Z.
# T at positions i<j (j>=i+2). Forced Z set R. Free positions get O's/Z's: choose 4 O's.
total_A = 0
for i, j in combinations(range(1, 11), 2):
    if j - i < 2:  # T's adjacent -> violates condition
        continue
    R = set()
    if i > 1: R.add(i - 1)
    R.add(i + 1)
    R.add(j - 1)
    if j < 10: R.add(j + 1)
    r = len(R)
    if r <= 4:
        total_A += comb(10 - 2 - r, 4)
print("formula case A (4 ones, 2 twos):", total_A)

# Case B: 1 two (T), 6 ones (O), 3 zeros (Z).
total_B = 0
for i in range(1, 11):
    R = set()
    if i > 1: R.add(i - 1)
    if i < 10: R.add(i + 1)
    r = len(R)
    if r <= 3:
        total_B += comb(10 - 2 - r, 6)
print("formula case B (6 ones, 1 two):", total_B)

print("total:", total_A + total_B)

# sanity: re-run brute force independently as a check
cnt = 0
for a in product(range(3), repeat=10):
    if sum(a) != 8 or a.count(1) not in (4, 6):
        continue
    if all((a[k-1] == 0 if k > 0 else True) and (a[k+1] == 0 if k < 9 else True)
           for k, v in enumerate(a) if v == 2):
        cnt += 1
print("brute force total:", cnt)

사례 B 공식에 버그가 있습니다: 사례 B에는 1개의 T가 있는데 제가 자유 슬롯을 10 - 2 - r로 사용했으므로, 10 - (#T) - r이 되어야 합니다. 확인해 보겠습니다.

Recorded Python call:

from math import comb

# Case B corrected: 1 two (T), 6 ones (O), 3 zeros (Z).
# T at i; forced Z at each existing neighbor; free slots = 10 - 1 - r, choose 6 for O's.
total_B = 0
detail = []
for i in range(1, 11):
    R = set()
    if i > 1: R.add(i - 1)
    if i < 10: R.add(i + 1)
    r = len(R)
    free = 10 - 1 - r
    c = comb(free, 6)
    detail.append((i, r, free, c))
    total_B += c
print("per-position (T pos, forced Z count, free slots, count):")
print(detail)
print("formula case B (6 ones, 1 two):", total_B)

# Case A unchanged (2 T's -> free = 10 - 2 - r)
total_A = 0
for i, j in __import__('itertools').combinations(range(1, 11), 2):
    if j - i < 2: continue
    R = set()
    if i > 1: R.add(i - 1)
    R.add(i + 1)
    R.add(j - 1)
    if j < 10: R.add(j + 1)
    r = len(R)
    if r <= 4:
        total_A += comb(10 - 2 - r, 4)
print("formula case A (4 ones, 2 twos):", total_A)
print("total:", total_A + total_B)

수식 계산 결과 이제 두 경우 모두 전수 조사와 일치합니다 (사례 A: 150, 사례 B: 112). 알고리즘을 완전히 다르게 사용한 세 번째 독립 검증으로, 위치 기반 동적 계획법(DP)을 적용해 보겠습니다:

Recorded Python call:

from functools import lru_cache

# DP over positions 1..10, tracking last bag's content, #ones used, #twos used.
# Constraint: a bag with 2 balls forces its neighbors to be 0 (checked locally via 'last').
@lru_cache(maxsize=None)
def dp(pos, last, ones, twos):
    # last = content of bag pos-1 (0 initially); but we need lookahead for T's,
    # so instead we enforce: placing value v at pos is blocked if last == 2 and v != 0.
    if pos == 11:
        return 1 if ones == 0 and twos == 0 else 0
    total = 0
    for v in range(3):
        if last == 2 and v != 0:   # neighbor of a 2-bag must be empty
            continue
        if v == 1 and ones == 0: continue
        if v == 2 and twos == 0: continue
        total += dp(pos + 1, v, ones - (v == 1), twos - (v == 2))
    return total

caseA = dp(1, 0, 4, 2)   # 4 ones, 2 twos, 4 zeros
caseB = dp(1, 0, 6, 1)   # 6 ones, 1 two, 3 zeros
print("DP case A:", caseA)
print("DP case B:", caseB)
print("DP total:", caseA + caseB)

DP가 다른 값을 냅니다 (700/336 대 150/112). DP에 결함이 있습니다: 마지막 주머니에 공이 1개 있을 때 2를 놓는 것을 허용하는데, 이는 조건 (나)를 위반하는 것입니다 — 2가 들어 있는 주머니의 양쪽 이웃 주머니는 비어 있어야 합니다. 두 가지 국소 조건이 모두 필요합니다: last==2 → v==0 그리고 v==2 → last==0. 수정해서 다시 실행해 보겠습니다:

Recorded Python call:

from functools import lru_cache

@lru_cache(maxsize=None)
def dp(pos, last, ones, twos):
    if pos == 11:
        return 1 if ones == 0 and twos == 0 else 0
    total = 0
    for v in range(3):
        if last == 2 and v != 0:   # right neighbor of a 2-bag must be empty
            continue
        if v == 2 and last != 0:   # left neighbor of a new 2-bag must be empty
            continue
        if v == 1 and ones == 0: continue
        if v == 2 and twos == 0: continue
        total += dp(pos + 1, v, ones - (v == 1), twos - (v == 2))
    return total

caseA = dp(1, 0, 4, 2)
caseB = dp(1, 0, 6, 1)
print("fixed DP case A:", caseA)
print("fixed DP case B:", caseB)
print("fixed DP total:", caseA + caseB)

Recorded Python call:

from itertools import product
from functools import lru_cache
valid=[a for a in product(range(3),repeat=4) if a.count(1)==1 and a.count(2)==1 and all((i==0 or a[i-1]==0) and (i==3 or a[i+1]==0) for i,v in enumerate(a) if v==2)]
@lru_cache(None)
def dp(n,last,ones,twos):
    if n==0: return int(ones==0 and twos==0)
    total=0
    for v in range(3):
        if (last==2 and v!=0) or (v==2 and last!=0): continue
        if ones<(v==1) or twos<(v==2): continue
        total+=dp(n-1,v,ones-(v==1),twos-(v==2))
    return total
print('Small case valid sequences:',valid)
print('Small case enumeration and corrected DP:',len(valid),dp(4,0,1,1))
print('Original cases:',dp(10,0,4,2),dp(10,0,6,1))

풀이 정리

공의 개수 조건으로 각 경우가 완전히 결정됩니다:

• 경우 A: 1개 주머니 4개 → $4 + 2k = 8 \Rightarrow$ 2개 주머니 2개, 0개 주머니 4개
• 경우 B: 1개 주머니 6개 → $6 + 2k = 8 \Rightarrow$ 2개 주머니 1개, 0개 주머니 3개

경우 A (2가 2개, 1이 4개, 0이 4개): 2가 놓인 두 위치의 (존재하는) 이웃은 모두 0으로 강제됩니다. 위치쌍 $(i,j)$ ($j \ge i+2$)에 대해 강제된 0의 개수 $r$을 세면, 남은 $10-2-r$칸 중 4칸에 1을 배치합니다. 합계 150.

경우 B (2가 1개, 1이 6개, 0이 3개): 위치 $i$가 양 끝이면 강제 0이 1개(자유 8칸), 그 외는 2개(자유 7칸):

독립 검증: (i) 3진 전수조사(product(range(3), repeat=10))에서 150 + 112 = 262; (ii) 위치 기반 DP에서도 국소 조건 last==2 → v==0 과 v==2 → last==0를 모두 적용했을 때 150, 112, 합 262로 일치했습니다. 처음 DP 실행(700/336)은 두 번째 국소 조건이 빠진 잘못된 구현이었고, 소규모 케이스(주머니 4개, 2가 1개·1이 1개)에서 올바른 규칙이 열거 결과 6개와 일치함을 확인한 뒤 수정했습니다.

세 방법(전수조사, 조합 공식, 수정된 DP)이 모두 262로 일치하며, 검증상 남은 공백은 없습니다.

$\boxed{262}$