ラストヒントを出しておきます。
一週間後くらいに正解発表の予定です。
>>14のヒントより
(6-k)v>=12
が導けます。
kが6以上だと左辺が0以下となりますので、kは5以下です。
k=5とすると、v>=12です。
町の数が12個で自由度5の道路網を作ることは可能です。
平面上の1点をPとします。
Pを中心とする正五角形ABCDEを描きます。
さらに、その正五角形をAを中心に拡大した正五角形A'B'C'D'E'を描きます。
対応する頂点同士を線で結びます。
これらの外部に点Qをとります。
PからA,B,C,D,Eに線をひき、QからA',B',C',D',E'に線をひきます。
さらにAとB'、BとC'、CとD'、DとE'、EとA'を結びます。
各点を町、各線を道路にすれば、町の数が12で自由度5の道路網ができます。
自由度の最大値は5です。
f(n)=5となるnの最小値は12です。
先程の道路網の構成で頂点が6個以上の正多角形を使えば
同様の方法で自由度5の道路網を作ることができます。
よって、nが12以上の偶数であれば常にf(n)=5です。
f(n)=5ならば、f(2n+1)=5です。
n個の町の道路網を2つ作ると、それぞれの外周の町はあわせて6個以上ですので、
新たに町を1個追加してその町から5本以上の道路を作ることができます。
全体として町の数が(2n+1)個の道路網になります。
よって、nが25以上の奇数であれば常にf(n)=5です。
nがf(n)≠5を満たす最大の自然数だとすると、この問題の答えは(n+1)です。
12〜24の偶数のどれかが答えです。
一週間後くらいに正解発表の予定です。
>>14のヒントより
(6-k)v>=12
が導けます。
kが6以上だと左辺が0以下となりますので、kは5以下です。
k=5とすると、v>=12です。
町の数が12個で自由度5の道路網を作ることは可能です。
平面上の1点をPとします。
Pを中心とする正五角形ABCDEを描きます。
さらに、その正五角形をAを中心に拡大した正五角形A'B'C'D'E'を描きます。
対応する頂点同士を線で結びます。
これらの外部に点Qをとります。
PからA,B,C,D,Eに線をひき、QからA',B',C',D',E'に線をひきます。
さらにAとB'、BとC'、CとD'、DとE'、EとA'を結びます。
各点を町、各線を道路にすれば、町の数が12で自由度5の道路網ができます。
自由度の最大値は5です。
f(n)=5となるnの最小値は12です。
先程の道路網の構成で頂点が6個以上の正多角形を使えば
同様の方法で自由度5の道路網を作ることができます。
よって、nが12以上の偶数であれば常にf(n)=5です。
f(n)=5ならば、f(2n+1)=5です。
n個の町の道路網を2つ作ると、それぞれの外周の町はあわせて6個以上ですので、
新たに町を1個追加してその町から5本以上の道路を作ることができます。
全体として町の数が(2n+1)個の道路網になります。
よって、nが25以上の奇数であれば常にf(n)=5です。
nがf(n)≠5を満たす最大の自然数だとすると、この問題の答えは(n+1)です。
12〜24の偶数のどれかが答えです。