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

4 min read読了の目安(約4200字 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)を構成できた!