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

質問

にゃんこ先生といいます。

2次元以上の空間に、異なるn点があったとします。
{1,2,3,…,n}
と名前をつけます。

もし、
{1,2,3}が同一直線上にあり、
{2,3,4}が同一直線上にあり、
{3,4,5}が同一直線上にあり、
…、
{n-2,n-1,n}が同一直線上にある
ことがわかれば、n点全部が同一直線上にあることがわかります。

そのように3点の組が同一直線上にあるという条件を書き出して、
n点全部が同一直線上にあることと同値にするには、
本質的に上記の場合以外にあるのでしょうか？
（本質的に同じとは、点の名前を適当に付け替えれば上記の条件と同じになるという意味です。）
また、何種類くらいの方法があるのでしょうか？
さらに、同一平面上などと発展させていけば、なにか面白いことでもあるでしょうか？

回答No.4

stomachman · ベストアンサー

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
を線で繋いでみれば分かるとおり、この限定をはずすと言えなくなっちゃいます。

お礼

ありがとうございます。

3点の組が同一直線上にあるという条件を書き出して、
n点全部が同一直線上にあることと同値にするには、
任意の3点の組に対して、別のある3点の組が存在し、それらの点集合としての共通部分が2点以上あればよいということがわかりました。

でも、そもそも同一直線上にあるという意味は、上記のこと自体を定義とするか、斉次座標として行列を作ったときのrankを2であることを定義とするかなのですね。

何種類くらいの方法があるのかを考えることくらいしかおもしろいことはなさそうです。何種類かを考えること自体も、それほど興味深くはなさそうです。

3次関数上に、9点{1,2,…,9}があるとき、
{1,2,3},{4,5,6},{1,4,7},{2,5,8},{3,6,9}がそれぞれ一直線上にあれば、{7,8,9}も一直線上にある。

調べてみれば、これは参考サイトのパスカルの定理の拡張の、３次曲線が3次関数や3直線になった場合に対応しているようですね。
http://www.geocities.jp/ikuro_kotaro/koramu/715_p4.htm

回答No.3

stomachman

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個あれば十分である。
　条件の作り方を数え上げる問題は、にゃんこせんせいなら鎧袖一触では？

お礼

ありがとうございます。
でも、自分でも何を考えたいのかよくわかっていませんでした。

n=4として、異なる4点{1,2,3,4}が同一直線上にある
⇔{1,2,3},{1,2,4}がそれぞれ同一直線上
⇔{1,2,3},{1,3,4}がそれぞれ同一直線上
⇔{1,2,3},{2,3,4}がそれぞれ同一直線上
⇔{1,2,4},{1,3,4}がそれぞれ同一直線上
⇔{1,2,4},{2,3,4}がそれぞれ同一直線上
⇔{1,3,4},{2,3,4}がそれぞれ同一直線上

n=5とした時点でお手上げです。

異なるn点があるとき、それらが同一直線上にあるという条件の作り方は、次のようであるようですね。

まずある3点が同一直線上にあることを述べる。残りn-3点はまだ不明。
次に、すでに同一直線上にあるとわかっている点から2点を抜き出し、不明の点から1点を抜き出し、それら3点が同一直線上にあることを述べる。今、4点が同一直線上にあり、残りn-4点はまだ不明。
同様に、すでに同一直線上にあるとわかっている点から2点を抜き出し、不明の点から1点を抜き出し、それら3点が同一直線上にあることを述べる。
これらを繰り返す。

上記の方法以外にないことはどうやって証明できるのでしょうか？

また、4点の組が同一直線上にあるという条件も許すとき、なんらかの設定をして、効率のよい条件の述べ方というのがあるのでしょうか？

イメージとして、{1,2,3}が同一直線上ということは、その3点に添え木をつけるかんじです。次に、{3,4,5}が同一直線上ということは、その3点に添え木をつけ、結果的に、点3のところで、添え木同士が関節のようになっているかんじです。n点全部をまっすぐにしたいとき、なんらかの設定をして、効率のよい添え木のつけ方を考えるというものです。

なお、一連の発端は、次の問題です。
3次関数y=ax^3+bx^2+cx+d上に、3点があるとき、それらが一直線上にある条件は、3つのx座標の和が-b/aであることを示せ。
♯これは3次関数と1次関数を連立して、解と係数の関係を考えます。
3次関数y=ax^3+bx^2+cx+d上に、9点{1,2,…,9}(異なっていなくてもよい)があるとき、
{1,2,3},{4,5,6},{1,4,7},{2,5,8},{3,6,9}がそれぞれ一直線上にあれば、{7,8,9}も一直線上にあることを示せ。
♯これは、それぞれのx座標の和が-b/aであることを全部書き出し、加えるとわかります。
この問題の背景がわかる人はいますか？

回答No.2

echoes_x86

おはようございます．
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点を持ってきて，他の点が内分点か外分点にある，
という条件を記述しても良いでしょう(上のものとほぼ同じ意味です)．

申し訳ないのですが，
もっと抽象的に，座標が利用可能でない場合はについては私には分かりません．

回答No.1

rabbit_cat

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

という条件なら、
{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-2個より少なくすることは可能でしょうか？
例えば条件がn-2個与えられたとして、n点が同一直線上にあるかどうか判断する方法はあるのでしょうか？