🌊

単位分数の和が1(Juliaで解いてみた!)

2021/01/03に公開1

はじめに

2020年の年末に生徒から問題が送られてきました。さっそく考えてみます。

A=\{(x,\,y)|1\leqq x\leqq n,1\leqq y\leqq n,x+y\geqq n+1,\gcd(x,y)=1,n\in\mathbb{N},x\in\mathbb{N},y\in\mathbb{N}\}

このとき,

\sum_{(x,y)\in A}\frac1{xy}=1

を示せ。

Juliaで調べてみる

手で書いていってもいいのですが,Juliaで調べてみることにしました。

function aa1(n)
for x=1:n,y=1:n
    if gcd(x,y)==1 && x+y>=n+1
        println(x,",",y)
        end
    end
end

aa1(10)

1,10
2,9
3,8
3,10
4,7
4,9
5,6
5,7
5,8
5,9
6,5
6,7
7,4
7,5
7,6
7,8
7,9
7,10
8,3
8,5
8,7
8,9
9,2
9,4
9,5
9,7
9,8
9,10
10,1
10,3
10,7
10,9

x<yx>yの場合があるので,n\geqq 2のときは

\sum_{(x,y)\in A,x<y}\frac1{xy}=\frac12

を示せばよさそうです。関数を修正します。また,和が\frac12になることもチェックするようにしました。

function aa2(n)
s=0
for x=1:n,y=x+1:n
    if gcd(x,y)==1 && x+y>=n+1 
            s= s+ 1/(x*y)
        println(x,",",y,",",x*y)
        end
    end
println(s)
end

aa2(10)

1,10,10
2,9,18
3,8,24
3,10,30
4,7,28
4,9,36
5,6,30
5,7,35
5,8,40
5,9,45
6,7,42
7,8,56
7,9,63
7,10,70
8,9,72
9,10,90
0.5

nが1から8までのまとめ

  • n=1のときは(x,y)=(1,1)
\sum_{(x,y)\in A}\frac1{xy}=\frac{1}{1\cdot1}=1
  • n=2のときは(x,y)=(1,2)
\sum_{(x,y)\in A,x<y}\frac1{xy}=\frac{1}{1\cdot2}=\frac12
aa2(3)

1,3,3
2,3,6
0.5

  • n=3のときは(x,y)=(1,3),(2,3)
\sum_{(x,y)\in A,x<y}\frac1{xy}=\frac{1}{1\cdot3}+\frac{1}{2\cdot3}=\frac{2+1}{6}=\frac12
aa2(4)

1,4,4
2,3,6
3,4,12
0.49999999999999994

  • n=4のときは(x,y)=(1,4),(2,3),(3,4)
\sum_{(x,y)\in A,x<y}\frac1{xy}=\frac{1}{1\cdot4}+\frac{1}{2\cdot3}+\frac{1}{3\cdot4}=\frac{3+2+1}{12}=\frac12
aa2(5)

1,5,5
2,5,10
3,4,12
3,5,15
4,5,20
0.5

  • n=5のときは(x,y)=(1,5),(2,5),(3,4),(3,5),(4,5)
\sum_{(x,y)\in A,x<y}\frac1{xy}=\frac{1}{5}+\frac{1}{10}+\frac{1}{12}+\frac{1}{15}+\frac{1}{20}=\frac{12+6+5+4+3}{60}=\frac12
aa2(6)

1,6,6
2,5,10
3,4,12
3,5,15
4,5,20
5,6,30
0.49999999999999994

  • n=6のときは(x,y)=(1,6),(2,5),(3,4),(3,5),(4,5),(5,6)
\sum_{(x,y)\in A,x<y}\frac1{xy}=\frac{1}{6}+\frac{1}{10}+\frac{1}{12}+\frac{1}{15}+\frac{1}{20}+\frac{1}{30}=\frac{10+6+5+4+3+2}{60}=\frac12
aa2(7)

1,7,7
2,7,14
3,5,15
3,7,21
4,5,20
4,7,28
5,6,30
5,7,35
6,7,42
0.5

  • n=7のときは(x,y)=(1,7),(2,7),(3,5),(3,7),(4,5),(4,7),(5,6),(5,7),(6,7)
\sum_{(x,y)\in A,x<y}\frac1{xy}=\frac{1}{7}+\frac{1}{14}+\frac{1}{15}+\frac{1}{21}+\frac{1}{20}+\frac{1}{28}+\frac{1}{30}+\frac{1}{35}+\frac{1}{42}=\frac12
aa2(8)

