競技数学解説

文献あり

競技数学典型/主客転倒

組み合わせ論,競技数学典型,主客転倒

5392

はじめに

皆さんこんにちは！今回は主客転倒というテクニックについて解説していきます。数学オリンピックや競技プログラミングなどに幅広く使えるテクニックですのでぜひ見ていってください。

注意の見出し

本記事に修正、加筆を加えた最新版もぜひご覧ください。

主客転倒とは？

突然ですが皆さんは下記の表の総和を数える時,列ごとに数えますか?それとも行ごとに数えますか?

列 \ 行	1	2	3	4	5
1	1	0	0	4	5
2	1	2	0	4	0
3	0	2	3	4	5
4	1	0	0	4	0
5	0	2	3	0	5
6	1	2	0	0	5
7	0	0	3	0	0

おそらく各行を足してからそれらの合計を出すよりも,各列を足してからそれらの合計を出す方がわかりやすいですよね.今回の表は行ごとに見るとなんの法則性もありませんが,列ごとに見ると「同じ数字が出てくる」という法則性があると言うところにあります.実は,今回扱う主客転倒も自分が数えやすように工夫しようと言う考え方なのです.

主客転倒を一言で言うと,「視点を変えて楽に数え上げをしよう」ということです.もう少し具体的に言うと、「各事象がどれだけ合計に寄与、貢献しているかを考える」と言うことです.とは言ってもイメージが湧かないと思うのでとりあえず以下の例を見ていきましょう.

$(1, 2, \dots, n)$ の並べ替え $(a_{1}, a_{2}, \dots, a_{n})$ に対して"スコア"を「 $a_{i} = i$ なる $i$ の個数( $1 \leq i \leq n$ )」で定める.この時, $(a_{1}, a_{2}, \dots, a_{n})$ として有り得るもの全てについてそのスコアの総和を求めよ．

まずは具体例で実験です.

①

n = 3

の場合

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)

の

6

通りのスコアを計算することで

3 + 1 + 1 + 0 + 0 + 1 = 6

、すなわちスコアの総和は

6

であるとわかります.

①

n = 4

の場合

(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2)

(2, 1, 3, 4), (2, 1, 4, 3), (2, 3, 1, 4), (2, 3, 4, 1), (2, 4, 1, 3), (2, 4, 3, 1)

(3, 1, 2, 4), (3, 1, 4, 2), (3, 2, 1, 4), (3, 2, 4, 1), (3, 4, 1, 2), (3, 4, 2, 1)

(4, 1, 2, 3), (4, 1, 3, 2), (4, 2, 1, 3), (4, 2, 3, 1), (4, 3, 1, 2), (4, 3, 2, 1)

の

24

通りのスコアを計算することで

4 + 2 + 2 + 1 + 1 + 2 + 2 + 0 + 1 + 0 + 0 + 1 + 1 + 0 + 2 + 1 + 0 + 0 + 0 + 1 + 1 + 2 + 0 + 0 = 24

、すなわちスコアの総和は

24

であるとわかります.

一般式を立てて計算！といきたいところですが,残念ながら各並べ替えのスコアを一般式で表すのは難しそうです.そこで少し視点を変えて見てみましょう.

まずは手始めに「 $a_{1} = 1$ となるケースが何通り存在するか?」を考えてみましょう.

$a_{1} = 1$ となるケースを数えるには,単純に $a_{1} = 1$ を固定して残りの並べ替えを考えれば良いですね. $n - 1$ 個の数字を並べ替える方法なので $(n - 1)!$ 通り存在しますね.

例:

n = 4

の場合

1

を固定すると以下の

6

通りが考えられる.

(1, 2, 3, 4), (1, 2, 4, 3), (1, 3, 2, 4), (1, 3, 4, 2), (1, 4, 2, 3), (1, 4, 3, 2)

つまり, $a_{1} = 1$ が貢献する回数は $(n - 1)!$ となります.同様に他の文字についても考えると, $\underset{n 個}{\underset{⏟}{(n - 1)! + (n - 1)! + \dots + (n - 1)!}} = n!$ となるわけです.
よって求めるスコアの総和は $n!$ となるわけです.

このように「貢献」を考えることを主客転倒と言います.とても便利な考え方ですね!次の例題にて,応用的な問題も見てみましょう.

例題

$(1, 2, \dots, n)$ の並べ替え $(a_{1}, a_{2}, \dots, a_{n})$ に対して"スコア"を「 $a_{i} = i$ なる $i$ の個数( $1 \leq i \leq n$ )」で定める.この時, $(a_{1}, a_{2}, \dots, a_{n})$ として有り得るもの全てについてそのスコアの二乗の総和を求めよ．

困りましたね,スコアの二乗の総和です.以下に例を載せておきます.

①

n = 3

の場合

(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1)

の

6

通りのスコアを計算することで

3^{2} + 1^{2} + 1^{2} + 0 + 0 + 1^{2} = 12

、すなわちスコアの二乗の総和は

12

であるとわかります.

このような場合は以下のように言葉で書き換えてみると良いでしょう.

( $a_{i} = i$ なる $i$ の個数) $^{2}$
=( $a_{i} = i$ なる $i$ の個数) $\times$ ( $a_{i} = i$ なる $i$ の個数)
=( $a_{i} = i$ なる $i$ の個数) $\times$ ( $a_{j} = j$ なる $j$ の個数)

