3人対戦ゲームの試合数・対戦表 / 組み合わせ問題を線形計画問題ソルバ GLPK を使って解く

2021/05/31 7:46 整数計画問題
数学(大学の教養科目)でこんな問題がありました。
・3人で行うゲームがある
・9人が参加する
・各プレイヤーは4回だけプレイできて、さらに他のすべてのプレイヤーとちょうど1回ずつプレイする
・このような条件をみたすゲームの個数(=試合数)は何通りあるか、対戦表は作れるか
この問題を整数計画問題として(整数計画問題に「擬態」して、それ用のソルバで解けるようにして) GLPK (Gnu Linear Programming Kit) を使って解いてみたので、これで正解なのか自信がありませんが(なんだか A+ の成績はいただけたけど、正解したとは限らないし・・・、コロナ禍のもと対面授業ではなかったので質問の機会がなかったのです)、私なりの解答を披露したいと思います。

#Yahoo!知恵袋 でも、同じ問題の答えを聞いている人がいました(こちらこちら)。
#前者の回答例は、私の解答での m02,m12,m22,m23,m30,m46,m47,m51,m63,m66,m74,m76 パターンで、対戦表では No. 352 にあたります。
#似てるけどちょっと違う出題に、数学の部屋『3人ゲームのリーグ戦』の「問題1」があります。

途中、GLPK を何百回も繰り返して実行する箇所がありますので、そういうところは perl スクリプトで自動実行しています。

答案

まず、9人に1,2,3,・・・,9と番号を付ける。
9人のうち3人でゲームをするから、その組み合わせは {}_9 \mathrm{C}_3 で、84通りある。
この組み合わせにも番号を付け、それぞれ m01, m02, ..., m84 と表す。
一覧は次の通り。

続きを読む

2020/04/05(日)切手組み合わせ問題を整数計画問題として解く

計算できるサイトを作りました→ http://xrea.satomichan.jp/stamp_problem/

例えば 1,405円分(定形外1kg以内の一般書留・速達郵便)の切手の組み合わせを考えると、1円切手、84円切手、320円切手がそれぞれ1枚に500円切手が2枚の計5枚だと、最低の枚数で済むんですね。暗算で出来る、500 + 500 + 100 + 100 + 100 + 100 + 5 だと7枚だから、2枚減らせました。普通は窓口で印紙を貼ってもらうか・・・。

それから逆に最小枚数にこだわらない場合、210円切手(定形外150g以内に相当)は常備しなければいけないものでもなさそうです。63 + 63 + 84 = 210 でも代用できます。

Wikipedia日本語版「整数計画問題」: https://ja.wikipedia.org/wiki/%E6%95%B4%E6%95%B0%E8%A8%88%E7%94%BB%E5%95%8F%E9%A1%8C
Wikipedia日本語版「切手問題」:https://ja.wikipedia.org/wiki/%E5%88%87%E6%89%8B%E5%95%8F%E9%A1%8C

#かつて205円切手があった頃は面白かったなー。ちょっと重い(150g)定形外用として常備していたし、2枚合わせて410円にして(特定記録+250gだっけかな?)使っていました。