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


和公式の対称性

 投稿者:かたつむり  投稿日:2017年 1月 4日(水)10時19分53秒
編集済
  和公式 Σ{k:from 0 to q-1}[kp/q]=(p-1)(q-1)/2  (p,q は互いに素な正整数)の対称性について,
知人(J.K.氏)から次のような解釈を教わりました.

この和 S は「座標平面で3点(0,0),(q,0),(q,p)を頂点とする三角形の内部(周を含まない)にある格子点の個数」に等しい.
2点 (0,0),(q,p) を結ぶ線分(両端を除く)上に格子点はないので,
  S=(4点(0,0),(q,0),(q,p),(0,p)を頂点とする長方形の内部(周を含まない)にある格子点の個数)/2
   =(p-1)(q-1)/2.
 

(無題)

 投稿者:南海  投稿日:2017年 1月 3日(火)10時13分38秒
  いろいろありがとうございます.
Concrete Mathematicsの式(3.32)は,x=0でd>1のときは示せたので,x≠0でd=1で示せれば,組みあわせてできそうです.

前文を読むと「Concrete Mathematics」つまり具体数学は,抽象数学と違う数学だということで,70年代からアメリカで展開してきたとのこと.このあたり,情報技術でのアメリカの底力を感じます.
 

Knuth 他 著 Concrete Mathematics

 投稿者:かたつむり  投稿日:2017年 1月 3日(火)08時45分18秒
  >それと,<Knuth 他 著 Concrete Mathematics>は計算機科学の教科書ですね.
たしかに,邦訳の書名は『コンピュータの数学』ですが,原著のタイトルからも察せられるように,
「狭義の計算機科学」の本ではないように思います.

>計算機科学の教科書で,このような等式がどのように使われるのか,
例の等式の「計算機科学における意義」は,私には全く見当が付きませんが,その導出・証明はとても良い勉強になりました.

この和は,同書第3章の最後の話題で,p.89(ITさんが紹介されたpdfのp.23)の最後の文から始まります.
p.92(pdfのp.26)中程の書き換えからが「本論」です.
私はそこから読み始め,随時戻って (3.26),(3.25),(3.11) の等式を学習しながら,証明を再構成しました.
 

Concrete Mathematics

 投稿者:IT  投稿日:2017年 1月 2日(月)21時32分49秒
編集済
  <Knuth 他 著 Concrete Mathematics>は
下記にちょうどInteger Functions部分のサンプルページがあり
その等式は3.5 FLOOR/CEILING SUMS の最後の94ページ(PDF28p)にあります。
http://ptgmedia.pearsoncmg.com/images/9780201558029/samplepages/9780201558029.pdf
 

(無題)

 投稿者:南海  投稿日:2017年 1月 2日(月)18時43分14秒
  それと,<Knuth 他 著 Concrete Mathematics>は計算機科学の教科書ですね.
Knuth は私が1日も使わない日はない TeX の創始者ですね.
計算機科学の教科書で,このような等式がどのように使われるのか,知りたいものです.
 

(無題)

 投稿者:かたつむり  投稿日:2017年 1月 2日(月)17時46分58秒
  この入試問題は知りませんでした.ありがとうございます.

解答---(2.2)の補題---に記しましたように,私が前提として用いたのは,この上智大入試問題の(4)の性質だけなので,
ここまでさかのぼれば,高校数学の範囲に収まります.
 

近似分数

 投稿者:南海  投稿日:2017年 1月 2日(月)13時56分21秒
  かたつむりさんの解答の近似分数ですが,2000年に入試に出ています。上智大後期
http://aozoragakuen.sakura.ne.jp/kakomon/2000/jyouti2.htm
最良近似であることまではいらないので,この問題と解答を再掲して使い,一般化された問題とその解答を,これまでの議論を元に作ってみます。
高校範囲で一般化でき解答できることを確認してみようと思います。
 

京大特色入試4番の一般化に関わる〈和公式〉

 投稿者:かたつむり  投稿日:2016年12月31日(土)12時31分1秒
  >完璧な一般化ですね。
ありがとうございます.ITさんの問題提起がなければ試みなかったと思います.

例の〈和公式〉の証明は,次のようにしました.ITさんの証明と,実質的に同じだと思います.

kpをqで割った余りを r_k とおくと(商は [kp/q] なので),
  kp=q[kp/q]+r_k, 即ち [kp/q]=(kp-r_k)/q
が成り立つ.p,qは互いに素なので,
    r_i=r_j ⇔ i=j
