平面上のn個の頂点から直角三角形は最大幾つ作れるか

質問

「平面上の相異なるn個の点のうち３点を結んで出来る直角三角形は最大で幾つか。ただし、nは３以上の整数とし、三角形同士は辺や頂点を共有しても、あるいは重なっても構わないものとする」

どこかに載っていた問題ではなく、ふと思いついたもので、解決できるとは限りません。ただ、私にはどうやっても無理なようです。数学の得意な方、解いて頂けませんか。

題意がわかりにくいかもしれませんので補足しますと、点の位置は任意です。ただ、それらを適当に配置すれば、それらを結んで出来る直角三角形の個数は、その点の個数nに対する最大値を取るはずです。

単なる「三角形」は当然nC３個できるので、そのnC３個が全部直角三角形になりうるのならそれで問題解決ですが、nが５以上のときは残念ながらそうはいきません。

nが４のときは、４点が長方形の頂点の位置にあれば最大値４なので、これを上手く使えば解けるかもしれないとか、あるいは、終点が同じで内積が０になる一次独立な２本のベクトルの組がなるべく多くなるようにすればよいとか、色々考えてみましたが、どれも行き詰まってしまいました。どうでしょう、解けますか？

回答No.4

hrsmmhr

n=5のときはさいころの五の目の形の時が最大になる気がするのですが、どうでしょう？
一般には多分グリッド状（n=9なら田の形になる配置）にしていくのが最大な気がするのですが、どうでしょう？
n>=9は数学的帰納法で、
グリッドの辺を、点を一つ一つ追加してグリッドのサイズを大きくしていく方法で得られる配置が
最大であるとは証明できないでしょうか？

縦横だけの直角を考えると
は一点を追加して増える直角三角形は、n個の配置の最大値がn-1個で、グリッドならn-┌√n┐個
最大の配置とグリッドのn個までの直角三角形の数の差でカバーできると思うのです
おそらく他の角度を考えても、グリッドを形成していく追加による増分が大きいと思うのです

ただ、そうかもとは思うのですが、やっぱり証明はしんどいですね…
もし上の仮説が正しいと思われて、アイデアがありそうなら、続きをお試しください

お礼

ありがとうございます。

ええ、私も直観的にグリッドが最大だろうと考えたのですが…
間違った反証をしてその可能性を否定していたことに
いま気がつきました。ご指摘のお陰です。

最大であるかどうかはとりあえず置いておいて、
n=k*lのとき縦k個×横l個（マス目の数で言えば (k-1)個×(l-1)個）
の正方形グリッド状に点を配置した場合の直角の数なら、
（ちょっと今詳しく考えている暇がありませんが、）
直交座標系に格子点(a,b) (a=0,1,2,...l; b=0,1,2,...k)を取って、
直線y-b=m(x-a)上の格子点の個数と
直線y-b=-1/m・(x-a)上の格子点の個数、
あと直線x=aと直線y=b上の点の個数を考えれば
No.1のお礼に書いた様な考え方で求めることができそうです。

回答No.3

alice_44

←No.1 補足
その場合は △PQQ' が線分へ潰れてしまうから、
直角三角形が nＣ3 個は無いことを示すには、
非共線を仮定して考えれば十分だけどね。

4[(n-1)/4] にせよ、n(n-2)/4 にせよ、
n-1 点の配置に強い制限がついて
帰納的に使えないために、総数の評価としては
大変ゆるくなってしまう。

直角の数が極大な点の配置はどんな性質を持つか、
一点を除去しても保たれる性質を何か見つける
必要がありそう。

お礼

なるほど。確かに非共線を仮定した方が若干手っ取り早かったようです。

ご助言に感謝致します。そうですね…もう少し一般性のある考察に進みたいところです。

回答No.2

student_of_kit

点間の距離を微小にとれば無限個になるのでは？

お礼

ご回答ありがとうございます。

距離を微小にとったとき、果たして角度は直角に近づくのでしょうか？
例えば、６０度の角を成している３点を如何に近づけたとしても、
６０度はやはり６０度なのではないかと思いますが…。

つまり、改めて認識しましたが、これは距離の問題ではなく、位置関係の問題なのです。

また、無限個にはどうしたってなりえません。
どんなに多くても、n点からできる角の数nC3を超えることはありません。

ついでながら、直角nC3個も一般的には実現しないことが証明出来ます。
(1)n=3のときは言うまでもなく実現、
(2)n=4のとき、角の数は4C3=4個で、4点が長方形の頂点の位置にあればこれらは全て直角になります。
逆に、これらが全て直角のとき、4点は長方形の頂点の位置にあります。
従って、4点について、「直角の数が最大⇔4点は長方形の頂点」が言えます。
これを使って、nが5以上のときnC3個にはならないことを示します。
(3)n=5のとき、仮に5C3=10 個の角がすべて直角であるとすると、上の事情から、
5点のうちどの4点を選んでも、それは長方形になっているはずです。
5点をA,B,C,D,Eと名付けると、たとえばABCDとABCEは両方長方形のはずです。
しかし、ABCD が長方形だとすると、ABCEが長方形であるためには
点Eが点Dに重なっていなければなりませんが、
「n個の点は相異なる」という条件からこれは不適当です。
従って、n=5のとき、考えうるすべての角が直角になるわけではありません。
nが6以上のときも同様です。
というわけで、「nが5以上のとき全ての角が直角となることはない」ことが証明出来ました。
まあ、これがわかっても肝心の解は少しも見えてこないんですけどね…

回答No.1

alice_44

難しいね。

とりあえず、nＣ3 個全てが直角三角形にはならないことの証明。
一点を頂点とする直角の最大数は、残りの n-1 点を 4 つ毎の組にして
90 度づつの位置に置いた場合の 4[(n-1)/4] 個。([ ] はガウスの記号)
これは n-1 以下だから、直角の総数は、ゆるく見積もって n(n-1) 以下。
n＞4 の範囲では、n(n-1)(n-2)/6 より小さいことが解る。

直角の数を求めるには、ほど遠いけれど…

お礼

考えて下さってありがとうございます。

でも…１点を頂点とする直角の最大数は4[(n-1)/4]個ではありません。
ある1点Pと、その他のある４点の組との関係においては、確かにその1点を頂点とする直角は４個です。
しかし、その４点を使った、Pを頂点とする直角は、すべてその組の中だけで完結するわけではないのです。
その組の中の1点と、Pと、その組以外の1点とで作られる直角があります。
４点のうち２点をQ、Rとして、角QPRが直角とすると、PQの延長上に点Q’があれば、各Q’PRは直角になります。
つまり、4[(n-1)/4]個という勘定は、残念ながら成り立ちません。

ただ、1頂点あたり最大幾つできるのかという問題は考えていなかったので、参考になりました。
上の記号を使うと、Pを頂点とする直角の数を最大にしたければ、
Pを直交座標の原点の位置に置き、縦軸と横軸の上に残りの点を
（(縦軸上の点),(横軸上の点)）の組の数が最大になるように配置することになりますね。
言わずもがなですが、この組ひとつに直角ひとつが対応します。
縦軸上の点の数をkとすると横軸上の点の数はn-1-k個で、
k(n-1-k)が最大になるように上手くkを定めてやればよいので
nが奇数のとき　k=(n-1)/2で最大値(n-1)^2/4個
nが偶数のとき　k=n/2 or (n-2)/2で最大値n(n-2)/4個
になりますか。
ただ、これは明らかに、上のように設定した頂点Pにしか当てはまらないことなので、
これをn倍してそれ以下とやってもやはり意味はあんまりなさそうですね…。