問53の答え

ヒントではないですが、1本のときから順に考えるしかなさそうです。

問53に戻る。

解答と解説は下にあります↓↓↓







※ こちらは問題の解答のみです。注意してください。問題は別の場所に掲載してあります。

解53
スポンサーサイト

コメントの投稿

非公開コメント

承認待ちコメント

このコメントは管理者の承認待ちです

たけちゃんさん

> 私は,各蚊取り線香を,
> (一端に火をつける時刻a,他端に火をつける時刻b,燃え尽きる時刻c)
> で特徴付けて考えました.ただし,一端にのみ火をつける場合はb=a+1とします.
> a≦b≦a+1であり,c=(a+b+1)/2となりますね.
> 蚊取り線香を1本目,2本目,…のように順序付けて考えると,
> 各蚊取り線香に可能なa,bは,
> ・0
> ・すでに考えた蚊取り線香のcに登場する値
> ・bについてのみ,a+1
> ですべてであり,
> 1本目について1*2通り,2本目について2*3通り,3本目について3*4通り,
> 4本目について4*5通り,5本目について5*6通り
> をすべて調べれば完了となるはずです.
> (実際は,a>bやa+1<bとなるケースが除外され,もう少し減ります.)
>
> 手で調べるには多すぎるので,この考えに沿って,
> BASICのプログラムを組んで調べたところ,78通りという結論を得ました.
> 照合したところ,解答に挙げられていない「66/32」が可能のようです.
> 実際,(0,0,1/2),(0,1/2,3/4),(1/2,3/2,3/2),(3/4,3/2,13/8),(3/2,13/8,33/16)
> の5本で,時刻0から時刻33/16の間の時間が66/32となりますね.
>
> プログラムは以下のもの(十進BASIC)を用いました.
> 端数を避けて,各時刻は32倍したものを用いています.
>
> K=5
> KK=2^K
> DIM X(-1 TO K),F(0 TO K*KK)
> FOR A1A=0 TO 0
> FOR A1B=-1 TO 0
> LET X(-1)=X(A1A)+KK
> IF X(A1A)>X(A1B) OR X(A1A)+KK<X(A1B) THEN GOTO 500
> LET X(1)=(X(A1A)+X(A1B)+KK)/2
> FOR A2A=0 TO 1
> FOR A2B=-1 TO 1
> LET X(-1)=X(A2A)+KK
> IF X(A2A)>X(A2B) OR X(A2A)+KK<X(A2B) THEN GOTO 400
> LET X(2)=(X(A2A)+X(A2B)+KK)/2
> FOR A3A=0 TO 2
> FOR A3B=-1 TO 2
> LET X(-1)=X(A3A)+KK
> IF X(A3A)>X(A3B) OR X(A3A)+KK<X(A3B) THEN GOTO 300
> LET X(3)=(X(A3A)+X(A3B)+KK)/2
> FOR A4A=0 TO 3
> FOR A4B=-1 TO 3
> LET X(-1)=X(A4A)+KK
> IF X(A4A)>X(A4B) OR X(A4A)+KK<X(A4B) THEN GOTO 200
> LET X(4)=(X(A4A)+X(A4B)+KK)/2
> FOR A5A=0 TO 4
> FOR A5B=-1 TO 4
> LET X(-1)=X(A5A)+KK
> IF X(A5A)>X(A4B) OR X(A5A)+KK<X(A5B) THEN GOTO 100
> LET X(5)=(X(A5A)+X(A5B)+KK)/2
> FOR I=0 TO K
> FOR J=0 TO K
> LET F(ABS(X(I)-X(J)))=1
> NEXT J
> NEXT I
> 100 NEXT A5B
> NEXT A5A
> 200 NEXT A4B
> NEXT A4A
> 300 NEXT A3B
> NEXT A3A
> 400 NEXT A2B
> NEXT A2A
> 500 NEXT A1B
> NEXT A1A
> LET S=0
> FOR I=1 TO K*KK
> IF F(I)=0 THEN GOTO 600
> PRINT I;
> LET S=S+1
> 600 IF MOD(I,20)=0 THEN PRINT
> NEXT I
> PRINT
> PRINT S
> END
>
> このプログラムは12重ループを使っていて,
> 同じ考え方だと,蚊取り線香n個に対しては2n+2重ループが必要となるため,
> より多数の蚊取り線香について考察するには,
> もう少し工夫した方がよさそうです.
> (時間があれば考えてみたいと思います.)


この問題は初めもっと簡単に求められるかと思っていたのですが、案外数えるだけでもかなり大変な内容になってしまいました!しっかり考えてもらいありがとうございます♪たしかに66/32は見逃していましたね!あとで追加したいと思います☆

承認待ちコメント

このコメントは管理者の承認待ちです

承認待ちコメント

このコメントは管理者の承認待ちです

たけちゃんさん

