ｸｲｽﾞ大陸

さらにヒントです。

町の数がn個のときの自由度の最大値をf(n)とします。
n1<n2ならばf(n1)≦f(n2)が成り立つように思われるかもしれませんが、成り立ちません。

f(n)には上限があり最大値があります。その最大値をkとします。
f(n1)=f(n2)=kであれば、f(n1+n2)=kです。
n1個の町で自由度kの道路網を作り、別のn2個の町で自由度kの道路網を作ります。
それぞれの道路網の外周の町を一つずつ選び道路でつなぐと、
町の数が(n1+n2)個で自由度kの道路網が作れます。

また、n1,n2が互いに素であれば、任意のn≧n1*n2についてf(n)=kです。
nがn2の倍数のときに成り立つのは明らかですので、nがn2の倍数でない場合を考えます。
n1とn2が互いに素なので、
n1*1,n1*2,n1*3,・・・,n1*(n2-1)
をn2で割った余りは0にはならず、すべて異なります。
(n2-1)個ありますので、1から(n2-1)までのすべての自然数が現れます。
その中にはnをn2で割ったときの余りと一致するものが必ずあります。
それをn1*mとすると、n-n1*mはn2の倍数です。
よって、町の数n1の道路網m個と町の数n2の道路網をいくつか連結すれば、
町の数n個で自由度kの道路網が作れます。

町の数が互いに素で自由度kの道路網が存在することを示します。
f(n)=kとします。
n個の町で自由度kの道路網が作れます。
この道路網をk個作ります。
新たに町を1個追加します。
その町にk個の道路網の外周の町1個ずつから道路を作ると、
全体として町の数(nk+1)個で自由度kの道路網ができます。
nと(nk+1)は互いに素です。

以上より、nがある値より大きければ常にf(n)=kになることが証明できました。
f(n)≠kとなるnは有限個しかありません。