◆千葉県 たけ さんからの解答。
【問題１】
これは絶対解けたと思う。
なんてったって鍵の種類は２つでいいのだから
まず鍵を２種類用意します。
ｎ人にどちらか一方（○と×とします）の鍵を渡します。
ここでポイントなのは同じ鍵が２つあれば金庫があくようにします。Ａさん○○○×××
Ｂさん×○○×○○
Ｃさん××○×○○
これをみると３人がそろえば絶対開くわけです。
２人のときは問題にもあったように開くとき開かないときがあります。
◆愛知県 知多高弓道部 さんからの解答。
電気回路として考えたらだめでしょうか。
ｎ種の鍵を用意して、ｎ人に持たせます。
そして、任意の３個を取り出して直列に並べた回路を作りそのすべてを並列につなげます。
すると任意の３人が揃えば通電しますので金庫が開くと。
インチキかなこれは。
どうもこの鍵の問題は電気回路のような気がして頭から離れないので解答してみました。
でもこの解答だと巨大な回路が必要になりますね。
【コメント】
実務では、鍵をたくさん作ったり、鍵穴だらけの金庫を作っても仕方がないですから、当然、電気回路を作るでしょうね。
◆東京都 Asami さんからの解答。
とりあえず………
【問題１】
結論から言えば、
２k人のときｋ種類鍵があれば良くて
２k+１人のときｋ+１種類の鍵があれば良いです。
縦に人を並べ、横に鍵を並べた表を作ります。
わかりやすいようにｎ＝９を例にとります。
○はその人の持っている鍵を。□は持っていないことを表します。
『３人そろえば必ず開けられる』によって、各列には□が高々２個しか存在できないので、９人のとき４列しかなければ、ある行は○で埋まってしまいます。
これは『１人では開けられない』に反します。
そして５列あれば下のように埋めることができます。
どの行も○で埋まっていなく、３行とればどの列からも○をとることができるので、ＯＫです。
○○○○□
○○○○□
○○○□○
○○○□○
○○□○○
○○□○○
○□○○○
○□○○○
□○○○○
ガウス記号でまとめれば
| [ | ｎ+１ ２ | ] |
◆東京都 goya さんからの解答。
【問題２】
１８個の鍵を用意し、各自に表の通りに渡します。
横が人、縦が鍵で、○はその人の持っている鍵を。
□は持っていないことを表します。 ＡＢＣＤＥＦＧＨＩ
01□□○○○○□○○
02□○□○○○□○○
03□○○□○○□○○
04□○○○□○□○○
05□○○○○□□○○
06○□□○○○○□○
07○□○□○○○□○
08○□○○□○○□○
09○□○○○□○□○
10○○□□○○○○□
11○○□○□○○○□
12○○□○○□○○□
13○○○□□○○○□
14○○○□○□○○□
15○○○○□□○○□
16○○○○○○□□□
17○□○○○○□○□
18□○○○○○○□□
１番目の鍵(以下ではK01で表す)はA,B,Ｇの３人が□(持っていない)が、他の６人が○(持っている)なので、A,B,Ｇの３人がそろってもK01を開けることができませんが、他の６人の内の誰かが加わり４人になると開けることができます。
このことは他の鍵についても同じである。
（どの行も□が３つ、○が６つ）
よって、４人そろえばすべての鍵がそろう。
また、どの２つの列(人)も両方が□の鍵がある。
つまり、その鍵が無いため２人では開けられない。
この表は次のように作成しました。
●１．
６人グループで２人では開けられないが３人そろうと必ず開けられる組み合わせを作成。
どの２人でも開けられない鍵が最低１つあり、互いに異なる鍵である。
「もし、そうでないならＡとＢでK05が不足しており、ＢとＦでもK05が不足するならＡ、Ｂ、Ｆの３人がそろってもK05の錠が開けられない」
したがって、6Ｃ2＝１５個の錠が必要
この結果が前述の表のＡ〜Ｆ列の１〜１５行
●２．
「９人グループで〜４人そろうと必ず」にするには、３列（Ｇ，Ｈ，Ｉ）追加するにあたって
・１５個の鍵について
@この３人が持たない鍵は互いに重なってはならない。
３人の内２人が持たない鍵があると、その鍵はＡ〜Ｆの内の２人も持っていないため、この４人がそろっても開けられない。
−このままでは３人の中の２人で金庫を開けることができる為、鍵を増やす必要がある。
−各行に□を１つ追加することができる。
A各自１０個の鍵を持たなくてはならない。（と思う）
・３人の内のどの２人もが互いに持たない鍵が必要であり、
その数は3Ｃ2＝３個。
・追加した３個の鍵について、３人は前項のように割り当て最初の６人にはとりあえず３個とも渡すことにします。
その結果３人の内の１人と６人の中の誰かの２人で開くことになりますから、その人には渡さないようにします。
◆東京都 goya さんからの解答。
【問題２】×××○○○○○○
×○○××○○○○
×○○○○××○○
×○○○○○○××
○×○××○○○○
○×○○○××○○
○×○○○○○××
○○×××○○○○
○○×○○××○○
○○×○○○○××
○○○×○××○○
○○○×○○○××
○○○○×××○○
○○○○×○○××
○○○○○×○××
○○○○○○×××
こちらの方を先に作り、しかも、錠が１６個と少ないのですが、できた時は渡す鍵の数が人によって３個の差があるので均等に配布する方法は無いかと検討し、前回の解を出しました。
改めて、見ると前回のも均等では無いのでこちらの方が良かったですね。
でも、均等にする方法が判りました。
「２人では開けられない」に惑わされました。
「３人でも開けられない」と考えれば良かったのです。
そうすれば、『３人ゲームのリーグ戦』の応用になりますから..
ゲームでの対戦相手を持たない鍵とすれば次のようになります。 ＡＢＣ ＤＥＦ ＧＨＩ
01××× ○○○ ○○○
02○○○ ××× ○○○
03○○○ ○○○ ×××
04×○○ ×○○ ×○○
05○×○ ○×○ ○×○
06○○× ○○× ○○×
07×○○ ○×○ ○○×
08○×○ ○○× ×○○
09○○× ×○○ ○×○
10×○○ ○○× ○×○
11○×○ ×○○ ○○×
12○○× ○×○ ×○○
３行がゲームでの１回戦、その各行がテーブルに対応します。
どの２人の組み合わせでも互いに持っていない鍵がある
（ゲームの問題で総当たりが条件）ので開けられない。
また、各鍵を６人が持っているので４人そろえば開けられる。
◆大阪府 箱 さんからの解答。
【問題１】
※条件設定によってまちまちな回答が考えられるので、問題に明記されていない条件について、一応以下のように仮定しました。
k種類の鍵を作るとして、この鍵を「1人の人が同種の鍵を2本以上持つことなく」かつ「各人が持つ鍵の組合せが重複しないよう」にしてできるだけ多くの人に配分することを考えてみます。
例えば、5種類の鍵K1〜K5を配るとすると、
N1さん（K1,K2）
N2さん（K1,K3）
N3さん（K1,K4）
N4さん（K1,K5）
N5さん（K2,K3）
N6さん（K2,K4）
N7さん（K2,K5）
N8さん（K3,K4）
N9さん（K3,K5）
N10さん（K4,K5）
（つまりk＝5だと最大10人に対して、各人が異なる組合せで鍵を持たせることができます。）
このように、一人につき2本（2種類）の鍵を持たせると最も多くの人数に配分することができます。
これは、kが何種であっても成り立ちます。
（※ただし、問題の条件から考えて人数は3人以上なので、k≧3 です）
より少ない種類の鍵で間に合わせるために、鍵は1人につき2種類渡す、ということにしてみましょう。
さて、1人につき2種類の鍵を持たせた場合、金庫側では、（k個の鍵穴を作った上で）各人が2種類の鍵を持っているので、『少なくとも3種類の鍵があれば金庫が開く』ようにすることが最低条件です。
【★1／ここを問題2で使います。】
1人だと2種類の鍵があり、2人だと3種類または4種類の鍵が揃い、3人だと4種類以上の鍵が揃います。
でもこれだと、2人でも確実に開いてしまいますね。
問題の条件から完全に外れてはいませんが、少し無駄があるようです。
各人に違う組合せで鍵を持たせるとすると、3人が集まった時に最低でも4種類の鍵が揃うことになりますので、どうもこれは無駄っぽいです。
3人が集まった時に最低必要なのは3種類で良いので、仮に3人のうち2人が同じ組合せ（つまり、2人合わせて2種類）を持っていても構わないことになります。
例えば、
N1さん（K1,K2）
N2さん（K1,K2）
N3さん（K1,K3）
とかでもOKなわけです。
【★2／これを『鍵種節約』と名付けます。】
以上をふまえて・・・
k種類の鍵を2種類ずつ、各人が異なる組合せで配ることのできる最大人数nは
| n = | k(k-1) 2 | です。 |
さらに、一つの組合せにつき2人まで重複して良いので、n人に対して最低必要な鍵の種類（および鍵「穴」の数）kは
n ≦ k(k-1)
を満たす最小のkということになります。
（もちろん、必要な鍵の「数」はn×2です。）
まとめると、人数をn人として
『n ≦ k(k-1) を満たす最小のk種類の鍵の型を用意し、各人に2本（種類）ずつの鍵をある所持組み合わせが重複する人数が2人までになるように配付し
（※配付の際に同種の鍵を適宜複製する。人数×2「本」の「鍵」が必要。）
いずれかの「3」種類の鍵が揃った時に金庫が開くようにする』
【問題２】
問題2は問題1の応用です。
まず問題1と同じように始めて、★1の段階まで考えます。
★1の段階で、「2人では絶対開かない」ようにするには、問題1の★１の条件を、「少なくとも5種類の鍵があれば金庫が開くようにする」としてやる必要があります。
（2人で揃う最大の鍵の種類は4種類なので）
さて、続けてもし★2の「鍵種節約」をしてしまうと、4人で揃う最低の種類は3種類、
すなわち例えば
N1さん（K1,K2）
N2さん（K1,K2）
N3さん（K1,K3）
N4さん（K1,K3） …
などになってしまいますので、この場合「4人で必ず開けられる」に反するので「鍵種節約」はできませんね。
（※「鍵種節約」をしなければ、4人では最低でも5種類の鍵が揃うので大丈夫です。）
鍵種節約をしないので、n人に対して最低必要な鍵の種類（および鍵「穴」の数）kは
| n ≦ | k(k-1) 2 |
まとめると、人数を9人とすると
| 『9 ≦ | k(k-1) 2 | を満たす最小のk種類の鍵 |
「5」種類の鍵が揃った時に金庫が開くようにする』