にゃんこ先生の自作問題、n点が同一直線上にある条件

Question

にゃんこ先生といいます。

2次元以上の空間に、異なるn点があったとします。
{1,2,3,…,n}
と名前をつけます。

もし、
{1,2,3}が同一直線上にあり、
{2,3,4}が同一直線上にあり、
{3,4,5}が同一直線上にあり、
…、
{n-2,n-1,n}が同一直線上にある
ことがわかれば、n点全部が同一直線上にあることがわかります。

そのように3点の組が同一直線上にあるという条件を書き出して、
n点全部が同一直線上にあることと同値にするには、
本質的に上記の場合以外にあるのでしょうか？
（本質的に同じとは、点の名前を適当に付け替えれば上記の条件と同じになるという意味です。）
また、何種類くらいの方法があるのでしょうか？
さらに、同一平面上などと発展させていけば、なにか面白いことでもあるでしょうか？

stomachman · Accepted Answer

ANo.3のコメントについてです。

> 上記の方法以外にないことはどうやって証明できるのでしょうか？

>> 点jがL上にある、ということを言うためには、jを含む「条件」が少なくともひとつ必要である。

とANo.3で申し上げましたが、これは証明不要でしょうから、必要な条件の最小個数については疑義なしとして良いですかね。で、

{1,2,3}は同一直線上
{1,4,5}は同一直線上
とやったとすると、ふたつの直線が同じものかどうかはまだ決まっていません。両者をそれぞれ直線L, Mとすると、LとMが同一の直線だということをどこかで言わなくちゃいけない。しかし一つの条件では、直線1本と点ひとつしか指定できないのだから、
2はM上にある
3はM上にある
4はL上にある
5はL上にある
のどれかを言うしかない。そして、Lを指定するには{1,2,3}のうちのどれかふたつ、Mを指定するには{1,4,5}のうちのどれかふたつを使わなくちゃならない。たとえば、「2はM上にある」「Mとは1,4を通る直線である」を使って、

{2,1,4}は同一直線上

と言う。並べ直せば

{1,2,3}は同一直線上
{1,2,4}は同一直線上
{1,4,5}は同一直線上
となって、これはANo.3で述べた

>> すでに同一直線上にあるとわかっている点から2点を抜き出し、不明の点から1点を抜き出し、それら3点が同一直線上にあることを述べる。

というやり方になっているのが分かります。

{1,2,3}は同一直線上
{4,5,6}は同一直線上
とやった場合についても、同じような考察ができます。
　もちろん、ANo.2にあるように行列のrankを使うアプローチもあると思いますが。


> {1,2,3},{4,5,6},{1,4,7},{2,5,8},{3,6,9}がそれぞれ一直線上にあれば、{7,8,9}も一直線上にある

という話はなるほど興味深いです（楕円曲線論と関係あるのかな？）が、3次関数の曲線上の点に限定されているから言えることであって、
・1　・4　・7
・2　・5　　　　　　・8
・3　・6　　　・9
を線で繋いでみれば分かるとおり、この限定をはずすと言えなくなっちゃいます。

stomachman · Answer

k次元空間の(m-1)次元超平面(k≧m)を、n個の点(n≧m)が共有する場合を考えましょ。直線ならm=2です。
　点1,2,…,mを指定すればm次元超平面が決まるから、これをLとします。残りの各点j (j∈{m+1,..,n})について、点jがL上にある、ということを言うためには、jを含む「条件」が少なくともひとつ必要である。従って、「条件」の個数はn-m未満にはできない。
　さて、jを含む「条件」を作るには、
P⊂{1,2,…,j-1} ∧ |P|=m　
すなわち{1,2,…,j-1}の中から相異なるm個の要素を任意に取り出して作った集合Pを使って
「P∪{j} が同一直線上にあり」
とやればよいから、「条件」はn-m個あれば十分である。
　条件の作り方を数え上げる問題は、にゃんこせんせいなら鎧袖一触では？

echoes_x86 · Answer

おはようございます．
n点の共線条件ということですが，n点の座標が与えられる，
と言うことであれば斉次座標を使えば簡単に条件を記述できます．
i番目の点の斉次座標を Xi = [xi yi 1]^T (^Tは転置記号)，
j番目の点の斉次座標を Xj = [xj yj 1]^Tとします．
ここで，この2点を通る直線の斉次座標は次の行列の零空間です．
[Xi^T]
[Xj^T]
これはXiを通る直線 L = [u v 1]^T の方程式はL*Xi^T = 0，Xjを通る直線の方程式は L*Xj^T = 0と書けることによります．
したがって，n点 Xi = [xi yi 1]^T (i~=1,...,n)の座標系が与えられたとき，
次の行列のランクが2であれば，すべての行に直交するLが存在し，
n点全てが共線であることになります．
[X1^T]
[X2^T]
[ :  ]
[Xn^T]
ランクが1の場合を考えなくて良いのは，これが X1 = X2 = Xn の場合だからです．
以上，n点の座標が利用可能な場合の必要十分条件でした．

斉次座標を使うのが面倒ならば，
n点から適当な2点を持ってきて，他の点が内分点か外分点にある，
という条件を記述しても良いでしょう(上のものとほぼ同じ意味です)．

申し訳ないのですが，
もっと抽象的に，座標が利用可能でない場合はについては私には分かりません．

rabbit_cat · Answer

＞本質的に同じとは、点の名前を適当に付け替えれば上記の条件と同じになるという意味です。

という条件なら、
{1,2,3}が同一直線上にあり、
{1,2,4}が同一直線上にあり、
…
{1,2,n}が同一直線上にある
ていうのは、点の名前をどう付け替えても、質問の文とは同じにはなりませんが。

もっと言えば、
{1,2,3}が同一直線上にあり、
{a4,b4,4}が同一直線上にあり、
{a5,b5,5}が同一直線上にあり、
…
{an,bn,n}が同一直線上にある
ていうので、
a_k < b_k < k
を満たすように適当に数字を入れれば、「本質的に違う」条件になるはずです。

にゃんこ先生の自作問題、n点が同一直線上にある条件

ANo.3のコメントについてです。

k次元空間の(m-1)次元超平面(k≧m)を、n個の点(n≧m)が共有する場合を考えましょ。

おはようございます．

＞本質的に同じとは、点の名前を適当に付け替えれば上記の条件と同じになるという意味です。

似たような質問が見つかりました

関連するカテゴリからQ&Aを探す

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング

　k次元空間の(m-1)次元超平面(k≧m)を、n個の点(n≧m)が共有する場合を考えましょ。