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


京大特色入試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
の等号が成り立つことを言いたかったのです。そう書いた方が良かったかも知れません。

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

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

 投稿者:かたつむり  投稿日:2017年12月 3日(日)16時10分31秒
編集済
  南海先生の解答を拝見しました.
分からない箇所があり,教えていただければ幸いです.

(2)の解答の表の下に
 1≦l≦n-1 のときは,1≦a_{lk}<a_{lk+1}<2^n-1 なので a_{lk+1}-a_{lk}=2^{l-1}(a_{k+1}-a_{k})
とありますが,最後の等式の右辺が 2^{n}-1 より大きくなってしまう可能性はないのでしょうか?

その次の,
 l=n のときは,・・・なので,a_{nk+1}-a_{nk}=2^{n-1}(a_{k+1}-a_{k})-(2^n-1)
についても,この右辺が正となってしまう可能性はないのでしょうか?

何か誤解をしているのかもしれませんが,よろしくお願いします.

【追記】2番目の疑問点に関し,もし
  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 と言えてしまいませんか?
つまり,ここで「証明すべきこと」を使っているように見えるのですが.

 

2008年 京大理系乙3番

 投稿者:南海  投稿日:2017年12月 2日(土)10時36分22秒
編集済
  こちらにも、問題と解答・解説があります.
http://aozoragakuen.sakura.ne.jp/kakomon/2008/08ka03.htm
 

2008年 京大3番

 投稿者:かたつむり  投稿日:2017年12月 2日(土)08時11分9秒
  「ベクトルについて」の問題は2008年に京大で出題されました.

4直線のそれぞれに平行なベクトル vec{a}, vec{b}, vec{c}, vec{d} を定める.(vec{} はベクトルを表す.)
このとき,実数 p, q, r, s が存在して,
  p vec{a}+q vec{b}+r vec{c}+s vec{d}=vec{0} ・・・(*)
が成り立つ.
「どの3直線も同一直線上にない」ので,pqrs≠0 である.(*) を
 (q vec{b})-(-p vec{a})=(-r vec{c})-(s vec{d}) ・・・(**)
と書き換え,4直線上の点 A, B, C, D を
  VEC{OA}=-p vec{a}, VEC{OB}=q vec{b}, VEC{OC}=-r vec{c}, VEC{OD}=s vec{d}
と定めれば,(**) により,
  VEC{AB}=VEC{DC}
が成り立ち,ABCD は平行四辺形となる.
 

ベクトルについて。

 投稿者:コルム  投稿日:2017年12月 1日(金)22時15分0秒
  空間の1点Oを通る4直線で、どの3直線も同一平面上にないようなものを考える。このとき、4直線のいずれともO以外の点で交わる平面で、4つの交点が平行四辺形の頂点になるようなものが存在することを示せ。

教えていただけると幸いです。
 

京大特色入試2番:別解

 投稿者:かたつむり  投稿日:2017年11月29日(水)11時29分18秒
編集済
  ssdさんの
>|c-a|<εを満たすような無理数cを1つ取り、
の「無理数」を,「分母が十分大きい既約分数で表される有理数」とすれば,
〈クロネッカーの稠密定理〉を用いずに解答できると思います.
当初,この方法で解答をまとめましたが,ITさんのアイデアを拝見し,自身の主解答をそちらに切り替えました.

本問は言い換えると,「写像
 (x,x^2)→({x},{x^2})   ({ } は小数部分を表すものとする)
による像が,正方形 {(x,y)|0≦x<1,0≦y<1} の中で稠密である」
という話なので,ssd さんの方法は自然であると感じました.
 

特色2番

 投稿者:ssd  投稿日:2017年11月29日(水)06時29分30秒
  横のラインの距離から見る答案が多いですが、ほぼ縦のラインからでも行けます。
(m+a,n+b)と(m+c,(m+c)^2)
の距離を考えると(0≦c<1)
√(c-a)^2+(n+b-m^2-2mc-c^2)^2
で与えられるが、
|c-a|<εを満たすような無理数cを1つ取り、
更に
2mc= N+d(0≦d<1)
とすると第2項は
(n- N-m^2+b-d-c^2)^2となり、
-1<b-c^2<1であるから、クロネッカーの定理よりmを上手く選ぶことで
b-d-c^2の小数部分も任意のεで抑えることができ、
後は整数部分が0になるようnを選んでやれば、
距離の式は全てεで抑え込めることになります。
勿論クロネッカーの定理は証明を要しますし、横のラインで見た方が簡単ではありますが。
 

京大特色入試4番(2)

 投稿者:かたつむり  投稿日:2017年11月28日(火)12時20分36秒
編集済
  昨日の投稿で「互いに素という前提は,(2) の証明では不要」と書きました.その証明の骨子を記します.
見た目より「単純」です.多くの方に確認していただけると有り難いです.

p=2^{n}-1 とおく.性質P(k,n)を持つ数列 a_{1},a_{2},...,a_{n} は(ハ)を満たすので,
2a_{m}-a{m+k}=pl_{m}  (1≦m≦n-k),  2a_{m}-a_{m+k-n}=pl_{m}  (n-k+1≦m≦n)  (l_{m} は整数)
と表される.この数列が(ロ)を満たすことに着目し,l_{m} を評価すると,
前者については l_{m}=0, 後者については l_{m}=1 となることが分かる.
(肝心なところですが,過程を省略します.)

つまり,a_{1},a_{2},...,a_{n} は,
    2a_{m}-a{m+k}=0  (1≦m≦n-k),   2a_{m}-a_{m+k-n}=p  (n-k+1≦m≦n) ,  ・・・(*)
