質問: ちらし寿司は何皿必要? ちらし寿司の具材として マグロ、イカ、サーモン、タコ、イクラ、玉子、きゅうり の7種類がある。 一皿のちらし寿司には4種類まで具材を乗せられる。 好物を2つ指定されたとき、それがどのような組み合わせであってもその両方が乗っているちらし寿司を用意しておきたい。 そのためには最低で何種類のちらし寿司を用意しておけばいいか? 方針 好物の組み合わせは21通り 一皿に含まれる具材の組み合わせは6通り →最低で4皿あれば足りる? 1. マグロ、イカ、サーモン、タコ 2. マグロ、イクラ、玉子、きゅうり 3. イカ、イクラ、玉子、きゅうり 4. サーモン、イクラ、玉子、きゅうり 5. タコ、イクラ、玉子、きゅうり →4皿では不可能? 本題 4皿で足りるか足りないかとその理由をお願いします。 また、「具材がn種類の時は何皿必要か」も可能であればよろしくお願いします。
回答: 次のように考えると、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皿必要です。