ムゲンの実の数学 #1 有限ムゲンの実問題

見切れている数式はスクロールで！

先日バイト中にあるお菓子を見つけました．

その名もムゲンの実．

f:id:dafuyafu:20200223021710j:plain — ムゲンの実

クラシエフーズ株式会社が出してるお菓子です．

無限プリン，無限きゅうり，無限ピーマン...と，やたらと無限のつく食べ物が多いのがとても気になります．そういうものは得てして高々有限です．本当に呆れ返るばかりです．

このムゲンの実もどうせ有限だろうな…と思っていたのですが，どうやら上記の無限偽装有限食品とは異なるようです．というのは，ムゲンの実の何が無限なのかというと，3つの実の組み合わせが無限通りあるということらしいのです．

どういうことかというと，パッケージに書いてあるとおり，このお菓子はヒエヒエの実，シャリシャリの実およびシュワシュワの実の3種類の実からなります．

ヒエヒエの実 (青)
シャリシャリの実 (赤)
シュワシュワの実 (黄)

これらの3つの中からいくつか実を選んで同時に食べると，無限の味を作り出せるということらしいです．

例 1.1

ヒエヒエ + シャリシャリ = かき氷味
シャリシャリ + シュワシュワ = コーラフロート味
シュワシュワ + シャリシャリ × 2 = グレープソーダ味

これは確かに，3個の実を重複を許して $n$ 個 (ただし $n \geq 1$ ) 取る組み合わせと考えると，実が無限個あって， $n \to \infty$ とすると無限通りの組み合わせとなります．よって数学的にもムゲンの実は無限です．

有限ムゲンの実問題

ムゲンの実を使って組合せ最適化問題を考えてみたいと思います．以下ではムゲンの実は高々有限個あるものとします．

f:id:dafuyafu:20200223023140j:plain — ムゲンの実の中身

僕の買ったムゲンの実は

シャリシャリの実 (赤) : 17個
シュワシュワの実 (黄) : 14個
ヒエヒエの実 (青) : 14個

それぞれ入っていました．実際，パッケージ裏面の注意書きには

3種の混合には配慮していますが，ばらつきが生じる場合があります．

と書かれています．

若干のばらつきを是正し，それぞれ15個ずつ，合計で45個入っているものを有限ムゲンの実モデル (Finite Infinite Berry Model)と定義します．さらに，それらが $n$ 個ある場合，これを $n$ ムゲンの実モデル ( $n$ -Infinity Berry Model ) と定義します．

ここで，

$\mathbb{P} = \{ (a,b,c) \ \mid\ a,b,c \in \mathbb{Z}_{\geq 0}, (a,b,c) \neq (0,0,0)\} / \sim$

ただし，

$(a,b,c) \sim (a', b', c') \Leftrightarrow (\lambda a, \lambda b, \lambda c) = (a', b', c')$ for some $\lambda \in \mathbb{Z}_{>0}$

と定めます．このようにして得られる $\mathbb{P}$ の要素を $[a:b:c]$ と表します．

これは単に，シャリシャリ(赤)を1つ，シュワシュワ(黄)を1つ，ヒエヒエ(青)を1つ食べる組み合わせを $[ 1:1:1]$ と表そうという意味です．さらに，もし(赤)を2つ，(黄)を2つ，(青)を2つ食べる場合，それは先述の $[1:1:1]$ を2つ食べているのと同じになるので，こういうのはすべて同じものだと思おうということを定式化しているに過ぎません．

f:id:dafuyafu:20200223030643j:plain — [1:1:1] ~ [2:2:2]

数学的に言うと， $\mathbb{P}$ という集合の中では $[1:1:1]$ と $[2:2:2]$ は同じ元だということです．また，何も食べないという組み合わせ $[ 0:0:0]$ は考察の範囲から逸れるため，これを除外します．

さて，非負整数の性質より，同値類の中で最も最小なものを取ることができます．実際 $[a:b:c]$ に対して最大公約数 $\mathrm{GCD}(a,b,c)$ を取ってそれらをGCDで割ると，既約な最小の組み合わせをwell-definedに取ることができます．

例 1.2

$[ 12 : 18 : 24] = [ 6 \cdot 2: 6\cdot 3: 6\cdot 4] \sim [2:3:4]$ ( $\because \mathrm{GCD}(12,18,24) = 6)$

このような組み合わせは任意の $\mathbb{P}$ の元に対して唯一に，かつwell-definedに(代表元のとり方によらず)定まります．これを同値類の最小元と定義し， $P = [a:b:c] \in \mathbb{P}$ に対して $P$ の最小元を $m(P) = (m_a, m_b, m_c)$ と表します．

ここで， $\mathbb{P}$ の有限部分集合 $V \subset \mathbb{P}$ が以下の条件を満たすとき， $V$ を $n$ 正則部分集合 ( $n$ -subset ) と言います: $V = \{ P_i = [a_i: b_i:c_i]\}$ と表したとき，

