(1)左の分数をa/b右の分数をc/dとして、a/b<c/dが成り立つとする。(a,cは0以上の整数、b,dは自然数とする)

ここで、a/b<c/d　から　ad-bc<0 が導ける。

この２分数の間に出来る分数は

(a+c)/(b+d)となる。

a/b-(a+c)/(b+d) = (ad-bc)/(b(b+d)) < 0
(a+c)/(b+d)-b/d = (ad-bc)/((b+d)d) < 0

より、a/b < (a+c)/(b+d) < b/d となる

あとは帰納法で(詳細省略)

＝＝＝＝＝＝＝＝＝＝
(3)が分かれば(2)は簡単に導けるんだけど…

問題を解く上で使用する言葉の補足。
分数列に対して、すべての隣り合う分数a/b,c/dから(a+c)/(b+d)を間に生成することを「一回の操作」と言うことにする。
0/1,1/1は0段目として、n回目の操作の後に得られる分数列はn段目と言うことにする。

(1)分数列の段数について、0から1まで大きさの順（等号成立はしない）に並んでいることを数学的帰納法で示す。
［証明］
1段目の分数列は0/1,1/2,1/1で確かに0以上1以下で大きさの順に並んでいる。
n段目の分数列について、大きさの順に並んでいるとして、(n+1)段目の分数列も大きさの順に並んでいることを示す。
n段目の任意の隣り合う二つの分数を、a/b,c/dとする。
帰納法の仮定より二数は大小の順に並んでいるので、a/b＜c/dが成立している。
0以上1以下の分数であるので、aは非負整数、b,c,dはすべて自然数だとする。
このとき、両辺bd＞0をかけると、ad＜bc（あるいはbc-ad＞0）が成立する�@。

一回操作するとこの分数の間に生成されるのは(a+c)/(b+d)という分数である。
これがa/b＜(a+c)/(b+d)＜c/dを満たすことを言えばよい。
まず左側について。
(a+c)/(b+d)-a/b
通分しても分母は正なので、通分後の分子だけ取り出して計算すると、
b(a+c)-a(b+d)=ab+bc-ab-ad=bc-ad＞0（∵�@）

c/d-(a+c)/(b+d)も同様に通分して分子だけ取り出して計算すると、
c(b+d)-d(a+c)=bc+cd-ad-cd=bc-ad＞0（∵�@）
したがってn段目が大小の順に並んでいるとき、n+1回目の操作によって間の数を生成すれば、大きさも間に入る。
したがって大きさの順に並んでいるn段目の隣り合う分数の間に、大きさがその間に入るような分数を生成しているので、n+1段目も大小の順に並んでいる。

以上より数学的帰納法からすべての分数列において、分数は大きさの順に並んでいる。［証明終］

(2)…を解く前に。
No.2のヒントとは方針が異なるようなので、解答の方針について具体的に三段目辺りで説明します。

0段目
0/1,1/1

1段目
0/1,1/2,1/1

2段目
0/1,1/3,1/2,2/3,1/1

3段目
0/1,1/4,1/3,2/5,1/2,3/5,2/3,3/4,1/1

…

三段目を見ると、ど真ん中に1/2がいて、1/2から見て右と左に同じだけ離れた分数を足し算すると1になっています。
例えば1/2の二つ隣りは1/3と2/3で足すと1になっています。
また1/2より左側を見ると、分数をa/bと表したとき、その一つ上の2段目の分数がa/(b-a)になっています。
例えば2/5だと真上は2/3=2/(5-3)です。
分数の数も三段目の0/1から1/2までがぴったり二段目の0/1から1/1になっています。

これらの性質を帰納法を用いて示します。
ただしnは自然数で考えます。

示すべき命題
(i)n段目の分数列の項数をS(n)と書くと、S(n)は奇数2m+1と表される。
（またS(n)=2m+1と表すとm≧1となる）
このとき中央、つまり左からm+1番目は1/2になる。

補題：S(n)はS(n+1)=2S(n)-1の漸化式を満たす。
∵項数をS(n)とするとと、間はS(n)-1個あるので、そこに間の分数を生成すればS(n)-1項増えて、S(n+1)=S(n)+S(n)-1=2S(n)-1となる。またm=1ならS(1)=3なので、漸化式よりS(n)は単調増加だと分かる。
これはmの範囲が自然数かどうかなどで迷う必要はないことを保証するためである。

