• ベストアンサー

　最長増加部分列(LIS)について勉強しています。資料に

pori_boyの回答

  • ベストアンサー
  • pori_boy
  • ベストアンサー率60% (18/30)
回答No.2

こんにちは この問題では， 「ある長さの部分増加列が存在しない」とき 「ある長さの部分減少列が存在する」ことを 証明するのが良いのではないかと思います． 参照URLでは，具体的な例から証明まで， 比較的わかりやすく紹介していると思うので， 一度見てみることをおすすめします．

参考URL：
http://www.lab2.kuis.kyoto-u.ac.jp/~itohiro/Puzzle/pigeon/Lv1_Q.html
hayami007
質問者

お礼

理解できました。ありがとうございます。

この回答がついた質問に戻る
回答 全件
ん～, 「長さが ceil(√n) の増加部分列がない」と仮定して, …
  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • 部分列の収束性

    こんばんは。「数列があって、それの収束する任意の部分列が同じ極限に収束するならば、その数列自身がその極限に収束する。ということを証明せよという問題です。 もしその数列がコーシー列であればその部分列がそのコーシー列と同じ値に収束するというのは証明したのですが、この問題では数列があってとだけ言ってます。コーシー列ならば、εーN法で行けるのですが、この場合どうやって証明すればいいのでしょうか？どなたか分かる方、証明宜しくお願いします。

  • 極限値を求める

    lim[n→∞]{1-2/(n-1)}^(n-1) を求めよ、という問題です。 lim[n→∞](1+1/n)^n=e なので、それに近い形になると思うのですが…。 とりあえず、a_n=(1-2/n)^nとおいて、二項展開しました。 が、正負の符号が+,-,+,-,…となり単調増加か減少かすら分かりません。 8項ぐらい計算すると、一応1未満の値に収束しそうなのですが…行き詰っています。 どなたか教えてください。

  • エクセルで連続した増加、減少を数えたいのですが

    エクセル2010で、列方向に数字が入っていくのですが、4回連続して増加（減少）した場合に数字が赤字になるような書式設定をしたいのですが。 現在は例えばA列に数値を入力するとして、B,C列を挿入して、B列にはA列の値が増加したら「B列の上のセル＋１」、でなければ「０」、C列には逆に減少したら「C列の上のセル＋１」でB列もしくはC列が４以上の場合、入力セルの数値が赤字になるように書式設定（B+C＞４）してアラームを出すようにしているのですが、対象セルが多い表だと、表が横に大きくなってしまう事と、何よりも作業に非常に手間がかかるので全部のシートには適用できない状況です。 どなたか列を挿入せずに何とか上記の目的を達成する方法を教えてください。

  • 証明問題です

    証明問題です nが自然数の時、√n　+　√n+1 が無理数であることを示せ 背理法でやろうと思ったんですがうまく矛盾を示せません 解き方やヒントを下さい お願いします

  • 対称行列の対角要素を増加させた場合の固有値について

    n次の対称行列Aの一つの対角要素を増加させた対称行列をA'とします． Aの固有値を大きい順にλ1，λ2，・・・λn， A'の固有値を大きい順にλ'1，λ'2，・・・λ'nとします． このとき，λ'1=>λ1，λ'2=>λ2，・・・，λ'n=>λn が成り立つことを証明したいのですが， クーランのミニマックス法（行列の二次形式を最大化し，拘束条件を動かして最小化する方法）を用いる以外の方法で，できるだけ簡単に証明できませんか？ どなたか，よろしくお願い致します．

  • コーシー列かどうか

    どのようにして良いのかわからず困っています。 宜しくお願い致します。 E：複素バナッハ空間 N：Eの閉部分空間 E/N：商ベクトル空間 E/Nにおいて ∥ξ+N∥=inf{∥ξ+η∥|η∈N} とおくとノルムになる。 E/Nはこのノルムに関してバナッハ空間 ノルムになることは証明できました。 よって、完備である事を示したいのですが、 {ξ_(n)+Ｎ}：E/Nにおけるコーシー列 ξ'_(n)を 　ξ'_(n)∈ξ_(n)+N　∥ξ'_(n-1)-ξ'_(n)∥＜2^(-n) を満たすようにとる。 そうすると{ξ'_(n)}がコーシ－列となる ここがどうして良いのかわかりません。

  • (Ａの逆行列)^nとＡ^nを掛けてＥになりますか？

    高校生です。来年受験です。 自分なりに導いた回答に自信がないので正しいかよろしくおねがいします。また別解でもかまいません。 『行列Ａは2×2行列(すべて実数)。ab‐bc≠0のとき、すべての自然数ｎについてＡ^n=０時ならばＡ^n≠Oを示せ。』という問題です。 私は背理法を用いました。 ad‐bc≠0のとき、Ａ≠0で行列が存在する。 ある自然数nについて、Ａ^n=0と仮定する。(←背理)両辺に(Ａ^-１)^nをかけるとＥ=0となり矛盾。よって… (省略) としました。 これは正しいでしょうか？ そもそも ｛(Ａ^-１)^n｝×Ａ^n=Ｅとして大丈夫でしょうか？ つまり、(Ａの逆行列)^nとＡ^nを掛けてＥになるのかどうかが不安な部分です。 見にくくてすみません。どうかよろしくおねがいします。

  • 文字列の整形方法

    "○○が5以下の場合、☆☆ 1減少<BR>●●が42以上の場合、▲▲3増加" "★★ 5増加<BR>□□ 2減少" "■■が85の場合、◎◎ 1減少" と言うような文字列が大量にあるんですが、 <BR>で区切り、条件判断の文を満たしていない、または条件判断の文でない場合はその区切り全体の文字色を黒 満たしていて、結果が減少の場合は赤、増加の場合は青 に変えたいのですが何か良い方法はありますでしょうか

  • 証明を教えてください

    A1,A2 ...........Amnをmn+１の実数の列として m+1の数からなる単調増加部分列 あるいはn+１からなる単調減少部分列 が存在する これを鳩ノ巣原理を用いて証明してください

  • 緩増加超関数について

    定義 Ｔが緩増加超関数であるとは、 １．ＴはＳ上の線形写像、ただしＳは急減少関数全体とします ２．Ｔは連続、i.e.任意のφ,φn∈Ｓに対してφn→φならＴ(φn)→Ｔ(φ) ２の定義中にあるφn→φ(n→∞)の意味なんですが これはＳにある位相をいれてあってその位相に関して収束するという意味です ここではその位相の紹介は省きます またＴ(φ)のことを<Ｔ,φ>と書きます 例 δ関数を次のように定義するとδ関数は緩増加超関数です <δ,φ>＝φ(０)、φ∈Ｓ 証明は定義の１，２を確かめればいいので省きます ここからが本題なのですが このデルタ関数が積分の中にでてくるのをよく見ます たとえば ∫（－∞～∞）ｄｘ・∫（－∞～∞）ｄｙ・ｐ（ｘ）・ｐ（ｙ）・δ（ｚ－ｘ／ｙ） などです。 このδ関数はｚ－ｘ／ｙに作用しているのですが これは上の定義のようなＳ上の関数にはなっていません あたかも普通の関数のように扱われています しかし、普通の関数としたら （今ｐは連続分布という仮定があります） この測度０上で値をとる関数なのでこの積分は０になるはずです ではどうしてこのように混同して書かれているのでしょうか？ ぜひ教えてください

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する
質問する