[問題]
数直線上の区間［0，1］をn等分して等分点をマークする。これをいくつかのnについて重ねて実行すれば区間［0，1］はさまざまの長さの小区間に分割される。さて、このn等分マークをn=2からn=100までのすべての自然数nについて重ねて実行したとき、同じ長さの小区間は最大いくつ現れるか？



[解答・解説]
この問題は高校生に質問された問題ですが、数時間ぐらいかかってしまいました。

もうノートが計算式だらけになってうへ～！って泣きそうになりながら解きました。

なんか問題を見た感じではほんまにこんなんわかるんかって問題ですね。


ただ色々考えてみたら分数の面白い結果もわかってきました。


まず二つの既約な分数a/c、b/d(a/c＞b/c)をとってきます。

[0,1]区間で2～100等分なのでここで出てくる既約分数は分母、分子が正で100等分までだから分母は100以下で分母≧分子でなければなりません。

a/cとb/dの差をとると

a/c - b/c = (ad-bc)/cd

です。

もしこの二つの分数が隣り合ってる、この二つの分数の間には他の分数が無いとすれば

ad-bc=1

が成り立ちそうな気がしました。


そしたら差は
1/cd
になると言うことは、cdが同じになるcdの組み合わせの数が同じ長さの小区間の数になるのではないか？って思いました。


この方針でやってみたら一応出来ました。
ただ、こんな方法でやるのかどうか知りません。


この問題はユークリッドの互助法を使いまくって解きました。

a/c,b/d(a/c＞b/d)が隣り合うならad-bc=1を示す。

a/cを固定して考えます。
mとnを整数として
am-nc=1
はユークリッドの互助法から
(m_1,n_1)=(d_1,c_1)(100＞d_1＞0,100＞c_1＞0)となる解が存在してd_1とc_1は互いに素である
(公約数を持つとするとad_1-b_1cはその公約数の倍数になるがad_1-b_1c=1より矛盾)
でa≦cだからad1-d1c≦0＜1=ad1-b1cよりd1＞b1でb1/d1は[0,1]区間になる既約分数になっている。

またもう一つ解を
d_2=d_1+jc
b_2=c_1+jc
(j≧0)
でd_2+c＞100
となるものをとってくると既約分数d_2/b_2はam-nc=1から
a/c-n/m=1/cm
よりもっともcmが大きくなる解なのでam-nc=1ではb_2/d_2がa/cに一番近い。

今度は
am-nc=i(i≧2)
を考えてad_1-b_1c=1の両辺をi倍して
aid_1-ib_1c=i
から
m=id_1+kc
n=ib_1+kc
が解である。

a/c-n/m=i/cmよりこのm=id_1+kcの解がさっきのd_2=d_1+jcのi倍より大きくて100以下であればそのn/mがa/cにb_2/d_2より近いことになるが

m＞id_2とすると
id_1+kc＞id_1+ijc
⇔
k＞ij
⇔
k≧ij+1
であるがこの時

m=id_1+kc≧id_1+ijc+c
=i(d_1+jc)+c
=id2+c
＞d2+c＞100

となり矛盾。


よってm=id?1+kcはd_2=d_1+jcのi倍より小さい。

従って、a/cに最も近い隣り合う分数はd_2/c_2である。


まとめると

a/cとb/dが隣り合う分数⇒ad-bc=1、b+c＞100

と言うことは
a/cとb/dが隣りあうなら

a/c-b/d=(ad-bc)/cd
=1/cd

で同じ長さの小区間になるにはこの分母のcdが一定になるようなc+d＜100で0＜c＜100、0＜d＜100となるcdの組み合わせを考えればよいことになります。


例えばp,q,rを整数としてcd=qprの時(c,d)=(q,rp),(pr,q),(r,pq)のように選べばこれらはcdがpqrで一定でそれぞれ違う分数を表すことになります。

ところでまたad-bc=1よりcとdは互いに素です。


ユークリッドの互助法からcとdが決まれば、aとbは一つに決まります。
(a1、b1って解があると
a=a1+kc
b=b1+kd
だから0≦a≦cと0≦b≦cとなる解が一つ存在する)

