くしゃみが止まらない。
ヒノキの花粉がおさまるのはやはりGW明けあたりだろうか・・・。
ヒノキの花粉がおさまるのはやはりGW明けあたりだろうか・・・。
日本でグラフ理論を世間に広く知らしめる本をたくさん著している秋山仁氏が好んで取り上げる問題の一つに，コンドームの問題がある。
一般向けには，女2人，男2人の計4人が男女で総当たりに一回ずつ肉体関係を持つことにするとして，お互いに性病を移さないようにするためにコンドームを必ず着用して行為に及ぶとしたら，コンドームはいくつあれば足りるか，といった設定で述べられる。もちろん男女の人数を色々変える一般化はすでになされている。
この問題を初めて知ったのはいつだったか忘れたが，確か秋山仁氏の著書のどれかを読んだ時だったと思う。こういう問題は苦手なので，自分で少し考えたものの，正解にはほど遠い個数を答えたものだった。正解と解説もその著書に載っていたように思うが，ほとんど覚えていない。
先日，とある知り合いがこの問題を話題にしていた。数年前にも同じ話をしたことがあったように思う。今回は真面目に考えてみた。ただし，問題は女3人，男3人のバージョンであり，しかも
コンドームの重ね掛けはOK,
裏返して使用するという発想もあり，
いくつあれば十分か，という正解と思しき数値も聞いてしまっている，
という，ヒントが多い状態でのチャレンジであったので，残された仕事としては，その個数でちゃんと目的が果たせることを示すことだけであるが，それはすぐに解決した。
さて，問題は，その正解らしい個数よりも少ないコンドームではうまくいかないのかどうかを明らかにすることである。それはそれで難問だと思うのだが，当然，世界の誰かがすでにその答えを見出しているはずである。というわけで，どんな本に載っているのか，あるいは解説サイトがあるのかどうか，ネットで検索してみたところ，いろいろわかったことがあるので，備忘録のつもりで以下にまとめておく。
まず，この問題はラスロウ・ロバース編の組み合わせ論の入門書（邦題『入門 組合せ論』）に載っているらしいことが判明した。また，この問題に対する答えは，ハイナル・ロバースの定理，もしくはロバースの定理と呼ばれているということもわかった。
次にすることは，ラスロウ・ロバースなる人物を調べることである。名前の原綴りがよくわからなかったが，いろいろ試しているうちに
László Lovász
であることを突き止めた。
この名前で検索すると Wikipedia の記事がすぐ見つかるが，それを見ると組合せ論における超大物らしいことはわかるものの，肝心のコンドームの問題は載っていない。
ということで，Condom problem というキーワードで検索したところ，MathWorld の記事でGlove problemという項目にたどり着いた。
なるほど，感染症を防ぐための医療用の手袋か！
この時点で，コンドームというのは誰かが面白く脚色したものではないかという疑惑が浮上した。そのあたりの事情については，MathWorldの記事で参考文献として挙げられている Ilan Vardi 氏の "Computational Recreations in Mathematica®" という著書の Chapter 10 の冒頭に少し述べられている。ちなみに，その章のタイトルはそのものズバリ "The Condom Problem" である。また，Hajnal と Lovász の1978年の論文の結果をより完璧にした結果が述べられているらしい。人数に関する場合分けをするなど，解読は大変そうなので試みていない。
以上，この問題の周辺を調べた結果を述べたが，私としてはこれで十分満足している。
[追記20170430]
Orlitsky と Shepp の "On Curbing Virus Propagation" の参考文献に，数理パズル研究家（？）として世界的に有名な Martin Gardner 氏による1977年の記事と1978年に出版された "Aha!Insight" という著書が紹介されている。
1977年の記事は "Science Fiction Puzzle Tales" という著書にまとめられて出版された。そこでは "2. The Doctors' Dilemma" というタイトルで，3人の外科医が二組しかない手袋を用いて一人の患者を安全に手術するにはどうしたらよいか，というストーリー仕立てになっており，解答の部 (Second Answers の Postscript) で，この問題の歴史的な経緯について述べられている。それによると，何年も前からやはりコンドーム問題という形態で数学者たちの間に伝わっていた問題とのことである。Gardner 氏のその記事が公に出版された最初であろうとも書かれている。
"Aha!Insight" には "Sanitary Surgeons" というタイトルで Chapter 5 に収められている。なお，Orlitsky と Shepp のノートの参考文献に引用されているタイトル "Science Fiction ..." と同じものになっているが，Issac Asimov の Science Fiction Magazine の原記事を見たわけではないので真偽のほどは不明である。また，日経出版から翻訳も出ているが，同記事は翻訳の下巻に「外科手術危機一髪」と題して一番最後に収録されている。
一般向けには，女2人，男2人の計4人が男女で総当たりに一回ずつ肉体関係を持つことにするとして，お互いに性病を移さないようにするためにコンドームを必ず着用して行為に及ぶとしたら，コンドームはいくつあれば足りるか，といった設定で述べられる。もちろん男女の人数を色々変える一般化はすでになされている。
この問題を初めて知ったのはいつだったか忘れたが，確か秋山仁氏の著書のどれかを読んだ時だったと思う。こういう問題は苦手なので，自分で少し考えたものの，正解にはほど遠い個数を答えたものだった。正解と解説もその著書に載っていたように思うが，ほとんど覚えていない。
先日，とある知り合いがこの問題を話題にしていた。数年前にも同じ話をしたことがあったように思う。今回は真面目に考えてみた。ただし，問題は女3人，男3人のバージョンであり，しかも
コンドームの重ね掛けはOK,
裏返して使用するという発想もあり，
いくつあれば十分か，という正解と思しき数値も聞いてしまっている，
という，ヒントが多い状態でのチャレンジであったので，残された仕事としては，その個数でちゃんと目的が果たせることを示すことだけであるが，それはすぐに解決した。
さて，問題は，その正解らしい個数よりも少ないコンドームではうまくいかないのかどうかを明らかにすることである。それはそれで難問だと思うのだが，当然，世界の誰かがすでにその答えを見出しているはずである。というわけで，どんな本に載っているのか，あるいは解説サイトがあるのかどうか，ネットで検索してみたところ，いろいろわかったことがあるので，備忘録のつもりで以下にまとめておく。
まず，この問題はラスロウ・ロバース編の組み合わせ論の入門書（邦題『入門 組合せ論』）に載っているらしいことが判明した。また，この問題に対する答えは，ハイナル・ロバースの定理，もしくはロバースの定理と呼ばれているということもわかった。
次にすることは，ラスロウ・ロバースなる人物を調べることである。名前の原綴りがよくわからなかったが，いろいろ試しているうちに
László Lovász
であることを突き止めた。
この名前で検索すると Wikipedia の記事がすぐ見つかるが，それを見ると組合せ論における超大物らしいことはわかるものの，肝心のコンドームの問題は載っていない。
ということで，Condom problem というキーワードで検索したところ，MathWorld の記事でGlove problemという項目にたどり着いた。
なるほど，感染症を防ぐための医療用の手袋か！
この時点で，コンドームというのは誰かが面白く脚色したものではないかという疑惑が浮上した。そのあたりの事情については，MathWorldの記事で参考文献として挙げられている Ilan Vardi 氏の "Computational Recreations in Mathematica®" という著書の Chapter 10 の冒頭に少し述べられている。ちなみに，その章のタイトルはそのものズバリ "The Condom Problem" である。また，Hajnal と Lovász の1978年の論文の結果をより完璧にした結果が述べられているらしい。人数に関する場合分けをするなど，解読は大変そうなので試みていない。
以上，この問題の周辺を調べた結果を述べたが，私としてはこれで十分満足している。
[追記20170430]
Orlitsky と Shepp の "On Curbing Virus Propagation" の参考文献に，数理パズル研究家（？）として世界的に有名な Martin Gardner 氏による1977年の記事と1978年に出版された "Aha!Insight" という著書が紹介されている。
1977年の記事は "Science Fiction Puzzle Tales" という著書にまとめられて出版された。そこでは "2. The Doctors' Dilemma" というタイトルで，3人の外科医が二組しかない手袋を用いて一人の患者を安全に手術するにはどうしたらよいか，というストーリー仕立てになっており，解答の部 (Second Answers の Postscript) で，この問題の歴史的な経緯について述べられている。それによると，何年も前からやはりコンドーム問題という形態で数学者たちの間に伝わっていた問題とのことである。Gardner 氏のその記事が公に出版された最初であろうとも書かれている。
"Aha!Insight" には "Sanitary Surgeons" というタイトルで Chapter 5 に収められている。なお，Orlitsky と Shepp のノートの参考文献に引用されているタイトル "Science Fiction ..." と同じものになっているが，Issac Asimov の Science Fiction Magazine の原記事を見たわけではないので真偽のほどは不明である。また，日経出版から翻訳も出ているが，同記事は翻訳の下巻に「外科手術危機一髪」と題して一番最後に収録されている。
確か3月26日に近所の桜の木々が，各々数輪，花を咲かせているのを見た。
それから一週間ほど経った今，まだ二分咲き程度といったところである。
にもかかわらず，今日，都心で桜が満開というニュースを目にしたような気がする。
あ，私が住んでいるのは都心ではないから，別に何の問題もないか。
花粉症なので花見のために外出しようという気はさらさら起きない。それはともかく，数年前には雪が降ったこともあるくらい，この時期は意外と寒い日があるので，夜桜を楽しむ際にはそれなりの格好で臨む必要があるだろう。
スギの脅威はそろそろスギ去ろうというところだろうが，ヒノキはまだまだ続くからねぇ・・・。
それから一週間ほど経った今，まだ二分咲き程度といったところである。
にもかかわらず，今日，都心で桜が満開というニュースを目にしたような気がする。
あ，私が住んでいるのは都心ではないから，別に何の問題もないか。
花粉症なので花見のために外出しようという気はさらさら起きない。それはともかく，数年前には雪が降ったこともあるくらい，この時期は意外と寒い日があるので，夜桜を楽しむ際にはそれなりの格好で臨む必要があるだろう。
スギの脅威はそろそろスギ去ろうというところだろうが，ヒノキはまだまだ続くからねぇ・・・。
今日は一年に一度の特別な日，エイプリルフールなのだが，これといったネタが思いつかない。
あ，そうだ。
ここ一年ほど更新をろくにしていないこのブログに，久々に今日から一年間，一日も欠かさず記事を投稿する，と宣言しておこう。
たぶん・・・嘘に・・・なる・・・。
あ，そうだ。
ここ一年ほど更新をろくにしていないこのブログに，久々に今日から一年間，一日も欠かさず記事を投稿する，と宣言しておこう。
たぶん・・・嘘に・・・なる・・・。
