しましょう $P$ である $30$-円に内接する側面ポリゴン。の値を見つける $\frac{N}{100}$。

Dec 05 2020

しましょう $P$ である $30$-円に内接する側面ポリゴン。がある$N$ 頂点がの頂点である三角形の数 $P$ 各三角形の任意の2つの頂点が、で少なくとも3つの他の頂点によって分離されるように $P$。の値を見つける$\frac{N}{100}$。

私が試したこと：これは、幾何学の問題というよりは組み合わせ論の問題に似ているので、これが私が思うことです。

まず、三角形の点を修正します。次のポイントはで選択できます$23$方法。しかし、私はどのように選択するのかわかりません$3$rdポイント、選択に関しては $2$第二に、ルールに従わないわずかな変動もあります。

私は前に1つのポイントを修正し、次に次のポイントを修正することを考えました $2$ ポイントはで選択できます ${23}\choose{2}$ 方法が、それから私はそれらが間違っていることに気づきました $2$ ポイントにはないかもしれません $3$ ポイントギャップ、そして私はこれをどのように進めるかを理解することができませんでした。

いつものように、私はまた、上の三角形の数が $n$-共有された辺のない辺のポリゴンは、次の式で与えられます：- $$\rightarrow\frac{n(n-4)(n-5)}{6}$$ したがって、三角形の総数は次のようになります。 $3250$、しかし、この事実がこの問題にどのように役立つかはわかりません。

誰か助けてもらえますか？ありがとうございました。

回答

4 cosmo5 Dec 05 2020 at 20:20

任意のポイントを選択してそれを呼び出します $A_1$。反時計回りにポイントにラベルを付けます$A_2,\ldots,A_{30}$ 。

2番目の頂点は $A_5$ に $A_{27}$。

2番目が $A_5$、3番目の頂点は $A_9$ に $A_{27}$。それは$19$ 方法。

2番目が $A_6$、3番目の頂点は $A_{10}$ に $A_{27}$。それは$18$ 方法。

等々。三角形の数$= 19+18+17+\ldots+1$

最初の頂点として任意の点から開始できるため、 $$\dfrac{19\cdot20}{2} \cdot \dfrac{30}{3}$$

少なくとも去るなら $k$ 隣接する頂点間のポイント、同じロジックで取得します $$\dfrac{n(n-3k-1)(n-3k-2)}{6}$$

適切に $k$。以来$3k+2$ 2番目の頂点が次の場合、最初に点の数が省略されます $A_{k+2}$。

2 BillyJoe Dec 05 2020 at 21:04

別のアプローチは、星と棒の方法を使用することです。

三角形の代わりに一般化して考えることができます、 $k$-両面ポリゴン。またしましょう$d$ それらの頂点間の最小の「距離」である $k$-側面ポリゴン。「距離」は、内側の頂点の数に1を加えたものです。私たちの場合、$k = 3$ そして $d = 4$。したがって、問題は次の解の数を見つけることになります。

$$ x_1 + x_2 + \ldots + x_{k-1} + x_k = n$$

どこ $x_i, i=1,\ldots,k$ の頂点間の「距離」です $k$-側面ポリゴン、制約付き：

$$x_i \ge d, i=1,\ldots,k$$

定義することができます $y_i = x_i+d, i=1,\ldots,k$、そして最初の方程式は次のようになります。

$$y_1 + y_2 + \ldots + y_{k-1} + y_k = n-kd$$

と $y_i \ge 0, i=1,\ldots,k$。したがって、星と棒の方法では、各頂点の解は次のようになります。

$${n-kd+k-1 \choose k-1}$$

そしてあります $n$ 頂点、しかしすべて $k$-側面ポリゴンはと共通です $k$ それらのうち、最終的な解決策は次のとおりです。