◆愛知県 Y.M.Ojisan さんからの解答。
【問題１】
| f(n)=[ | n 3 |
]*[ | n+1 3 |
]*[ | n+2 3 |
]， [ ]:ガウス記号 |
∵一本直線を引きます。
なるべくたくさん正三角形を作るには、後の直線はこの直線に対し、0度、120度、−120度のいずれかの傾きを持つべきです。
よってｎ本を３組に分けその積が最大になるようにすればよい。
| つまり、ほぼ同値の[ | n 3 |
]，[ | n+1 3 |
]，[ | n+2 3 |
]に分ければよい。 |
【問題２】
２本の線が重なったときは１本の線と同等とします。
またｎ≧３とします。
最大値f(n)の状態から 適当な線一本を平行な線の上に重ねれば
f(n-1)に低減できるのでf(n-1)+1〜f(n)-1本が可能であれば数学的帰納法により可能です。
なお、f(3)=１（のみ）であるからn=3において成立しています。
[大雑把な証明]
n=6mとします。
f(n)=8m3 ，f(n-1)=8m3-4m2
であるので f(n)をベースに１から4m2まで削減できれば十分です。
最初に下図の黒線と空色線で示されるように綺麗に並べる。
１本減らすには空色線の一本を「1」で示される線の位置に移動します。
２本の時は「2」で示される線の位置に移動します。
最初の線で最大「2m」削減可能です。
次にもう一本空色線を移動してゆきます。
２本目３本目は最大「2m-1」削減できます。
最後のm本目は「m」削減され、この手順により、1から3m2本まで全て削減可能ですが 4m2には不足です。
そこでベースを8m3-2.8m2ぐらいに減らすことを考えます。
(2.8に深い意味は無い。3より少し少ないだけ)
すなわち 2m*(2m-k)*(2m+k)≒ 8m3-2.8m2より
k=Ceiling(1.183√ｍ) とする。
下図に示すようにこの場合もほぼ3m2削減可能であり、2m2は十分削減できる。
mが大きくなれば、√の切り捨てや、nが6mでないことの影響は相対的に小さくなり、大雑把な証明で十分である。
問題はｎが小さい時であり、有限なので個別に調べればできるでしょう。
[ｍｍとした証明]
n=a+b+cに分けられているとき、g(a,b,c)=a*b*cからどれだけ交点に重ねる方法で正三角形を減らせるかというと、
| d(a,b,c)=[a*b+b*c+c*a+ | 1 4 |
-( | n 2 |
) | 2 | ]です。 |
ただしこの式は a+b≧c & a+c≧b & b+c≧a （三角形の３辺）のときに限ります。
単純に計算すれば出てきますので証明略。
[ ]を用いないと、d(a,b,c)はnの偶奇性で、f(n)は n mod 3 の値で若干表式が異なるので n mod 6で分類して考える必要がありますが、
1/4をはずして
| d(a,b,c)≧(a*b+b*c+c*a-( | n 2 |
) | 2 | )=ρ(a,b,c)で考え,n mod 3 で分類します。 |
即ち f(n)=g(m,m,m+p) ，n=3m+p，p=-1 or 0 or 1 を最初の状態とします。
もし、f(n)-d(m,m,m+p)≦f(n)-ρ(m,m,m+p)≦1+f(n-1) であれば証明終わりです。
しかしそうではないので a=m から1本 b=mへ移動させa=m-1,b=m+1にします。
このとき
f(n)=g(m,m,m+p)-ρ(m,m,m+p)≦1+g(m+1,m-1,m+p)であれば
g(m+1,m-1,m+p)まで順次削減できて、
g(m+1,m-1,m+p)-ρ(m+1,m-1,m+p)≦1+f(n-1)であれば証明終わりです。
だめならもう一本ということで一般に
g(m+k,m-k,m+p)-ρ(m+k,m-k,m+p)≦1+g(m+1+k,m-1-k,m+p) ---(1) または
g(m+k,m-k,m+p)-ρ(m+k,m-k,m+p)≦1+f(n-1) ----(2)
がk=0から(2)が成立するkまでの間で成立していればよい。
少し回りくどいですが、それはこの条件を、両式(1)(2)の加算である下記関係式(3)の成否で大まかに判定する方法をとるためです。
g(m+1+k,m-1-k,m+p)+f(n-1)+2(1+ρ(m+k,m-k,m+p)- g(m+k,m-k,m+p))≧０
＜p=-1の場合＞
この場合f(n-1)=g(m-1,m-1,m)です。
m=5+qとして計算すると(3)左辺は下記です。
(下駄値5は実は答えを知って出る値です。他も同様)
| (2+q)(k- | 4+q 2+q |
) | 2 | + | q3+8q2+20q+8 2q+4 |
この式はq≧0において正です。
即ち3m-1の系統ではn=14以上はＯＫです。
＜p=0の場合＞
この場合f(n-1)=g(m,m,m-1)です。
m=5+qとして計算すると(3)左辺は下記です。
| (3+q)(k- | q+5 3+q |
) | 2 | + | q3+9q2+23q+7 2q+6 |
この式はq≧0において正です。
即ち3mの系統ではn=15以上はＯＫです。
＜p=1の場合＞
この場合f(n-1)=g(m,m,m)です。
m=4+qとして計算すると(3)左辺は下記です。
| (3+q)(k- | q+5 3+q |
) | 2 | + | q3+9q2+21q+1 2q+6 |
この式はq≧0において正です。
即ち3m+1の系統ではn=13以上はＯＫです。
kはせいぜい [√(n/3)] ですから、ｎ≧13ではρの引数a,b,cに要求される３角形の関係は満足されています。
以上より ｎ≧13 以上では可能であることが証明されました。
＜ｎ＜13 の場合について具体的に調べます。＞
| m=[ | n+1 3 |
] | ， p=n-3m，f(n)=m3+pm2，k=[√( | d(m,m,m+p)+1 m+p |
)]として、 |
下表に示すようにn=3,4はそのままで成立。
n=5,6,7,8,10は１回目の削減で成立。
n=9,11,12は１本の移動を１回行い、２回目の削減で成立している。
以上で証明完了。
｛なお、n=12はぎりぎり届いたというところですが、a,b,cを4,4,4から3,3,6に移動させれば
g=54,d=9,g-d-1=44でらくらく到達します。｝
合わせて、n=13以降も一部下表に示しました。
２回までに到達しています。
【感想】
大雑把な証明までは容易でしたが、きっちりした証明の方はややこしくて疲れた。
どうせＥＸＣＥＬで下のほうを計算したので、もっと大まかな証明でもよかった。
【おまけ】
(a) 正三角形の内部と直線が交わらないもののみをかぞえた場合
【おまけa問題1】
| f(n)=[pm- | p2 2 |
+ | 3m2 2 |
] |
| ここでm=[ | n+1 3 |
] , p=n-3m , [ ]:切り捨て |
∵同様に直線を0度,120度,-120度の３グループに分けそれぞれa,b,cとする。
aから１本（青線）を持ってきて、bとｃ全部を使って最大何個正３角形が作れるか考えると、
下図のようにb=cでは b+c-1である。
またb＞cなら2cである。
したがって、bとｃでできる格子点間に、なるべくa方向の対角線に近いほうからaの線を差し込んで行くのが最大個数の正三角形をあたえる。
その数は、関わるbとｃの交点の２倍程度になるから、前の問題のｄのほぼ２倍であることがわかる。
実際に計算すると、
| f(a,b,c)=[2*(ab+bc+ca)- | n2 2 |
] ，n=a+b+c である。 |
この値が最大になるのはa=b=cのときである。
| 従ってｎが３の倍数のときはa=b=c= | n 3 |
| n mod 3=1のときは a=b= | n-1 3 |
，c=a+1 |
| n mod 3=2のときは a=b= | n+1 3 |
，c=a-1 が最大値を与える。 |
これを書き換えると解答である。
【おまけa問題２】
こちらは容易に可能である。
手順の一つをn=12の場合について下図に示す。
他にも方法はあるが、gifアニメのファイル圧縮率が高いと思われるものを採用した。
f(12)=24です。
この方法のポイントは１本（赤線）だけ整列させないところである。
◆出題者のコメント。
Y.M.Ojisan さん解答ありがとうございます。
【問題１】正解です。
【問題２】細かい計算以外は確認しました。
かなり良い評価をされていて見事です。
（私の用意していた解答ではn≧55とかなり評価が荒いです。）
以下は蛇足ですが、思ったことです。
[大雑把な証明]では２回の削減で済ませていますが、[ｍｍとした証明]では何回も削減を行っていますね。
こちらの方が精密ですが、[大雑把な証明]の方針で
k = [√(n/6)]
とした方が多少計算が楽かも知れません。
（ちゃんと計算してませんが）
＞きっちりした証明の方はややこしくて疲れた。
私も、自分なりに証明してから出題しようとしたので疲れました。
あと、発見的な方法による解答も期待していますが、こちらは難しいかもしれません。
【おまけa問題1】
多分正解でしょう。
というのも、私はこれを証明できていません。
この証明の問題点は、bとcでできる格子に１本ずつ直線を加えていく「各段階」で正三角形を最大の個数作ったとして
も、それが「全体」で正三角形が作れる最大個数だということは自明ではない、という所です。
なので、もう少し説明が必要だと思います。
【おまけa問題２】
問題１が正しければ正解です。
アニメーションが分かりやすくてばっちりです（＾＾
◆愛知県 Y.M.Ojisan さんからの解答。
【おまけa１】
御指摘御尤も。筆力限界にて省略御免。筆力回復下記詳述。
∵ a,b,cは三角形の3辺の関係にありb≧cとします。
bとｃの交点の集合をTとします。
作図の都合上aは上下方向とします。
なお、n=a+b+cです。
正三角形が３辺で構成されるのではなく、１辺(∈a)と１点(∈T)で規定されると考えます。
条件より、１辺と１点の間に他の辺∈aは入りこめません。
また、正三角形内部および辺上に他の点∈Tも存在し得ません。
（同一点上の２点は１点とみなすので、たくさん作る場合点は全部異なると考えて良く、正３角形頂点上を特に除外していない。）
即ち、１点∈Tにつき、aは１点の左右の２本のみが正三角形生成に有効です。
（蛇足：よって正三角形個数が2bc以下であることは確実）
以上から、aに直交する方向に強単調増加なｐ個の点列tｐ∈T を考えるとき、
aとtｐで作成可能な正三角形の最大数はaとtｐが交互に並ぶ場合であってその数は
a＞ｐの場合 2ｐ, a＝ｐの場合 2a-1, a＜ｐの場合 2a
であると言えます。
tｐとして下図赤線上のｃ組の点列の集合を考えます。
ｐ＝b-c+1 , b-c+3 ．．b+c-1 です。
これらはaに直交する方向に強単調増加という条件を満足しています。
よって正三角形の最大数は下記式以下となります。
Xはa=b-c+2I-1が成立した数で０か１です。
具体的には2I=a-b+c+1=(n+1)-2bなので nが奇数の時１ 偶数の時０です。
| ｃ I=1 |
2*Min(a,b-c+2I-1)−X |
[偶数時]
| I=1〜 | n 2 |
-b での狽ﾍ |
| (b-c+1+b-c+n-2b-1)( | n 2 |
-b)=(n-2c)( | n 2 |
-b) |
| I= | n 2 |
-b＋1〜ｃでの狽ﾍ2a(c- | n 2 |
+b) |
以上を合算すると
| n2 2 |
-nc-nb+2bc+2ac-na+2ab=2(ab+bc+ca)- | n2 2 |
[奇数時]
| I=1〜 | n+1 2 |
-b での狽ﾍ |
| (b-c+1+b-c+n+1-2b-1)( | n+1 2 |
-b)=(s-2c)( | s 2 |
-b) |
| I= | n+1 2 |
-b＋1〜ｃでの狽ﾍ2a(c- | s 2 |
+b) |
以上を合算すると
| s2 2 |
-sc-sb+2bc+2ac-sa+2ab-1 |
| =2(ab+bc+ca)+ | s(s-2n) 2 |
-1 |
| =2(ab+bc+ca)- | n2 2 |
- | 1 2 |
| まとめて[2(ab+bc+ca)- | n2 2 |
] であり、 |
また実際、前回解答の方法でそのようなaを作図可能です。
なお、a,b,cが三角形の3辺の関係にない場合(a≧b+c)はaが余りだすので、最大になることはありません。
◆出題者のコメント。
Y.M.Ojisan さん再び解答ありがとうございます。
【おまけa１】
今度は確実に正解です。 なるほど、横の折れ線は見えませんでした。実に納得がいきました。
一箇所だけ表現に注文を付けさせて貰いますと、
＞ 以上から、aに直交する方向に強単調増加なｐ個の点列tｐ∈T を考えるとき
ここは、点列tｐの（aに直交する方向）に隣り合う２点を結ぶ線分は、直線族b又はc（の一部）に含まれていなければいけない、というようなことが一言は必要ですね。
図ではそうなっているので証明に問題はありませんが。
◆愛知県 Y.M.Ojisan さんからのコメント。
【おまけa１ Reply】
＞というようなことが一言は必要ですね。
さすが厳密ですね。ご指摘の条件が必要です。暗黙知になっていました。
自分で書いておきながらですが、次の文も必然性に関し物言いが付きそうです。
＞ tｐとして下図赤線上のｃ組の点列の集合を考えます。
解説：Ｔの点を有効に使用するにはp＜aであることが望ましいのですが。
最初はどうしてもｐ＝ｂ＋ｃ−１≧ａの点列がある場合があってその部分は捨てざるを得ない。
以後最長の点列を採用してゆくと、図のｃ組になるわけです。