９個の点と直線パズル

レス16

（トピ主 8 ）

ぴたごらす

2011年07月05日 10:16

話題

こんにちは。少し長くなりますがお付き合い下さい。

9個の点と直線パズルと言うと3×3の形に置かれた9個の点を一筆書きの
直線でつなぐものが有名ですが、それではありません。

いつ頃のものか覚えていないのですが、次の様なパズルがありました。

「9個の点を平面上に置いて、3点を通る直線を最大何本にできるか。」

これは純粋な数学パズルで、点は大きさを持たず直線の幅はゼロです。

9個の点を3×3の形に置けば3点を通る直線は8本(縦3＋横3＋斜め2)ですが、
点の置き方を工夫すると10本にできます。

私はどうしても11本以上にする事ができないので10本と言いたいのですが、
それを証明する事ができないので、11本以上の解があるかもしれません。

なお、13本以上の解は不可能である事は簡単にわかります。

(理由)任意の点Aに着目するとこれを通る直線は他の2点を通る。点A以外の
点の個数は8個なので点Aを通る直線は最大4本である。9点すべてに4本の
直線が通る場合の本数は4×9÷3＝12となり、これを超える事はできない。

どなたかこのパズルをご存知の方はいらっしゃいませんか？

トピ内ID：0523487880

これポチに投票しよう！

ランキング

このトピを見た人は、こんなトピも見ています

その他も見るその他も見る

前のトピ

次のトピ

レス

レス数16

このトピックはレスの投稿受け付けを終了しました

聞いた事あります。

RIT

2011年07月05日 12:23

なにかのフリーマガジンで呼んだ覚えがあります。

トピ内ID：2944107772

...本文を表示

もう少しわかりやすくお願いします

クルー

2011年07月09日 21:53

「9個の点を平面上に置いて、3点を通る直線を最大何本にできるか」これ条件が少なすぎませんか？「点と点を直線で結ぶ」とか、なんかそういう条件ないんですか？直線はその性質上曲がれないですよね？任意に点を配置しても直線上に点がないと、点の上を通過することすらできないんじゃ？「3点を通る直線を最大何本」どういう条件で直線をひいてるのでしょう？あと、それますが、「直線の幅はゼロ」ではなく点と同様に「直線の幅も太さを持たない」では？幅がゼロだと線にならないんじゃ？

トピ内ID：6697915500

...本文を表示

考えてみました

クルー

2011年07月09日 21:53

続きです＞(理由)任意の点Aに着目するとこれを通る直線は他の2点を通る。点A以外の点の個数は8個なので点Aを通る直線は最大4本である。9点すべてに4本の直線が通る場合の本数は4×9÷3＝12となり、これを超える事はできない。なぜ最大４本になるのですか？任意の点をＡとして、数字を他の点としてみてください。　　１　　２３４Ａ５６　　７　　８・１２Ａ・２Ａ７・Ａ７８・３４Ａ・４Ａ５・Ａ５６この６通り考えられるのですが、これはだめ？もちろんこの配置ではたの８点に対して同じことは言えませんが・・・。任意の点Ａに関してだけ言えば６本以上は可能だと思います。それとも直線は重なってはいけない？ちなみに９点を以下のように配置して１　２　３　４５６７　８　９・１２３・４５６・７８９・２５８・１４８・３６８・２４７・２６９・３５７・１５９・３５７この１１本はだめ？

トピ内ID：6697915500

...本文を表示

サム・ロイドの「コロンブスの卵」ですか？

よすがん

2011年07月10日 15:43

数学パズルについては詳しくないのですが、トピ主さんの仰る条件で検索したら、サム・ロイドの「コロンブスの卵」というパズルの話がいくつか引っかかりました。これでしょうか？

トピ内ID：3029373355

...本文を表示

レスありがとうございます

ぴたごらすトピ主

2011年07月10日 17:29

RIT様その時の解は何だったかお分かりになりますか。やはり10本？クルー様クルー様が示された2番目の配置は直線10本の解です。 (11本ではありません。2回数えられている直線があります。) これは私が見たパズルの解であり、私もその解には到達しました。この問題は直線の長さを限定していないので、4個以上の点が同一直線上に並んでいても直線の数は1本として数えます。ですから点Aとそれ以外の2点を通る直線は最大4本なのです。もっとも、4点1,2,3,4がこの順に同一直線上に並んでいた時「1,2,3を通る直線と2,3,4を通る直線を別カウント」という条件で 11本以上の解が可能ならば、条件を変えた問題として考える事ができると思います。ただし、「1,2,4を通る直線や1,3,4を通る直線も別カウント」はダメです。それならば9個の点を同一直線上に置けば良いのですから。

トピ内ID：0523487880

...本文を表示

サム・ロイド

サム

2011年07月10日 19:59

サム・ロイドの「コロンブスの卵」のパズルですね。直線の本数は最大10本です。

トピ内ID：0351350790

...本文を表示

レスありがとうございます２

ぴたごらすトピ主

2011年07月12日 12:40

