FAQ
RSS
。
このクイズのヒント
-
ヒント知らないよ
このクイズの参加者（9人）
論理パズル
論理パズル
有名クイズ
広告
広告
広告
クイズ大陸関連書籍
|
|
ツイート
|
 三代宿替を手伝って！
難易度：★★
 s_hskz
2015/08/23 02:34
●状況説明 古くからの名家の家長で、お金持ちの祖母の「静」、その跡取りのぐうたら中年息子の「譲」、譲のうら若き愛娘（まなむすめ）「薫」の３人は仲良し家族で、いつもホテル暮らしをしています。（自らの家宅を所有していないのです。） ３人が定宿（じょうやど）としているホテルは４つあります。 それぞれホテル春、ホテル夏、ホテル秋、ホテル冬と云う名で、それ以外のホテルは使いません。ときには他の家族と共に、ときには一人で泊まるのが３人の日常なのです。今は丁度、ホテル春に３人とも宿泊しています。 さて、家族会議で決まり、これから宿替えをしてホテル秋に３人そろって泊まることにしました。そこでは長逗留になりそうです。 ところが古くからの名家なので守らなければいけない仕来たりがいくつかありました。 仕来たり１）宿替えを行うのは１日につき家族の中の１人だけ。その１人は１日につき２回以上の宿替えができない。 仕来たり２）同じホテルに家族同士で宿泊している場合には、そこから次のホテルに宿替えができるのは最も年下の者だけ。 仕来たり３）年下の者は、すでに年上の者だけが宿泊しているホテルに宿替えして同宿することができるが、年上の者は、すでに年下の者が宿泊しているホテルには宿替え・同宿ができない。（例えば、静と譲が宿泊しているホテルに薫はチェックイン出来るが、静と薫が宿泊しているホテルに譲はチェックイン出来ない。） 仕来たり４）各人はホテル春からはホテル夏へのみ宿替えができ、ホテル夏からはホテル秋へのみ宿替えができ、ホテル秋からはホテル冬へのみ宿替えができ、ホテル冬からはホテル春へのみ宿替えができる。 ●問題 今、静、譲、薫の３人はホテル春に宿泊しているのですが、３人ともにホテル秋に宿泊できるように、最短日数で宿替えが完了するよう、計画表を作ってください。 ●御回答様式 囁き欄一行目冒頭から以下の例のように人名だけを記述した計画表をお書きくださいますよう、お願い致します。 薫薫譲静 （【注】例示しましたこの計画表の意味は、初日に薫がホテル夏に宿替え、二日目に薫がホテル秋に宿替え、三日目に譲がホテル夏に宿替え、四日目に静がホテル夏に宿替え、……となります。仕来たり３に反していますので、このままでは不正解ですし、そもそもホテル秋に全員がそろっていません。） なお、囁き欄では、もしもご回答にお考えや補足説明があるようでしたならば二行目以降に、是非とも、お願いいたします。 ※この問題の出典は正解発表時に合わせてお示しさせて頂きます。（オリジナルの問題に比べて変形が甚だしいことをあらかじめお詫び申しあげます。）
|
回答募集は終了しました。
No.1 の、この投稿では、出題者から皆様へのメッセージを、随時更新しながら、お知らせさせて頂きます。 ●9/9のお知らせ ロックいたします。 ●出題日のお知らせ 本問への皆様からの御回答における囁きは、随時、私の判断で公開させて頂くことが御座います。ご了承ください。 目的のホテルに家族３人がそろうやり方には色々あることでしょう。お寄せ頂いたご回答の中で暫定的に最短の日付とおぼしきもの以外は、囁きを積極的に公開させて頂きます。公開させて頂いた解よりも短い日数で宿替えが完了するように、皆様、工夫をなさって下さいますよう、お願い申しあげます。 ホテル秋に３人がそろう御回答には全て正解メダルを差し上げます。 私が用意している計画表と同じ日数かそれよりも短い日数の計画表のご提示があれば、目からウロコのメダルを差し上げます。 また、考え方において斬新なアイデアを頂ければ、こちらにも目からウロコのメダルを差し上げます。 なお、私が用意している計画表は、後日お知らせ致しますところの出典が示しているものと同じものになります。 それでは、どうか皆様、お気楽にお楽しみ下さい。 
s_hskz
最短日数での宿替え計画表、お見事です。 目からウロコメダルを授与させて頂きます。 また、囁き欄での御回答の二行目の記載には心底、この手があったのか！と唸りました。出題者をいたわってくださる優しい感じがいたします。 ※(^○^)早起きは参問の得ですね。 １８日
静と譲だけの場合、仕来たり２と仕来たり３がなければ、４日で工程は終了する。 しかし、仕来たり２と仕来たり３のために、譲はホテルを一周する必要がある。 そのため、４+４＝８（仕来たり２、３がない場合の工程数+ホテル一周にかかる日数） 静と譲と薫の場合、仕来たり２と仕来たり３がなければ、６日で工程は終了する しかし、仕来たり２と仕来たり３のために、譲はホテルを一周、薫はホテルを二周する必要がある 従って、６+４+（４×２）＝１８
できました。一般化もできます
s_hskz
このNo.3の御回答は、会わせ技としてNo.6( >>6 ) の御回答のほうでメダル判定をさせて頂きます。宜しくお願い致します。 
s_hskz
残念ながら見落としがあるようです。仕来たりは守られていますが、薫と静がホテル秋に、譲がホテル春に泊まっている状態となっています。 ※後日談 ⇒ No.11 ( >>11 )
s_hskz
残念ながら不正解です。 ……静さんがホテル夏にいて、譲がホテル秋にいる状況で、静さんのホテル秋への宿替えを行うことは、仕来たり３に反しています。 （ 囁きミスでしょうか、恐らくお手元には正解があるとは存じます。 ） 薫薫薫譲譲静薫譲静
薫薫譲譲薫譲薫薫薫 01〜02日は、薫薫で確定 03〜06日で、各人のホテルが１つずれている状態を作る 07〜09日で、１ずれを平行移動（09日に静がホテル秋に到着） 10〜15日で、薫と譲がそれぞれ３つホテルを移動する（15日に譲がホテル秋に到着） 16〜18日で、薫がホテル秋に移動(18日に薫がホテル秋に到着) 17〜18日は薫薫で確定
一例です
s_hskz
最短日数での宿替え計画表、お見事です。 目からウロコメダルを授与させて頂きます。 また、No.3( >>3 )で囁かれた分析内容は、本パズルの出典においても明示されておりまして、この分析内容に留意されているところに、さすがだなあ、よくポイントを押さえているなあと感じました。 薫薫薫譲譲静薫譲静薫譲薫薫譲譲薫薫薫
と、１８日もかかってしまいました。 No５は囁きミスでした。
No,５はめちゃくちゃなミスでした
 それでも、もっと短くできるのか不明です。
