Table of Contents
AIME 1993
Problem
$S$ を$n$個の元からなる集合とする. $S$の２つの部分集合(同じでも良い)の組 $(A, B)$ であって, その和集合が
\[A \cup B = S\]となるような組はいくつ存在するか? ただし, 順番を変えただけのものは区別しないものとする.
例として, $S$の要素が6のとき$[{a, c}, {b, c, d, e, f}], [{b, c, d, e, f}, {a, c}]$は同一の組として扱う
解答
$A \cup B = S$ より $s \in S$について, 以下のいずれかが成立する
\[\begin{align*} (1)& \ \ s \in A \ \ \land \ \ s\notin B\\[3pt] (2)& \ \ s \in A \ \ \land \ \ s\in B\\[3pt] (3)& \ \ s \notin A \ \ \land \ \ s\in B\\[3pt] \end{align*}\]従って, 順番を変えただけのものも含めて $s\in S$を部分集合 $A, B$に割り当て方は $3^n$ 通り存在する. このうち, $A=B$となる場合(すべての要素が(2)パターンとなる場合)を除くと, ${A, B}$の組を２回ずつ数えていることになるので
\[\frac{3^n-1}{2} + 1\text{通り}\]が答えとなる.
AIME 1991改題
Problem
0より大きく1より小さい有理数であって既約分数で書いたときの分母と分子の積が100!となるようなものはいくつあるか？
解答
既約分数は互いに素. 100!を素因数分解すると
\[\{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97\}\]の25個である.
すべての素数が分子, 分母のいずれかに分類される. このままだと１より大きい分け方が発生してしまうが, 分子分母を入れ替えることで1より小さい既約分数となるペアが生成できることを考えると, 分子分母の区別のない組み合わせを数えれば良い = 重複して数えた分除去すれば良いので
\[2^{25} / 2 = 2^{24}\text{通り}\]が答えとなる.
Pythonでエラトステネスのふるいを実装して計算
なお100!を素因数分解するのは面倒なのでPythonでエラトステネスのふるいを実装して計算しました.
Sieve of Eratosthenes
\(\begin{align*} \textbf{Time Complexity: } O(n\log\log n) \end{align*}\)
\(\begin{align*} \textbf{Input: } n > 1 \textbf{ integer } \end{align*}\)
\(\begin{align*} \textbf{Output: }& A \textbf{ Array} \text{ - all prime numbers from 2 through n} \end{align*}\)
\(\begin{align*} \text{1.}\quad&\textbf{let } A \text{ be an}\textbf{ array of Boolean}\text{ values, indexed by}\textbf{ integers } 2\text{ to }n\\ \text{2.}\quad&\textbf{for } i = 2,3,\cdots, \text{ not exceeding } \sqrt{n} \textbf{ do}\\ \text{3.}\quad&\quad \textbf{if } A\text{[j]} \textbf{ is True}\\ \text{4.}\quad&\quad \quad \textbf{for } j = i^2, i^2+i,i^2+2i, \cdots, \text{not exceeding } n \textbf{ do}\\ \text{5.}\quad&\quad\quad\quad\textbf{set } A\text{[j]} := \textbf{ False}\\ \text{6.}\quad&\textbf{return }\text{ all i such that A[i] }\textbf{is True} \end{align*}\)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def Sieve_of_Eratosthenes(n):
if n < 2:
raise ValueError('n should be greater than 1')
idx = [True] * (n-1)
root = int(pow(n, 0.5)) + 1
for i in range(2, root):
if idx[i-2]:
j = i*i
while j <= n:
idx[j-2] = False
j += i
return [i+2 for i, j in enumerate(idx) if j]
2 ** (len(Sieve_of_Eratosthenes(100)) - 1)
>>> 16777216
(注意：GitHub Accountが必要となります）