> プログラムを改良し,任意の個数(n個)の蚊取り線香で実行できるようにしました.
> ただし,答えが出るかどうかは別の話です.
> 前とほぼ同じアルゴリズムを用いていて,計算量はほぼ(n!)^2に比例するので,
> nが少し大きくなっただけでも計算量は膨大になり,
> 実際に計算できるのはn=8あたりが限度です.
>
> 一応,得られた結果を報告しておきます.
> n=1,2,3,4,5までは,解答および前のコメントにある通りで,順に2,6,15,34,78通り.
> n=6に対しては174通り,n=7に対しては386通り,n=8に対しては844通りのようです.
> n=8の計算には,約1時間を要しました.
> n=9だと数日,n=10だと1年程度かかる見込みであり,
> このアプローチで解くのは現実的ではないですね.
>
> あと,最終結論だけをとりあえず修正していただいたものと思っていたのですが,
> よく見ると,その過程で「66/32」の追加もしていただいていたのですね.
> すると,最終結論の直前の「77通り」も「78通り」に直す必要があります.
> ついでの際に,よろしくお願いします.


6本から8本も計算ありがとうございます♪これをさらに手計算でしようとしたら、とんでもないことになりそうですね!

たしかに一ヶ所修正し忘れていました!ご指摘ありがとうございます☆

承認待ちコメント

このコメントは管理者の承認待ちです

たけちゃんさん

> 蚊取り線香100本の場合は,決定的な新しいアイディアがないと絶望的だと思いますが,
> 10本の場合は何とかならないものかと考えました.
> 各蚊取り線香の点火時刻が指定されれば,その蚊取り線香への操作が可能になるので,
> ・「先に燃え尽きる蚊取り線香から順に考える」ことにしても支障はない…[*]
> ことがわかり,これを用いて,かなりのスピードアップができました.
> ([*]自体はわかっていたのですが,その有用性に気付かなかったということです.)
>
> ・[*]を用いることで,蚊取り線香の考察順序が確定し,
> 実質的には同じであるパターンを多数調べていたのが解消されたこと
> ・新たに考える蚊取り線香が,既存の蚊取り線香より後に燃え尽きるようにすれば,
> (後に点火する時刻)が既存の蚊取り線香の燃え尽き時刻であるとき,
> ((まず点火する時刻)+(後に点火する時刻)+1)/2>(後に点火する時刻)となり,
> 自動的に(まず点火する時刻)>(後に点火する時刻)-1となって,
> これを満たすかどうかの判定が不要となったこと
> などから,プログラムをかなり高速化することができました.
> (それでも,1~11本で数時間かかっています.
> 12本だとかなり厳しく,13本は絶望的です.)
>
> n本のとき,計れる時間がf(n)種類であるとして,
> n=11までの結果は,(すでに提示したものも含め,)
> f(1)=2,f(2)=6,f(3)=15,f(4)=34,f(5)=78,f(6)=174,
> f(7)=386,f(8)=844,f(9)=1837,f(10)=3960,f(11)=8513
> でした.
> 用いたプログラムは次のものです.
>
> LET M=11
> LET MM=2^M
> DIM A(M),B(M),X(0 TO M),F(M*MM)
> FOR K=1 TO M
> LET KK=2^K
> LET STP=0
> 10 LET STP=STP+1
> LET A(STP)=0
> 20 LET B(STP)=A(STP)
> 30 LET X(STP)=X(A(STP))+KK
> LET X(STP)=(X(A(STP))+X(B(STP))+KK)/2
> IF X(STP)<=X(STP-1) THEN GOTO 40
> FOR I=0 TO STP-1
> LET F(X(STP)-X(I))=K
> NEXT I
> IF STP<K THEN GOTO 10
> 40 LET B(STP)=B(STP)+1
> IF B(STP)<=STP THEN GOTO 30
> LET A(STP)=A(STP)+1
> IF A(STP)<STP THEN GOTO 20
> LET STP=STP-1
> IF STP>=1 THEN GOTO 40
> LET S=0
> FOR I=1 TO K*KK
> IF F(I)=K THEN LET S=S+1
> NEXT I
> PRINT K;S
> NEXT K
> END


とうとう11本まで達成してしまいましたか!すごいです☆本問ではプログラムの助けもあったとはいえ、いつもたけちゃんさんの数学に対する熱心さや斬新な発想力には驚かされます!

スポンサーサイト

プロフィール

mm2445

Author:mm2445
アメリカ在住。日本人。
自作問題を作ることが趣味。
記事もいろんなところで書いています。

カテゴリ
アクセスランキング
[ジャンルランキング]
学問・文化・芸術
15位
アクセスランキングを見る>>

[サブジャンルランキング]
自然科学
3位
アクセスランキングを見る>>
更新率/拍手数/コメント数
開設してから現在までの
ーーーーーーーーーーーー
2017年5月までの
総拍手数: 48595拍手
ーーーーーーーーーーーー
2017年5月までの
全コメント数: 4789件
最新記事
全タイトルを表示
月別アーカイブ
06  05  04  03  02  01  12  11  10  09  08  07  06  05  04  03  02  01  12  11  10  09  08  07  06  05  04 
検索フォーム
簡易電卓
計算するとき使ってください♪
電 卓
リンク
関連記事
最新コメント
ブロとも申請フォーム

この人とブロともになる

QRコード
QR