凸レーダーチャート問題

問題：
5段階、6要素のレーダーチャートで凸6角形になるグラフは何通り？

— いのこり (@ImCallinx2You) 2020年4月18日

解答例です。言語はC++

#include <bits/stdc++.h>
using namespace std;

bool test(vector <int> a){
    
    bool ok = true;
    int ab, ac;
    
    for(int j=0; j<6; j++){
        ab = a[(j+1)%6];
        ac = a[(j+5)%6];
        if(a[j%6]<=ab*ac/(ab+ac)){
            ok = false;
            break;
        }
    }
    
    return ok;
}

int all(vector<int> a, int n){
    
    if(n==0)
        return test(a);
    
    int k;
    
    for(int i=0; i<5; i++){
        a[n-1] = i+1;
        k += all(a, n-1);
    }
    
    return k;
}

int main(){
    
    vector<int> a(6);
    
    cout << all(a,6) << endl;
    return 0;
}

コードの心臓は関数で、すべての要素のスコアが「隣り合うスコアを結んだ時の線分と要素の軸の交点のスコア」より大きければを返します。1個でも成り立たなければです。

(右の白点がレーダーチャートの中心。ぐるり一周あるうちの3要素だけに注目している。)

は、角の二等分線の性質を使って *1と求められます。

関数で全てのレーダーチャートの結果について を行い、の個数を数えます。

計算の結果、答えは 通りです。

*1:これは二等分すべき角を として、 であるのをとした特殊なケースです。 一般にM段階N要素のレーダーチャートの場合を考えましょう。 N<3の場合、レーダーは多角形にならないので 0通りです。 N=3の場合、 なる が 1個までなら三角形になるので 答えは通りです。 N>3の場合、 として上のコードを一般化し、計算機をブン回せばで求まるはずです。一般式や対称性を使えばもっと速いのかもしれませんが。