id:Nabetani:20041014:p1 から始まる、id:Nabetani:20050226:p4 の続き。 だいぶ高速化したので、n=6 の場合も計算できるようになった。 折角なので秒数とともに書いておくと： n=1 : 1個 / 0秒 n=2 : 5個 / 0秒 n=3 : 47個 / 0.016秒 n=4 : 733個 / 0.44秒 …

id:Nabetani:20041014:p1 の続き。 四則演算と n 個の変数で作れる式の数を数えるという問題。 もちろん、a+b-c+d と b-(c-a)+d は同じ式と見なす。 a/(b/c)+d と ac/b+d は、c=0 の時に計算できるかどうかという点で異なる式ではあるが、同じ式と見なすとい…

まだいいアルゴリズムはないかと考えているんだが、思いつかない。で。 id:Nabetani:20041014#p1 によると（って、私自身だけど）変数四つだと 733 通りの式があるらしい。 b,c,d を確定させると、残り一つの数 a は、高々 733 通りしかない（必ず一次方程式…

今日も、私の記事に対する反応と思える内容が http://pub.cozmixng.org/~the-rwiki/rw-cgi.rb?cmd=view;name=RHG%C6%C9%BD%F1%B2%F1%3A%3A%C5%EC%B5%FE+Sound+Stage に追記されていた。ありがとうございます＞反応してくださっている方。ところで。私の方も…

今日（昨日かも）もまた、私の記事に対する反応と思える内容が http://pub.cozmixng.org/~the-rwiki/rw-cgi.rb?cmd=view;name=RHG%C6%C9%BD%F1%B2%F1%3A%3A%C5%EC%B5%FE+Sound+Stage に追記されていた。ありがとうございます＞RHGの方……とは限らないのか*1。…

ここを読んでくださっているのか、有限手順の話が http://pub.cozmixng.org/~the-rwiki/rw-cgi.rb?cmd=view;name=RHG%C6%C9%BD%F1%B2%F1%3A%3A%C5%EC%B5%FE+Sound+Stage に追記された。ありがとうございます＞誰？ 遠慮なく引用すると： 有限手順の方法： a,…

http://pub.cozmixng.org/~the-rwiki/rw-cgi.rb?cmd=view;name=RHG%C6%C9%BD%F1%B2%F1%3A%3A%C5%EC%B5%FE+Sound+Stageからリンクされていて、びっくりした。 どなたがこのような辺境ページをお読みくださっているだろうか。先日の問題(id:Nabetani:20050211#…

