![[logo]](https://img.hyuki.net/20220628121544-7a397ed015277339.png)
Web連載「数学ガールの秘密ノート」
登場人物紹介
僕：数学が好きな高校生。
テトラちゃん：僕の後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。
ミルカさん：数学が好きな高校生。 僕のクラスメート。長い黒髪の《饒舌才媛》。
いまは放課後。ここは高校の図書室。
僕と後輩のテトラちゃんは、クラスメートのミルカさんといっしょに村木先生から渡された問題を解いていた。
一つ目と二つ目の封筒に入っていた問題をようやく解いたところ。（第294回参照）
ミルカ「さあ、じゃあ、そろそろ封筒を開けてもいいかな」
テトラ「え……？ もう開けましたが？」
僕「まさか……」
ミルカ「どうやらそのまさからしい」
ミルカさんは新しい封筒を取り出してひらひらさせる。
ミルカ「村木先生から封筒をもらってきた。 テトラに渡した封筒が二つとも開けられたら、 この封筒を開けるようにとのことだ。 村木先生はいつもの通り……」
僕「演出過剰！」
テトラ「ですね！」
僕とテトラちゃんとミルカさんは封筒を開ける。
中にはもちろん《カード》が入っていた。でも一枚じゃない。
《機材について》（カード1）
あなたは、二つの《施設》で《機材》を管理するスタッフである。
施設 $A$ には $m$ 台の機材 $a_1,a_2,a_3,\ldots,a_m$ がある。
施設 $B$ にも $m$ 台の機材 $b_1,b_2,b_3,\ldots,b_m$ がある。
機材には $1,2,3,\ldots,m$ の《型番》が付いていて、 同じ型番は同種類の機材を表している。 たとえば機材 $a_1$ と機材 $b_1$ は型番 $1$ の同種類の機材である。
僕「二つの施設と、 $m$ 台の機材……」
ミルカ「$m$ 台ずつだから、合計で $2m$ 台の機材だな」
テトラ「施設って何でしょう。機材とは？ ……気になります」
僕「よくわからないけど、これらの機材を僕たちが管理する……という設定なんだね」
テトラ「これまでの封筒が《過去》と《未来》でしたから、これは《現在》かもしれませんね」
ミルカ「《機材について》はこれだけだ。次の《カード》を読もう」
《ユーザと予約と割り当てについて》（カード2）
機材を利用する $n$ 人のユーザ $u_1,u_2,u_3,\ldots,u_n$ がいる。
※イラストは「いらすとや」さんから
ユーザは、それぞれ $1$ 台以上の機材を利用する。
利用するために各ユーザは、機材の番号を使って《予約》を行う。
たとえば、あるユーザが $1$ 番の機材一つに対して予約を行ったとするなら、この予約を $\SET{1}$ で表す。
$1$ 番の予約をしたユーザへ機材の《割り当て》を行う際には、 施設 $A$ と $B$ のどちらの機材を割り当ててもいい。
ただし、一人のユーザに割り当てるのはすべて同じ施設の機材でなければならない。
たとえば、ユーザが $1$ 番と $4$ 番の二つの機材に対して予約 $\SET{1,4}$ を行った場合、 そのユーザへの割り当ては、
のいずれかである。 二つの施設の機材が混じった $\SET{a_1,b_4}$ は割り当てではない。
僕「お、なるほど。パズルっぽくなってきたね」
テトラ「どうぶつユーザ、かわいいですねっ！ 機材を扱うどうぶつたち……」
ミルカ「予約は $\SET{1,4}$ のように型番の集合で表し、割り当ては $\SET{a_1,a_2}$ のように機材の集合で表すわけだな」
テトラ「機材を直接予約するのではなく、型番で予約するんですね」
僕「どちらの施設の機材が割り当てられてもかまわないという意味なんだね、きっと」
テトラ「どういうことでしょう」
僕「このカード2にある通りだよ。予約 $\SET{1,4}$ を行ったユーザが実際に使うのは施設 $A$ の $\SET{a_1,a_4}$ かもしれないし、 施設 $B$ の $\SET{b_1,b_4}$ かもしれない。 どちらの施設の機材でも、型番が同じだからいいでしょうという意味」
テトラ「ははあ……でも、これで何が起きるんでしょう」
僕「その前に、カード2に書かれている《制約》に注意しないとね。 さらっと読んだだけだと見逃すかも」
テトラ「制約というのは、これのことですね。《個人割当同一施設制約条件》ですっ！」
僕「長い名前付けるのブームなの、テトラちゃん……《同一施設制約》くらいにしようよ」
テトラ「ですよね……と、ともかく割り当てるときには $\SET{a_1,a_4}$ のように同じ施設の機材をまとめないといけないというのはわかりました。 そういう制約があるんですね」
ミルカ「カード3にはもう一つ制約が出てくるようだ」
《割り当ての衝突について》（カード3）
予約にしたがって機材の割り当てを行った結果、 複数の割り当てに同一機材が属してしまうことがある。 これを割り当ての《衝突》と呼ぶことにする。
たとえば、 $\SET{a_1,a_2,a_3}$ と $\SET{a_3,a_4,a_5}$ は衝突している（$a_3$ が両方に属している）。
また、 $\SET{b_1,b_3,b_5}$ と $\SET{b_2,b_4}$ は衝突していない。
$\SET{a_1,a_2,a_3}$ と $\SET{b_1,b_2}$ も衝突していない。
衝突が起きないように機材の割り当てを行うことが可能ならば、その予約の集まりを《割り当て可能》と呼ぶことにする。
また、どのように割り当てを行っても衝突が避けられないならば、その予約の集まりを、《割り当て不可能》と呼ぶことにする。
テトラ「なるほどです。同じ機材を二人に割り当てちゃまずいということですね」
僕「こちらは《衝突禁止制約》かな」
ミルカ「やっと問題が出てきた」
《問題》（カード4）
管理スタッフであるあなたの前には、予約が集まっている。
この予約の集まりに対して、
このための手順を考案せよ。
テトラ「えっ……！？」
僕「どうしたのテトラちゃん」
テトラ「これが問題なんですか？」
ミルカ「村木先生の《カード》にしては珍しいな。問題の形になっている」
テトラ「あ、あたしは……何か具体的な予約が与えられて、 それに対する割り当てを行ってくださいという問題が出てくると思ったんです。 《同一施設制約》と《衝突禁止制約》に注意しながら、根気よく割り当てていこう……と構えていたんですが」
僕「なるほどね。今回の《カード》の問題は、具体的な割り当てを見つけるのじゃなく、 割り当てを見つけるための手順を考えよというんだ」
ミルカ「割り当てが可能ならば、だな。割り当てが不可能ならば、不可能であることを示す」
テトラ「手順を考案する問題……」
僕とテトラちゃんとミルカさんは口を閉じて考える。
だいぶ複雑な設定で与えられた問題がある。 でも、どんな問題だとしても、最初にやることは決まっている。まず……
無料で「試し読み」できるのはここまでです。 この続きをお読みになるには「読み放題プラン」へのご参加が必要です。
ひと月500円で「読み放題プラン」へご参加いただきますと、 420本すべての記事が読み放題になりますので、 ぜひ、ご参加ください。
参加済みの方／すぐに参加したい方はこちら
結城浩のメンバーシップで参加 結城浩のpixivFANBOXで参加（2020年7月3日）
![[icon]](https://img.hyuki.net/20220619121014-abd58cfc2ab436f4.png)