即ち  2a_{m}=a{m+k}  (1≦m≦n-k),   2a_{m}=a_{m+k-n}+p  (n-k+1≦m≦n)   ・・・(**)
を満たす.(これらn個の等式を順に縦に並べると,左辺には a_{1},a_{2},...,a_{n} が,
右辺には a_{k+1},...,a_{n},a_{1},...,a_{k} がこの順に現れます.)

b_{m}=a{m+1}-a_{m} (1≦m≦n-1) とおいて数列 {b_m} を定める.(ロ)により,{b_m} の各項は正整数である.
(**) により,m≠k ならば b_{m}=2b_{i} なる i が存在するので,{b_m} の各項を小さい順に並べてできる数列は
「初項 b_{k}=a_{k+1}-a_{k}, 公比 2 の等比数列」になる.(ここも推論過程を省略しています.)  だから,
  a_{n}=a_{1}+b_{k}(2^{n-1}-1).
ここで,2a_{1}=a_{k+1}>0 により a_{1}≧1 であるから,もし b_{k}≧2 とすると
 a_{n}≧1+2(2^{n-1}-1)=2^{n}-1
となってしまう.したがって,
 b_{k}=1, 即ち a_{k+1}-a{k}=1.

性質 P(k,n) を持つ数列の存在は,上記の連立方程式(*)の解の性質に帰着します.
これについては,後日,記したいと思います.
 

京大特色入試4番

 投稿者:かたつむり  投稿日:2017年11月27日(月)13時22分1秒
編集済
  本問では要求されていませんが,
「互いに素で k<n を満たす自然数 k, n に対し,性質 P(k,n) を持つ数列がただ1つ存在する」・・・(*)
ことも証明してみました.
「互いに素」という前提は,(2) の証明では不要というか意識しなくても済みますが,(*) の証明で効いてきます.

(*) の証明では,巡回行列の性質を用いました.
2年前,その年の京大特色入試3番に関連して巡回行列を学習したことが,少し生きました.
 

(無題)

 投稿者:南海  投稿日:2017年11月27日(月)09時21分46秒
  >第2問も円の方程式とy=x^2が共有点をもつ条件を書いて,それを満たす定数の存在,という方向
これはなかなか難しいですが,別解として考える意味があり,この方法と図形的方法との関係まで調べると面白いです.
 

RE:京大特色入試

 投稿者:IT  投稿日:2017年11月26日(日)23時15分36秒
編集済
  きれいな答案より、それに至る思考過程の方が意味があると思います。
それを競争試験の限られた時間で測定するのは難しいでしょうが,特色入試では口頭試問である程度カバーされるのかも知れませんね。

第2問も円の方程式とy=x^2が共有点をもつ条件を書いて,それを満たす定数の存在,という方向でがんばるのも意味はありますね。
 

京大特色入試

 投稿者:南海  投稿日:2017年11月26日(日)21時27分58秒
  このようにいろいろ考える幅のある問題を提供することはたいへんいいことです.
その意味で特色入試は,いい試みだと思っています.
高校生で,これを機会に考える人が出てくればいいのですが.

私の方は4番の(2)をいろいろ考えています.
 

京大特色入試3番

 投稿者:かたつむり  投稿日:2017年11月26日(日)17時58分1秒
編集済
  (1) では2進法と樹形図を念頭に置いて考えました.
いくらか見通しがよくなりますが,解答をまとめるのは苦労しました.
また,余事象を考えずに p_{n+1}=(1/2)(p_{n}+p_{n}-(p_{n})^2) を導きました. P(A∪B)=P(A)+P(B)-P(A∩B) を適用.

(2),(3) では,最終段階で
 log(n+1)-log(n)-1/(n+2)=∫_{n}^{n+1}(1/x)dx-1/(n+2)>1/(n+1)-1/(n+2)
となり,「少し余裕がある」ことが気になりました.
そこで,(3) で与えられた不等式に頼らずに,p_n の大きさを評価することを試みました.

a_{n}=2/p_{n}-1 とおくと,a_{1}=3 で,a_{k+1}=a_{k}+1+1/a_{k} が成り立つ(過程は省略)ので,n≧2 のとき
 a_{n}=a_{1}+(1+1/a_{1})+・・・+(1+a_{n-1})=(n+2)+(1/a_{1}+・・・+1/a_{n-1})
となる.これから a_{n}≧n+2 が分かるので,
 1/a_{1}+・・・+1/a_{n-1}≦1/3+・・・+1/(n+1)≦∫_{2}^{n+1}(1/x)dx=log((n+1)/2).
したがって,n+2≦a_{n}≦n+2+log((n+1)/2) が成り立つ.これを p_{n} で表すと,
 2/(n+3+log((n+1)/2))≦p_{n}≦2/(n+3)
となる.

ちょっとだけ良い評価が得られました.
 

京大特色入試3番

 投稿者:IT  投稿日:2017年11月26日(日)15時17分35秒
編集済
  いずれの方法も類似の不等式の証明を知ってないと難しいかも知れませんね

南海先生の解答の③の次の
((n+2)/(n+1))^(n+2) < ((n+1)/n)^(n+1)
⇔1 < {((n+1)/n)^(n+1)}{((n+1)/(n+2))^(n+1)}{(n+1)/(n+2)}

右辺=[{(n^2+2n+1)/(n^2+2n)}^(n+1)]{(n+1)/(n+2)}
=[{1+ 1/(n^2+2n)}^(n+1)]{(n+1)/(n+2)}
二項定理により
≧{1+(n+1)/(n^2+2n)}{(n+1)/(n+2)}
=(n^3+4n^2+4n+1)/(n^3+4n^2+4n)>1
という方法もありますが、これも最後までやってみないと分からないので初めてだと難しいですね。

私は以前同様な不等式の証明を上記のように行った後、ネットで調べて定積分を使う前記の証明を見つけて感心したのでした。
 

/188