よすがん様、サム様サム・ロイドと言えばデュードニーと並んで２大パズル作家ですね。確かにこの問題の起源は「コロンブスの卵」なのかもしれません。どこかに「最大は10本である」という証明はないですかね・・・もしくは「11本の解と最大は11本であるという証明」もしくは「12本の解」でも、もちろん大歓迎です。

トピ内ID：0523487880

...本文を表示

あってる？

2011年07月18日 16:27

仮に12本引くことが可能なら、直線が通過する延べ点数は36個配置できる点は9点ですから、(ある点が有する直線は最大4本とするなら) 全点(9個)において4本の直線が通っていることになります。仮に11本可能なら延べ33個、少なくとも6点が4本の直線を有します。仮に10本可能なら延べ30個、少なくとも3点が4本の直線を有します。このようなことから、限界値の確認は次の点を調査することで可能と思います。「直線を4本保持可能な点は最大いくつ存在可能か？」以下は、直線を4本保持する点について述べています。 --- [1] まず、直線状に4点以上が存在する場合を考えます。 A　B　C　D　←こんな感じ直線状の点Aは残りの5点との間に最大2直線しか形成できません。従って、ある点に対して4本の直線が引ける場合、各直線上には、3点のみが存在すると言えます。

トピ内ID：8650579189

...本文を表示

あってる？2

あってる？

2011年07月18日 16:27

[2] 次に、4直線を有する点A,Bについて、A,B上を通過する直線無しに存在可能であるかを考えます。仮にAが4直線を有する場合、BはBと他7点で4直線を形成している事になります。しかしこれは不可能です。従って、BはA,Bを通過する直線上に存在するといえます。 [3] ここで、仮にA,B,C上を通過する直線が存在し、この3点が全て4直線を有する場合これ以外の点は4直線未満といえます。何故なら[2]よりA,B,C上の直線を含まずに4直線を形成することは不可能で [1]より、ある直線状に4点以上は存在し得ないためです。ここの仮定では4直線を有する点は最大3点となります。 [4] 逆に、Aと他1点のみが4直線を有する場合、 Aを通過する直線は4本ですので、最大(Aも含め)5点が4直線を保持する可能性を持ちます。 --- [3],[4]より、11本の直線を引くことは不可能といえるのではないでしょうか？ ※11本引くには4直線を保持する点が6個は必要なため

トピ内ID：8650579189

...本文を表示

あってる？

2011年07月18日 19:32

仮に12本引くことが可能なら、直線が通過する延べ点数は36個配置できる点は9点ですから、（ある点が有する直線は最大4本とするなら）全点「9個」において4本の直線が通っていることになります。仮に11本可能なら延べ33個、少なくとも6点が4本の直線を有します。仮に10本可能なら延べ30個、少なくとも3点が4本の直線を有します。このようなことから、限界値の確認は次の点を調査することで可能と思います。「直線を4本保持可能な点は最大いくつ存在可能か？」以下は、直線を4本保持する点について述べています。＝＝＝「1」まず、直線状に4点以上が存在する場合を考えます。 A　B　C　D　←こんな感じ直線状の点Aは残りの5点との間に最大2直線しか形成できません。従って、ある点に対して4本の直線が引ける場合、各直線上には、3点のみが存在すると言えます。

トピ内ID：8650579189

...本文を表示

レスありがとうございます３

ぴたごらすトピ主

2011年07月20日 10:36

あってる？様考えていただいてどうもありがとうございます。私なりに検討してみましたが誤りがあればご指摘ください。 9点をA～Iとします。 3点X,Y,Zを通る直線をXYZと表す事にします。点Xと他の2点を通る直線の本数を@Xで表す事にします。 [1]は、@A＝4ならば Aを含む4点が1直線上に存在する事はあり得ない事を示しています。 [2]は、@A,@B＝4ならば A,Bと他の1点を通る直線が必ず存在する事を示しています。 [3]は、ABCが存在して@A,@B,@C＝4であれば [2]よりABCを含まずに@D＝4とする事は不可能と言っている様に思えます。しかし[2]から言えるのは@D＝4ならば必ずADE,BDF,CDGが存在する事で、さらにDHIが存在可能ですから@D＝4の可能性は残ると思います。 [4]は、ABCが存在して@A,@B＝4,@C≦3であれば Aを含めて@X＝4の点が最大5点ある可能性があるという事でしょうか？その理由が良くわかりませんでした。 [2]を発展させたらどうかと思案中です。

トピ内ID：0523487880

...本文を表示

最大は10本

ぴたごらすトピ主

2011年07月30日 10:27

３点を通る直線の本数を11本にする事はできないという証明をずっと考えていました。それらしきものを考え付いたのですが長いです。あらすじはこんな感じです。以降「3点を通る直線」を3で表す事にします。まず条件の明確化：4点以上が1直線上にあっても3は1本と数える 311本の解があれば、3が4本通る点が6個と3が3本通る点が3個存在する事を示す ↓ 3が4本通る点3個を通り、同じ点を通らない2本の3が存在する事を示す ↓ その2本を軸に特定の位置にある2個の点に注目すると3が11本存在しない事になり矛盾 ↓ ゆえに311本の解は存在しない２番目までは図を使わずに可能ですが、最後は図を必要とします。少しずつ書いていこうと思います。途中で誤りが発見されたらごめんなさい。

