FAQ
RSS
このクイズのヒント
-
ヒント知らないよ
このクイズの参加者（3人）
算数・数学クイズ
算数・数学クイズ
広告
クイズ大陸関連書籍
|
|
ツイート
|
 テイク・ファイブ
難易度：★★★
 s_hskz
2015/09/24 01:05
舞台は、とある田舎の小さなjazzバー。７席あるカウンターで仲良し男子５人組、Ａ、Ｂ、Ｃ、Ｄ、Ｅが並んで座って、カウンターの中のマスターと馬鹿話をしながら，したたか飲み、騒いでいました。jazzそのものも熱狂しております。 最初、仲良し５人組はこのように席についていました。（『…』は空席を表します。） [Ａ、Ｂ、Ｃ、Ｄ、Ｅ、…、…] エンモタケナワ。 ２人が腕組みをしてから立ち上がり、連れションに行き、店を出て路上に出て、そのままの腕組みをしたまま、（器用ですね）立ちションをし、そのままの腕組みをしたまま、店に帰り、再びカウンターの空席につきました。（カウンター内のマスターに向き合ってです。）そしてその２人は腕組みを解き、乾杯するのでした。 そのままの腕組みと言えば、本当に立ち上がる前のそのままで、空席についてから腕組みを解いたのでカウンター席での左右の位置取りは変わりません。 腕を組むときには２人の間に空席はないものとします。着席時にも空席をはさまない隣同士で座ることとします。 全く同じように連れションが何度かおこなわれました。 ふと気がつくと彼らは[Ａ、Ｂ、Ｄ、Ｅ、Ｃ、…、…] と並んで座っていました。席を立つのが連れション以外になかったとすると、最低何回、連れションが起きていたでしょうか。その回数と、各回ごとの連れションのペアおよび着席場所を特定してください。 御回答にあたっては、たとえば以下のように記述することをお願い申し上げます。 ０：[Ａ、Ｂ、Ｃ、Ｄ、Ｅ、…、…] １：[…、…、Ｃ、Ｄ、Ｅ、Ａ、Ｂ] ２：[Ｅ、Ａ、Ｃ、Ｄ、…、…、Ｂ] 以下同様に。ゴールは、 ？：[Ａ、Ｂ、Ｄ、Ｅ、Ｃ、…、…] です。 なお、最小の回数であることを証明する必要はありません。いろいろやってみたけどこれ以上少なくなりそうにないという感触があれば十分です。 （お下劣ですみません。出典ではマトモなパズルなのです。） 【本質的にクイズ大陸既出ならば、どうかご指摘くださいますようお願い申し上げます。】
|
回答募集は終了しました。
No.1のこの投稿は、出題者からのお知らせ用に使わせていただきます。随時更新することがあります。 【最新ステータス】 ・（１０／１４） スレッドをロックいたしました。 【ステータス履歴】 ・（１０／９） 回答を締め切りました。 ・（９／２８） 表題をJazzの名曲（五拍子）の名前にに変えました。こっそりと、もっとイイ、タイトルを緩募いたします。 今、ロックの１９拍子のタイコを叩けるように日々あせっております。 ・（９／２４朝）問題文に不備がありました。青文字で追加いたしました。申し訳ありません。 ９回の解の、一例をあげます。 ０：[Ａ、Ｂ、Ｃ、Ｄ、Ｅ、…、…] １：[Ａ、Ｂ、…、…、Ｅ、Ｃ、Ｄ] ２：[Ａ、Ｂ、Ｅ、Ｃ、…、…、Ｄ] ３：[…、…、Ｅ、Ｃ、Ａ、Ｂ、Ｄ] ４：[Ｃ、Ａ、Ｅ、…、…、Ｂ、Ｄ] ５：[Ｃ、Ａ、Ｅ、Ｂ、Ｄ、…、…] ６：[Ｃ、Ａ、…、…、Ｄ、Ｅ、Ｂ] ７：[Ｃ、Ａ、Ｄ、Ｅ、…、…、Ｂ] ８：[…、…、Ｄ、Ｅ、Ｃ、Ａ、Ｂ] ９：[Ａ、Ｂ、Ｄ、Ｅ、Ｃ……]
s_hskzです。 最小手順かどうか確証をもてませんが、一例を囁いておきたく存じます。 
s_hskz
囁きを公開しました。 本問題については以下を参考にさせて頂きました。 ■出典 『鴛鴦の問題とその拡張について』 ( h◎◎p://www.ed.ehime-u.ac.jp/~hirata/publish/120904-hirata.pdf ) 最短で９回だと思います。
始．ABCDE・・ １．AB・・ECD ２．ABEC・・D ３．・・ECABD ４．BDECA・・ ５．B・・CADE ６．BCA・・DE ７．・・ABCDE ８．AB・・CDE ９．ABDEC・・
なんとか解けました。
腕組みしながら行くとは、真の臭い仲でしょうか。 
s_hskz
きたちゃさん、大正解です。No.2に囁き投稿した私の解とは異なるフレーバーでして別解探索趣味をもつ私としては、ものすごく幸せです。 有難うございました。４手めからは未知の世界でした。 （ちなみに手数はNo.2で用意致しました解と同じです。） やんややんや（死語？） 追伸。確かに臭い仲ですね。田舎の小さなバーですからトイレは１人用のが１基据えられていただけとの裏設定です。 っていうかコイツラ手も洗わずに乾杯しやがります。お下劣。（この件、３分前に気がつきまして愕然とした出題者であります。） 私が考えたルートは、最短ではないかもしれないですが、
とりあえず、一旦ゴールにたどり着こうというもの。 空席を@で表したとして、 ABCDE@@ AB@@ECD と、このように席が離れると、動かせる場合の数が 極端に減ります。そこで、一旦全部左詰にすること にすると、続けて、 @@ABECD CDABE@@ と、ここまで３手で、AB⇔CDが実現したことに。 ３手一組で、ふたり⇔ふたりが入れ替わる操作は、 実は３種類しかなくて、 12345@@ から始まって、（12345はそのときの ABCDEのいずれかを表す） 1が不動となる14523@@ （交換操作１） 3が不動となる45312@@ （交換操作３） 5が不動となる34125@@ （交換操作５） のみっつ。 また、同じ操作を二回繰り返すと（当然）元に戻るので、 ふたり⇔ふたりを入れ替える操作は、前回と違う操作を しなければならない。 入れ替わるふたり＋ふたりを[]でくくって表現すると [AB][CD]E ↓３手 （交換操作５） [CD]A[BE] ↓３手 （交換操作３） [BE][AC]D ↓３手 （交換操作５） [AC]B[ED] ↓３手 （交換操作３） [ED][BA]C ↓３手 （交換操作５） B[AE][DC] ↓３手 （交換操作１） [BD]C[AE] ↓３手 （交換操作３） A[EC][BD] ↓３手 （交換操作１） ABDEC ２４手で完成。 すべて左詰なので空席は省略。 課題。これで最短かどうかはっきりしない。 最短ルートがまだあるとすれば、 左詰だけでなく、右詰をうまく活用していくもの になるのではないか。
とりあえずたどり着きましたが・・・手数については自信なし
s_hskz
この登坂ルートはとてもとても景色がよいですね。王道を行く手法をお使いになられたからでしょうか。 ルービックキューブを群論的に解く本を読んだことがありますが、ちょうどYSSさんがおやりになったような奇麗な仕掛けに満ちていました。必ず目的地につけることを示すものでした。 ところで、YSSさんの解のパーツをじっとみつめておりますと、大略、以下のショートカットがあることに気がつきました。 [ABCDE--] [BADCE--] [--DCEBA] [--DECAB] [ABDEC--] ただ今示したものよりも更にまだいけます。よろしければ手数を減らしたルートも探索してみてくださいませ。 解は一通りだと思ってたら、まだあったんですね。ということで、４手目からやってみました。
始ABCDE・・ １．AB・・ECD ２．ABEC・・D ３．・・ECABD ４．CAE・・BD ５．CAEBD・・ ６．CA・・DEB ７．CADE・・B ８．・・DECAB ９．ABDEC・・ ４手目以降は、こうなるのでしょうか。 また、証明が必要ないということだったので、楽しめました。 証明するのであったら、お手上げでした。
解は一通りだけだと思ってたら、４手目以降 別のペアでの連れしょんがあったんですね。
もしかして、一手目から別のペア順があるかもしれませんが、私には分かりません。 それから、一基のトイレって・・・読んでるうちに匂ってきそうでした。
s_hskz
正解です。No.2で私が囁いたものと全く同じです。 …実は初手から異なる解もあります。そちらも同じ手数でして出典に記載されているものです。 ＞ におってきそう はい。(>_<) 表記法：
[AB][CD]（[]でくくられた組の両方が人の場合）は、 [AB]が席を立ち、空席へ、 元ABのいたところに、[CD]が移る 元CDのいたところに、[AB]が移る という三手をかけた、ふたり⇔ふたりの位置交換操作。 [AB][@@]（[]でくくられた組の片方が空席の場合）は、 [AB]が席を立ち、空席へ移動する、 という一手の操作。 念のため、配置のあとに１または３の数字を記載。 これがその配置から、次の配置へ移す際の手数。 [AB]CDE[@@] 1 @@[CD][EA]B 3 [@@]EAC[DB] 1 D[BE][AC]@@ 3 DAC[BE][@@] 1 [DA]C[@@]BE 1 @@[CD][AB]E 3 [@@][AB]CDE 1 AB[@@]C[DE] 1 ABDEC@@ これで１５手。
だいぶ短縮出来ました。
私はにおいよりも、よくもまあ、そう何度もトイレに行けるなぁ、という方に感心（というかあきれた）してたのですが・・・
s_hskz
改善、いい感じですね。 離席回数はまだまだ減らせます。よろしければチャレンジをお願いいたします。 ええと…？ 手数×２÷５が、ひとりあたりの平均トイレ回数でしたか……確かに多すぎですかね……
「私はこのように遊んでいます」ということを例題を通じて書いてみたいと思います。 ■例題 [ABCDE--] から [ACDBE--] への、短めの手順を作ってみます。 ■こんなふうに スタートとゴールとを見比べます。 [ABCDE--] [ACDBE--] AとEと空席の位置が一致しています。Bがいた席にCが、Cがいた席にDが、Dがいた席にBが、移動しています。三すくみの循環です。これらの観察をもとに、例えば、以下のようなものを書き留めます。 [AbcdE--] [AcdbE--] AとEとに注目していくためにマークをつけることがポイントです。 次に、スタートから始めて、適当にランダムに離席着席を何回か繰り返します。 0:[AbcdE--] 1:[A--dEbc] 2:[AdE--bc] 3:[--EAdbc] 今回はたまたまこの形になにかあれば良いなとヤマカンを働かせて 3:[--EAdbc] あたりで止めておきます。大事なことは、AとEとの位置関係に着目することです。かたちとしては以下が重要と捉えておきます。 [--EA???] ???にはあまり重きをおかず、AとEとが、この位置関係となることを目標に、再度、スタートから始めて、もうひとつの別の手順を作っていきます。ほどなくして次のようなものが得られました。 0:[AbcdE--] 1:[--cdEAb] 2:[cd--EAb] 3:[cdEA--b] 4:[--EAcdb] （[--EA???]の形を狙って作りにいっています。） これで二通りの手順が出来ました。ゴールを比べてみます。 [--EA???] [--EAdbc] [--EAcdb] ???の中身が、かたや dbc で かたや cdb なのですが、これがイイんです。却って一致してもらったら困ります。 最初の手順と次の手順とで、AとEとの位置、空席の位置は一致していて、??? の位置には差違がある、これを利用して、当初の問題を解きにいきます。 ２番目の手順の、bcdを適宜入れ換えて、２番目の手順のゴールが最初の手順のゴールと一致するようにします。 0:[AcdbE--] 1:[--dbEAc] 2:[db--EAc] 3:[dbEA--c] 4:[--EAdbc] これでほぼ、もとめる解がみえました。 書き換えられた２番目の手順を、さらに逆順にします。 4:[--EAdbc] 3:[dbEA--c] 2:[db--EAc] 1:[--dbEAc] 0:[AcdbE--] これを、最初の手順の後に継ぎ足します。 0:[AbcdE--] 1:[A--dEbc] 2:[AdE--bc] 3:[--EAdbc] 4:[--EAdbc] 3:[dbEA--c] 2:[db--EAc] 1:[--dbEAc] 0:[AcdbE--] （中継点（[--EA???]で折り返しているイメージですね。これでスタートから始まり中継点でAとEとの位置がずれていたのが再び最初の位置に戻りました。） さらに整理して、以下の７手の手順にたどりつきました。 0:[AbcdE--] 1:[A--dEbc] 2:[AdE--bc] 3:[--EAdbc] 4:[dbEA--c] 5:[db--EAc] 6:[--dbEAc] 7:[AcdbE--] 今回はたまたま適切な中継点をみつけることができたように書いていますが、実際にはトライアンドエラーを繰り返しています。遊びですのでこれもまた楽しいですね。 以上で、「私はこのように遊んでいます」ということを例題を通じて書いてみました。 さて、本問題のテイク・ファイブでは手数はいかほどになるでしょうか。 【追記】:No.3 と No.5 とで、きたちゃさんは ４手めまで同一の２つの解をご提示になりました。 No.3の解を頂いたときに、出題者はとても驚きました。おそらく、きたちゃさんも私の驚きに共鳴していただいたのではないかと思われます。 「これだけの手数のなかで４手めまで同一、しかも中継点が異なる２通りの解があるなんてっ」私のビックリを、のちほど、回答発表の折りに、皆さんにシェアできないかなあと存じまして、この投稿を準備いたしました。 さて中継点が異なる複数解があるということは、まだ解の構造に余裕度がある兆候なのかもしれません。こうなって参りますと、No.2で私が用意した解の手数よりも短いものがあるかもしれないと疑心暗鬼になってきます。今、試行錯誤しております。 |
問題へジャンプ