(ii)n段目の分数列において、中央からみて左右対称な位置にある分数を足し算すると1になる。
つまり、n段目の左からk番目の分数をA(n,k)と書くと(1≦k≦m+1)、中央について対称な位置は右からk番目、すなわち左からS(n)-k+1=(2m+1)-k+1=(2m+2-k)番目であり、これをA(n,2m+2-k)と書けば、
A(n,k)+A(n,2m+2-k)=1である。

(iii)n段目の中央から左側についてみる。
n段目、左からk番目の分数をA(n,k)=a/bと書いたとき（1≦k≦m+1）、A(n-1,k)=a/(b-a)である。
（なお項数がそろっていることは、漸化式S(n+1)=2S(n)-1よりS(n)=2m+1のとき、S(n-1)=m+1であることから確認でき、1/2の真上は1/1となっている。
また、中央より左側なのでa/b≦1/2であるから、a/(b-a)=1/(b/a-1)≦1となるので、少なくとも0以上1以下な分数にはなっている。
これらについては特に証明しない。）

これらを帰納法を用いて証明する。
さらにこれと併せて、n段目の分数がすべて既約分数、すなわち分母分子が互いに素であることも帰納法を用いて証明する。
これは上の三つの命題のうち、二つ目と三つ目、および一般に自然数x,yが互いに素なときは、x,(x±y)も互いに素であることを利用します。

［証明］（一気に）
以上の命題を帰納法により証明する。
1段目の分数は0/1,1/2,1/1である。
分数の数は3個で奇数であり、中央、すなわち左から2番目は1/2である。
また左右対称な分数同士足し算すると、0/1+1/1=1, 1/2+1/2=1であり、確かに満たす。
また0/1,1/2について、a/bと表したときにそれぞれa/(b-a)を作ると
0/(1-0)=0/1
1/(2-1)=1/1
となり0段目の分数列と一致している。
またすべての分数が既約分数である。

n段目の分数列について以上の命題が成立しているとする。
この仮定を用いてn+1段目の分数列についても成立していることを示す。
まず項数については補題よりS(n+1)=2S(n)-1なので、必ず奇数になる。
またS(n)=2m+1と書くと、S(n+1)=2(2m+1)-1=2(2m)+1であり、中央は(2m)+1である。
帰納法の仮定(i)より、n段目の1/2は左からm+1番目にある。
一番左から1/2まで間はm個あるから、間に分数を生成するとm個増える。
したがって、1/2はn+1段目では左から(m+1)+m=2m+1番目である。
したがって1/2は中央に位置している。（(i)の成立）

n段目の中央より左の分数A(n,k)(1≦k≦m+1)と、それと中央について左右対称A(n,2m+2-k)について、帰納法の仮定(ii)より
A(n,k)+A(n,2m+2-k)=1が成立している。
n段目の左からk番目の分数は、上の1/2と同様にして考えれば、n+1段目になると左から2k-1番目になる。
同様に左から(2m+2-k)番目の分数は、n+1段目では2(2m+2-k)-1=4m+3-2k=S(n+1)+2-2k=S(n+1)-(2k-1)+1番目になる。
つまり左から(2m+2-k)番目とは、右から(2k-1)番目であり、二つは中央について左右対称な位置にある。
したがって任意の分数についてn段目で左右対称なら、n+1段目でも左右対称な位置にある。
このとき、A(n,k)+A(n,2m+2-k)=1であったので、n+1段目でも
A(n+1,2k-1)+A(n+1,4m+3-2k)=1は成立する。

次にn+1段目になったときに生成された分数についても成立することを示す。
n段目の隣り合う分数A(n,k)=a/b、A(n,k+1)=c/dと表す。
（1≦k≦m　←となり合う二分数なので一つ少ないことに注意。mの範囲を指摘したのはこういうことがあるためである。）
すると対称な位置の分数はそれぞれ
A(n,2m+2-k)=1-a/b=(b-a)/b
A(n,2m+2-k-1)=1-c/d=(d-c)/d
である。
n+1段目を生成すると、k番目は2k-1番目へ、k+1番目は2k+1番目になるので、
A(n+1,2k-1)=A(n,k)=a/b
A(n+1,2k+1)=A(n,k+1)=c/d
であり、間の分数は
A(n+1,2k)=(a+c)/(b+d)
である。
また対称な位置の二数から生成されるほうを考える。
n段目の左から(2m+2-k)番目は、n+1段目の左から2(2m+2-k)-1=(4m+3-2k)番目。
n段目の左から(2m+2-k-1)番目、n+1段目の左から2(2m+1-k)-1=(4m+1-2k)番目であって、
A(n+1,4m+3-2k)=A(n,2m+2-k)=(b-a)/b
A(n+1,4m+3-2k-2)=A(n,2m+2-k-1)=(d-c)/d
である。
したがって間の数は左から(4m-2k+2)番目であり、その分数は
A(n+1,4m-2k+2)={(d-c)+(b-a)}/(b+d)={(b+d)-(a+c)}/(b+d)=1-(a+c)/(b+d)=1-A(n+1,2k)
となる。
4m-2k+2=S(n+1)-2k+1（∵S(n+1)=4m+1）
なので、左から(4m-2k+2)番目とはすなわち右から2k番目のことである。
つまりn+1段目の対称な位置に新たに生成された二つの分数についても和が1となっている（(ii)の成立）。