トピ内ID：0523487880

...本文を表示

証明1/4

ぴたごらすトピ主

2011年08月12日 21:21

A～I：9個の点直：3点を通る直線 #x：点xを通る直の本数 ■：全点の#xの合計 4点以上が直線上にあっても直は1本なので、2本の直は2点を共有しない。以下は直11本の配置が存在するものと仮定して話を進める。 4点A～Dを通る直があれば、Aを通る直はこの1本とE～Iのうち4点を通る2本なので#A≦3。同様に#B～#D≦3。E～Iは自分以外が8点なので#E～#I≦4。以上より■≦32。しかし直は3点以上を通るので11本ならば■≧33。ゆえに4点を通る直は存在しない。これより■＝33。 #x＝1の点があれば、この点を削除した8点の配置は直が1本減って■＝33－3＝30。 #x＝2の点があれば、この点を削除した8点の配置は直が2本減って■＝33－6＝27。しかし8点の配置ならば点x以外が7点なので#x≦3。したがって■≦24。ゆえに#x＝1,2の点は存在しない。一方9点の配置では点x以外が8点なので#x≦4。 ■＝33であるから9点は#x＝3の点が3個と#x＝4の点が6個となる。

トピ内ID：0523487880

...本文を表示

証明2/4

ぴたごらすトピ主

2011年08月12日 21:21

前回のまとめ：9点は#x＝3の点が3個と#x＝4の点が6個。 #x＝3の2点A,Bを通る直があれば、Aとの間に直が存在する点はBを含めて6点なので #x＝4の少なくとも1点はAとの間に直が存在しない事になり矛盾する。ゆえに#x＝3の2点を通る直は存在しない。したがって11本の直は以下の2種類。 α(9本)：#x＝3の1点と#x＝4の2点を通る β(2本)：#x＝3の点を通らない(#x＝4の3点を通る) 2本のβが1点を共有すれば#x＝4の5点を通るので、βが通らない#x＝4の1点を通る 4本の直はすべてα。すると#x＝3の点が4個存在する事になり矛盾する。ゆえに2本のβは1点を共有しない。これらをβ1,β2とする。 αが通る#x＝4の2点はβ1上の1点とβ2の1点である。 #x＝3の点☆を通る3本のαのイメージを下図に示す。 ○───○───○　←β1 〃＼〃〃│〃〃／〃〃○─○─○　←β2 〃〃〃＼│／〃〃〃〃☆ 直11本の配置では上図以外に2個の☆と6本のαが存在する。

トピ内ID：0523487880

...本文を表示

証明3/4

ぴたごらすトピ主

2011年08月12日 21:21

前回のまとめ：9本のαはβ1上の1点、β2上の1点、#x＝3の1点を通る。以下ではβ1とβ2が平行の場合と交点を持つ場合に分けて、3点の位置関係を考える。１．β1とβ2が平行の場合 ◎：β1上の端の点 ●：β2上の中間の点外〃＼〃〃◎──○──○　←β1 〃〃〃＼〃〃〃〃内〃〃〃〃〃＼〃〃〃△──●──◇　←β2 〃〃〃〃〃〃〃＼〃〃〃〃〃〃〃〃外可能性１．◎と●を結ぶ直線上に#x＝3の点が存在しない →9本中1本のαが存在しない。可能性２．◎と●を結ぶ直線の「内」の区間に#x＝3の点☆が存在する →☆と◇を通る直線上に○が存在しないので、この☆を通るαは2本。可能性３．◎と●を結ぶ直線の「外」の区間に#x＝3の点☆が存在する →☆と△を通る直線上に○が存在しないので、この☆を通るαは2本。 β1とβ2が平行の場合はαが9本存在しないので、直11本の配置は不可能である。

トピ内ID：0523487880

...本文を表示

注目!おすすめトピ一覧

すべて見るすべて見る

証明4/4

ぴたごらすトピ主

2011年08月12日 21:21

２．β1とβ2が交点を持つ場合 ◎：β1上の交点の隣の点 ●：β2上の交点から1点置いた点図は○が両側に1点ずつ存在するが、片側に2点あっても良い。図は◇が存在可能な位置を示すもので、実際に◇が2個存在するわけではない。外〃◇ 〃＼│ 〃〃● 〃〃│＼〃〃△〃内〃〃│〃〃＼ ○─┼───◎─○　←β1 〃〃│〃〃〃〃＼〃〃◇〃〃〃〃〃外〃〃↑ 〃〃β2 可能性１．◎と●を結ぶ直線上に#x＝3の点が存在しない →9本中1本のαが存在しない。可能性２．◎と●を結ぶ直線の「内」の区間に#x＝3の点☆が存在する →☆と◇を通る直線上に○が存在しないので、この☆を通るαは2本。可能性３．◎と●を結ぶ直線の「外」の区間に#x＝3の点☆が存在する →☆と△を通る直線上に○が存在しないので、この☆を通るαは2本。 β1とβ2が交点を持つ場合もαが9本存在しないので、直11本の配置は不可能である。以上

トピ内ID：0523487880

...本文を表示