本文へ

9個の点と直線パズル

レス16
(トピ主 8
041
ぴたごらす
話題
こんにちは。少し長くなりますがお付き合い下さい。

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

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

聞いた事あります。

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

トピ内ID:2944107772

...本文を表示

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

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

トピ内ID:6697915500

...本文を表示

考えてみました

041
クルー
続きです >(理由)任意の点Aに着目するとこれを通る直線は他の2点を通る。点A以外の 点の個数は8個なので点Aを通る直線は最大4本である。9点すべてに4本の 直線が通る場合の本数は4×9÷3=12となり、これを超える事はできない。 なぜ最大4本になるのですか? 任意の点をAとして、数字を他の点としてみてください。   1   2 34A56   7   8 ・12A ・2A7 ・A78 ・34A ・4A5 ・A56 この6通り考えられるのですが、これはだめ? もちろんこの配置ではたの8点に対して同じことは言えませんが・・・。 任意の点Aに関してだけ言えば6本以上は可能だと思います。 それとも直線は重なってはいけない? ちなみに9点を以下のように配置して 1 2 3  456 7 8 9 ・123 ・456 ・789 ・258 ・148 ・368 ・247 ・269 ・357 ・159 ・357 この11本はだめ?

トピ内ID:6697915500

...本文を表示

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

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

トピ内ID:3029373355

...本文を表示

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

041
ぴたごらす トピ主
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

...本文を表示

サム・ロイド

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

トピ内ID:0351350790

...本文を表示

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

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

トピ内ID:0523487880

...本文を表示

あってる?

041
あってる?
仮に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

041
あってる?
[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

...本文を表示

あってる?

041
あってる?
仮に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

...本文を表示

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

041
ぴたごらす トピ主
あってる?様 考えていただいてどうもありがとうございます。私なりに検討してみましたが 誤りがあればご指摘ください。 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本

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

トピ内ID:0523487880

...本文を表示

証明1/4

041
ぴたごらす トピ主
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

041
ぴたごらす トピ主
前回のまとめ: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

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

トピ内ID:0523487880

...本文を表示

証明4/4

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

トピ内ID:0523487880

...本文を表示
[PR]
気に入ったトピを保存するといつでも読み返せる
気に入ったトピを保存するといつでも読み返せる
使用イメージ
使用イメージ

マイページ利用でもっと便利に!

お気に入り機能を使う ログイン
レス求!トピ一覧