最後に(iii)について。
n段目において、帰納法の仮定より、n段目左からk番目の分数をA(n,k)=a/bと書いたとき（1≦k≦m+1）、A(n-1,k)=a/(b-a)である。
n段目左からk番目は、n+1段目では左から(2k-1)番目であるので、
A(n+1,2k-1)=A(n,k)=a/b
一方n-1段目左からk番目も、n段目では左から(2k-1)番目であるので、
A(n,2k-1)=A(n-1,k)=a/(b-a)
となる。
したがってn+1段目の分数A(n+1,2k-1)=a/bとすると、その真上のn段目の分数はA(n,2k-1)=a/(b-a)となり、(iii)を満たしている。
（なお項数は中央1/2が左からm+1番目で、n+1段目では2m+1番目になることから、n段目の分数全体の個数と一致していることは確認できる）

n+1段目で新たに生成された分数についても成立していることを示す。
n段目の隣り合う二分数をA(n,k)=a/b,A(n,k+1)=c/dとする。
（(ii)の証明と同様、この場合のkの範囲は1≦k≦mである）
帰納法の仮定よりA(n-1,k)=a/(b-a), A(n-1,k+1)=c/(d-c)である。
上と同様で左からk,k+1番目は一段増えると、それぞれ左から2k-1,2k+1番目になる。
すなわち
A(n+1,2k-1)=A(n,k)=a/b
A(n+1,2k+1)=A(n,k+1)=c/d
間の数は左から2k番目であり、生成すると
A(n+1,2k)=(a+c)/(b+d)
となる。
一方n-1段目の左からk,k+1番目の数からn段目を生成すると
A(n,2k-1)=A(n-1,k)=a/(b-a)
A(n,2k+1)=A(n-1,k+1)=c/(d-c)
であり、その間の生成された分数は
A(n,2k)=(a+c)/{(b-a)+(d-c)}=(a+c)/{(b+c)-(a+c)}
したがって、A(n+1,2k)とその真上の分数A(n,2k)についても(iii)の関係が成り立っている。
すなわち生成された分数についても(iii)が成立することから、n+1段目についても(iii)は成立する。

以上の証明から、各段について(i),(ii),(iii)が成立することが分かったので本題を考える。
帰納法の仮定よりn段目が既約分数であるとする。
(iii)の関係よりn+1段目の左半分の分数をa/bと表すと、真上n段目の分数はa/(b-a)と表され、aとb-aが互いに素である。
一般にx,yが互いに素な整数のとき、x,x+yも互いに素になる。
したがってa,b-aが互いに素であれば、a,(b-a)+a=b、この二数も互いに素である。
したがってn+1段目の1/2より左側全体a/bについても既約分数になる。
また右半分は(ii)より左側のa/bと対称な位置の分数は(b-a)/bと表されるので、a,bが互いに素だと、b,b-aも互いに素になる。
つまり左側すべて既約分数なので、対応する右側もすべて既約な分数になることが言える。
すなわちn+1段目についても命題は成立する。

以上より数学的帰納法から命題は証明された。［証明終］

(2)では
(ii)n段目の分数列において、中央からみて左右対称な位置にある分数を足し算すると1になる。
すなわちa/bと(b-a)/bが対称な位置にいる。

(iii)n段目の中央から左側についてみるとa/bの真上n-1段目の分数はa/(b-a)である。

これらのことを証明した。

(3)（背理法）
［証明］
この方法では生成されない有理数m/n（0＜m/n＜1）が少なくとも一つ存在したと仮定する。
またm/nは既約分数だとする。
0/1や1/2や1/1は現に表されているので、少なくともm/n≠1,1/2,0である。
0でないということで、m,nは互いに素な自然数を考えればよい。
（上の不等号は既にそのことを考慮している）