が成立(詳細略)し,
  Σ{k:from 0 to q-1}r_k=Σ{k:from 0 to q-1}k
となる.したがって,
  Σ{k:from 0 to q-1}[kp/q]=Σ{k:from 0 to q-1}(kp-r_k)/q
                             =(p-1)/q Σ{k:from 0 to q-1}k
                             =((p-1)/q)(q(q-1)/2)
                             =(p-1)(q-1)/2.

調べたところ,Knuth 他 著 Concrete Mathematics に,この和公式を特殊な場合として含む
(恐ろしく)一般的な公式が載っていました:

  xを実数,mを正整数,nを整数とする.m,nの最大公約数をdとすると,
     Σ{k:from 0 to m-1}[(kn+x)/m]=(m-1)(n-1)/2+(d-1)/2+d[x/d].

著者は次のように記しています:
This is astonishing, because there's no reason to suspect that such a sum should be symmetrical.
 

Re:京大特色入試 4番の一般化(まとめと補足)

 投稿者:IT  投稿日:2016年12月31日(土)00時29分46秒
編集済
  かたつむりさん、完璧な一般化ですね。

> 和公式
> Σ{k:from 0 to q-1}[kp/q]=(p-1)(q-1)/2  (p,q は互いに素な正整数,[kp/q] は kp/q の整数部分)
> です.(右辺が p,q について対称であることが,ちょっと不思議な気がします.)
私も不思議な気がしたので、不思議を減らそうとしてみました。
結局証明をすることになりました。(かたつむりさんの証明と同じかもしれませんが)

