投稿者
 メール
  題名
  内容 入力補助
    
 URL
[ ケータイで使う ] [ BBSティッカー ] [ 書込み通知 ]


(無題)

 投稿者:南海  投稿日:2017年12月13日(水)21時05分23秒
  ありがとうございます。
あすは時間が取れそうで、まとめてみます。
 

京大特色入試4番:k,n が互いに素でない場合

 投稿者:かたつむり  投稿日:2017年12月13日(水)18時25分58秒
  次の定理を証明します.
【定理】互いに素でない自然数 k,n (k<n) に対し,性質 P(k,n) を持つ数列は存在しない.

正方行列 C, A や,列ベクトル u,v, そして(列ベクトルで表した)数列 a, b を,以前と同じ意味で用います.

【証明】k,n の最大公約数を d (d>1) とする.先に導いたように,
  a=Σ_{m=0}^{n-1} 2^{n-1-m}C^{km}u
が,性質 P(k,n) を持つ数列の唯一の候補である.これが条件(ロ)を満たさないことを示す.
A=Σ_{m=0}^{n-1} 2^{n-1-m}C^{km} を C の多項式として昇巾の順に表し,
  A=Σ_{i=0}^{n-1}c_{i}C^{i}
とする.このような表現は一意的に定まる.
ここで,数列 {c_{i}} の「定義域」を整数全体に周期的に拡張しておく.

---k,n が互いに素の場合,(c_{0},c_{1},...,c_{n-1}) は (2^{0},2^{1},...,2^{n-1}) のある順列でした.
  k,n が互いに素でない場合には,c_{i}=0 となる i が存在し,このことが重要な意味を持ちます.---

このとき,
  c_{i}≠0 ⇔ d|i
が成立する.(詳細は省略します)
A の第1行は (c_{0},c_{1},...,c_{n-1}) であり,A の (λ,μ) 成分は c_{μ-λ} である.
また,k,n が互いに素の場合と同様に,a の階差数列 b=(C-I)a=Av について,
 b_{l}=c_{n-k-l}-c_{n-l} (1≦l≦n)
となる.いま,l が d の倍数でないならば,d|n, d|k により
  (n-l) も (n-k-l) も d の倍数でない
ので,
 b_{l}=0-0=0
となる.1≦l≦d-1 のとき,l が d の倍数でないので
 b_{l}=0.
したがって,
 a_{1}=a_{2}=・・・=a_{d}
であり,数列 a は条件(ロ)を満たさない.即ち,性質 P(k,n) を持つ数列は存在しない.
 