1,8,8
2,7,14
3,7,21
3,8,24
4,5,20
4,7,28
5,6,30
5,7,35
5,8,40
6,7,42
7,8,56
0.49999999999999994

  • n=8のときは(x,y)=(1,8),(2,7),(3,7),(3,8),(4,5),(4,7),(5,6),(5,7),(5,8),(6,7),(7,8)
\sum_{(x,y)\in A,x<y}\frac1{xy}=\frac{1}{8}+\frac{1}{14}+\frac{1}{21}+\frac{1}{24}+\frac{1}{20}+\frac{1}{28}+\frac{1}{30}+\frac{1}{35}+\frac{1}{40}+\frac{1}{42}+\frac{1}{56}=\frac12

しかし,この後方針がわからず,2,3日停滞する。

Webで調べたこと

この停滞期にWebで調べたことをまとめます。

https://ja.wikipedia.org/wiki/エジプト式分数

https://ja.wikipedia.org/wiki/単位分数

https://ja.wikipedia.org/wiki/ライプニッツの調和三角形

これらの中で

\frac1n=\frac{1}{n+1}+\frac{1}{n(n+1)}

を用いて変形することが書かれており,この方針でいけばいいのかな?と思って,チェックしていきました。

n=1からn=4までは順調に拡張できました。

\frac11=\frac12+\frac12
\frac12=\frac13+\frac16
\frac13=\frac14+\frac12

しかし,n=4からn=5にかけて

\frac16=\frac1{10}+\frac1{15}

は説明できない変形が出てきました。

その後もn=6からn=7にかけて

\frac1{10}=\frac1{14}+\frac1{35}
\frac1{12}=\frac1{21}+\frac1{28}

とでてきたので,違うロジックが必要なのだと理解しました。

そして,そもそも,x+y\geqq n+1の条件がどのように効いてくるのかがまだ見えていませんでした。

今回とは関係なかったのですが,1を2桁までの単位分数の和で表す話は面白かったです。

解答に向かって

解答の鍵となったのはx+y\geqq n+1でした。数学的帰納法でn=kからn=k+1へちゃんと作ってみることにしました。(ここまで4日くらいかかっています。)

  • n=kのとき,k+1\leqq x+y\leqq 2kである。
(x,y)=(p_1,q_1),(p_2,q_2),\cdots (p_N,q_N)\cdots\bigstar

とする。

  • n=k+1のとき,k+2\leqq x+y\leqq 2k+2である。

    • \bigstarの中で,p_r+q_r\geqq k+2のものそのまま使える。
    • \bigstarの中で,p_r+q_r= k+1のものは
\frac{1}{p_rq_r}=\frac{1}{k+1}\left(\frac1{p_r}+\frac1{q_r}\right)=\frac1{(k+1)p_r}+\frac1{(k+1)q_r}

とすればよい。

このとき,

k+1+p_r\leqq k+1+k=2k+1\leqq 2k+2

k+1+q_r\leqq k+1+k=2k+1\leqq 2k+2

である。また,
k+1=\alpha s,p_r=\beta s,\gcd(\alpha,\beta)=1とすると,p_r+q_r= k+1より,

q_r=k+1-p_r=(\alpha-\beta)s

s\geqq 2とすると,\gcd(p_r,q_r)=1に反する。
よって,s=1となり,\gcd(p_r,k+1)=1である。同様に\gcd(q_r,k+1)=1となる。

よって,n=k+1のとき,(x,y)を構成できた!

Discussion

さざんかぬふさざんかぬふ

こんにちは、この問題はとてもおもしろいですね!
30分ぐらい、図を描いていたら解けました。参考まで。
(定石っぽいですが、n(=k)を増やした時にはみ出す部分と増える部分の対応を取りました。)

これ、どうやって気づいたんだろう、ということに興味がわきました。センスのある生徒さんですね。

※あまりにも日本語になっていなかったので補足
黄色のセルの→と↓にある緑のセルの和を計算すると、黄色のセルの値になります。その計算を図の下の方に書いていました。このような対応付をすると、黄色のセルと緑のセル2つの対応がつき、したがって全体の総和としても対応がつくので、和の値が一定=1になるということで、数学的帰納法によって示される、という事でした。