$\sum m_{a_i} \leq 15 n$ ，
$\sum m_{b_i} \leq 15 n$ ，
$\sum m_{c_i} \leq 15 n$ ．

例1.3 (赤)を10個，(黄)を1個食べる組み合わせ $[16:1:0]$ と (赤)を6個，(青)を5個食べる組み合わせ $[6: 0: 5]$ からなる集合 $V$ は 1正則ではありません．

$V = \{[16:1:0], [6:0:5]\}$ : 1正則でない．

なぜならば，(赤)の総数を見ると $16 + 6 = 22 > 15$ となり，これらの組み合わせは1袋ではまかないきれません．しかし，2袋あれば事足ります．つまり $V$ は2正則です．実際，2以上の整数 $k$ に対して $V$ は $k$ 正則です．

このように，正則という概念はその組み合わせは $n$ 袋で食べることができるか？を考えるためのものです．

さて， $n$ 正則部分集合全体の集合を $\mathrm{Reg}(n)$ と表します． $\mathrm{Reg}(n)$ のなかで，集合の位数すなわち元の個数が最大であるものが存在し，その位数を $S_n$ と表します．

問題 $n$ -IBMにおける $S_n$ を求めよ．

簡単な例

$1$ -IBM を考えます．なにはともあれ，平均的に食べていったほうが組み合わせは多くなりそうな気がするので，そういう食べ方を考えます．

まず，1個ずつ食べる組み合わせが3つあります．

赤だけ食べる． $[1:0:0]$
黄だけ食べる． $[0:1:0]$
青だけ食べる． $[0:0:1]$

さらに，2個食べる組み合わせも $\binom{3}{2}$ 個．

赤 + 黄　 $[1:1:0]$
赤 + 青　 $[1:0:1]$
黄 + 青　 $[0:1:1]$

ここで，赤だけを2つ食べたり，黄だけを2つ食べたりする組み合わせは上記の1個ずつ食べる組み合わせで計上しているものと考えられるので，これらは除外されます（数式的には $[2:0:0] \sim [1:0:0]$ となっていることに注意）．

3個ずつ食べる組み合わせは少し複雑で，重複を許して3個食べる組み合わせが7通りあります．

赤 + 赤 + 黄　 $[2:1:0]$
赤 + 赤 + 青　 $[2:0:1]$
赤 + 黄 + 黄　 $[1:2:0]$
赤 + 黄 + 青　 $[1:1:1]$
赤 + 青 + 青　 $[1:0:2]$
黄 + 黄 + 青　 $[0:2:1]$
黄 + 青 + 青　 $[0:1:2]$

これは重複組合せ $_{3} \mathrm{H}_3 = 10$ の中で除外されるべき3通り(赤+赤+赤など)を除いた7通りであると考えれば分かりやすいかと思います．

ここまでで，赤黄青それぞれ10個ずつ消費しました．残り5個ずつを使って最も多く組み合わせを作ることが目標となります．順当に行くと次は4つずつ食べる組み合わせを考えることになります．実際これは9通りあります．

赤 + 赤 + 赤 + 黄　 $[3:1:0]$
赤 + 赤 + 赤 + 青　 $[3:0:1]$
赤 + 赤 + 黄 + 青　 $[2:1:1]$
赤 + 黄 + 黄 + 黄　 $[1:3:0]$
赤 + 黄 + 黄 + 青　 $[1:2:1]$
赤 + 黄 + 青 + 青　 $[1:1:2]$
赤 + 青 + 青 + 青　 $[1:0:3]$
黄 + 黄 + 黄 + 青　 $[0:3:1]$
黄 + 青 + 青 + 青　 $[0:1:3]$

この中から，うまく実を5個ずつだけ使って組み合わせを多く取らなければなりません．つまり， $[3:1:0]$ のような組み合わせは優先的に取るべきではないということです．

しかしながら，やってみるとわかるのですが，どのように取ろうとしてもこの中から3つしか取れません．例えば，

$[2:1:1],\ [1:2:1],\ [1:1:2]$
$[0:3:1],\ [3:0:1],\ [1:0:3]$
$[2:1:1],\ [0:1:3],\ [1:2:1]$

といった具合です．どのように取ってもかならず3つ実が残ってしまいます．

ここまで考えると，組み合わせの総数は

$3 + 3 + 7 + 3 = 16$

となっています．

問題1. $S_1 = 16$ を示せ．

気が向いたらやってみてください．

考えられる別問題としては

$S_n$ を取る組み合わせでは実がいくつ余るか？
1つも実を余らせないで $S_n$ を取ることができる $n$ は存在するか？
よりモデルを一般化し実の種類を $m$ としたとき， $S_{m,n}$ はどうなるか？
一つの実を複数食べる場合なども計上するように単純化すると $S_n$ はどうなるか？(チーズバーガーを2個食べるのと，ダブルチーズバーガーを1個食べるときの味は等価か？)