RSS Feed

규칙에 위배되는 예비 특수합 집합의 수

Problem 106

출제 일시 : 2013-02-20 11:56:13, ☕ 10

크기가 n인 집합 A의 원소들을 모두 더한 값을 S(A)라고 합시다. A의 공집합이 아닌 서로소 집합 B, C가 아래 두 가지 조건을 만족하면 '특수합 집합'이라고 부르기로 합니다.

  1. S(B) ≠ S(C)
  2. B가 가진 원소의 개수가 C보다 많을 때 S(B) > S(C)

이 문제에서는 원소가 오름차순으로 정렬되어 있고, 두 번째 조건은 이미 만족한 집합만을 고려해 보겠습니다(편의상 이를 '예비 특수합 집합'이라고 부르겠습니다).

놀랍게도, n=4일 때 찾을 수 있는 25개의 예비 특수합 집합 중, 단 1개만이 첫번째 규칙에 위배됩니다. n=7인 966개 예비 특수합 집합 중에서는 70개밖에 안 됩니다.

n=12개일 때는 총 261625개의 예비 특수합 집합이 있습니다. 이 중 몇 개가 첫번째 규칙에 위배됩니까?

주) 본 문제는 103번, 105번 문제와 연관되어 있습니다.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.