二月八日のパズル( id:Nabetani:20050208#p1 )の続き。 1〜9 ではなく、1〜20 で総当りしてみたが、1,2,5,8 にかなう組み合わせは見当たらなかった。 惜しかったのは、1,2,5,101,2,4,10*1 で、1〜50 まで作れる。 で。問題。 以下の条件を満たす a,b,c,d は…

昨日の続きで、N=5 の場合を計算しているんだが、場合の数が多くてなかなか終わらなかった。 Athlon64様様である。 N=5 → 192 : [4, 5, 6, 7, 8] 9 を使うと 192 までは行けないらしい。意外である。 それと、「1〜9がN個」ではなく「正の整数がN個」にした…

昨日計算した結果、1,2,5,8 と四則演算があれば 1〜51 の整数が全部作れることがわかったので、確かめようと、通勤中に頭の中で考えた。 全部確認するのに30分ぐらいかかった。 寝ぼけた頭にはちょっとつらかったが、いいパズルだったと思う。 通勤に30分以…

ふと思いついた問題。 1〜9 の数字 N個の組を q とする。q と四則演算を組み合わせて作ることのできる正の整数の集合をS(q)とする。S(q)に含まれない最小の正の整数を X(q)+1 とする。 X(q) が最大になるような q と、そのときの X(q) を求めよ。 厳密に書こ…

先日書いたプログラムでは、平成元年等の虱をつぶしきれなかったので、さらに枝刈りを行った結果、平成元年から17年までの問題を解くことができた。 例によって、無駄な括弧を減らす処理なんかは入ってないので、とても見にくいが： 1989 = ( (1 + (1 + 1) )…

情報の共有の問題に明け暮れている間に先を越されてしまった。 17 をいくつかと四則演算と括弧で、2005を作る。17の数が一番少ないのはどんな方法か を、解くプログラムを書こうと思っていたんだが、id:igatoxin さんに先を越されてしまった。 id:igatoxin …

一昨日・昨日と続いている「情報共有と電話の回数」（ http://www.hyuki.com/diary/200501#i20050110133233 ）の続き。 http://www.hyuki.com/diary/200501#i20050113223350 → http://www.sampou.org/cgi-bin/haskell.cgi?comment%3aEveryday%3a2005-01-12&l…

昨日の「情報共有と電話の回数」（ http://www.hyuki.com/diary/200501#i20050110133233 ）の続き。9人の場合の計算をさせておいたら、寝ている間に完了した。計算に要した時間は 5時間余り。 やはり、x(9) = 9×2-4 = 14 だった。平方数なので何かあるかもと…

NUM = ARGV.size==0 ? 4 : ARGV[0].to_idef uniques( s ) (0...s.size).map{ |i| if s[i] && (0...i).any?{ |j| s[i]==s[j] || ( s[i].size==1 && s[j] && s[j].size==1 ) } nil else i end }.select{ |x| x } end def each_pair(s0) vi = uniques( s0 ) pai…

http://www.hyuki.com/diary/200501#i20050110133233 の話題。 わかっていることを取り急ぎ書いておく。 4人のとき、ab-cd-ac-bd の4回で共有ができる。 n人のときに、x(n)回で共有できる場合、x(n+1)≦x(n)+2 (なぜならば。新たに加わった人が最初と最後に電…

上と下をおさえておこう。 下限は、場合の数で。7個あるんだから、正解は21通りある。天秤の出力は3通りなので、2回で正解を網羅することはできない。ということで、3以上。 上限は、自明な解で抑える。コインを七角形の頂点に並べて、隣同士を比較すると偽…

昨日書いた問題は、解ける気がしない。というか、設問としてまずそうだ。 S(N,2,3)が解を持つNは無さそうだし、D(N,2,3)が解を持つNはほぼ間違いなくない。 というわけで、条件を簡単にして、単純な問題にしてみた。 7 個のコインがある。そのうち 2 個は偽…

12個から天秤3回使用で偽物を見つけだす問題は、何度も見た。 そこで問題。 N 個のコインがある。そのうち F 個は偽物である。偽物は本物とは重さが違うことがわかっているが、重いか軽いかわからない。天秤を B 回使用して、偽物を検出せよ。但し、2F＜N と…

n個の数字と四則演算で、何通りの計算ができるかという問題。 n=6 の場合を数えようと、アルゴリズムを見直してみたら、n=5 の場合の計算速度が 10 倍以上になった。 20倍ぐらいまでは行けそうだが、もういいやと思って n=6 にトライしてみた。 が。 メモリ…

n=5 の場合も数えてみた。結果は 15907個。またもや素数である。ちなみに、15907の前後は、素数率10%程度。計算する前の予想は2万個であった。悪くない。 n=6 の場合についてはまだ計算していない。なんとなく、一晩かかりそうな感じなので、そのまえに効率…

よく、1,2,3,4 と四則演算と括弧で10をつくれ、みたいな問題がある。 ブルートフォースで絶対解けるよね、なんて思いつつも、場合の数がどれだけあるのか調べたことがなかった。 で。問題。 a1,...,an と四則演算と括弧で値の異なる式が何種類できるか。但し…

何かと情報ありがとうございます＞id:igatoxin様 で。 先日(id:Nabetani:20040909)定義した mn を用いて、 幾何平均とxの間に算術何平均がある → x = m-1/2 幾何平均とyの間に調和平均がある → y = m3/2 となる。収束することの証明はしてないけど。 物の見…

「調和平均と g の間に算術平均がある」の g は、あまり平均らしくない。 というのは、 g(100,1)≦g(100,50) のように、一価関数と見なした時に単調ではなくなってしまうからだ。 とはいえ。(a*a+b*b)/(a+b) という式は、値で重み付けされた平均である。住ん…

id:igatoxin さんの書いた答えが正しいことを確認した。 以下、am は算術平均、hm は調和平均である。 手順は f(a,b)≦hm(a,b)≦am(a,b) を示す 任意の a, b について、c|a,b|≧|f(a,b)-am(a,b)|, 1≦c を満たす定数 c が存在することを示す である。g も同様。

通勤の電車の中で三十分ばかり考えたが、よくわからなかった。 平均値を保存するというアイディアまではあったんだが、計算が追いつかなかった。とほほ。帰宅してみると、id:igatoxin さんのところ( id:igatoxin:20040909 )に解答が！ ありがとうございます…

というわけで、そうなるとこんなことを考えたくなる： 以下の条件を満たす関数 f をひとつ求めよ（あるいは, そのような f が存在しないことを示せ）. a0, b0が正の実数であり, 0≦n において an+1 = 算術平均( an, bn ) bn+1 = f( an, bn ) を満たす時, a∞ =…

id:igatoxin さんが id:igatoxin:20040908 に書かれているとおり、収束値は幾何平均である。で。その証明。但し、計算は省略。 簡単な計算で、両者とも有界単調であることがわかる。そうすると、収束は自明。 しかし。{an}の極限と{bn}の極限が一致すること…

昨日は相加平均（算術平均）と相加平均（幾何平均）だったが、名のある平均はもう一つある。調和平均である。 というわけで： 正の実数a0, b0がある. 0≦n について, anとbnの相加平均をan+1, 調和平均をbn+1とする. このとき an, bnが, n→∞ で同じ値に収束す…