３人対戦ゲームの試合数・対戦表 ／ 組み合わせ（数え上げ）問題を線形計画問題ソルバ GLPK を使って解く
2021/07/29 19:01
・３人で行うゲームがある数え上げ問題なのですが、この問題を整数計画問題として（もともと数え上げ問題だったものを整数計画問題に「擬態」して、それ用のソルバで解けるようにして） GLPK (Gnu Linear Programming Kit) を使って解いてみたので、これで正解なのか自信がありませんが（なんだか A+ の成績はいただけたけど、正解したとは限らないし・・・、コロナ禍のもと対面授業ではなかったので質問の機会がなかったのです）、私なりの解答を披露したいと思います。
・９人が参加する
・各プレイヤーは４回だけプレイできて、さらに他のすべてのプレイヤーとちょうど１回ずつプレイする
・このような条件をみたすゲームの個数（＝試合数）は何通りあるか、対戦表は作れるか
＃Yahoo!知恵袋 でも、同じ問題の答えを聞いている人がいました（こちら や こちら）。
＃前者の回答例は、私の解答での m02,m12,m22,m23,m30,m46,m47,m51,m63,m66,m74,m76 パターンで、対戦表では No. 352 にあたります。
＃似てるけどちょっと違う出題に、数学の部屋『３人ゲームのリーグ戦』の「問題１」があります。
途中、GLPK を何百回も繰り返して実行する箇所がありますので、そういうところは perl スクリプトで自動実行しています。
答案
まず、９人に１，２，３，・・・，９と番号を付ける。９人のうち３人でゲームをするから、その組み合わせは {}_9 \mathrm{C}_3 で、８４通りある。
この組み合わせにも番号を付け、それぞれ m01, m02, ..., m84 と表す。
一覧は次の通り。