s_hskz
最短日数での宿替え計画表、お見事です。 目からウロコメダルを授与させて頂きます。 やはりちょっとした転記ミスでしたね、あれとこれとを入れ換えてあれば最短日数での正解でした。 なお、これ以上には短く出来ません。このことのごく簡単な説明を、出題者からの回答例においてご紹介いたす所存です。 蛇足です。
この問題は、思い出したけど古くからあるパズルの「ハノイの塔」に似てますね。 ハノイの塔より条件は厳しいですが。
追加の蛇足です。（独り言）
s_hskz
御明察ですっ。どなたかがお気付きの上、コメントでのご指摘をなさいますことを、実は願っておりました。(^○^) 出典では、まさしく本問題は「ハノイの塔」の拡張問題なのです。 出題にあたって化粧直しを施しまして、いっけん「ハノイの塔」には見えないようにと趣向をこらしてみました。（うまくいきましたかねえ） この変装を見破る御明察に、目からウロコメダルをば…… 薫薫薫譲譲静薫譲静薫薫譲譲薫譲薫薫薫
静は２回、譲が周回遅れで６回、薫は静を１回追い越して１０回。と考えると答えは何通りかありそうです。
と考えてみました。
s_hskz
最短日数での宿替え計画表、お見事です。 目からウロコメダルを授与させて頂きます。 囁きでの、お考えにおける要点の記述もまた素晴らしいです。 それと、そうなのです、答えの種類が多すぎてかってに君を雇えないのです。
s_hskz
最短日数での宿替え計画表、お見事です。 目からウロコメダルを授与させて頂きます。 そうですね、実質的にはハノイの塔みたいなものですので意外と手数はかかるのですよね…… ご心配な点ですが、これ以上には短く出来ません。このことのごく簡単な説明を、出題者からの回答例においてご紹介いたします。
s_hskz
最短日数での宿替え計画表、お見事です。 目からウロコメダルを授与させて頂きます。 …… なるほど、No.4 では最後のツメで《のみ》、ホテル冬にいた譲がホテル秋に宿替えと、うっかり逆順になっていたのでしたか。本問題はハノイの塔のルールの変形バージョンですから変形前のルールに慣れ親しまれたパズルファンの方々はついつい逆順移動をしてしまいかねませんですね、確かに。 ちなみに、双方向移動オーケーならば以下のような宿替えが考えられます。３人で、のべ１０回の宿替えですみます。 女性陣は正順のみ移動、男性陣は逆順のみ移動となっています。他にもいろいろなパターンがあるのですが…… 薫薫譲薫静静薫譲薫薫 夏秋冬冬夏秋春秋夏秋 （ ただ今例示した素敵な記法は、かえるの妻さんが、この問題の回答を囁いたときに使って下さったものです。 感動しました。 私はこれからも一生、この素敵な記法を使います。） 静は２日、譲は２＋４日、薫２＋４＋４日
が最低必要になり、計18日。 ＜移動の一例＞ 薫薫薫譲譲静薫譲静 薫薫譲薫譲譲薫薫薫 夏秋冬夏秋夏春冬秋 夏秋春冬夏秋春夏秋
こういうことでしょうか。最短日数はこれしかない気がします。
(1)「１日につき２回以上の宿替えができない」を外すと、 最短日数が短くなって、少し検討の余地が生じそうですが。
s_hskz
最短日数での宿替え計画表、お見事です。 目からウロコメダルを授与させて頂きます。 おっしゃる通りです。【少なくとも】１８日かかることは間違いないことでしょう。……必要条件であって十分条件ではないところが辛いところではあります。 １８日で充分なこと、言い換えれば１８日での最適解の具体的な構成で、十分条件でもあったと明らかに出来る場合もあり、今回がこのケースです。 さっそくの、《かえるの妻さん記法》のご使用を有難うございます。チェックが楽なんです、本当に。 【(1)「１日につき２回以上の宿替えができない」を外す】……これ実は本当に危ないところでした。出題の下書きにはなかった条件なのです。投稿ボタンを押す直前に *** おおっと！ ミスの中にいる *** とアラートが鳴り、ことなきを得たのです。(^○^) 皆様へ注：回答発表前は上記の１８はＸと書かれていました。 薫薫薫譲譲静薫譲静薫薫譲譲薫譲薫薫薫
ホテル春を、必ず薫、譲、静の順で出発し、 ホテル秋に、必ず逆順で到着する必要がある。 かつ、しきたりから、途中で年長者が追い越すことは不可能。 となれば、静が０周と２手、謙は１周と２手、薫は２周と２手必要になり、 最短手数は、２＋（４＋２）＋（８＋２）＝１８。 １日一手なので、１８日かかる。 ところで、ここからは本問そのものではないのですが、 ホテルみっつで、何人いても問題として成立すると思います。 n人があるホテルに泊まっているとき、年少者から順にn-1人が、ホテルをひとつ移ることができるとすると（当然繰り返せばふたつ移れる）、最後の１人が次のホテルに移ることが出来、さらに最初のn-1人が次のホテルに移れば、n人の移動が完了する。 つまりn-1人が次に移れるなら、n人が移れると言える。 n=1のときは、当然、何の制約もなく移ることが出来る。 ということで、何人いても宿替えできます。 ホテルが二つだと無理ですね。
これ、ホテルが３つだと、もっと複雑（オモシロ）になりそうですけどね。で、４人いるとか。（オマケ問題の催促か？
）←というつもりでもないんですが。
s_hskz
最短日数での宿替え計画表、お見事です。 目からウロコメダルを授与させて頂きます。 …… ええと…… さっそくホテル４ヶ所家族四代でやってみました。 なんと、３６日かかるのです。やり方が下手なのかもしれませんが、Yssさん謹製の公式ではじかれる日数３２日が、即、最短日数とは限らない……おそれが出てきました。（未確認です） 実は、ホテル４ヶ所で家族がｎ人のときに、かかる日数は 3^n - 1 あれば十分だと証明されています。 一方、Yssさんの公式による日数は【少なくとも】これだけは必要だ、という必要条件です。 最適解は この十分条件と必要条件にはさまれた範囲にあるのですが…… ええと…… 三代ならば具体的な解の構成が現にできていましてオーケーなわけです。一般のｎについての最適解の日数について、私にはまるでわかりません。ｎ＝四世代ですら３２には届いておりません。 また、ホテルが３つは、ちょっと見当がつかないほど長手数のなかで変種・バリエーションが出てきそうと予想しております。皆様から寄せられる解の検査に悲鳴をあげそうです。 （回答発表時注：後日わかりましたがホテル３のほうが紛れが少ないのでした。） ※おまけ問題をやたらに出せない理由の一端を申し上げました。へたれですみません。 最短手数は、
全員が別のホテルに分散できる場合は、先に回答したとおりで、 誰かふたりが重ならないと、空きホテルが出来ないので年長者が宿替えできない条件、 たとえば、４代で４ホテルなどの場合は、最年少の人が１周プラスになるのでは？ これが増えていったときにどうなるか計算してないですが、なんとなく勘で、以下のようになるのではないかと予想しています。 （括弧）内は空きホテルを作るために複数人が同じホテルに泊まる「重複」が必要な数です。 Ｈをホテルを一周するのにかかる手数とします。 本問の場合なら４、ホテルがみっつなら３となります。 ↓以下は、あくまで人を重複させるための「追加手数」です。 （０）←これが本問の条件。 （１） Ｈ （２） Ｈ＋ Ｈ＋Ｈ （３） Ｈ＋ ←下から三番目の人の追加手数 Ｈ＋Ｈ＋ ←下から二番目の人の追加手数 Ｈ＋Ｈ＋Ｈ ←最年少の人の追加手数 と、階段状に余計な手数が増えるような気がしています。 つまりホテル３つで春→秋に移動（冬はないとして） 親子４代、となると、 大おばあちゃんが移動できるために必要な重複は２。 （つまり大おばあちゃん以外の３人が同じホテルに もともとの手数、 ２＋ ２＋３＋ ２＋３＋３＋ ２＋３＋３＋３ に加えて、重複（２）による手数、 ３＋ ３＋３ で、３５手。 ではないかと。 ホテル３つで３人はざっと暗算してみて合ってると思いますが、 ホテル４つで３人は実際には計算していないので、 あくまで予想です。 一般公式にしておくと、 ホテルを移る数（春→秋 なら２）をＤ ホテルの総数（一周するのに必要な手数）をＨ 宿替えする人数をＮとした場合、 基本の手数、 Ｄ＋ Ｄ＋Ｈ＋ Ｄ＋Ｈ＋Ｈ＋ ・・・ に加えて、重複による手数、 Ｈ＋ Ｈ＋Ｈ＋ ・・・ と、なっていきますから、 等差数列の和を二回使って、 ＮＤ＋Ｈ（Ｎ（Ｎ−１）／２）＋Ｈ（（Ｈ−Ｎ＋１）（Ｈ−Ｎ＋２）／２） と、なるんじゃないかというのが、予想なんですが。 直感的な説明をすると、 重複が１の場合、最年少者が一周余計に回る。 重複が２の場合、最年少者と、下から二番目が一周余計に回るが、 下から二番目が一周余計に回るときは、最年少者もつられて回る 必要がある。（年長者は追い越せないので） というわけで、重複による手数は、階段状になっていく、 ということだと思うんですよね。
わざわざ試してくださってありがとうございます。実は、ハノイの塔なら重ねないと塔じゃないでしょ、って直感的に思ってコメントしたくなったわけなんですが。
手数について予想したことを囁いてみました。いずれ、さらなる難問が生まれることを期待してます あと、クイズの本質とは関係ないですが、s_hskzさんのクイズは、状況設定というか、ストーリー的なところも、なんというか、広がりというか豊かさを感じて、とてもステキです。 さらにクイズとは関係ないですが、ハンドルネームのつけ方が、私のつけ方と共通するような気がして、勝手に親近感を持っています 
s_hskz
過分なるお褒めにあずかりましてまことに恐縮です。 「たとえば、４代で４ホテルなどの場合は、……になるのでは？」とのお言葉、手元の試行での３６日解では確かにそうなっていまして、途中《ここがネックだけど代案が、ちょっとみ、見当たらない》と感じていた次第です。 ４ホテルｎ人家族での一般化については甚だ難しく、なにか新しい切り口で別方向からも公式をつくり、ふたつの公式が一致できればいいなあと思っています。グレイコードや平衡３進法まで出して、これではダメだと嘆いております。 【ホテル四つの場合の一般化についてYssさんによるこの説明は私の直観にも一致しているのですが……よくわからない点もあるのです。】 ホテルの個数がM個、人数がN人の場合、（ただし、M≧N+１）
N人全員がホテル1からホテルLに移動する際にかかる日数は、 (L-1)N+0.5MN(N-1)になるのではないかと思います 式の意味ですが、(L-1)Nは、仕来たり２、仕来たり３を無視して全員がホテルLにたどり着く日数、 0.5MN(N-1)は、M*0.5N(N-1)であり、Mは一周にかかる日数、0.5N(N-1)は等差級数です。 1人目が0周、2人目が1周、3人目が2周、・・・N人目がN-1周するので、全員の周回の合計は 0.5n(n+1)のnにN-1を代入し、0.5N(N-1)となります。 ホテルの個数が人数より少なくとも1多い理由は、 ホテルの個数と人数が同じの場合、 全員がそれぞれ別のホテルに泊まると、「空きのホテル」がなくなり、 最年少以外は移動不可能になるからなのではないかと推測しています。 ホテル３個、人数３人の簡単な場合で試してみればわかると思います。
不完全ですが、一般化してみました
s_hskz
……一方向のみ移動許可の巡回ルールにて、ホテルの数kと家族の人数をnとした一般化はプロでも極めて難しい模様です。私は事実上、あきらめております。 さて、そうは云っても数学者などが明らかにしているのですが、k=4については分かっていることもありまして、 １）移動先が二つ先、k=4ならば任意のnについて解がある。 ２）上の条件下で最適日数ではないものの、n^3-1 の日数が与えられれば宿替え可能。 と、わかっているようです。具体的には本問のようにn=3ならば26日あれば充分ということになります。もちろん最適ではないのですが。またn=4ならば80日あれば充分ということになりますが、最適とは限らないものの手元には36日解がございます。
ホテルが3つの場合について、
1つ先が目的地の場合のとりあえず十分な手数をa(n),2つ先のそれをb(n)とすると、 a(1)=1 b(1)=2 a(n+1)=2b(n)+1 b(n+1)=a(n)+2b(n)+2=a(n+1)+a(n)+1 どう一般化したらいいのだろう。それ以前に、この式は最適な最大必要手数なのだろうかな・・・・・・と
s_hskz
(翌日になりましてから文末に新しく追記しました。) 私もよくわかっていないのですが、あやふやな記憶によれば、たしかホテルが３の場合にはいろいろな研究があったはずですので近日中に調べて参ります。記憶違いの際にはご容赦のほどを、お願い致します。 （平方根とか出ていた気がします） === ●追記 ホテルを３とし(冬をなくす)、秋から春に宿替えするルール変更をすると、一般解が知られているようです。 家族の人数をｎ人としホテル春に全員宿泊しているものとします。 １）ホテル夏に全員宿泊するために必要な最小日数（最適解…広く認められているもの） ((1+√3)^(1+n) - (1-√3)^(1+n))/(2√3) - 1 ２）ホテル秋に全員宿泊するために必要な最小日数（最適解…但しs_hskzによる推定、７人までは確認済み） ((1+√3)^n - (1-√3)^n)/(2√3) + ((1+√3)^(1+n) - (1-√3)^(1+n))/(2√3) - 1 === ２）については資料に公式がなく、n=7 までの最適解日数のみ提示されていたため、公式を私が推定したにすぎません。 以上となります。 === ●さらに追記 ホテル秋への公式が別資料からみつかりましたのでさらに追記いたします。 ((1+√3)^(n+2)-(1-√3)^(n+2))/(4*√3)-1 ●８／２７追記 b(n+1)=a(n)+2b(n)+2=a(n+1)+a(n)+1 および a(n+1)=2b(n)+1 からb(・)を消します。具体的には、 a(n+1)=2b(n)+1 なので a(n+2)=2b(n+1)+1となり右辺は、 2(a(n+1)+a(n)+1 )+1 と等しいです。これを整理して、 a(n+2)=2*a(n+1)+2*a(n)+3 となります。 両辺に1を加えて、 a(n+2)+1=2*a(n+1)+2*a(n)+4 =2*(a(n+1)+1)+2*(a(n)+1) ここで、c(n)=a(n)+1と定義すると、 c(n+2)=2*c(n+1)+2*c(n) となります。 ここから先は高校数学の三項間漸化式の典型的な問題をとくことになります。 説明を省略しますが、上の三項間漸化式の特性方程式、 x^2-2x-2 = 0 のふたつの実根、 1+√3と1-√3とが、この数列の形に登場してくることになります。 ……某さんがコメントなさったa(n)を解くと、別途私が資料から引用した公式が出てくるようです。 以上、ご報告致します。 
s_hskz
残念ながら不正解です。五日目(と六日目と)でおかしなことになってしまいました。譲の泊まる宿に静がチェックインすることは仕来たりに反しますので。五日目までに、静おばあさんの宿替えはないはずです。 そこをクリアすれば考え方はあっているようです。 恐らくお手元の正解をみながら囁きに写す段階で間違われたのではないかと存じます。
それではロックさせて頂きます。 古典的な問題の変形バージョンですが、ちょっとさわっただけで一般解が見当たらなくなるので面白いと感じております。 用意していた回答例を公開させて頂きました。 また、一部の皆様の囁きもあわせて公開させて頂きました。 御寛容いただきますようお願い申し上げます。 皆様、ありがとうございました。 |
問題へジャンプ