実数p,qと任意のnに対して、
点(p,q)を中心とする円の内部にn個の格子点を含められるようなp,qの条件を求めよ。
無理数は当てはまる気がするのですが、それ以外の求め方が分からないです
|
No.73287 - 2021/03/13(Sat) 13:00:55
| ☆ Re: 格子点 / IT | | | 各ｎに対して適当な円の半径が取れて、ちょうどｎ個の格子点を含められるように出来る。
という意味でしょうか？ 問題文をそのまま書いてください。
まず 0≦p≦1/2,0≦q≦1/2 のときだけ 考えればよさそうですね。
|
No.73291 - 2021/03/13(Sat) 14:34:44 |
| ☆ Re: 格子点 / IT | | | ダメな場合を考えればよい気がします。
ダメな場合とは、
ある実数ｒについて、(p,q)を中心とする半径ｒの円周上に２点以上の格子点がある。
|
No.73294 - 2021/03/13(Sat) 14:53:37 |
| ☆ Re: 格子点 / あさみ | | | 各ｎに対して適当な円の半径が取れて、ちょうどｎ個の格子点を含められるように出来るという意味です
|
No.73295 - 2021/03/13(Sat) 15:03:52 |
| ☆ Re: 格子点 / IT | | | 任意の異なる２つの格子点(a,b),(c,d)を結ぶ線分の垂直二等分線上にない。 という条件で調べると良いかも知れません。
（出来てはいませんが）
（いかなる異なる２つの格子点(a,b),(c,d)からも、等距離にない と同じことですね）
|
No.73297 - 2021/03/13(Sat) 15:19:39 |
| ☆ Re: 格子点 / あさみ | | | No.73306 - 2021/03/13(Sat) 21:14:51 |
| ☆ Re: 格子点 / あさみ | | | 調べてみましたが、結局答案のまとめ方が分からないです。
|
No.73307 - 2021/03/13(Sat) 21:40:33 |
| ☆ Re: 格子点 / あさみ | | | 高2の数列の格子点の範囲の問題です。
先生が言うには高校レベルで解けるそうです。
|
No.73309 - 2021/03/13(Sat) 21:59:43 |
| ☆ Re: 格子点 / あさみ | | | ありがとうございます。
思っていたよりも難しい問題ですね。
p、qが√3と1の時に
各ｎに対して適当な円の半径が取れて、ちょうどｎ個の格子点を含められるように出来ることを示す
問題が学校の出てきて解けたのですが、それじゃp、qがどんな時に成り立つのかを
調べてみるように言われて困っていました。
|
No.73311 - 2021/03/13(Sat) 22:23:41 |
| ☆ Re: 格子点 / IT | | | 2つの異なる格子点(a,b),(c,d) から (p,q)が等距離にある
⇔ 2(c-a)p+2(d-b)q=c^2+d^2-(a^2+b^2)…(1)
このような２つの格子点がないための必要十分条件を求めるのですが
p、qが√3と1のとき条件を満たす（十分である）ことを示すのは簡単ですが
すべての場合を考えるのは結構難しそうですね。
（数列の問題というより整数の問題といえると思います）
|
No.73313 - 2021/03/13(Sat) 22:54:31 |
| ☆ Re: 格子点 / らすかる | | | 少なくとも
「uv≠0かつup+vq+w=0を満たすような整数u,v,wが存在しない」
を満たせば、条件を満たします。
2つの格子点の垂直二等分線は整数係数の直線になりますので、
上記の条件を満たせばp,qは格子点の垂直二等分線になり得ず、
異なる同距離の格子点は存在しません。
逆を考えてみると
(x-p)^2+(y-q)^2=r^2にx=ut,y=vt（tは実数）を代入して整理すると
(u^2+v^2){t+w/(u^2+v^2)}^2-w^2/(u^2+v^2)+p^2+q^2=r^2となりますので、
(u^2+v^2)c^2-w^2/(u^2+v^2)+p^2+q^2＞0を満たすように
t+w/(u^2+v^2)=±cを定めれば
r=√{(u^2+v^2)c^2-w^2/(u^2+v^2)+p^2+q^2}として
x=ut,y=vtただしt=-w/(u^2+v^2)±cが条件を満たします。
しかしx,yは整数でなければなりませんので、
固定のrに対し複数のtで式を満たすためには
w/(u^2+v^2)が1/2の整数倍すなわち
2w/(u^2+v^2)が整数でなければならないと思います。
よって2w/(u^2+v^2)=kとおけばw=(u^2+v^2)k/2なので
up+vq+w=0は
2up+2vq+(u^2+v^2)k=0となり、
「uv≠0かつ2up+2vq+(u^2+v^2)k=0を満たすような整数u,v,kが存在しない」
が必要十分条件になりそうですが、あまり自信がありません。
|
No.73314 - 2021/03/13(Sat) 23:33:25 |
| ☆ Re: 格子点 / IT | | | 0＜p＜1/2,0＜q＜1/2 のときだけ 考えることにして
(p=0,1/2 などの場合は２つ以上の格子点が等距離にあります）
らすかるさんの uv≠0かつ2up+2vq＝k(u^2+v^2) でs=2p,t=2q とおくと
0＜s＜1,0＜t＜1 で|us+vt|=|k(u^2+v^2)|
ここで0≦|us+vt｜≦|us|+|vt|＜|u|+|v|≦u^2+v^2なので
k=0 したがってus+vt=0
すなわち（すこし端折ってますが）
q/p=-u/v（有理数）の場合はだめ
q/pが無理数ならOK
これをxy平面全体に拡大する。
|
No.73320 - 2021/03/14(Sun) 07:03:27 |
| ☆ Re: 格子点 / らすかる | | | > これをxy平面全体に拡大する。
一般には、例えばp=2√2,q=3-√2のようにq/pが無理数であっても
だめな場合がありますが、うまく「拡大」できるのでしょうか。
|
No.73324 - 2021/03/14(Sun) 09:45:55 |
| ☆ Re: 格子点 / IT | | | p,q （2p,2qかも） の小数部分を考えればよいのでは？
↑だめですね。
ということは、この前の議論も間違っていそうです。
|
No.73327 - 2021/03/14(Sun) 09:56:31 |
| ☆ Re: 格子点 / IT | | | 「スタインハウスの問題」という（有名）問題のようです。
下記に記述がありますが、一般解は載っていません。
（載ってないところをみると、簡単な表現はないのかも知れません。）
先生が答えを示されたら教えていただきたいです。
http://ikuro-kotaro.sakura.ne.jp/koramu/372_s.htm
http://infoshako.sk.tsukuba.ac.jp/~hachi/COS/combin.jp/maebara_08.pdf
|
No.73337 - 2021/03/14(Sun) 18:41:10 |
| ☆ Re: 格子点 / らすかる | | | ちょっと間違いがありましたので訂正します。
73314の2行目
「uv≠0かつup+vq+w=0を満たすような整数u,v,wが存在しない」
は間違いで、正しくは
「u^2+v^2≠0かつup+vq+w=0を満たすような整数u,v,wが存在しない」
でした。
つまり「uとvは両方とも0であってはならない」（片方が0でもよい）
を（最初から）数式で書きたかったのですが、
これを「uv≠0」でよいと勘違いしていました。
u^2+v^2≠0ならば「少なくとも一つは0ではない」になりますので
これが正しい式です。
下から2行目も同様に
「uv≠0かつ2up+2vq+(u^2+v^2)k=0を満たすような整数u,v,kが存在しない」
ではなく
「u^2+v^2≠0かつ2up+2vq+(u^2+v^2)k=0を満たすような整数u,v,kが存在しない」
が正しいです。
> ITさん
「スタインハウスの問題」は
「この問題の条件を満たすようなp,qは存在するか」だけで
p,qの条件までは問うていないように思います。
|
No.73338 - 2021/03/14(Sun) 19:27:38 |
| ☆ Re: 格子点 / IT | | | らすかるさんの
＞「u^2+v^2≠0かつ2up+2vq+(u^2+v^2)k=0を満たすような整数u,v,kが存在しない」が必要十分条件になりそうですが、あまり自信がありません。
勘違いかも知れませんが、反例を書きます。
らすかるさんが示された(p,q)=(2√2,3-√2)を適当に移動した
(p,q)=(3-2√2,√2-1)を考えると、２つの格子点(2,-3),(4,1)から等距離にあり、
0＜p＜1/2,0＜q＜1/2…(1) です。
この(p,q)について
u^2+v^2≠0かつ2up+2vq+(u^2+v^2)k=0…(A)を満たすような整数u,v,kが存在すると仮定すると、
|2up+2vq|=|(u^2+v^2)k|
ここで(1) から0＜2p＜1,0＜2q＜1 であり、u,v の少なくとも１つは０でないことから
|2up+2vq|＜｜u|+|v|≦u^2+v^2 なので k=0
よって up+vq＝0
すなわち u(3-2√2)+v(√2-1)=0
整理して (3u-v)+(v-2u)√2=0
u,v は整数で√2は無理数なので 3u-v＝v-2u＝0∴ u=v=0
(A) を満たすような整数u,v,kは存在しない。
|
No.73340 - 2021/03/14(Sun) 22:11:36 |
| ☆ Re: 格子点 / らすかる | | | 実例と比較して、「x=ut,y=vtとおくのが間違い」と気づき、再度考え直しました。
u^2+v^2≠0かつup+vq+w=0を満たす整数u,v,wが存在するとき
「wがgcd(u,v)で割り切れる」⇔「au+bv+w=0を満たす整数a,bが存在する」
であり、このようにa,bを定めることができたとき
(x-p)^2+(y-q)^2=r^2にx=ut+a,y=vt+b（tは整数）を代入して整理すると
(u^2+v^2)t^2+(p-a)^2+(q-b)^2=r^2
となりますので、r=√{(u^2+v^2)c^2+(p-a)^2+(q-b)^2}（cは0でない整数）
とすればt=±cすなわち(x,y)=(uc+a,vc+b),(-uc+a,-vc+b)の2格子点を通ります。
(x-p)^2+(y-q)^2=r^2にx=ut+a,y=vt+bを代入してtに関して平方完成したときに
{t+(au+bv+w)/(u^2+v^2)}^2となりますが、wがgcd(u,v)で割り切れなければ
(au+bv+w)/(u^2+v^2)は整数にも半整数にもならず、{t+(au+bv+w)/(u^2+v^2)}^2が
同一値になる2整数がとれませんので、複数の格子点を通りません。
よって問題の条件を満たす必要十分条件は
「up+vq+w=0を満たす整数u,v,w（uとvは互いに素）が存在しない」
になると思います。
# 0と0は互いに素ではありませんのでu^2+v^2≠0は省略できます。0と1は互いに素です。
# 100%ではありませんが、以前よりは自信があります。
# 出題した先生はこんなとこまでちゃんと考えているんですかね？
|
No.73344 - 2021/03/15(Mon) 04:47:54 |
| ☆ Re: 格子点 / あさみ | | | 難しい問題なのですね。
最初3日間ぐらい一人で考えていてわからなかったので、
姉(No.73084で質問を書いている人)にも聞いたけど、多分かなりの難問で解けないって言われたので
ここで聞いてみました。
先生に確認しに行ったら、本当に挑戦する人が居るとは思わなかったと言われました。先生も解答を持っていないそうです。ひどいです。
|
No.73355 - 2021/03/15(Mon) 18:53:28 |
| ☆ Re: 格子点 / IT | | | らすかるさんのNo.73344の後半で
> (x-p)^2+(y-q)^2=r^2にx=ut+a,y=vt+bを代入して
>
> tに関して平方完成したときに
> {t+(au+bv+w)/(u^2+v^2)}^2となりますが、
> wがgcd(u,v)で割り切れなければ ．．．
とありますが、ここのa,b はどんなa,b ですか？
任意の整数ということでしょうか？
前半の
>「au+bv+w=0を満たす整数a,bが存在する」
であり、このようにa,bを定めることができたとき
は、掛かっていないので、このa,b ではないですよね？
|
No.73361 - 2021/03/15(Mon) 21:19:33 |
| ☆ Re: 格子点 / あさみ | | | 姉が5日前に京大理学部に合格しました。
できれば私も京大に行きたいです。
京大だとこのレベルの問題が解けないといけないのですね。
受験まであと2年あるので頑張ります。
|
No.73362 - 2021/03/15(Mon) 23:02:07 |
| ☆ Re: 格子点 / らすかる | | | > ITさん
> > (x-p)^2+(y-q)^2=r^2にx=ut+a,y=vt+bを代入して
> >
> > tに関して平方完成したときに
> > {t+(au+bv+w)/(u^2+v^2)}^2となりますが、
> > wがgcd(u,v)で割り切れなければ ．．．
> とありますが、ここのa,b はどんなa,b ですか？
> 任意の整数ということでしょうか？
>
> 前半の
> >「au+bv+w=0を満たす整数a,bが存在する」
> であり、このようにa,bを定めることができたとき
> は、掛かっていないので、このa,b ではないですよね？
同じa,bなのですが、ちょっと書き方がいい加減、というか
きちんと整理できていませんね。
a,bを任意の整数としてx=ut+a,y=vt+bを代入して平方完成まですると
{t+(au+bv+w)/(u^2+v^2)}^2という形になるので、
もしau+bv+w=0となる整数a,bが存在するならば少し上の
(u^2+v^2)t^2+(p-a)^2+(q-b)^2=r^2
という形にまとめることができて、同距離の複数点が存在する、という意味です。
そしてau+bv+w=0となる整数a,bが存在しない場合はどんなa,bを使っても
(au+bv+w)/(u^2+v^2)の項が消えないから、・・・
という議論です。
|
No.73364 - 2021/03/15(Mon) 23:45:05 |
| ☆ Re: 格子点 / IT | | | なるほど、きれいな証明というよりも、着想を基にして 証明の大綱を説明されたという感じですかね。
|
No.73365 - 2021/03/16(Tue) 07:31:26 |
| ☆ Re: 格子点 / らすかる | | | 最初はきれいに書いたつもりだったのですが、不備を補い
つぎはぎしているうちに「ただの着想のメモ」っぽくなってしまいました。
|
No.73366 - 2021/03/16(Tue) 08:11:10 |
| ☆ Re: 格子点 / あさみ | | | 〉(x-p)^2+(y-q)^2=r^2にx=ut+a,y=vt+bを代入してtに関して平方完成したときに
〉{t+(au+bv+w)/(u^2+v^2)}^2となりますが、
wはどこから出てきたのですか？
|
No.73367 - 2021/03/16(Tue) 11:50:14 |
| ☆ Re: 格子点 / IT | | | ある実数ｒについて、(p,q)を中心とする半径ｒの円周上に２点以上の格子点がある。
ための(p,q)の条件（必要十分条件）を考えることにした方が分かりやすいですね。
まず必要条件として、
「u^2+v^2≠0かつup+vq+w=0を満たす整数u,v,wが存在する」を導いて、ここから議論を始める。ということだと思います。
|
No.73368 - 2021/03/16(Tue) 12:45:30 |
| ☆ Re: 格子点 / あさみ | | | 議論を始めるところは分かったのですが、
そうすることで上の部分で平方完成したらいきなりwが出てくるのでしょうか？
|
No.73369 - 2021/03/16(Tue) 14:11:41 |
| ☆ Re: 格子点 / らすかる | | | (x-p)^2+(y-q)^2=r^2を展開すると
-2px,-2qyという項が含まれていますので
x=ut+a,y=vt+bを代入して展開すると
-2upt,-2vqtという項が出てきます。
up+vq+w=0からup+vq=-wですから
-2upt-2vqt=-2(up+vq)t=2wtとまとめれば
wが出てきますね。
|
No.73370 - 2021/03/16(Tue) 15:40:06 |
| ☆ Re: 格子点 / あさみ | | | wが出てくる部分は理解出来ました。
ありがとうございました。
|
No.73373 - 2021/03/16(Tue) 19:00:36 |
| ☆ Re: 格子点 / IT | | | 勘違いかも知れませんが、反例を挙げます。
(p,q)=(√2,-2√2+5/2) について考えます。
(p,q) は、直線4x+2y-5=0 上にあります。ここでgcd(4,2)=2 です。
この直線上の任意の点から２つの格子点(0,0),(2,1) は等距離にあります。
今この(p,q)が整数係数の直線 ux+vy+w=0,（ただしgcd(u,v,w)=1）上にあるとすると
u√2+v(-2√2+5/2)+w=0
(u-2v)√2+5v/2+w=0
∴ u=2v, 5v/2+w=0
∴ v=2,u=4,w=-5
すなわち (p,q)を通る整数係数の直線は、4x+2y-5=0 のみである。
したがってup+vq+w=0,(u,vは互いに素)なる整数 u,v,w は存在しない。
ところが、(p,q) から２つの格子点(0,0),(2,1) は等距離にある。
＃だいぶスレッドが長くなったので、私の投稿で本筋に関係ないものは削除します。
|
No.73375 - 2021/03/16(Tue) 21:33:23 |
| ☆ Re: 格子点 / らすかる | | | やはり反例がありましたか。
私の回答でtが整数と決めつけていますが
ひょっとして整数でなくても成り立つ場合もあるかも、とは思っていました。
（そこが100%の自信がない点でした）
「up+vq+w=0を満たす整数u,v,wが存在する場合」の条件は難しいですね。
|
No.73379 - 2021/03/17(Wed) 00:00:12 |
| ☆ Re: 格子点 / らすかる | | | 中途半端な状態で終わらせるのは気持ち悪いので、
改めて別の方法で考え直しました。
今度は（凡ミスや考え落としなどの間違いはあるかも
知れませんが）完全解答にしたつもりです。
2つの格子点から等距離の点の集合は整数係数の直線なので
「u^2+v^2≠0かつup+vq+w=0を満たすような整数u,v,wが存在しない」
を満たす場合は(p,q)から同距離の複数の点が存在することはありません。
u^2+v^2≠0かつup+vq+w=0を満たすような整数u,v,w(gcd(u,v,w)=1)が存在する場合に
同距離の複数の点が存在するかどうかを検討します。
(p,q)はux+vy+w=0上の点
格子点(a,b)を通り直線ux+vy+w=0に直交する直線は(x-a)v=(y-b)u
この直線とux+vy+w=0の交点は
((av^2-uw-buv)/(u^2+v^2),(bu^2-vw-auv)/(u^2+v^2))
なので、直線ux+vy+w=0に関して(a,b)と対称の位置にある点は
(2(av^2-uw-buv)/(u^2+v^2)-a,2(bu^2-vw-auv)/(u^2+v^2)-b)
=((av^2-au^2-2uw-2buv)/(u^2+v^2),(bu^2-bv^2-2vw-2auv)/(u^2+v^2))
=(a-2u(au+bv+w)/(u^2+v^2),b-2v(au+bv+w)/(u^2+v^2))
よって
2u(au+bv+w)/(u^2+v^2)と2v(au+bv+w)/(u^2+v^2)が
整数になるようなa,bが存在する条件を考えればよい。
uv=0（u^2+v^2≠0なのでu,vのうち一つだけ0）の場合
例えばu=0とすると
2u(au+bv+w)/(u^2+v^2)=0
2v(au+bv+w)/(u^2+v^2)=2v(bv+w)/v^2=2b+2w/v
よってvが2wの約数であればよいが、u=0からgcd(v,w)=1なのでv=±1,±2
v=0のときも同様なので、uv=0の場合は
(u,v)=(0,±1),(0,±2),(±1,0),(±2,0)のみ。
u=v（u^2+v^2≠0なのでu=v≠0）の場合
2u(au+bv+w)/(u^2+v^2)=2v(au+bv+w)/(u^2+v^2)=a+b+w/u
よってuがwの約数であればよいが、gcd(u,v,w)=1なのでu=v=±1でなければならない。
従ってu=vの場合は(u,v)=(±1,±1)のみ。
uv≠0,u≠v,gcd(u,v)=1の場合
au+bv+wが任意の値をとれるので、必ず分子をu^2+v^2の倍数にすることが
出来る。よってuとvが0でなく互いに素なら必ず割り切れるようなa,bがとれる。
uv≠0,u≠v,gcd(u,v)=g＞1の場合
u=gs,v=gtを代入して整理すると
2s(as+bt+w/g)/(s^2+t^2), 2t(as+bt+w/g)/(s^2+t^2)
gcd(u,v,w)=1からwはgで割り切れないのでg=2と決まり、
s(2as+2bt+w)/(s^2+t^2), t(2as+2bt+w)/(s^2+t^2)
となる。
sとtは互いに素なので、a,bを変化させることにより
2as+2bt=2(as+bt)は任意の偶数をとることができる。
もしsもtも奇数のときs^2+t^2は偶数となるが、
wが奇数（∵gcd(u,v,w)=1）なので分子は奇数となり、
a,bをどう変えても割り切れることはない。
よってs,tのうちどちらかが偶数でなければならない。
（両方偶数ということはない。）
このときs^2+t^2は奇数なので、aとbの値を変えることにより
2as+2bt+wはs^2+t^2の任意の奇倍数をとることができて、
割り切れるようなa,bがとれる。
以上をまとめると、(a,b)とux+vy+w=0に関して対称な点が
格子点となるような(a,b)が取れるのは
・gcd(u,v)=1（(0,±1),(±1,0),(±1,±1)はこれに含まれる）
・gcd(u,v)=2で、uv/4が偶数（(0,±2),(±2,0)はこれに含まれる）
となるので、
円の内部に任意個の格子点を含められる、すなわち(p,q)から同距離の
複数の点が存在しないための必要十分条件は、
「u^2+v^2≠0かつup+vq+w=0を満たす整数u,v,wが存在しない」または
「u^2+v^2≠0かつup+vq+w=0を満たす整数u,v,w（gcd(u,v,w)=1）が存在し、
gcd(u,v)≧3または「gcd(u,v)=2かつuv/4が奇数」」
となります。
# u,v,wが複数組とれる場合は、gcd(u,v)が最小となるようにします。
# （p,qが整数の場合など）
|
No.73380 - 2021/03/17(Wed) 06:54:01 |
| ☆ Re: 格子点 / IT | | | 私も解いてみました。
点P(p,q) から等距離にある２つの異なる格子点をA(a,b),B(a+u,b+v)とする。
u^2+v^2≠0である。
A,B から等距離にある点からなる直線の方程式は
2ux+2vy＝2(ua+vb)+u^2+v^2 …(1)
これと等価な整数係数の直線の方程式で３つの係数のgcdが1であるものについて条件を求める。
g=gcd(u,v)とおく u=gs,v=gt とおくとgcd(s,t)＝1で、sa+tbは任意の整数値をとる。…(2)
(1)をgで割って､2sx+2ty=2(sa+tb)+g(s^2+t^2)…(3)
g が偶数または、s,tがともに奇数の場合は、
(3)の各係数が偶数となるので、両辺を２で割ると
sx+ty=(sa+tb)+g(s^2+t^2)/2 右辺は任意の整数値をとる。
g が奇数で
sが偶数、tが奇数 またはsが奇数、tが偶数のとき
g(s^2+t^2)は奇数となるので、
(2)より2(sa+tb)+g(s^2+t^2)は任意の奇数値をとる
# いずれの場合もu^2+v^2≠0を満たしている。
よって(p,q)から等距離の複数の点が存在するための必要十分条件は、
下記のどれかを満たすような整数s,t,w があることである。
sp+tq=w (s,t は互いに素)
4sp+2tq=w (t,wは奇数,s,t は互いに素）
2sp+4tq=w（s,wは奇数,s,t は互いに素)。
|
No.73383 - 2021/03/17(Wed) 21:44:20 |
|
