数理パズル１０－５
490 名前：１３２人目の素数さん[] 投稿日：2005/11/01(火) 17:58:20
前前スレ814の問題を考えてたんだけど555個でいいんでしょうか？
http://www3.tokai.or.jp/meta/gokudo-/omoshi-log/1074751156.html
バナナを消費するタイミングが書いてないので誤差があるかもしれないけど。
よろしくお願いします。
492 名前：１３２人目の素数さん[sage] 投稿日：2005/11/01(火) 21:01:35
転載しましょ。答えでてないしね。
814 名前：１３２人目の素数さん ：04/08/23 23:11
これぞまさに「面白い問題」かな
：問題
あなたは１０００ｋｍの砂漠を横断して隣町まで行きます
今３０００個のバナナを持っています
１ｋｍ毎に１個のバナナを食べないと死にます
一度に運べるバナナは最大で１０００個です
この状況で、あなたは最大何個のバナナを隣町まで運べるでしょうか？
これで意味わかる？
つまり最初に１０００個のバナナを運んで、途中に置いて、一旦戻ってまた行かないと隣町に着いても全部無くなる
まず、最初に１０００個のバナナを運ぶ
途中の地点にバナナを何個か置いていく
その後引き返す（引き返している間にもバナナを食う必要がある）
そしてまた１０００個のバナナを持って旅立つ
途中で置いておいたバナナを補給する
そんな感じ
考えてくだせえ
解答
491 名前：１３２人目の素数さん[sage] 投稿日：2005/11/01(火) 20:47:29
>>490
確かにバナナの消費タイミングを厳密に決める必要があるな。
たとえばこんな感じか？
・道中には1キロごとに石碑が立っていて、バナナを保存できるのはその石碑のところだけとする。
・また、進むか引き返すかを選択できるのも石碑地点だけとする。
・さらに、バナナを食うのは必ず石碑と石碑の中間点とする。
つまりn本のバナナを持って石碑を出発すれば、次の石碑までは引き返すことはできず、
次の石碑で手持ちバナナはn-1本になっている。
もし空手で出発すれば、たとえ次の石碑に山のようなバナナが保存してあっても、
途中でのたれ死ぬ。
‥とか設定した上で、行程10キロ、バナナ30本、最大手持ち10本
くらいに単純化して考えてみてはどうだろう。5本いける？
493 名前：490[sage] 投稿日：2005/11/01(火) 21:14:37
つまり1キロずつに区切ってその間にバナナを食い始め、食い終わるわけですね。
ということは1本持ってスタートして1km地点で折り返した場合、
スタート地点についてからそこにあるバナナを食べるのではなく帰り途中に死んでしまう、と。
＞‥とか設定した上で、行程10キロ、バナナ30本、最大手持ち10本
＞くらいに単純化して考えてみてはどうだろう。5本いける？
同じ考え方でやってみたところ3本しかもっていけないという結論になったけど・・・。
どうしても余りが出るんだけどしかたないのかなぁ？
494 名前：１３２人目の素数さん[sage] 投稿日：2005/11/01(火) 21:42:48
「行程10キロ、バナナ30本、最大手持ち10本」の設定で、
「常に全てのバナナを次の地点に運ぶ」という作戦（*）でやると、4本はいけるよ。
(*) バナナが3点以上に分散しないようにする作戦。たとえば最初は、
スタート地点と1キロ地点を往復して、全てのバナナを1キロ地点に集める。
それには2.5往復必要なので、結果1キロ地点に集まったバナナは25本になる。
以後繰り返し。
5キロ地点で1本捨てることになるのがもったいない。何とかならんかねえ。
495 名前：490[sage] 投稿日：2005/11/01(火) 22:04:04
ああ、4本のまちがいだ。
でも>>493のやり方で5m地点まで1mずつもってくと5m地点に11本あつまるから
そこから10本もってゴールに直行すれば5本行ける？
496 名前：１３２人目の素数さん[sage] 投稿日：2005/11/01(火) 22:11:33
結局>>492の問題で>>491の解釈のもとでの現在わかっている可能な最大数っていくつ？
現時点で｢n本までは可能｣が証明できた最大の数って結局いくら？
みんなどれぐらいの答えもってるの？
497 名前：１３２人目の素数さん[sage] 投稿日：2005/11/01(火) 22:51:30
[1] 1,000本のバナナを 持って 1本食って 1km 先に行き、
帰りに食う1本を抜いて998本置き、出発点に戻る。
[2] また 1,000本持って 998本置いて、出発点に戻る。
[3] また 1,000本持って1本食って 1km地点に行く。
到着したとき、バナナは 998+998+999=2,995本。
[4] 1kmを2往復半して運ぶのである。
1km進むごとにバナナは 5 本ずつ減っていく。
[5] 1,000÷5＝200
200km 進んだとき、バナナは 2,000本になっている。
[6] ここからは1往復半して運べばよい。
[7] 201km地点には 1,997本運べる。
つまり、1km 進むごとに 3 本ずつ減る。
[8] 1，000÷3＝333 余り 1
200＋333＝533 km地点には、1,001本のバナナを運べる。
[9］ もったいないが、1本は沙漠に残し、1,000本積んで
ゴールをめざす。1 km進むごとに1本消費する。
[10]残りは 1,000－533＝467 km である。
1,000本のうち 467本食ってしまうから、
到着時には 533本が残る。
499 名前：１３２人目の素数さん[sage] 投稿日：2005/11/02(水) 15:24:39
考え方がわかってきたような。
1. 途中のある地点まで1000本もってスタートし、
戻るのに必要な本数を除いたあまりをすべて置いてくる、というプロセスを3回繰り返すとすると、
スタート地点からxメートル地点に全てのバナナを運ぶと
(1000-2x)*2+(1000-x) = 3000-5x 本のバナナを運ぶことができる。
ちなみに1mずつ2.5往復して運ぶのを繰り返したとしても結局
それぞれの1km区間について2.5往復しているので結果は同じ。
2. このとき、x>=200だと運べるバナナの本数が2000を切るわけだが、
2000を切るということは、ある一部分の区間について2.5往復という手間を省くことができる。
200を超えるxメートル地点に全てのバナナを運ぼうとした場合、
単純にそこまで2.5往復するよりも、一度200m地点に2000本のバナナを集め、
そこから1.5往復すれば、200mを越える区間について1往復分のバナナ消費量を省くことができる。
従って、200m地点から200+yメートル地点に運ぶことができるバナナの本数は
(1000-2y)+(1000-y) = 2000-3y
500 名前：499[sage] 投稿日：2005/11/02(水) 15:25:01
3. 同様にして、ある地点に運べるバナナの本数が1000本を切る場合も
一部の区間について消費量を省くことができる。
y>334だと1000本を切るので、(200+333)mを超える区間にバナナを運ぶ場合は
533m地点にバナナ（1001本）を集めてそこから片道で運ぶのが最も効率がよい。
また、これ以上は引き返してバナナを補充する必要がないので（1本だけ残る）
あとはゴール地点に行くだけである。
従ってゴールに運べるバナナの本数は
1000-(1000-533) = 533本
502 名前：１３２人目の素数さん[sage] 投稿日：2005/11/02(水) 18:18:59
問題もうすこし数学的に書きなおすと
非負整数からなる有限数列(ai) (0≦i≦1000)と0≦i≦1000の組
(i,ai)に次の操作がゆるされている。
操作I
i<1000のときaiをai-k、a(i+1)をa(i+1)+k-1におきかえiをi+1におきかえる。
ただしkは1≦k≦ai,1000をみたす整数
操作II
i>0のときaiをai-k、a(i-1)をa(i-1)+k-1におきかえiをi-1におきかえる。
ただしkは1≦k≦ai,1000をみたす整数
でaiをa0=1000、ai=0 (i>0)とおいて組(0,ai)に操作I、操作IIを何回かくわえてえられる組
(1000,bi)におきかえることができるもののなかでb1000の最大値をもとめよ。
とかになると思うんだけど。
ほとんどあきらかに操作Iではk=min{ai,1000} (つまり進むときは常に運べるだけ運ぶ)
かつ操作IIではk=1 (つまり戻るときには１本だけもってもどる)
に限定してもよさそうにはみえる。しかしどうやって証明していいかもわからんし。
操作IIを２回連続しない解のなかに最大値が存在するのもあきらかっぽいんだけど
どうやって証明すりゃいいかわからんしorz。
503 名前：499[sage] 投稿日：2005/11/02(水) 19:15:06
証明ではないけど自分なりの解法ということで。
ただ、バナナが2001～3000本残っていたら全てを運搬するのに2.5往復せざるをえないし、
1001～2000本残っていたら1.5往復する必要がある。
（放置するなら別だけど。）
533本以上バナナをゴールに運ぶということは道中のバナナの消費量を抑えなければいけない、
すなわち移動量を減らす必要があるけど、
これ以上に効率のよい歩き方というのはないといっていいんじゃないかなぁ？
504 名前：１３２人目の素数さん[sage] 投稿日：2005/11/02(水) 19:32:51
>>503
それはオレもおもった。>>497の解は全部で2466工程で1本を砂漠に残してる。
運べる本数は3000-工程数-砂漠に残した数。結局534本はこべるとすれば
工程数が2465工程未満か2466工程で砂漠に残さないか。
どっちでも不能といえばいいんだけど。
505 名前：１３２人目の素数さん[sage] 投稿日：2005/11/03(木) 01:14:06
533km地点に1001本のバナナを運んだ時点で
533+1/3km地点まで一往復半して
533+1/3km地点に1000本のバナナを置くことが出来るので
そこから残り全部持っていけば466km進んだ時点で
残りの距離は2/3km、所持バナナ数534、あとの工程では
進む距離は1kmに満たないので534本運べる。
508 名前：１３２人目の素数さん[sage] 投稿日：2005/11/03(木) 02:04:06
>>505
なるほど。行動を1kmごとって縛りをぬけば1本のこらずはこべるのか。むしろこの問題は
｢>>492の問題文には1kmごとに行ったり着たりしないといけないとは一言もいってないでしょ？｣
ってとこがミソなんだな。まあちょっと数学的な面白さといえるかどうか微妙だけど。
で後はこれがホントに最大ですかってとこだな。
509 名前：１３２人目の素数さん[sage] 投稿日：2005/11/03(木) 10:12:30
まずはじめに、この問題の中で引き返す動きが得になりうるのは
引き返した先においてきたバナナがあって、
それを回収しに行く場合以外には考えられない。
よって、先に進むときは常にもてるだけもって行き、
引き返すときは引き返したい地点まで行って帰ってくるのに
餓死しない最低限だけ持っていくというのが最善である。
また、置いてきたバナナはその地点までの往復の距離よりはたくさんないと
取りに行く意味がないので、実際には引き返す際に携えるバナナは
片道の距離移動するのに餓死しないだけの本数となり、
引き返し始めるときの、「次にバナナを食べるまでに歩く距離」をx,
片道の距離をyとすると、[(1-x)+y]本あればいいことになる。ただし[ ]はガウス記号。
次にこの問題では、残バナナ数が2001本以上3000本以下の間と
1001本～2000本の間ではそれぞれ、大まかに動いても小刻みに動いても損得は変わらない
大まかに動くというのは、例えばいきなり200km地点まで2.5往復するような場合。
1000本持っていく→600本置いて引き返す→
1000本持っていく→600本置いて引き返す→
1000本持っていく→200km地点に2000本置ける
小刻みに動くというのは、例えば200m先まで2.5往復を1000回繰り返すような場合。
1000本持っていく→1000本置いて引き返す→
1000本持っていく→1000本置いて引き返す→
1000本持っていく→200m地点に2999本置ける
よって、残り工夫する余地があるのはワンセットの運搬でバナナの残り本数が
2001以上から2000以下の間をまたぐかどうかだが、これは少し考えれば
1.5往復で済ませられる所を無駄に2.5往復するだけになるので損。
したがってこれ以上効率よく運ぶことはできない。
510 名前：１３２人目の素数さん[sage] 投稿日：2005/11/03(木) 11:28:11
＞2001以上から2000以下の間をまたぐかどうかだが
残った問題は、こういう数字を誰が想像出来るかってことだけだな。
511 名前：１３２人目の素数さん[sage] 投稿日：2005/11/03(木) 20:36:25
ん？ バナナの問題って、解決不能じゃなかったっけ？（「ビューティフルマインド」に書かれてた）
512 名前：１３２人目の素数さん[sage] 投稿日：2005/11/03(木) 22:36:48
解決不能ってことはないでしょう。あたえられた問題に対しては
考えうる組合せは有限なんだから、最悪全通り調べれば答えはわかるはず。