(無題)

 投稿者:かたつむり  投稿日:2017年12月13日(水)16時47分6秒
  >(#)つまり互いに素でないとき存在しない証明もあげていただくとありがたいです
了解しました.自家用の解答では既にまとめてありますので,今日中に投稿します.
 

Re:京大特色入試4番:性質 P(k,n) を持つ数列の存在と一意性-補足

 投稿者:南海  投稿日:2017年12月13日(水)16時28分37秒
  かたつむり様
(#)つまり互いに素でないとき存在しない証明もあげていただくとありがたいです.
こちらでもやらないといけないのですが,この問題に集中する時間がとれていません.
 

Re:京大特色入試4番:性質 P(k,n) を持つ数列の存在と一意性-補足

 投稿者:南海  投稿日:2017年12月11日(月)14時30分22秒
  いろいろとありがとうございます.
ほぼ読み終え,整理しているところです.
 

京大特色入試4番:性質 P(k,n) を持つ数列の存在と一意性-補足

 投稿者:かたつむり  投稿日:2017年12月11日(月)11時06分21秒
編集済
  目標とした定理の証明は完了しましたが,(2)との関係を補足します.

(2)との関係とは,前稿の終盤で導いた
  1≦l≦n-1 のとき  b_{l}=2^{n-1-m_{n-l}}
から,(2) の結果が得られるということです.まず,
  b_{k}=2^{n-1-m_{n-k}}.
ここで,m_{n-k} の定義に戻ると
  k m_{n-k}≡n-k (mod n), 即ち  k m_{n-k}≡-k (mod n),  つまり m_{n-k}≡-1 (mod n)
であるから,m_{n-k}=n-1.  したがって,
  b_{k}=2^{n-1-(n-1)}=1, 即ち a_{k+1}-a_{k}=1.
 

Re:引き算は連続写像?

 投稿者:Madison  投稿日:2017年12月11日(月)02時15分31秒
  どうも有難うございます。  

(無題)

 投稿者:南海  投稿日:2017年12月 8日(金)14時59分5秒
編集済
  >√[(a-a')^2+(b-b')^2]
は√[|a-a'|^2+|b-b'|^2]で,これがC^2での距離ですね.
そこを直せば下記でいいと思います.
 

引き算は連続写像?

 投稿者:Madison  投稿日:2017年12月 8日(金)12時18分58秒
  複素関数f:C^2→CをC^2∋∀(a,b)→f(a,b):=a-bで定義します。
この時,fは連続である事を示したいのですが,下記のようにしましたがこれで大丈夫でしょうか?

∀ε>0に対して,(a',b')∈{(a',b')∈C^2;√[(a-a')^2+(b-b')^2]<ε/3}=:Pと取ると,三角不等式より
f(a',b')=a'-b'∈{z∈C;|z-(a-b)|<2ε/3}=:Qとなる。
すなわち, f(P)⊂Qとなるのでfは連続。
 

(無題)

 投稿者:南海  投稿日:2017年12月 7日(木)22時37分29秒
  ありがとうございます.
これをTeXになおして,再読のうえ紹介させていただきます.
 

京大特色入試4番:性質 P(k,n) を持つ数列の存在と一意性-3

 投稿者:かたつむり  投稿日:2017年12月 7日(木)18時05分39秒
編集済
  b_{l}=a_{l+1}-a_{l} (1≦l≦n) によって数列 b_{1},...,b{n} を定め,これを縦に並べた列ベクトルを b とする.
b_{n}=a_{n+1}-a_{n}=a_{1}-a_{n} に注意する.すると,
  b=(C-I)a=(C-I)Au=A(C-I)u
となる.v=(C-I)u とおけば,v について
 第(n-k)成分が1, 第n成分が-1 で,他の成分は0
である.したがって,
 b_{l}=(A の(l,n-k)成分)-(A の(l,n)成分)=c_{n-k-l}-c_{n-l}=2^{n-1-m_{n-k-l}}-2^{n-1-m_{n-l}}.
ここで m_{i} の定義に戻り,
  km_{n-k-l}≡n-k-l (mod n),  km_{n-l}≡n-l (mod n)
から,k(m_{n-l}-m_{n-k-l})≡k (mod n) を得る.k,n は互いに素なので
  m_{n-l}-m_{n-k-l}≡1 (mod n).
左辺の取り得る値の範囲は 1-n 以上 n-1 以下であるから,
  m_{n-l}-m_{n-k-l}=1 または m_{n-l}-m_{n-k-l}=1-n.
後者が成立するのは,m_{n-l}=0, 即ち n-l≡0 (mod n), つまり l=n のときに限るので,1≦l≦n-1 のとき,
   m_{n-l}-m_{n-k-l}=1,
    b_{l}=2^{n-m_{n-l}}-2^{n-1-m_{n-l}}=2^{n-1-m_{n-l}}.
特に,1≦l≦n-1 のとき b_{l}>0, 即ち a_{l}<a_{l+1}.
この結果と前稿の最後に記したことによって(※)の証明が完成した.

【注意】lと1が判別しにくいかもしれません.御容赦願います.
【感想】最後の場面,予想を越える綺麗な決まり方で自分でも驚きました.
 

京大特色入試4番:性質 P(k,n) を持つ数列の存在と一意性-2

 投稿者:かたつむり  投稿日:2017年12月 7日(木)16時56分53秒
  南海先生,コメントをありがとうございます.長文の連続投稿で恐縮ですが,前稿の続きを記します.

以下,数列 a_{1},a_{2},...,a_{n} と,これを縦に並べた列ベクトル a を同一視します.
性質 P(k,n) を持つ数列の「唯一の候補」a が
 a=(Σ_{m=0}^{n-1} 2^{n-1-m}C^{km})u  (u は前稿で定義した列ベクトル)
と表されました.右辺のカッコ内を A とし,これを C の多項式として昇巾の順に表すところから始めます.

k,n は互いに素なので,整数 i に対し,
  km_{i}≡i (mod n),  0≦m_{i}≦n-1
を満たす m_{i} がただ一つ定まる.このとき,i≡j (mod n) ⇔ m_{i}=m_{j} である.
(とりあえず 0≦i≦n-1 としてもよいが,数列{m_{i}}をこのように周期数列として拡張しておくと,後で都合がよい.)
すると,A=Σ_{i=0}^{n-1} 2^{n-1-m_{i}}C^{i} と表される.ここで
  c_{i}=2^{n-1-m_{i}}
とおくと,A の第1行は (c_{0},c_{1},...,c_{n-1}) であり,これは (2^{0},2^{1},...,2^{n-1}) のある順列である.
A の各行は第1行から順に巡回置換で得られるので,
  (A の(λ,μ)成分)=c_{μ-λ}=2^{n-1-m_{μ-λ}}
と表される.

数列 a の各項は
  (2^{0},2^{1},...,2^{n-1}) からk個を取った和(k個取る組合せは各項で異なる)
ですから,(2進法で考えることにより)2^{n} 未満の相異なる正の整数であることが分かります.
数列 a が増加数列であることを示すために,次稿では階差数列に着目します.
 

Re:京大特色入試4番:性質 P(k,n) を持つ数列の存在と一意性-1

 投稿者:南海  投稿日:2017年12月 7日(木)12時46分32秒
  ありがとうございます.

こちらも(*)まで示し,これがn個の値a_{1},a_{2},...,a_{n}に関するn個の式であるので,
解けるのか,というところまで考えたのですが,それ以上はまだできていませんでした.

投稿いただいたものをこちらでも整理して,あげさせていただきます.
 

京大特色入試4番:性質 P(k,n) を持つ数列の存在と一意性-1

 投稿者:かたつむり  投稿日:2017年12月 7日(木)12時22分14秒
編集済
  (2) は「性質 P(k,n) を持つ数列の存在」を前提とした問ですから,その「存在」を保証する定理
を確立しないことには,話が完結しません.一般に,
 「互いに素な自然数 k,n (k<n) に対し,性質 P(k,n) を持つ数列がただ1つ存在する」・・・(※)
 「互いに素でない自然数 k,n (k<n) に対し,性質 P(k,n) を持つ数列は存在しない」・・・(#)
が成り立ちます.とりあえずここでは(※)を証明します.
11/28 に記したように,数列 a_{1},a_{2},...,a_{n} が性質 P(k,n) を持つためには,
    2a_{m}-a{m+k}=0  (1≦m≦n-k),   2a_{m}-a_{m+k-n}=2^{n}-1  (n-k+1≦m≦n)  ・・・(*)
を満たすことが必要です.n=5, k=2 の場合,(*) を具体的に書くと,ITさんの解答にある
  2a_{1}-a_{3}=0, 2a_{2}-a_{4}=0, 2a_{3}-a_{5}=0, 2a_{4}-a_{1}=31, 2a_{5}-a_{2}=31
となります.(※)を示すには,
 「連立1次方程式(*)がただ1つの解をもち,それが条件(イ),(ロ)を満たす」 ・・・(**)
ことを示せばよいわけです.まず,(*)を行列で表現することから始めます.
具体例で確かめながら読まれると,分かりやすいと思います.

n次単位行列Iの第i行(2≦i≦n) を第i-1行に移し,第1行を第n行に移して得られる行列をCとする.
C は C^{n}=I を満たすことに注意する.
(a_{1},a_{2},...,a_{n}) と  (0,...,0,1,...,1)(最初のn-k個が0,後のk個が1)
を転置した列ベクトルを,それぞれ a, u とする.すると (*) は
  (2I-C^{k})a=pu  (p=2^{n}-1)   ・・・(*)
と表される.(2I-C^{k}) の逆行列を求めたい.そこで,多項式の等式
  (2-x)(2^{n-1}+2^{n-2}x+・・・+2x^{n-2}+x^{n-1})=2^{n}-x^{n}
に着目する.これから,行列の等式
 (2I-C^k)(2^{n-1}I+2^{n-2}C^{k}+・・・+2C^{k(n-2)}+C^{k(n-1)})=pI
を得る.右辺の書き換えで C^{n}=I を用いた. これにより,
 (2I-C^k)^{-1}=p^{-1}(2^{n-1}I+2^{n-2}C^{k}+・・・+2C^{k(n-2)}+C^{k(n-1)})
であるから,連立1次方程式(*)はただ1つの解
  a=(2^{n-1}I+2^{n-2}C^{k}+・・・+2C^{k(n-2)}+C^{k(n-1)})u
をもつ.こうして,性質 P(k,n) を持つ数列の「唯一の候補」を具体的に表すことができた.

ここまで,k,n が互いに素であることは用いていませんので,最後の結果は(#)の証明にも活かせます.
長くなったので,続きは稿を改めます.
 

京大特色入試4番:(2)の解答について

 投稿者:かたつむり  投稿日:2017年12月 4日(月)13時44分45秒
編集済
  南海先生の方針
>差をとってからの等号ではなく、その前の表に書いた合同式において
>1 \le l \le n-1 のとき a_{lk+1}=2^{l-1}a_{k+1}+M(2^n-1)、a_{lk}=2^{l-1}a_k+M(2^n-1)
> l=nのとき a_{nk+1}=2^{n-1{a_{k+1}-(2^n-1)+M(2^n-1)、a_{nk}=2^{n-1}a_k+M(2^n-1)
>の等号が成り立つことを言いたかったのです。
は理解しましたが,IT さんの(1)の解答の ①---⑤ を一般化した
  2a_{m}-a{m+k}=0  (1≦m≦n-k),   2a_{m}-a_{m+k-n}=2^n-1  (n-k+1≦m≦n)  ・・・(*)
を用いれば,直接,差について
 1≦l≦n-1 のとき a_{lk+1}-a_{lk}=2^{l-1}(a_{k+1}-a_{k}),
  a_{nk+1}-a_{nk}=2^{n-1}(a_{k+1}-a_{k})-(2^n-1) ・・・(★)
が言えます.やはり,(*) が本問において最も重要な関係式であるように思います.
また,繰り返しで恐縮ですが,(★)を導きさえすれば,後は一言で済みます.

【追記】(★)の証明,及び(2)の解答.
b_{l}=a_{lk+1}-a_{lk} (1≦l≦n) とおく.k,n は互いに素なので,
 lk≡n (mod n) ⇔ l=n,  lk≡k (mod n) ⇔ l=1
であることに注意する.ことことと (*) により,
 2≦l≦n-1 のとき b_{l}=2b_{l-1},  b_{n}+(2^n-1)=2b_{n-1}
が成り立つ.したがって,b_{n}+(2^n-1)=2^{n-1}b_{1}, 即ち
  a_{nk+1}-a_{nk}=2^{n-1}(a_{k+1}-a_{k})-(2^n-1). ・・・(★)
ここで,a_{nk+1}-a_{nk}=a_{1}-a_{n}<0 により
  2^{n-1}(a_{k+1}-a_{k})<(2^n-1),  即ち a_{k+1}-a_{k}<2 であるから,
  a_{k+1}-a_{k}=1.

 

(無題)

 投稿者:南海  投稿日:2017年12月 4日(月)04時17分57秒
  ありがとうございます。
私の先の書き込みは間違いです。

差をとってからの等号ではなく、その前の表に書いた合同式において
1 \le l \le n-1 のとき a_{lk+1}=2^{l-1}a_{k+1}+M(2^n-1)、a_{lk}=2^{l-1}a_k+M(2^n-1)
l=nのとき a_{nk+1}=2^{n-1{a_{k+1}-(2^n-1)+M(2^n-1)、a_{nk}=2^{n-1}a_k+M(2^n-1)
の等号が成り立つことを言いたかったのです。

ただこれでは、論述不足です。
後日改訂します。
 

京大特色入試4番(1):IT さんの解答

 投稿者:かたつむり  投稿日:2017年12月 4日(月)00時12分16秒
編集済
  (1) について,私もITさんと同じようにやりました.
IT さんの ①---⑤ を一般化した結果が,11/28 に記した
  2a_{m}-a{m+k}=0  (1≦m≦n-k),   2a_{m}-a_{m+k-n}=p  (n-k+1≦m≦n)  ・・・(*)
です.これが,数列 a_{1},a_{2},...,a_{n} が性質 P(k,n) を持つための必要条件になります.
私は,(*)を用いて数列{a_n}の階差数列を考察し,(2)を解決しました.それが11/28の投稿内容です.

実は,一般化する前に,n=5;k=1,2,3,4 や n=6,7 の場合を調べました.
回り道になりますが,やはり実験・観察は楽しいです.


 

京大特色入試4番:(2)の解答について質問-2

 投稿者:かたつむり  投稿日:2017年12月 4日(月)00時04分45秒
編集済
  まだ勘違いしているのかもしれないのですが,
>1 \le l \le n-1 のとき a_{lk+1}=2^{l-1}a_{k+1}
について,2^{l-1}a_{k+1} が 2^{n}-1 以上になってしまう可能性はないでしょうか?

>l=nのとき ・・・ a_{nk}=2^{n-1}a_k
について,2^{n-1}a_{k} が 2^{n}-1 以上になってしまう可能性はないでしょうか?
例えば,n=5,k=3 のとき a_{n}=2^{n-1}a_{k}, 即ち a_{5}=2^4 a_{3} は成り立ちません.

また,先の【追記】に記したように,
  a_{nk+1}-a_{nk}=2^{n-1}(a_{k+1}-a_{k})-(2^n-1)
が言えるならば,右辺が負であることから,
  a_{k+1}-a_{k}<2
が導けるので,即 a_{k+1}-a_{k}=1 が言えてしまい,以降の議論は不要となります.
 

京大特色入試4番(1)

 投稿者:IT  投稿日:2017年12月 3日(日)22時49分24秒
編集済
  京大特色4番解答(1)だけやってみました。

k=2,n=5のとき
(イ)は,a[1],a[2],a[3],a[4],a[5]は整数.
(ロ)は, 0≦a[1]<a[2]<a[3]<a[4]<a[5]<31.
(ハ)は,2a[1]-a[3],2a[2]-a[4],2a[3]-a[5],2a[4]-a[1],2a[5]-a[2]は31で割り切れる。

以下(イ)は断りなしに使う。
まず(ロ)より各不等式が成立する。(不等式は、まとめてしまってもいいかも知れません)
 -31<-a[3]≦2a[1]-a[3]<a[1]<31 よって(ハ)より2a[1]-a[3]=0,a[3]=2a[1]…①
 -31<-a[4]≦2a[2]-a[4]<a[2]<31 よって(ハ)より2a[2]-a[4]=0,a[4]=2a[2]…②
 -31<-a[5]≦2a[3]-a[5]<a[3]<31 よって(ハ)より2a[3]-a[5]=0,a[5]=2a[3]…③
 0<a[4]≦2a[4]-a[1]<2a[4]<62 よって(ハ)より2a[4]-a[1]=31,a[1]=2a[4]-31…④
 0<a[5]≦2a[5]-a[2]<2a[5]<62, よって(ハ)より2a[5]-a[2]=31,a[2]=2a[5]-31…⑤

①③よりa[5]=4a[1]
④より      =4(2a[4]-31)
②より      =4(4a[2]-31)
⑤より      =4(4(2a[5]-31)-31).
よって    0=31a[5]-31×20.
よって a[5]=20,
a[2]=9,a[1]=5,a[4]=18,a[3]=10

これは(ロ)も満たす。
 

(無題)

 投稿者:南海  投稿日:2017年12月 3日(日)22時19分30秒
  差をとってからの等号ではなく、その前の表に書いた合同式において
1 \le l \le n-1 のとき a_{lk+1}=2^{l-1}a_{k+1}、a_{lk}=2^{l-1}a_k
l=nのとき a_{nk+1}=2^{n-1{a_{k+1}-(2^n-1)、a_{nk}=2^{n-1}a_k
の等号が成り立つことを言いたかったのです。そう書いた方が良かったかも知れません。

そのうえで差をとりました。
 

/182