なので、cとdだけ考えたらよいことになります。


cdが互いに素な整数6つの積である時、

もっとも小さい互いに素な整数は2,3,5,7,11,13
であるが
2・3・5・7・11・13=30030
より
cd≦10000
に矛盾。

よってcdは互いに素な整数が5つ以下の積。

cdが互いに素な整数5つの積である時、

1個と4個って言う組み合わせは明らかに4個はどんなけ小さく選んでも2×3×5×7=210で100を越えるからあり得るのは2個と3個の組み合わせ5C2×2=20通り以下である。


2,3,5,7,11で条件を満たすのは(c,d)=(33,70)(70,33)(35,66)(66,35)(77,30)(30,77)の6つ
2,3,5,7,13で条件を満たすのは(c,d)=(39.70)(70,39)(35,78)(78,35)(65,42)(42,65)(91,30)(30,91)の8つ。

2,3,5,7,17はであるが17と後二つの組み合わせは17を除いた残り4つから2つ選んで4C2=6で17×2×3=102より全て100を越えて、7×17＞100から10-7=3つでcとdの区別を作って3×2=6つ以下。

よって2,3,5,7,q(q≧13)は6つ以下。

2,3,5,q,r(q≧11、r＞q)はq×r＞100で2,3,5から一つ選んでq,rとペアにすると当然これらも100を越えて3×5×r＞100、2×5×r＞100、2×5×q＞100で計7つ以上不適となるから10-7=3で6つ以下。

2,3,q,r.s(q≧7、s＞r＞q)はqrx＞100、3rs＞100、2rs＞100、2qr＞100、3qr＞100、2qs＞100、3qs＞100より6つ以下。

2,q,r,s,t(q≧5、t＞s＞r＞q)はtsr＞100、tsq＞100、2ts＞100、2tr＞100、qtr＞100、2tq＞100、2sr＞100で6つ以下。

3,4,5,7,9
q,r,s,t,u(q≧3、u＞t＞s＞r＞q)はstu＞100、rtu＞100、qtu＞100、rsu＞100、qsu＞100、qru＞100、3ts＞100で6つ以下。

cdは互いに素な整数が4つの積の時、1個と3個の組み合わせはc+dが100を越えようとすると

2×3×5=30で他方は71以上
2×3×7=42で他方は59以上
2×3×11=66で他方は35以上
2×3×13=78で他方は23以上
2×3×17＞100

3×4×5=60で他方は41以上
3×4×7＞100
3×5×7＞100

4×5×7＞100

だから
2×3×5=30で他方は71以上
2×3×7=42で他方は59以上
2×3×11=66で他方は35以上
2×3×13=78で他方は23以上
3×4×5=60で他方は41以上
の組み合わせが考えられるが
2×71＞100
2×59＞100
3×41＞100
より
2×3×5=30で他方は71以上
2×3×7=42で他方は59以上
3×4×5=60で他方は41以上
はc,dの組み合わせは2つ以下

2,3,11,37は(66,37)(74,33)だけでc,dの組み合わせは2×2=4つ。

2,3,13,23は(78,23)の一つだけでc,dの組み合わせは2つ。


2個と2個の組み合わせしかない時、4C2=6よりc、dの組み合わせは6つ以下になる。


cdは互いに素な整数が3つ以下の積の時、3C1×2=6より6つ以下。


よって組み合わせの数が最大になる

2,3,5,7,13で条件を満たすのは(c,d)=(39.70)(70,39)(35,78)(78,35)(65,42)(42,65)(91,30)(30,91)の8つ。

でこの時区間の長さは2×3×5×7×13=2730より
1/2730



c,dの組み合わせを求めるのに途中で何回も血吐いて死にました。

もっと簡単に示せる方法があるんかもしれません。

しかし分母が100以下(有限であればオッケー？)の既約分数とかではa/c,b/dは隣り合っているとad-bc=1になることや、(a+b)/(c+d)がa/c,b/dの間にある新たな既約分数になることなど面白い結果が副産物としてわかりました。

高校数学の問題と解説