ちらし寿司は何皿必要？

質問

ちらし寿司の具材として
マグロ、イカ、サーモン、タコ、イクラ、玉子、きゅうり
の7種類がある。
一皿のちらし寿司には4種類まで具材を乗せられる。
好物を2つ指定されたとき、それがどのような組み合わせであってもその両方が乗っているちらし寿司を用意しておきたい。
そのためには最低で何種類のちらし寿司を用意しておけばいいか？

方針
好物の組み合わせは21通り
一皿に含まれる具材の組み合わせは6通り
→最低で4皿あれば足りる？

1. マグロ、イカ、サーモン、タコ
2. マグロ、イクラ、玉子、きゅうり
3. イカ、イクラ、玉子、きゅうり
4. サーモン、イクラ、玉子、きゅうり
5. タコ、イクラ、玉子、きゅうり
→4皿では不可能？

本題
4皿で足りるか足りないかとその理由をお願いします。
また、「具材がn種類の時は何皿必要か」も可能であればよろしくお願いします。

回答No.2

staratras

次のように考えると、4皿では不可能で、最少でも5皿必要であることが分かります。
まず、（A,B,C,D,E,F,G)=(マグロ、イカ、サーモン、タコ、イクラ、玉子、きゅうり)とし、下の図の7角形の頂点とします。

ここで4種類の具材を皿に乗せるのは、「7角形の頂点のうちの4頂点を結んで四角形を作ること」に相当し、題意は「7角形の2頂点を結んでできる線分（7辺と14本の対角線）がすべてそのいずれかの辺または対角線に含まれるような四角形の数の最小値を求める」ことに帰着します。

ここで四角形ABCDと四角形AEFGを考えると、「A,B,C,D」どうしの組み合わせと「A,E,F,G」どうしの組み合わせはすべてカバーしています。また2つ合わせれば片方がAの組み合わせも網羅しています。含まれないのは、「片方が「B,C,D」でもう片方が「E,F,G」の組み合わせ」で3×3=9通りあります。

これを2つの四角形でカバーすることはできません。なぜならば、四角形の4頂点をどのようにとったとしても、この4角形の辺のうち2辺は「B.C,D」または「E,F,G」どうしを結ぶものなので、「片方が「B,C,D」でもう片方が「E,F,G」の組み合わせ」は最大でも4通りしかなく、仮に2つの四角形の辺と対角線に全く重複がなかったとしても4×2=8<9だからです。

では3つの四角形であれば可能か、実は可能です。たとえば四角形BCFGと四角形CDEF、それに四角形BDEGを作ればできます。

つまり「7角形の2頂点を結んでできる線分（7辺と14本の対角線）がすべてそのいずれかの辺または対角線に含まれるような4角形の数の最小値」は5です。皿は5皿必要です。

回答No.1

PROTECTHIM

まず、数学的観点から言うと足りない。

21通りで4で割りきれなく、5皿で具材を余らせてしまう。

次に料理人観点から言うとそんな具材の少ないちらし寿司はちらし寿司とは言えない。
せっかくちらし寿司を作るんなら奮発して具材を多くして作れ言う話しです( ^∀^)

補足

"4で割り切れなく"の4は何の4でしょうか？
・皿に乗せられる具材の数
・必要な皿の推測値
・どこからか湧いたマジックナンバー

皿に乗せられる具材の数として考えましたが、本当に4で割り切れないことが
4皿ではできないことの証明になるのでしょうか？
"せっかくちらし寿司を作るんなら奮発して具材を多くして作れ"
とのことなので具材に甘エビを追加し8種類で試します。

具材が8種類のとき好物の組み合わせは8C2の28通り。
一皿に含まれる具材の組み合わせは変わらず4C2の6通り。
よって 4 < 28/6 < 5 であるから少なくとも5皿は必要となる。

具体例を挙げて考えてみる。
1.マグロ、イカ、タコ、サーモン （6通りの好みをカバー）
2.イクラ、甘エビ、玉子、きゅうり（新たに6通りで計12通りの好みをカバー）
3.マグロ、イカ、玉子、きゅうり（新たに4通りで計16通りの好みをカバー）
4.タコ、サーモン、イクラ、甘エビ（新たに4通りで計20通りの好みをカバー）
残り1皿で8通りの組み合わせを乗せることはできない。

一般の場合では1皿目と2皿目で何種類の具材が重複するかで場合分けして考えていますが
今のところ乗せられなさそうです。（検証中）
28は4の倍数であるためその説明で正しいのであれば乗せられるはずですが...