ジュニア算数オリンピック 二次元上のユークリッド幾何の問題 その２２

ジュニア算数オリンピックにおけるユークリッド幾何学の問題の解答の自動化を模索している。まず三角形定理ループを回し、回答できなかったら1ステップの作図を試していって、それらで回答できるか探る。それでも駄目だったら2ステップ、3ステップと増やしていく。作業手順は今はこれを参考にする。
　

07年度トライアル問題　問題5

『xの角度を求めなさい。

』

交点には、上からアルファベット順で名前を付けていく。同じ高さにあるものは、左から右へ付けていく。

graph := [
    A : [
        [[C, E], []],
        [[D, F, H], []],
        [[G], []]
    ]
    ,
    B : [
        [[C, D, G], []],
        [[E, H], []]
    ]
    ,
    C : [
        [[A], [E]],
        [[B], [D, G]]
    ]
    ,
    D : [
        [[A], [F, H]],
        [[B, C], [G]
    ]
    ,
    E : [
        [[B], [H]],
        [[A, C], []],
        [[G, F], []]
    ]
    ,
    F : [
        [[A, D], [H]],
        [[E], [G]]
    ]
    ,
    G : [
        [[A], []],
        [[B, C, D], []],
        [[E, F], []],
        [[H], []]
    ]
    ,
    H : [
        [[G], []],
        [[A, D, F], []],
        [[B, E], []]
    ]
];

parallel_lines_lst := [
];

triangle_lst := [
];

cluster_lst := [
];

always {
    DAG_p == 20;    #答えで確認した。紛らわしいが
    CBE_p == 50;
    BGE_p == 65;
    EGH_p == 15;
    AHB_p == 30;
}

クラスタをどう設定するかが問題なんだが、今回はそれを探るために、あえて最初はクラスタには何も登録しないことにした。

三角形をまず更新することにする。graphを確認して、keyのvalueの中身で更にgraphを確認し、その中にkeyのvalueの中身と同じものがあれば（ただしkeyと同一直線上のは抜かす）、それらは三角形だ。

更に角のイコールを確認する。平行線のリストには何も無し。対頂角はCとDとFにある。

辺のイコールは定義通り。

辺の和を確認する。graphを確認して、ある点を跨る辺がある時は、辺の和として更新する。

graph := [
    A : [
        [[C, E], []],
        [[D, F, H], []],
        [[G], []]
    ]
    ,
    B : [
        [[C, D, G], []],
        [[E, H], []]
    ]
    ,
    C : [
        [[A], [E]],
        [[B], [D, G]]
    ]
    ,
    D : [
        [[A], [F, H]],
        [[B, C], [G]
    ]
    ,
    E : [
        [[B], [H]],
        [[A, C], []],
        [[G, F], []]
    ]
    ,
    F : [
        [[A, D], [H]],
        [[E], [G]]
    ]
    ,
    G : [
        [[A], []],
        [[B, C, D], []],
        [[E, F], []],
        [[H], []]
    ]
    ,
    H : [
        [[G], []],
        [[A, D, F], []],
        [[B, E], []]
    ]
];

parallel_lines_lst := [
];

triangle_lst := [
    △ACD : [CAD_p, AC, ACD_p, CD, ADB_p, AD],
    △ACG : [CAG_p, AC, ACD_p, CG, AGB_p, AG],　
    △AEF : [CAD_p, AE, AEG_p, EF, AFG_p, AF],
    △AEH : [CAD_p, AE, AEH_p, EH, AHB_p, AH],
    △AEG : [CAG_p, AE, AEG_p, EG, AGE_p, AG],
    △ADG : [DAG_p, AD, ADG_p, DG, AGB_p, AG],
    △AFG : [DAG_p, AF, AFG_p, FG, AGE_p, AG],
    △AGH : [DAG_p, AG, AGH_p, GH, AHG_p, AH],
    △BCE : [CBE_p, BC, BCE_p, CE, AEB_p, BE],
    △BDH : [CBE_p, BD, BDF_p, DH, AHB_p, BH],
    △BEG : [CBE_p, BE, BEG_p, EG, BGE_p, BG],
    △BGH : [CBE_p, BG, BGH_p, GH, BHG_p, BH],
    △CEG : [DCE_p, CE, AEG_p, EG, BGE_p, CG],    #ミスで抜かしていた
    △DFG : [FDG_p, DF, AFG_p, FG, BGE_p, DG],
    △DGH : [FDG_p, DG, BGH_p, GH, AHG_p, DH],
    △EGH : [GEH_p, EG, EGH_p, GH, BHG_p, EH],
    △EFH : [GEH_p, EF, EFH_p, FH, AHB_p, EH],
    △FGH : [GFH_p, FG, EGH_p, GH, AHB_p, FH]
];

cluster_lst := [
];

always {
    DAG_p == 20;    #答えで確認した。紛らわしいが
    CBE_p == 50;
    BGE_p == 65;
    EGH_p == 15;
    AHB_p == 30;

    ACG_p == DCE_p;
    ACD_p == BCE_p;
    ADB_p == FDG_p;
    ADG_p == BDF_p;
    AFE_p == GFH_p;
    AFG_p == EFH_p;
    AC + CE == AE;
    BC + CD == BD;
    BC + CG == BG;
    AD + DF == AF;
    AD + DH == AH;
    BD + DG == BG;
    CD + DG == CG;
    BE + EH == BH;
    AF + FH == AH;
    DF + FH == DH;
    EF + FG == EG;
}

三角形からクラスタを登録する。

更に、クラスタの辺が、辺の和の全体になっていて、例えばその間の点と三角形のクラスタの頂点が結び付いていたら、その点も含めてクラスタとして登録できるし、角の和として登録できる。間の点と点が結び付いていたら、それでもクラスタの分割になって、クラスタとして登録できる。
新しい作業なので、過程を貼る。一番上が三角形で、その後は何となく察してほしい。

ACG
CD + DG == CG;
AD
　[[A, C, D, G], [CAG_p, AC, ACD_p, CD, CDG_h, DG, AGB_p, AG]],
　CAD_p + DAG_p == CAG_p;

AEF
AC + CE == AE;
AD + DF == AF;
CD
　[[C, E, F, D], [DCE_p, CE, AEG_p, EF, AFG_p, DF, BDF_p, CD]]

AEH
AF + FH == AH;
EF
　[A, E, H, F], [CAD_p, AE, AEH_p, EH, AHB_p, AF, AFH_h, FH]
　AEG_p + GEH_p == AEH_p;

AEH
AC + CE == AE;
AD + DH == AH;
CD
　[C, E, H, D], [DCE_p, CE, AEH_p, EH, AHB_p, DH, BDF_p, CD],

AEG
AC + CE == AE;
CG
　[[A, C, E, G], [CAG_p, AC, ACD_h, CE, AEG_p, EG, AGE_p, AG]],
　AGB_p + BGE_p == AGE_p;

AEG
EF + FG == EG;
AF
　[[A, E, F, G], [CAG_p, AE, AEG_p, EF, EFG_h, FG, AGE_p, AG]],
　CAD_p + DAG_p == CAG_p;

AFG
AD + DF == AF;
DG
　[[A, D, F, G], [DAG_p, AD, ADF_h, DF, AFG_p, FG, AGE_p, AG]],
　AGB_p + BGE_p == AGE_p;

AGH
AD + DH == AH;
DG
　[[A, G, H, D], [DAG_p, AG, AGH_p, GH, AHG_p, DH, ADF_h, AD]],
　AGB_p + BGH_p == AGH_p;

AGH
AF + FH == AH;
FG
　[[A, G, H, F], [DAG_p, AG, AGH_p, GH, AHG_p, FH, AFH_h, AF]],
　AGE_p + EGH_p == AGH_p;

BDH
BC + CD == BD;
BE + EH == BH;
CE
　[[C, D, H, E], [DCE_p, CD, BDF_p, DH, AHB_p, EH, AEH_p, CE]],

BDH
BE + EH == BH;
DF + FH == DH;
EF
　[[E, B, D, F], [BEG_p, BE, CBE_p, BD, BDF_p, DF, AFE_p, EF]],

BEG
BC + CG == BG;
CE
　[[B, E, G, C], [CBE_p, BE, BEG_p, EG, BGE_p, CG, BCD_h, BC]],
　BEA_p + AEG_p == BEG_p;

BEG
BD + DG == BG;
EF + FG == EG;
DF
　[[B, E, F, D], [CBE_p, BE, BEG_p, EF, AFE_p, DF, BDF_p, BD]],

BGH
BD + DG == BG;
DH
　[[B, D, G, H], [CBE_p, BD, BDG_h, DG, BGH_p, GH, BHG_p, BH]],
　AHB_p + AHG_p == BHG_p;

BGH
BE + EH == BH;
EG
　[[B, G, H, E], [CBE_p, BG, BGH_p, GH, BHG_p, EH, BEH_h, BE]],
　BGE_p + EGH_p == BGH_p;

BGH
BE + EH == BH;
BC + CG == BG;
CE
　[[C, G, H, E], [DCE_p, CG, BGH_p, GH, BHG_p, EH, AEH_p, CE]],

？？？
BGH
BC + CG == BG;
BD + DG == BG;
CD
　[[B, G, H], [CBE_p, BG, BGH_p, GH, BHG_p, BH]],
？？？

CEG
CD + DG == CG;
EF + FG == EG;
DF
　[[C, E, F, D], [DCE_p, CE, AEG_p, EF, AFE_p, DF, BDF_p, CD]],

DGH
DF + FH == DH;
FG
　[[D, G, H, F], [FDG_p, DG, BGH_p, GH, AHG_p, FH, AFH_h, DF]],
　BGE_p + EGH_p == BGH_p;

EGH
EF + FG == EG;
FH
　[[E, F, G, H], [GEH_p, EF, EFG_h, FG, EGH_p, GH, BHG_p, EH]],
　AHB_p + AHG_p == BHG_p;

更に、graphを確認して、辺によって辺の180°が区切られているようなのを探して登録する。対頂角は登録されているので、半分ほど省けるだろう。

三角形に着目して、外角も登録する。いや、外角は登録しなくても良いな。三角形の内角は自動的に合計180°だと登録されるし、辺を辺で区切ることによる180°も登録されるので（そういう風にする）、自動的に弾き出される。（よく考えると、対頂角も自動的に取得されるか？）（錯角も自動的にと記述していたが、いや、でもそれも？）

graph := [
    A : [
        [[C, E], []],
        [[D, F, H], []],
        [[G], []]
    ]
    ,
    B : [
        [[C, D, G], []],
        [[E, H], []]
    ]
    ,
    C : [
        [[A], [E]],
        [[B], [D, G]]
    ]
    ,
    D : [
        [[A], [F, H]],
        [[B, C], [G]
    ]
    ,
    E : [
        [[B], [H]],
        [[A, C], []],
        [[G, F], []]
    ]
    ,
    F : [
        [[A, D], [H]],
        [[E], [G]]
    ]
    ,
    G : [
        [[A], []],
        [[B, C, D], []],
        [[E, F], []],
        [[H], []]
    ]
    ,
    H : [
        [[G], []],
        [[A, D, F], []],
        [[B, E], []]
    ]
];

parallel_lines_lst := [
];

triangle_lst := [
    △ACD : [CAD_p, AC, ACD_p, CD, ADB_p, AD],
    △ACG : [CAG_p, AC, ACD_p, CG, AGB_p, AG],　
    △AEF : [CAD_p, AE, AEG_p, EF, AFG_p, AF],
    △AEH : [CAD_p, AE, AEH_p, EH, AHB_p, AH],
    △AEG : [CAG_p, AE, AEG_p, EG, AGE_p, AG],
    △ADG : [DAG_p, AD, ADG_p, DG, AGB_p, AG],
    △AFG : [DAG_p, AF, AFG_p, FG, AGE_p, AG],
    △AGH : [DAG_p, AG, AGH_p, GH, AHG_p, AH],
    △BCE : [CBE_p, BC, BCE_p, CE, AEB_p, BE],
    △BDH : [CBE_p, BD, BDF_p, DH, AHB_p, BH],
    △BEG : [CBE_p, BE, BEG_p, EG, BGE_p, BG],
    △BGH : [CBE_p, BG, BGH_p, GH, BHG_p, BH],
    △CEG : [DCE_p, CE, AEG_p, EG, BGE_p, CG],    #ミスで抜かしていた
    △DFG : [FDG_p, DF, AFG_p, FG, BGE_p, DG],
    △DGH : [FDG_p, DG, BGH_p, GH, AHG_p, DH],
    △EGH : [GEH_p, EG, EGH_p, GH, BHG_p, EH],
    △EFH : [GEH_p, EF, EFH_p, FH, AHB_p, EH],
    △FGH : [GFH_p, FG, EGH_p, GH, AHB_p, FH]
];

cluster_lst := [
    [[A, C, D], [CAD_p, AC, ACD_p, CD, ADB_p, AD]],
    [[A, C, G], [CAG_p, AC, ACD_p, CG, AGB_p, AG]],　
    [[A, E, F], [CAD_p, AE, AEG_p, EF, AFG_p, AF]],
    [[A, E, H], [CAD_p, AE, AEH_p, EH, AHB_p, AH]],
    [[A, E, G], [CAG_p, AE, AEG_p, EG, AGE_p, AG]],
    [[A, D, G], [DAG_p, AD, ADG_p, DG, AGB_p, AG]],
    [[A, F, G], [DAG_p, AF, AFG_p, FG, AGE_p, AG]],
    [[A, G, H], [DAG_p, AG, AGH_p, GH, AHG_p, AH]],
    [[B, C, E], [CBE_p, BC, BCE_p, CE, AEB_p, BE]],
    [[B, D, H], [CBE_p, BD, BDF_p, DH, AHB_p, BH]],
    [[B, E, G], [CBE_p, BE, BEG_p, EG, BGE_p, BG]],
    [[B, G, H], [CBE_p, BG, BGH_p, GH, BHG_p, BH]],
    [[C, E, G], [DCE_p, CE, AEG_p, EG, BGE_p, CG]],
    [[D, F, G], [FDG_p, DF, AFG_p, FG, BGE_p, DG]],
    [[D, G, H], [FDG_p, DG, BGH_p, GH, AHG_p, DH]],
    [[E, G, H], [GEH_p, EG, EGH_p, GH, BHG_p, EH]],
    [[E, F, H], [GEH_p, EF, EFH_p, FH, AHB_p, EH]],
    [[F, G, H], [GFH_p, FG, EGH_p, GH, AHB_p, FH]],
    [[A, C, D, G], [CAG_p, AC, ACD_p, CD, CDG_h, DG, AGB_p, AG]],
    [[C, E, F, D], [DCE_p, CE, AEG_p, EF, AFG_p, DF, BDF_p, CD]],
    [[A, E, H, F], [CAD_p, AE, AEH_p, EH, AHB_p, AF, AFH_h, FH]],
    [[C, E, H, D], [DCE_p, CE, AEH_p, EH, AHB_p, DH, BDF_p, CD]],
    [[A, C, E, G], [CAG_p, AC, ACD_h, CE, AEG_p, EG, AGE_p, AG]],
    [[A, E, F, G], [CAG_p, AE, AEG_p, EF, EFG_h, FG, AGE_p, AG]],
    [[A, D, F, G], [DAG_p, AD, ADF_h, DF, AFG_p, FG, AGE_p, AG]],
    [[A, G, H, D], [DAG_p, AG, AGH_p, GH, AHG_p, DH, ADF_h, AD]],
    [[A, G, H, F], [DAG_p, AG, AGH_p, GH, AHG_p, FH, AFH_h, AF]],
    [[C, D, H, E], [DCE_p, CD, BDF_p, DH, AHB_p, EH, AEH_p, CE]],
    [[E, B, D, F], [BEG_p, BE, CBE_p, BD, BDF_p, DF, AFE_p, EF]],
    [[B, E, G, C], [CBE_p, BE, BEG_p, EG, BGE_p, CG, BCD_h, BC]],
    [[B, E, F, D], [CBE_p, BE, BEG_p, EF, AFE_p, DF, BDF_p, BD]],
    [[B, D, G, H], [CBE_p, BD, BDG_h, DG, BGH_p, GH, BHG_p, BH]],
    [[B, G, H, E], [CBE_p, BG, BGH_p, GH, BHG_p, EH, BEH_h, BE]],
    [[C, G, H, E], [DCE_p, CG, BGH_p, GH, BHG_p, EH, AEH_p, CE]],
    [[C, E, F, D], [DCE_p, CE, AEG_p, EF, AFE_p, DF, BDF_p, CD]],
    [[D, G, H, F], [FDG_p, DG, BGH_p, GH, AHG_p, FH, AFH_h, DF]],
    [[E, F, G, H], [GEH_p, EF, EFG_h, FG, EGH_p, GH, BHG_p, EH]]
];

always {
    DAG_p == 20;    #答えで確認した。紛らわしいが
    CBE_p == 50;
    BGE_p == 65;
    EGH_p == 15;
    AHB_p == 30;

    ACG_p == DCE_p;
    ACD_p == BCE_p;
    ADB_p == FDG_p;
    ADG_p == BDF_p;
    AFE_p == GFH_p;
    AFG_p == EFH_p;
    AC + CE == AE;
    BC + CD == BD;
    BC + CG == BG;
    AD + DF == AF;
    AD + DH == AH;
    BD + DG == BG;
    CD + DG == CG;
    BE + EH == BH;
    AF + FH == AH;
    DF + FH == DH;
    EF + FG == EG;

    CAD_p + DAG_p == CAG_p;
    AEG_p + GEH_p == AEH_p;
    AGB_p + BGE_p == AGE_p;
    AGB_p + BGH_p == AGH_p;
    AGE_p + EGH_p == AGH_p;
    AEB_p + AEG_p == BEG_p;
    AHB_p + AHG_p == BHG_p;
    BGE_p + EGH_p == BGH_p;
    ACB_p + BCE_p == 180;
    ACB_p + ACD_p == 180;
    ADB_p + BDF_p == 180;
    ADB_p + ADG_p == 180;
    ABE_p + AEH_p == 180;
    BEG_p + GEH_p == 180;
    AFE_p + EFH_p == 180;
    AFE_p + AFG_p == 180;
}

で、まあ点に着目して確認すると、必要な角の和は取得されてるわけだ。おそらく全体が三角形で構成されていたからだろう。

今回は使わないが、クラスタ内での交点の発生についても考えてみる。
交点さえ考えることができれば、何と何が繋がっているかはgraphにあるので、分割したクラスタもまた分割することができるだろう。

まず2つの辺について考える。
頂点同士から伸びている場合は、同じ頂点から伸びている場合は、交点は発生しない。違う頂点から伸びている場合は、交点は必ず発生する。

頂点から伸びている辺と、辺から辺へ伸びている辺だと、頂点を挟む辺同士で発生している辺だと、必ず交点は発生する。底辺が関わる場合、底辺における2つの辺の位置関係で、交点ができる場合とできない場合の2通りが考えられる。

辺から辺へ伸びている辺同士の場合は、もしその辺が同じ端点を共有している場合は、交点は絶対に発生しない。
また、（三角形の）2辺で完結する場合は、その2辺の間で点と点の位置関係を見れば良い。
（三角形の）3辺が関わる場合も、2つがくっついている辺と、1つずつしかくっついていない辺の、位置関係を見れば良い。

2つの辺の場合は簡単だが、3つの辺が絡んでくると、交点が発生する際の位置関係が難しくなるのではないか。
三角関数？が必要なんじゃないかなあ。そうすると、平面が概念として必要になるのではないか。同一平面上にある点同士で無ければ、そもそも三角関数？は成立しないだろう。交点ができるとしたらどこかを判定することはできるが、いや、それならクラスタの中であれば必要無いのか。

まあ、辺における点の前後関係自体は、graphにおいて、まず片方に点が何も無いのを探して、次にその一つ前だけがあるのを探して、というのを続ければ良いと思うけど。そういう位置関係が曖昧なのは、そもそも入れないとして。いや、入れるんだっけな？まあ実際に詳しくやってみないと分からないが。