超難問なんですが数学詳しい方わかりますか？

質問

ちょっと知人に聞かれてさっぱりなんですが
数学なんですが以下のようなものです
「私たちの店のシェフは不器用で、パンケーキを焼くと、みんな違った大きさになり　積み上げると変な風になってしまう　だから　私がお客さんに出すとき　テーブルに行くまでの間に、１番小さいパンケーキが１番上にきて　１番下に１番大きいパンケーキがくるように何枚かずつ並べ替えます　パンケーキがｎ枚あるとすると　１番上から１番下まできれいに揃えるには最大何枚並べ替えなければならないか？」

ビルゲイツがハーバード時代に解法に寄与したという問題です
つもりとけなかったらしいです　当時のハーバードの教授も解けなかったそうです　今は解がでているかわかりません

回答No.8

stomachman · ベストアンサー

ANo.7 stomachmanです。
　他の回答に付けられたコメントを読んでいたら、引っこ抜いたブロックを裏返して載せる、という手もアリだと気がつきました。
つまり「手」とは、山
p = p[0]…p[i-1]p[i]p[i+1]…p[j]p[j+1]…p[n-1]
を
q = p[i]p[i+1]…p[j]p[0]…p[i-1]p[j+1]…p[n-1]　(0＜i≦j≦n-1)
に変換するか、もしくは
r = p[j]…p[i+1]p[i]p[0]…p[i-1]p[j+1]…p[n-1]　(0≦i＜j≦n-1)
に変換すること。
　この手を認めると、逆順の山はもちろん１手で整列できてしまう。

　なるほど、この場合に最短手数を求めるとなるとメンドそうですね。アプローチとしては、
(1) （ANo.7 の[1]にある「異常度」のような）「山の混乱度合いを測る尺度であって、変換によって最良でも1ずつしか減らないもの」を見つける。
(2) （ANo.7 の[2]のように）具体的な手順や最も手数が掛かる山の並べ方を見つけて、その手順が最短であること、山の並べ方が最悪であることを帰納法で証明する。
(3) 変換によって移り合う山の状態をグラフ（代数系）で表しておいて、その系の対称性を利用する。
などの方法を使うことになるだろうと思います。

　ところで、手数を数えるのではなく、（ご質問にあるように）「並べ替える枚数」だけを数えるのであれば、ANo.7 の[1]に帰着します。なぜなら、ブロックで引っこ抜こうが裏返そうが、それと同じことが１枚ずつ動かす手順でもできるからです。例えば、逆順の山を全部まとめてえいやっと裏返すのはn枚を並べ替えたことになるから、１枚ずつ動かす場合（n-1枚動かす）よりも並べ替えた枚数が多いということになります。

お礼

ご返事遅れてすいませんでした
この度は大変エレガントな回答
ありがとうございました
これほど見事な解を頂けるとは
思わなかったです

早速プリントアウトさせて
いただきました
なるほど異常度という概念を使うんですね
当時のクリストスパパディミトリューハーバード
大学教授がこの問題をとく学生が
いたら私は教職を放り出して
その学生の従業員になってもいいと
いっていたそうです
当時質問者さんがその教授と
なにかの縁で向かいあえたら
おもしろかったかもしれません

補足

質問者さん→回答者さん
でした
ご回答して頂いたみなさま
ありがとうございました
これにて締め切ります

回答No.7

stomachman

[1] パンケーキを皿に山と積んだまま並べ替える。その手段として、「山のなかからパンケーキを１枚引きずり出して山のてっぺんに積む」という操作だけを許す場合には、ごく簡単な問題です。

　山の中で隣り合っているパンケーキ同士（n-1組あります）を比べて、大きいものの方が上になっている箇所を数えます。この数値を「異常度」と呼ぶことにします。（従って、パンケーキの山が正しく整列していれば異常度0（これが最小）、逆順になっていれば異常度n-1（これが最大）です。）　さて「パンケーキを１枚抜き取っててっぺんに載せる」という操作を１回行うと、異常度は1増えるか、変化しないか、1減るか、のどれかであることが簡単に証明できます。パンケーキが逆順になっている場合を考えると、異常度がn-1の状態から始めて異常度が0になるようにするわけですから、最低でもn-1回の操作が必要。従ってn-1枚動かす必要がある。（証明終わり。）