ガウス記号なしで考えると,
 Σ{k:from 0 to q-1}(kp/q)=(q(q-1)/2)p/q=p(q-1)/2 なので, (#ここでなんとなく対称の可能性が見えてきました。)

ここからガウス記号で失われる小数部分の和が p(q-1)/2 - (p-1)(q-1)/2 =(q-1)/2 であることを示せばいい.
 これは、折り返して足すと出てきます.

 pとqは互いに素なので k=1,..,q-1 についてkp はq で割り切れない。

 qが奇数のときは、1からq-1まで偶数個で
  (p/q)-[p/q]+((q-1)p/q)-[(q-1)p/q]=p-([p/q]+[(q-1)p/q])=1などと,1が(q-1)/2 個作れる.

 qが偶数のときは、1からq-1まで奇数個、またpは奇数
  (p/q)-[p/q]+((q-1)p/q)-[(q-1)p/q]=p-([p/q]+[(q-1)p/q])=1などと,1が(q-2)/2 個作れる.
  ペアにならず真ん中に残る1個は ((q/2)p/q)-[(q/2)p/q]=(p/2)-[p/2]=1/2.
  合わせて(q-1)/2 となる.

p,q を入れ替えると,同様に
 Σ{k:from 0 to p-1}(kq/p)=(p(p-1)/2)q/p=q(p-1)/2 なので
 ガウス記号で失われる小数部分の和が q(p-1)/2 -(p-1)(q-1)/2 =(p-1)/2.
こう考えるとp,q について対称であることが納得できます。図解できるとさらに分かりやすいと思います.

# 結果的には,ガウス記号で失われる小数部分の和を考えるより,
 直接[1p/q]+[(q-1)p/q]=p-1 などと考えた方が簡明ですね。(後から気がつきました)

 

京大特色入試 4番の一般化(まとめと補足)

 投稿者:かたつむり  投稿日:2016年12月30日(金)11時39分49秒
編集済
  年が変わる前に,改めて整理しておきます.(長文失礼します)

[問題の定式化]
正の実数αと自然数nに対し,xy平面上で
  0≦x≦n-1, 0≦y≦αx  ・・・(*)
を満たす格子点(x,y)の個数をS_{α}(n)とおく.
(1) lim_{n→∞} S_{α}(n)/n^2=α/2  を示せ.
(2) 以下の条件(H)を満たすような実数Cが存在するかどうか調べよ.
     (H) すべての自然数nについて,|S_{α}(n)-(α/2)n^2|<C が成立する.

(注)京大・特色入試4番は α=1/√(5) の場合に当たります.
(注)(α/2)n^2 は,3点(0,0), (n,0), (n,αn) を頂点とする三角形の面積に等しく,
   S_{α}(n) は,「(*) を満たす格子点を左下の頂点とする単位正方形のなす図形」の面積に等しい.
     (1)は両者の比が1に収束することの証明,(2)は両者の差を考察する問題です.

[(2) の結論]
αが無理数の場合,次のことが成り立つ:
α>1 のとき S_{α}(n)-(α/2)n^2 は下に有界でない;
α<1 のとき S_{α}(n)-(α/2)n^2 は上に有界でない.
(注)〈連分数展開による近似分数列〉の性質を用いて証明できます.

αが有理数の場合,α=p/q(p,q は互いに素な自然数)とおくと,次のことが成り立つ:
p>q+1 のとき S_{α}(n)-(α/2)n^2 は下に有界でない;
p<q+1 のとき S_{α}(n)-(α/2)n^2 は上に有界でない;
p=q+1 のとき S_{α}(n)-(α/2)n^2 は周期qの周期数列をなす.(特に,α=2/1=2 のときは「定数列」となる.)

したがって,条件(H)を満たすCが存在するのは,α=(q+1)/q(q は自然数)と表される場合に限る.

[補足1]問題解決の〈決め手〉となったのは,和公式
      Σ{k:from 0 to q-1}[kp/q]=(p-1)(q-1)/2  (p,q は互いに素な正整数,[kp/q] は kp/q の整数部分)
です.(右辺が p,q について対称であることが,ちょっと不思議な気がします.)
この証明だけでも,一つの入試問題になり得ると思います.

[補足2]元の入試問題(2)に対し,高校数学の範囲で答えるには,「ITさんのアイデア」が最適だと思います.
その本質は,x軸に平行な線分上の格子点の個数を数えてそれらを加える,つまり,格子点の総数を
    Σ{y:from 0 to [(n-1)/√(5)]}(x軸に平行な線分上の格子点の個数を表すn,yの式)
と計算することにあります.([(n-1)/√(5)] は (n-1)/√(5) の整数部分.)
和の上限 [(n-1)/√(5)] の扱いが少し面倒ですが,√(5) を2より大きい実数で置き換えた場合にもそのまま使えます.
 

お礼

 投稿者:南海  投稿日:2016年12月29日(木)13時12分10秒
編集済
  誤植のご指摘有り難うございます。直しておきました。  

誤植でしょうか

 投稿者:pencil  投稿日:2016年12月29日(木)12時29分35秒
  初めまして。いつも拝見させて頂いております。
今年の京大特色3番の解答についてですが、(2)の最初の行は「n-456=15」ではなく「n-441=15」だと思います。些細なことかもしれませんが、受験生のために注を加えて頂ければと思います。宜しくお願い致します。
 

Re:可測集合になること

 投稿者:Imogene  投稿日:2016年12月17日(土)09時23分11秒
  このようにしてみました。

Y:={x∈proj_1(E);f({x}×(N_b∩proj_2(E))⊂C}と置いておきます。

任意の実数rに対して,f^-1(r,+∞)はボレル集合ですね。
そしてY=f^-1(r,+∞)∩proj_1(E)×(N_b∩proj_2(E))でproj_1(E)と(N_b∩proj_2(E))ともボレル集合なので
proj_1(E)×(N_b∩proj_2(E))もボレル集合ですよね。
よって,f^-1(r,+∞)∩proj_1(E)×(N_b∩proj_2(E))もボレル集合。
以上より,Yは可測集合(終り)。

としたのですがこれで大丈夫でしょうか?
 

可測集合になること

 投稿者:Imogene  投稿日:2016年12月13日(火)04時57分9秒
  宜しくお願い致します。

E⊂C^2を開領域とし,bをproj_2(E)の集積点, N_b⊂Cをbの開近傍とする。
もし,f:E→Cが可測関数(任意のボレル集合B⊂Cに対してf^-1(B)⊂C^2もボレル集合)なら,
{x∈proj_1(E);f({x}×(N_b∩proj_2(E))⊂C}は可測集合(ボレル集合)となる事を示せ。

はどうすれば示せますでしょうか?
 

京大特色入試 4番の一般化(その5)

 投稿者:かたつむり  投稿日:2016年12月 7日(水)18時17分24秒
  『初等数学』の情報有り難うございます.
いずれにしても,自家用にきちんとまとめる予定です.(そうしないと,じきに忘れてしまうので.)
一般化した問題に答える方が,元の入試問題を「不等式で評価して考える」よりも易しいかもしれません.
(連分数の基本事項を前提とすれば,ですが.)

当初,京大特色入試4番(2)は,難しいだけで,昨年の3番と比べると「数学的構造の面白さ」に欠けると感じていました.
思いがけず〈連分数〉と結びつき,とても楽しめました.昨年の3番が〈巡回行列〉と結びついたことを思い起こします.

【付記】3番は,高校生にとって,∀と∃に関する良い勉強になり,またプログラミングの題材としてもふさわしいと思います.
何か「漸近的な法則」を見出せないものかと,n以下の自然数で後手必勝となるものの個数 f(n) (n≦10^5) を
(すべて)求めてみましたが,徒労に終わりました.ちなみに
 f(100)=20, f(1000)=114, f(10000)=578, f(100000)=2780
でした.
 

『初等数学』

 投稿者:南海  投稿日:2016年12月 7日(水)16時46分9秒
  『初等数学』は,1984年創刊の季刊雑誌です。1冊1000円です。
CiNiiでは
http://ci.nii.ac.jp/ncid/AA11997372
にあります。

私はもう10年以上前からとっていて,2013年にいちど投稿したことがあります。
http://aozoragakuen.sakura.ne.jp/taiwa/taiwasen/egyptian2/node1.html

いつもいくつか面白い文章が載っています。前はサイトもあったのですが,今は「和算の館」の管理人さんがかつてのサイトの一部の写しを置いておられます。
http://www.wasan.jp/shotosugaku/shoto.html

現在は九州の高校の先生が実務をやっておられます。必要なら連絡先など,伝えます。
 

京大特色入試 4番の一般化(その4)

 投稿者:かたつむり  投稿日:2016年12月 7日(水)14時20分33秒
編集済
  >論文の紹介ありがとうございます。
実は,私が読んだのは2頁目のLemma1,2(とその証明)だけ(!)です.
Lemma2の最初の等式に目を奪われました.

>4番の一般化をまとめて,『初等数学』などに投稿していただけないでしょうか。
『初等数学』と言いますのは?
 

Re: 京大特色入試 4番の一般化(その3)

 投稿者:南海  投稿日:2016年12月 7日(水)10時36分17秒
  かたつむりさん,論文の紹介ありがとうございます。
印刷したので,読んでみます。
あるいは出題者は,この論文なんかをもとに,4番を作ったのかも知れません。

できればのお願いですが,4番の一般化をまとめて,『初等数学』などに投稿していただけないでしょうか。たいへんおもしろい分野です。
 

京大特色入試 2番

 投稿者:かたつむり  投稿日:2016年12月 6日(火)18時44分7秒
編集済
  2番(2)で,私は
 a_n=∫_{2}^{3}(t^2-1)^{n-1} dt ・・・(*)
と書き換えてから漸化式を導きました.回り道ですが,(*) を見ると
「a_n が有理数であり,分母が奇数の既約分数で表される」理由(?)が分かります.
「被積分関数が偶数巾のみを含む整数係数の整式で表され,上端・下端が整数である」ので.
 

京大特色入試 4番の一般化(その3)

 投稿者:かたつむり  投稿日:2016年12月 5日(月)17時24分4秒
編集済
  昨日の投稿(その2)における設定を踏襲します.
昨日の段階では,「b が 1/2<b<2 の範囲の無理数の場合」は未解決で,解決済みの内容を整理すると次の通りでした:
・b>2 の場合は S_b(n)-(b/2)n^2→-∞ (n→∞) となる.(その1)の【追記】に記したように比較的易しい.
・0<b<1/2 の場合は S_b(n)-(b/2)n^2→∞ (n→∞) となる.元の入試問題と同様の手法(2通り)が使える.
・b が正の有理数(b=q/p) の場合は,
   q>p+1 なら S_b(n)-(b/2)n^2→-∞ (n→∞),  q<p+1 なら S_b(n)-(b/2)n^2→∞ (n→∞),
     q=p+1 ならS_b(n)-(b/2)n^2 は周期数列になる.

今日ようやく,連分数展開を用い,正の無理数bについて,
   S_b(n)-(b/2)n^2 は,b>1 なら下に有界でなく,b<1 なら上に有界でない
ことを証明できました.次の論文の出だし(2頁目のLemma2)が参考になりました.
 http://people.math.sfu.ca/~vjungic/tbrown/tom-27.pdf
そこに,昨日記した和公式
  Σ{k:from 0 to p-1}[kq/p]=(p-1)(q-1)/2  (p,q は互いに素な正整数)
と同等の等式が書かれていてビックリしました.無理数の場合も,結局これに帰着したわけです.

【付記】たとえば,元の入試問題の√(5)を√(2)で置き換えると,さらに難しくなる(だろう)ということです.
 

/182