このとき(2)で証明した(ii)より、1-m/n=(n-m)/nがもし生成されていると矛盾するので、この分数もこの方法では生成されない有理数である。
m/n+(n-m)/n=1より、少なくともどちらか一方は1/2より小さい。
ここでm/n＜1/2としても特に一般性は失われない。
（(n-m)/n＜1/2ならn-mをmに取り直せばよいだけである）

以上より、この方法で生成されない有理数全体は1/2より小さい有理数だけをまず考慮すればいいことが分かる。
そこで、この方法では生成されない、1/2より小さな有理数の集合全体について考える。
このとき、nは自然数であるため最小のnが存在し、これをNとおく。
このときm/N＜1/2より2m＜Nである。
m/Nが生成されないので、(2)の(iii)よりm/(N-m)が生成されていると、その真下がm/Nになり、生成されてしまうので矛盾する。
すなわちm/(N-m)も生成されない分数である。
このときm/(N-m)＜1/2だと、mが自然数であるため分母がN-m＜NなのでNの最小性に矛盾する。
したがって、「この方法で表されない分数全体の集合」に1/2は含まれないので、m/(N-m)＞1/2（等号は成立しない）が成立している。
すると対称な位置に生成されるであろう分数、すなわちこれを1から引いた有理数、1-m/(N-m)=(N-2m)/(N-m)は0より大きく1/2より小さい。
この分数がこの方法によって表される分数であると、(2)の(ii)(iii)より、順を追って辿ればm/Nがこの方法で表されて矛盾する。
ところが分母N-m＜NよりNの最小性にも矛盾している。
すなわちこのような分数m/Nは存在しない。

以上から、既約分数のうち、この方法で生成されないような既約分数は存在しないことが分かる［証明終］。

(2)の補足説明です。
(2)で登場した性質のうち(ii)については、ご指摘いただきましたように、
(ii)'「1/2について左右対称な位置の分数について、生成されたそのまま（仮に約分できたとしてもせずに）の分数の分母は互いに共通しており、この二分数は足して1」
のように、少し条件が厳しい性質に書き換えます。
(ii)'は(ii)の帰納法の証明を見れば成り立っていることはわかります。

(2)の(ii)'と(iii)の性質の証明においては、帰納法の仮定の中に「分数が既約」という条件は使っておらず、a/b,c/dが別に可約分数であってもいいことになります。
条件としては「a/b,c/dや、(a+c)/(b+d)が生成されたそのままの形であること」なので、これを付け加えれば「1/3と2/6の区別の問題」は解消されると思います。

つまり途中で可約な分数が登場しても約分せずにそのまま次へ次へと進行していくことになります。
a/bというより、(a,b)という組を考えているイメージでしょうか。
このように見れば、(1,3)と(2,6)は異なる組になり、便宜的に1/3と2/6が区別されます。

以上をふまえて、登場する分数a/bなどはすべて「そのままの形」だと考えます。
(iii)の性質より、a/bとc/dからn+1段目に生成された分数そのままの形でみると(a+c)/(b+d)であり、その真上はa/(b-a)とc/(d-c)から生成された分数で、そのままで書くと(a+c)/{(b+d)-(a+c)}となっています。
このままでは約分できるかどうかはまだ不明です。
証明する内容を「n段目は既約分数列」ではなく「n段目を生成するとそのままの形で既約分数列」ということに考え直します。
帰納法の仮定として、n段目がそのままの形で既約分数である、という条件を考えれば、そのままの形である(a+c)/{(b+d)-(a+c)}が既約分数であり、結局その下の分数について、そのままの形で見た(a+c)/(b+d)という分数もやはり既約分数になります。

ここまでは左半分です。

右半分については、生成された分数をそのままで見たとき分母共通なことから、n+1段目の左半分のそのままの分数をa/bと書いたときに、それと対称な位置の分数はそのままの形が(b-a)/bであり、a/bが互いに素なら(b-a)/bも互いに素になります。

a/b<c/d かつ bc-ad=1 とする（0/1 と 1/1 はこれを満たしている）。

1.
(a+c)/(b+d)-a/b=(ab+bc-ab-ad)/b(b+d)=1/b(b+d)
c/d-(a+c)/(b+d)=(bc+cd-ad-cd)/d(b+d)=1/d(b+d)
より
a/b<(a+c)/(b+d)<c/d がいえる。
2.
a+c=e,b+d=f とすると
be-af=cf-de=bc-ad=1。
隣り合った2つの分数に対し常に bc-ad=1 が成り立つ。
a,b か c,d が2以上の公約数Gを持つとき、bc-ad も G で割り切れる。これは bc-ad=1 に矛盾するので、全ての分数は規約である。