[2] 一方、ご質問の文中にある「何枚かずつ並べ替えます」という文言に注目しますと、並べ替える操作として「山のなかから、一連の何枚かのパンケーキをまとめて引きずり出して、それらをそのまんまてっぺんに積む」という操作も許す、という解釈もできます。
　この場合、１回の操作で異常度の増減は+2～-2まで生じうるので、異常度を使っても証明が旨く行きません。んなもんで、直感的には答が明らかであるにも関わらず、めんどくさい証明になっちゃいました。もっとエレガントな方法はないかなー。
　しかし答は同じで、パンケーキが逆順に並んでいるときに、最低でもn-1回の操作が必要で、動かすパンケーキの枚数も最低でもn-1です。

定義1
n枚のパンケーキに、大きい順に0,1,2,…,n-1と番号を付けます。パンケーキの重なり方を、列p
p = p[0], p[1], …, p[n-1]
で表します。（この列の左の方が「パンケーキの山の上の方」、列の右の方が「パンケーキの山の下の方」を意味することにします。）

定義2:パンケーキを並べ替える「手」とは、列pの連続する一部分　p[i], p[i+1], …, p[j]　(ただし、0＜i≦ｊ≦n-1)を抜き取って、それらを山の上に載せる操作です。つまり、
p = p[0], p[1], …　,p[i-1], p[i], p[i+1], …, p[j], p[j+1],…,p[n-1]　を
q = p[i], p[i+1], …, p[j], p[0], p[1], …　,p[i-1], p[j+1],…,p[n-1]　に変換する操作です。
　このとき動かすまとまり　p[i], p[i+1], …, p[j]　を「ブロック」と呼ぶことにします。
　また、手を幾つも並べたものを「手順」と呼ぶことにします。手順に含まれる手の個数を「手数」と呼ぶことにします。

定義3:「整列する」とは、手順によってパンケーキが
n-1, n-2, …, 1, 0
の順に並んだ列を作ることです。

定理1: n枚のパンケーキがどんな順番であろうとも、手数n-1手以下で整列する手順が存在する。
証明： 第k手目でパンケーキk（１枚だけ）を動かせば良い。（もし第k手目をやる直前にkがてっぺんにあれば、その手は「パス」すれば良い。）

補助定理1:　逆順に並んだn枚のパンケーキを整列するあらゆる手順において、最後の手で動かすブロックの上端（列で言えば左端）はパンケーキn-1である。（自明）

