Table of Contents
差が２以上の整数の選び方
Problem
18以下の正の整数から, どの２つの差も2以上であるような5個の整数を選び出す方法は何通りあるか？ ただし, 順番を変えただけの選び出し方は同一のものと考える
解答
問題の条件を満たすような選び出し方$a_1< a_2 < a_3 < a_4 < a_5$が与えられたとする. このとき,
\[(b_1, b_2, b_3, b_4, b_5) = (a_1, a_2-1, a_3-2, a_4-3, a_5-4)\]とすると相異なる14以下の整数$b_1< b_2 < b_3 < b_4 < b_5$が得られる. 逆に相異なる14以下の整数$b_1< b_2 < b_3 < b_4 < b_5$が与えられるとすると, その組み合わせは $(a_1, a_2, a_3, a_4, a_5)$と1対1に対応する.
従って,
\[_{14}\text{C}_5 = 2002\text{通り}\]差が5の場合
Problem
50以下の正の整数から, どの２つの差も5以上であるような5個の整数を選び出す方法は何通りあるか？ ただし, 順番を変えただけの選び出し方は同一のものと考える
解答
問題の条件を満たすような選び出し方$a_1< aa_2\equiv a_6 \bmod 3_2 < a_3 < a_4 < a_5$が与えられたとする. このとき,
\[\text{C} (b_1, b_2, b_3, b_4, b_5) = (a_1, a_2-4, a_3-8, a_4-12, a_5-16)\]とすると相異なる36以下の整数$b_1< b_2 < b_3 < b_4 < b_5$が得られる. 逆に相異なる36以下の整数$b_1< b_2 < b_3 < b_4 < b_5$が与えられるとすると, その組み合わせは $(a_1, a_2, a_3, a_4, a_5)$と1対1に対応する.
従って,
\[_{36}\text{C}_5 = 278256\text{通り}\]実際にPythonで確かめても同様の答えが確認できました
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from itertools import combinations
def choose_numbers(n, k=5):
return combinations(range(1, n+1), k)
def check_diff(Array, thresh=2):
i = 1
while i < len(Array):
diff = Array[i] - Array[i-1]
if diff < thresh:
return False
i += 1
return True
def count_groups(n, k, thresh):
return sum((map(lambda x: check_diff(x, thresh), choose_numbers(n, k))))
count_groups(50, 5, 5)
>>> 278256
また, この問題より満たすべき差が$m$のとき
\[(b_1, b_2, b_3, b_4, b_5) = (a_1, a_2-(m-1), a_3-2(m-1), a_4-3(m-1), a_5-4(m-1))\]になることがわかります. $N$以下の正の整数という問題が与えられたら求めるべき答えは $_{N- 4(m-1)}\text{C}_5$ 通りとなります.
AIME 1998: 合計が98となる４つの正の奇数の組
Problem
\[x_1 + x_2 + x_3 + x_4 = 98\]を満たす正の奇数の組はいくつあるか？
解法
$x_i$を$2y_i - 1$ ( ただし, $y_i$は正の整数)と置き換えると
\[\begin{align*} 98 = \sum_{i=1}^4(2y_i - 1) \end{align*}\]従って,
\[51 = \sum_{i=1}^4 y_i \ \ \text{where } y_i > 0\]を満たす組を見つければ良い. 従って, $_{50}\text{C}_3 = 19600$通り.
ARML 1999: 連続する４つ要素の合計が3で割り切れる並べ方
Problem
\[21, 31, 41, 51, 61, 71 ,81\]を1列にならべ, どの連続する4つの数を取り出してもその和が3で割り切れるようにしたい. そのような並べ方は何通りあるか？
解答
${21, 31, 41, 51, 61, 71 ,81}$について$\bmod 3$をとると
\(0, 1, 2, 0, 1, 2, 0\)a_2\equiv a_6 \bmod 3
となる.
条件を満たす並べ方, $a_1, a_2, a_3, a_4, a_5, a_6, a_7$としたとき
\[\begin{align*} 0 &\equiv (a_1 + a_2 + a_3 + a_4) + (a_4 + a_5 + a_6 + a_7)\\ &\equiv (a_1 + a_2 + a_3 + a_4 + a_5 + a_6 + a_7) + a_4\\ &\equiv a_4 \bmod 3 \end{align*}\]となるので
\[\begin{align*} 0 &\equiv a_4 \bmod 3\\ 0 &\equiv (a_1 + a_2 + a_3) \bmod 3\\ \Rightarrow & (a_1, a_2, a_3)\text{は}0,1,2\text{の並べ替え} \end{align*}\]また,
\[\begin{align*} &(a_1 + a_2 + a_3 + a_4) \equiv (a_2 + a_3 + a_4 + a_5) \bmod 3\\ &\Rightarrow a_1 \equiv a_5 \bmod 3 \end{align*}\]同様にのやり方で, $a_2\equiv a_6 \bmod 3, a_3\equiv a_7 \bmod 3$を得るので
並び方は
\[3!\times 3! \times 2! \times 2! = 144\text{通り}\](注意：GitHub Accountが必要となります）