続きです。
【転】
目新しい話題だったようで、例会での発表は割と受けが良かったです。
その日の夜、1通のメールが届きました。
例会での私の発表のあと、一般解を求めてみたいと声を掛けてくださった方からのメールで、
Ｎ袋に対して、1,2,4,7,13,24,44,84,…とずっと先まで、
きれいな形で一般形が示されていました。
ここには詳しく書きませんが、大きいほうから詰めていく戦法です。
その戦法で求めたものが最小である証明ができているわけではありませんが、2^nよりはずっと小さな数に
なっており、しかも漸化的に求めることができるものです。
これには驚きました。だって、私が発表してから５時間後くらいですよ！
私は２ヶ月くらい抱えていて、先に進めなかったのに、それがわずか数時間。
もっと真摯にパズルと向き合わないといけない、ととても刺激になりました。
【結】
その後、この1,2,4,7,13,24,44,84,という数列は、Conwayがずっと以前に求めていたこと、
最小値かどうかの証明はされていない未解決問題であること、
この問題に対してエルデシュが賞金を掛けていたこと、などがわかりました。
Distinct Subset Sumsという有名な未解決問題だったようです。
エルデシュが賞金を掛けている、のですから、私が蒲団の中で解決できるような問題じゃありませんでしたね。
また、新しい進展もでてきています。
たとえば、10袋を重量計2回使う問題だと、13枚で5袋ずつ求める以外に、
うまいこと組み合わせれば12枚でもできます。
複数回使う場合には、前回の結果に応じて次の量り方を変えれば、もっと少ない枚数でもできそうです。
いろいろと発展しそうな面白い分野です。
- 2012/04/30(月) 23:59:59|
- パズル
-
| トラックバック：1
-
| コメント：0
コインが本物かどうかを判別するパズルの話をします。
【起】
偽コインのパズルというと、
天秤を何回か使って重さの違う偽コインを見分けるパズルもありますが、
ここで話題にするのは重量計を1回使って偽コインの入った袋を見分けるパズルです。
ここにコインがたくさん入った袋がいくつかある。
偽コインが入った袋には偽コインだけが入っており、
本物と偽物のコインは10gと9gのように重さが異なる。
重量計を1回だけ使って、偽コインが入っている袋を判別したい。
てな感じで前提が説明され、続いて次のような2問がセットで出されます。
第1問
5袋あり、そのうちの1つだけが偽コインの袋である。
→各袋からそれぞれ1,2,3,4,5枚のコインを取りだして重さを量る。
たとえば重さが147gだったら、3枚取りだした袋が偽コインの袋。
第2問
5袋あり、その中に偽コインの袋がいくつあるかは不明である。
→各袋からそれぞれ1,2,4,8,16枚のコインを取りだして重さを量る。
たとえば重さが300gだったら、2枚と8枚取りだした袋が偽コインの袋。
よく見かけるパズルで、古典と言ってよいでしょう。
【承】
ここからが本題。
1月のパズル懇話会の例会で、
第2問の形式で各袋の中にコインが16枚も入っていない場合の話題が出ました。
ハッとしました。
何度も接するうちに条件反射のように刷りこまれてしまっていたが、
そういえば、昔々初めてこのパズルに接したときに感じた違和感。
第1問なら1,2,4,5,7、第2問なら1,10,100,1000,10000でもできる、
要は答えは他にもいっぱいある、という違和感。
第2問の形式で、各袋から取り出す枚数の最大値を減らせるんじゃないか。
偽コインの袋の出現パターンは2^N通りあって、それらが全部区別できれば良い。
寝る前にフトンの中でざっと検討したら、出てくる出てくる。
3袋は1,2,4が普通だが、同じ最大4でも2,3,4もある。
4袋は1,2,4,8が普通だが、3,5,6,7なら最大7に減らせる。
5袋は1,2,4,8,16が普通だが、3,6,11,12,13や6,9,11,12,13なら最大13に減らせる。
普通に言われている2^N枚取る方法は、全袋から取り出す枚数の合計を最小にするけど、
1つの袋から取り出す最大枚数については、決して最小にはなっていなかった。
この最大枚数は袋数が増えるに従って、1,2,4,7,13…である。
その先の検討は進んでいなかったけど、とりあえずこのことを
3月のパズル懇話会の例会で発表しました。
長くなったので【転】【結】は別の機会に。
- 2012/03/21(水) 02:17:25|
- パズル
-
| トラックバック：0
-
| コメント：0
あけましておめでとうございます。
今年も良いパズルに出会えますように。
今年の年賀パズルです。
上の図の右上にあるような
円を2つ繋げた8の字型のパーツを
24個（●の数としては48個）で
タツノオトシゴ（のつもり）を描いてみました。
さて、パーツの敷き詰め方は
全部で何通りあるでしょう？
（年末年始は旅行に出ています。この記事は2011.12.29に用意したものです。うまく自動投稿されたかな？）
- 2012/01/01(日) 08:00:00|
- パズル
-
| トラックバック：0
-
| コメント：2
近況です。
●駒場祭
2011/11/26に東大の駒場祭に小太郎（長男,高1）と2人で行ってきました。
ペンシルパズル同好会のところでいろんなかたと会え、長いこと遊ばせてもらって楽しかったです。
難問パズル集ハバネロ、他いろいろお土産をもらいました。まだ消化しきれていません。
学生時代に3年間住んでいた駒場寮が無くなった、とは聞いていたけど、
跡地にとてもきれいな建物が建っていて感慨深かったです。
●さゆりさんとこの記念パズル8
2011/12/16、さゆりさんのところ（
こちら）で記念パズル8が出題され、頑張って解きました。
出題から32時間余りかかってようやく解けたのですが、それでも3位に入れて記念品を頂くことができました♪
さゆりさんのところでは毎月難問パズルが出題されていて、これに正解すると暗号？の一部がもらえます。
これを沢山あつめると、年に1回出題される記念パズルの在り処がわかり、晴れて参加できるようになります。
毎月の難問パズルをある程度以上解けた人だけが記念パズルに挑めるわけで、参加者は猛者ばかり、ということになります。今回の記念パズルは、そういう猛者達が四苦八苦してようやくとけるかどうか、というレベルの問題でした。
興味のあるかたは、今からでも参加できるので、是非、やってみてください。といっても難問パズルを解いて暗号を集めるところから始めないといけませんが。
記念パズルを必死こいてやっていて、12/17のパズル懇話会の例会には行けませんでした。ゲスト参加したはずのPeter Winkler氏に会いたかったので、それだけが心残りです。
●ファイブレイン
NHK Eテレのパズルアニメです。番組の最後5分間に、パズるな話題を紹介するコーナーがあります。
2011/12/4の回で、パズル懇話会の例会の様子が放映されました。私も軽くインタビューを受けており、少しだけ登場しました。他の回でも、條さんと森西さん（12/18）、仕掛屋定吉さん（12/25）、など知り合いが登場しています。これからも目が離せません。
●speed sudoku
ずっと昔からあったサイトで、数独の早解きを競い合うところです。（
こちら）
今頃どうしてなのか自分でもわからないのだけど、始めました。
無料でできるのは1日に2題（正確には12時間のうちに2題）だけなので、あまり時間を取られないのが助かります。問題はEasyからVeryHardまで4段階ありますが、VeryHardといってもそんなに難しくない問題です。最大8人で同じ問題のタイムを競うのですが、思ったほどは1位が取れず、自分の解くのが速くないことを痛感しています。レーティングがどのあたりで落ち着くのか、しばらく続ける積り。
●LMI
LogicMastersIndiaのオンラインコンテストになるべく参加するようにしています。最近は低調な成績が多く、体調が良くないためなのか、実力低下なのか、と焦りを感じています。多分、両方でしょうね。まぁ気長にやります。
●ニコリコム優勝
2011/12/16、ニコリコムの第125回パズル早解き選手権で優勝しました。とはいっても、ナンバーリンクが同時に2題出題されて優勝者も2名出るボーナス回で、しかも実際に解けたのは3番目（上位2名は既に今年の早解き選手権で優勝していたので対象外）なのに繰り上げ優勝、というものでした。でもまあ、嬉しかったです。
通算で3回目の優勝ですが、数独、カックロはともかく、ナンバーリンクで優勝できたのは意外でした。マウスさばきが遅いので。
●パズル本
・ナンプレ超上級編27
2011.8.11〜2011.12.11。途中しばらく行方不明になっていたこともあって、4ヶ月もかかっています。
・ニコリのペンパ2012
2011.11.19〜2011.12.14。いろんな種類のパズルを20〜30題ずつ集めたパズル本です。
少ないと物足りないし、ペンパ本で100問もあると食傷気味になったりするけど、
このくらいだとちょうど良いボリュームでした。
・究極難解ナンプレ1
2011.12.11〜2011.12.11。全部で133問入っていますが、そのうちの数問だけ味見して終わりにしました。
この本のナンプレは全て、ヒント数が17個です。
ちまたにあふれているナンプレ本は沢山あり過ぎて手を出す気にならないです。
この本はチラッと表紙の問題を見た時に、何か違和感を感じました。そう、ヒントが対称形でないのです。
昔は対称形ヒントは手作り感、安心感で、非対称形ヒントは無機質感、という印象でしたが、
今ではコンピュータが作る問題でも当然のように対称形ヒントになっています。
それで、この本の非対称形ヒントの問題が却って目を引きました。
確かに、最小ヒント数である（と信じられている）17ヒントだとまず対称形になりませんね。
ヒント数が少ないから、埋めなきゃいけないマス数が多い＝究極難解ナンプレ、というような
タイトル付けと想像しましたが、ヒント数を極限まで減らすと、こった仕組みは入りっこない気がします。
それを確認するために買いました。数問解いたけど、予想通りどれも難しくはなく、同じようなレベルでした。
- 2011/12/29(木) 23:46:08|
- パズル
-
| トラックバック：0
-
| コメント：1