補助定理2:次の命題J(n)は真である。
命題J(n): 「逆順に並んだn枚のパンケーキをm手(m≦n-1)で整列する手順であって、その手順の第k手目(k≧0)より前の全ての手(第j手目(0＜j＜k)）について、第j手目で動かすブロックの上端がjであるならば、第k手目が終わった時点で、パンケーキk, k+1, k+2, …, n-1はこの順で並んでいる。」
証明：帰納法を用いる。
k=0のとき、自明。
k＞0のとき、
0＜j＜kである全てのjについて、第j手目に動かしたブロックの上端はjであるとする。そして、J(k-1)が真であると仮定します。
従って、第k-1手目が終わった時点で、山にはパンケーキk-1, k, k+1, k+2, …, n-1がこの順で入っている。
さて、第k手目で動かすブロックは上端がkです。場合分けをします。
(場合 a)第k手目で動かすブロックはパンケーキn-1を含まない。
(場合 b)第k手目で動かすブロックはパンケーキn-1を含む。
(a)の場合、k手目で動かす操作によってk, k+1, …, n-1の相互の順番が変わらないのは自明。
(b)の場合、k, k+1, …, n-1は全てブロックに含まれる。従って、k, k+1, …, n-1の相互の順番は変わらない。
いずれにせよ、k手目の結果得られる列にはk, k+1, …, n-1がこの順に並んでいるから、J(k)は真です。
終わり。

定理2: 次の命題H(n), L(n)は真である。
命題H(n) ：「逆順に並んだn枚のパンケーキをn-1手で整列するあらゆる手順において、第k手目で動かすブロックの上端はパンケーキkである。」
命題L(n) ：「逆順に並んだn枚のパンケーキをn-1手未満で整列する手順はない。」
証明:　帰納法を用いる。
H(1), L(1)は自明。
n≧2のとき、H(n-1), L(n-1)が真であると仮定します。
そして、n-1枚のパンケーキが逆順で並んでいる列
p=0, 1, 2, …, n-2, n-1
をm手で整列するひとつの手順Xを考えます。パンケーキn-1を無視してその手順Xを眺めれば、それは（パンケーキn-1を１枚だけ動かす手を除いて）「pからパンケーキn-1を除いた列（p'とする）をm手以下で整列する手順」のどれかと同じである筈です。
（手順Xの第k手で動かすブロックがパンケ－キn-1だけから成る場合、その手は、パンケ－キn-1を無視したとき、何もしないことと同等です。また、手順Xの第k手のブロックがパンケ－キn-1以外のものを少なくとも1枚含んでいる場合、パンケーキn-1を無視したとき、その手はp'を整列する手順の中の一つの手になっている訳です。）

　以上から手順Xは、パンケーキn-1を無視したとき、p'を手数m手以下で整列する手順のどれかと同じです。

　さて、手順Xの途中に、パンケーキn-1を1枚だけ動かす手（パンケーキn-1を無視したときにはなにもしなかったことになる手。これを以下「手[n-1]」と書くことにしましょう。）が挟まっているかもしれない。ところが、
　手順Xによってpが整列するのなら、「手順Xから全ての手[n-1]を除外した手順に続けて手[n-1]を行う」という手順（これを手順X'とする）によっても整列します。[なぜなら、パンケーキn-1を無視すれば、手順Xと手順X'は全く同じである。すなわち、どちらの手順によっても、p'は整列する。手順X'が終わった時点でパンケーキn-1は列のどこかにあるので、最後に手[n-1]を行えばpの整列が完成する。]
　だから、もし手順Xの中に（最後の手として以外に）手[n-1]が含まれていれば、手順Xを短縮した手順X'が構成できます。

　以上から、手順Xとして（最後の手として以外には）手[n-1]を含んでいない手順だけを考えても一般性を失いません。

　一方、仮定L(n-1)により、p'をn-2手未満で整列する手順はありません。従って、手順Xの手数mはm≧n-2でなくてはなりません。

　パンケーキn-1を無視したとき、手順Xの第k手目(1≦k≦n-2)で動かすブロックの上端は（仮定H(n-1)によって）パンケーキkです。しかし（パンケーキn-1を無視しないで眺めると）この手順によってパンケーキn-1もときたま一緒に動き回るかもしれない。このため、手順Xの第k手目で動かすブロックは
(場合 a)上端が k　である。
(場合 b)上端がn-1, 二番目がk である。（が、パンケーキn-1を無視すると上端がkであるのと同じである）
のいずれかです。
ところが、実際には場合bは生じません。
[場合bが生じないことを帰納法で証明します。
　手順Xの第0手目（なにもしない状態）では、勿論場合bは生じない。
　手順Xの第k-1手目(k＞1)まで、場合bが一度も生じなかったとする。すると 「逆順に並んだn枚のパンケーキをm手(m≦n-1)で整列する手順であって、その手順の第k手目までの全ての手（第j手目(j≦k)において動かすブロックの上端がjである」から、（補助定理2によって）第k-1手目の直後、k-1, k, k+1, k+2, …, n-1はこの順で並んでいる。従って、n-1はkを含むブロックの上端になることはできない。ゆえに、第k手目にも、場合bは生じない。]
　以上から、手順Xの第k手目(1≦k≦n-2)に動かすブロックの上端はkであることが分かります。

　　さて、パンケーキ0～n-1を整列するあらゆる手順において（補助定理1によって）最後の手で動かすブロックの上端はn-1でなくてはなりません。従って、第n-2手目は最後の手ではあり得ず、整列するには少なくとも第n-1手目が必要である。（手順Xの手数mはm≧n-1である。）よってL(n)は真だと分かります。
　また、第n-2手目が終わった時点でパンケーキn-2, n-1, …, 1, 0 はこの順に並んでいるのだから、あとは手[n-1]によってパンケーキn-1を（１枚だけ）動かせば整列が完了します。だから、第k手目(1≦k≦n-1)で動かすブロックの上端はkである。つまりH(n)は真です。
終わり。

