アットランダム≒ブリコラージュ

17640：天秤ばかり...8個のボールから1個だけ重いボールを図りを２回使って見つける...基本 ^^

問題17640・・・https://blog.goo.ne.jp/difkou/e/73576ad75c2d339680c622703dafc50e?fm=entry_awp より 引用 Orz〜

解答

・わたしの...

3=3なら、

残りの2個で、

3>3 なら、

左側のうちの2個で、

1=1なら残り、

1>1 なら、その重い方で ^^

17639：天秤が釣り合う場合の数...

問題17639・・・算数にチャレンジ！！ http://www.sansu.org より Orz〜

天秤と、１ｇ，２ｇ，４ｇ，８ｇ，１６ｇ，３２ｇ，６４ｇ，１２８ｇ，２５６ｇ，５１２ｇの重りが１つずつあります。また、３４１ｇの重りXがあります。

これら１１個の重りのいくつかを天秤の両皿に載せて、釣り合わせることを考えます。

例えば、左の皿に「８ｇ，１６ｇ，６４ｇ，２５６ｇ」の４つの重りを載せ、右の皿に「１ｇ，２ｇ、３４１ｇ」の３つの重りを載せると、両方の皿の重さが３４４ｇとなり、釣り合います。

このとき、重りの載せ方は何通りあるでしょうか。ただし、左の皿と右の皿の重りを入れ替えたものは同じ載せ方と見なして１通りと数えることにします。

解答

結局わからないままでした...^^;

考えてたのは、341+x同士にできなければいけないので...

341=101010101

1023-341=682=1010101010

偶数桁目が1になるものが2つできることはないので、

偶数桁目が必ず1個残るような場合...(1023+341)/2=682〜341の範囲で...

を引いた個数を考えればいいと思うもよくわからなかったですばい...^^;;

・友人からのもの ...

341が無いとすると、例えば最大値が256であると1〜128

すべて足しても256より小さいからダメで、341は選ばれなければいけない

結局341を2^0,2^1,2^2,……..2^8,2^9の＋−で表すことである。

漸化式風に計算しました

nを1,2,4,8,……..,512　のどれかとする

kを1,2,4,8,….,nの＋−で表せる場合の数をf(n,k)とする　求めるのはf(512,341)

例えばf(8,5)であれば8を含まない場合と8を含むものに分けると

前者はf(4,5)　後者は4以下が+3であればよいからf(4,3)　と分けられる

さらにf(4,5)=f(2,5)+f(2,1)=0+2=2

f(4,3)=f(2,3)+f(2,1)=1+2=3

よってf(8,5)=5　求まる

figのようにしてf(512,341)=89　通り

*難しあるね ^^;

・鍵コメT様からのもの Orz〜

友人さんの記法f(x,y)を使います．
1,2,4,…,2^kを用いて偶数2nを表す際，「1」は使えないので，
2nを含め，すべての重りの重さが半分になった場合を考えて，
f(2m,2n)=f(m,n)です．
1,2,4,…,2^kを用いて奇数2n+1を表す際，「1」は必ず使います．
2n+1と同じ側に1を使った場合，(2n+1)+1および残りの重りすべてについて，
重さが半分になった場合を考えて，重りの載せ方はf((2^k)/2,n+1)通り．
2n+1と反対側に1を使った場合，(2n+1)-1および残りの重りすべてについて，
重さが半分になった場合を考えて，重りの載せ方はf((2^k)/2,n)通り．
よって，f(2m,2n+1)=f(m,n+1)+f(m,n)です．

以上を用いて，

f(512,341)=f(256,171)+f(256,170)
=(f(128,86)+f(128,85))+f(128,85)=2f(128,85)+f(128,86)
=2(f(64,43)+f(64,42))+f(64,43)=3f(64,43)+2f(64,42)
=3(f(32,22)+f(32,21))+2f(32,21)=5f(32,21)+3f(32,22)
=5(f(16,11)+f(16,10))+3f(16,11)=8f(16,11)+5f(16,10)
=8(f(8,6)+f(8,5))+5f(8,5)=13f(8,5)+8f(8,6)
=13(f(4,3)+f(4,2))+8f(4,3)=21f(4,3)+13f(4,2)
=21(f(2,2)+f(2,1))+13f(2,1)=34f(2,1)+21f(2,2)
=34*2+21*1=89です．

係数にフィボナッチ数列が登場し，結論もフィボナッチ数ですね．
341以外でも，二進法で1,0が交互に現れる数なら同様になります． 

*もどかしいくらいよくわからない問題で...^^;

熟読玩味ぃ〜 ^^;☆