パズルは面白い

パズルが好きで毎日やっているわけですが、自分の軌跡を残しておきたいと、ふと思いました。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
  1. --/--/--(--) --:--:--|
  2. スポンサー広告

偽コイン袋の問題(2)

続きです。

【転】
目新しい話題だったようで、例会での発表は割と受けが良かったです。
その日の夜、1通のメールが届きました。
例会での私の発表のあと、一般解を求めてみたいと声を掛けてくださった方からのメールで、
N袋に対して、1,2,4,7,13,24,44,84,…とずっと先まで、
きれいな形で一般形が示されていました。
ここには詳しく書きませんが、大きいほうから詰めていく戦法です。
その戦法で求めたものが最小である証明ができているわけではありませんが、2^nよりはずっと小さな数に
なっており、しかも漸化的に求めることができるものです。
これには驚きました。だって、私が発表してから5時間後くらいですよ!
私は2ヶ月くらい抱えていて、先に進めなかったのに、それがわずか数時間。
もっと真摯にパズルと向き合わないといけない、ととても刺激になりました。

【結】
その後、この1,2,4,7,13,24,44,84,という数列は、Conwayがずっと以前に求めていたこと、
最小値かどうかの証明はされていない未解決問題であること、
この問題に対してエルデシュが賞金を掛けていたこと、などがわかりました。
Distinct Subset Sumsという有名な未解決問題だったようです。
エルデシュが賞金を掛けている、のですから、私が蒲団の中で解決できるような問題じゃありませんでしたね。
また、新しい進展もでてきています。
たとえば、10袋を重量計2回使う問題だと、13枚で5袋ずつ求める以外に、
うまいこと組み合わせれば12枚でもできます。
複数回使う場合には、前回の結果に応じて次の量り方を変えれば、もっと少ない枚数でもできそうです。
いろいろと発展しそうな面白い分野です。

スポンサーサイト
  1. 2012/04/30(月) 23:59:59|
  2. パズル
  3. | トラックバック:1
  4. | コメント:2

FC2Ad

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。