この変形はとても当たり前のことですが,実はとってもありがたいのです.その理由は以下のように簡単に計算できることにあります.(二つのケースに場合分けして計算)

①AA型

「 $a_{i} = a_{j} = i = j$ であるケース」について考えます.これは例1そのまんまですね. $n!$ 通りです.

②AB型

「 $a_{i} = i$ かつ $a_{j} = j$ であり $i \neq j$ なケース」について考えます.これは $a_{i}$ と $a_{j}$ の二つを固定して主客転倒をしてあげれば良いです. $_{n} C_{2} \cdot 2 \cdot (n - 2)! = n!$ 通りです.

よって,上記の二通りを足し合わせれば $2 \cdot n!$ 通りであるとわかります.

二乗を言葉に表現してあげることで,論理積へと分解することができました.とても有用なテクニックだと思います.それでは,基本的なことはわかったと思うので演習問題で慣れていきましょう!

演習問題

$(1, 2, \dots, n)$ の並び替え $(a_{1}, a_{2}, \dots, a_{n})$ に対して"スコア"を $a_{i} = i$ なる $i$ ( $1 \leq i \leq n$ )の総和で定める.このとき, $n!$ 通り全ての並べ替えの"スコア"の総和を求めよ.

スコアの例

(1, 2, 5, 3, 4, 6)

と言う並べ替えの場合"スコア"は

1 + 2 + 6 = 9

となります.

解答

解説冒頭の例1と同様に主客転倒して考えると

(n - 1)! \cdot (1 + 2 + 3 + \dots + n) = \frac{(n + 1)!}{2}

よりスコアの総和は

\frac{(n + 1)!}{2}

となります.

$n \geq 2$ とする. $(1, 2, \dots, n)$ の並び替え $(a_{1}, a_{2}, \dots, a_{n})$ に対して"スコア"を $a_{i} = i, a_{i + 1} = i + 1$ なる $i$ ( $1 \leq i \leq n$ )の個数で定める.(ただし, $n + 1 = 1$ とみなす.)このとき, $n!$ 通り全ての並べ替えの"スコア"の総和を求めよ.

スコアの例

(1, 2, 5, 3, 4, 6)

の並べ替えの場合"スコア"は

2

です.

解説

a_{k} = k, a_{k + 1} = k + 1

を固定したとき,残りの並べ替え方は

(n - 2)!

通りです.

k

の選び方は

n

通りであるから"スコア"の総和は

n \cdot (n - 2)!

となります.

$f (x)$ を $x$ の $200$ 以上の約数の個数とする.このとき以下の値を計算せよ.

f (1) + f (2) + \dots + f (1000)

解答

200

以上の整数が何回寄与するかを考えれば良いですね.例えば

200

は

f (200), f (400), \dots, f (1000)

の計

5

回数えられると言った具合です.

\sum_{n = 200}^{1000} ⌊ \frac{1000}{n} ⌋ = 5 \cdot 1 + 4 \cdot 50 + 3 \cdot 83 + 2 \cdot 167 + 1 \cdot 500 = 1228

$n \times n$ のマス目を白と黒の2色で塗り分ける.黒いマスと白いマスの両方に隣接している辺を"境界辺"と呼ぶ.このとき, $2^{n^{2}}$ 通り全ての塗り分けについて"境界辺"の個数の総和を求めよ.

解答

"境界辺"に関する主客転倒で考えるとわかりやすいです."境界辺"になり得る辺の個数は

2 n (n - 1)

.ある辺が"境界辺"となるような場合の数は

2 \cdot 2^{n^{2} - 2} = 2^{n^{2} - 1}

なので,

2^{n^{2}} \cdot n (n - 1)

個となります.

OMC030-C

$N$ 以下の順序付き正整数の組 $(a, b, c)$ 全てについて, $m a x (a, b, c)$ の総和を計算したものを $f (N)$ とおきます.このとき, $4 f (10^{2021})$ の各桁の総和を求めてください.

解答

OMCのリンクに飛びます.

OMC095-E

$272$ 項からなる数列 ${a_{i}}_{i = 1, 2, \dots, 272}$ の"スコア"を以下で定めます.

\sum_{i = 1}^{256} | a_{i} - a_{i + 16} |

1, 2, \dots, 272

を並び替えてできる整数列は

272!

通り考えられますが,それらのスコアの平均値を求めてください.

解答

OMCのリンクに飛びます.

OMC072-F

$N$ を $99, 100, 101$ で割った余りのうち最小のものを $f (N)$ について,以下の総和を求めてください.

f (1) + f (2) + \dots + f (99 \times 100 \times 101)

解答

OMCのリンクに飛びます.

OMC120-D

$1, 2, \dots, 1000$ の置換 $a_{1}, a_{2}, \dots, a_{1000}$ について, $a_{i} < a_{i + 1}$ を満たす正整数 $i$ の個数を $N$ とします. $1000!$ 通りある全ての置換に対して $N^{2}$ の(相加)平均 $M$ を求めてください.

解答

OMCのリンクに飛びます.

JMO2017-9

$1, 2, \dots, 2017$ の並べ替え $σ = (σ (1), σ (2), \dots, σ (2017))$ について, $σ (i) = i$ となる $1 \leq i \leq 2017$ の個数を $F (σ)$ とする.全ての並べ替え $σ$ について $F (σ)^{4}$ を足し合わせた値を求めよ.