回答No.6

Ishiwara

これは、かなりハイレベルな数学者の間で話題にしている問題と思われます。私のような素人の手に負えるものではなさそうです。
「ハノイの塔」は簡単ですが、これはその系列に属し、めちゃくちゃ難しそうです。一見して２ｎより大きくならないことは、分かりますが。

回答No.5

Quattro99

例えであることはもちろんわかっていますよ。
パンケーキに例えるということは、途中の何枚かを入れ替えるという操作はできない．．．という意味です。

上から何枚かをそっくりひっくり返して動かしていない山に乗せる操作を繰り返して何回で揃えられるかという意味のようですね。

回答No.4

puchner

バブルソートが一般的ですかね。。。？
これを使えばどうにでもなりそうな気がしますが、、、、
どーかな。。。
一応、SEやってます。

既に他の方もおっしゃってますが、一番理不尽な並べ方（要は1番上が一番大きく、その後順を追って小さくなり、一番下が一番小さい）の状態で並べていけば良いのではないでしょうか。。

あ、お皿の数とかは制限があったりするのでしょうか？
一枚の皿のうえでしか行ってはいけないとか、2枚の皿で実現しろとか、無制限とか。

想定すべき状況が複数ありますね。。

お礼

回答ありがとうざいますソートで間違いないと思います皿はおそらくそうゆのも含めて問題かもしれませんが多分１枚だと思います
こちらは翻訳版です
http://honyaku.yahoofs.jp/url_result?ctw_=sT,eCR-EJ,bT,hT,uaHR0cDovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9QYW5jYWtlX3NvcnRpbmc=,qlang=ja|for=0|sp=-5|fs=100%|fb=0|fi=0|fc=FF0000|db=T|eid=CR-EJ,k7b0d762a027935a2fe1614c2e8239e40,t20070719100956,
ここちょっとみてみます

回答No.3

Quattro99

並べ替えるというのがどういう操作を示しているのかがよくわかりません。どういう操作が許されているのでしょうか？

積み上がったパンケーキということからすると途中のパンケーキを入れ替えるというのは無理があり、上から何枚かを隣に置くという操作しかできないように思うのですが、このとき、その何枚かをいっぺんにひっくり返しておいてよいのかとか条件がよくわかりません。

お礼

回答ありがとうございます　パンケーキはそのままパンケーキではなくどうもひっくり返せるもの　移動できるものの例えのようです
http://honyaku.yahoofs.jp/url_result?ctw_=sT,eCR-EJ,bT,hT,uaHR0cDovL2VuLndpa2lwZWRpYS5vcmcvd2lraS9QYW5jYWtlX3NvcnRpbmc=,qlang=ja|for=0|sp=-5|fs=100%|fb=0|fi=0|fc=FF0000|db=T|eid=CR-EJ,k7b0d762a027935a2fe1614c2e8239e40,t20070719100956,

回答No.2

aquarius_hiro

そ、そうなんですか？(^^;)

普通に考えたら、最も不利な最初の状況は、一番上が一番大きく、一番下が一番小さい状態だから、一番手間のかかる場合は簡単にわかると思うのだけど、それではいけないのですか？ それよりももっと手間のかかる場合ってありますか？

「何枚並べ替えるか」の意味を明確にしていただけませんか？
どういう数え方するのですか？

となりあったパンケーキの入れ替えを一回と数えるとか、そういう数え方ですか？
それとも飛び越えても一回に数えるのですか？（それはナンセンスな感じしますが。）

お礼

回答ありがとうございます　複雑ですいません^^; バブルソートにおけるパンケーキのような並べ替え　という事のようです
http://en.wikipedia.org/wiki/Pancake_sorting

回答No.1

N64

コンピュータの分野にソート（並び替え）のアルゴリズムがあるそうですが、それが解法の参考になるかも知れません。

お礼

ありがとうございますソートで検索したらでてきました　米のwikiにありましたパンケーキソートというものらしいです　http://en.wikipedia.org/wiki/Pancake_sorting
Pancake sorting is a variation of the sorting problem in which the only allowed operation is to reverse the elements of some prefix of the sequence.