허락하다 $P$ 될 $30$원에 새겨진 양면 다각형. 가치 찾기 $\frac{N}{100}$.

Question

허락하다 $P$ 될 $30$원에 새겨진 양면 다각형. 있습니다$N$ 정점이 정점 인 삼각형의 수 $P$ 각 삼각형의 두 꼭지점이 적어도 세 개의 다른 꼭지점으로 분리되도록 $P$. 가치 찾기$\frac{N}{100}$.

내가 시도한 것 : 이것은 기하학 문제 라기보다는 조합 문제에 더 가깝기 때문에 여기에 내가 생각하는 것이 있습니다.

먼저 삼각형의 점을 고정합니다. 다음 포인트는$23$방법. 그러나 나는 선택하는 방법을 잘 모르겠습니다$3$rd point, 선택에 관해서는 $2$그리고 규칙을 따르지 않는 약간의 변형도 있습니다.

한 점을 고치기 전에 생각했다가 다음 점을 $2$ 포인트 선택 가능 ${23}\choose{2}$ 하지만 그게 잘못된 것임을 깨달았습니다. $2$ 포인트가 없을 수 있습니다 $3$ 포인트 갭, 그리고 나는 이것을 진행하는 방법을 얻을 수 없었습니다.

평소와 같이 삼각형의 수는 $n$공유 된면이없는면 다각형은 다음 공식으로 제공됩니다. $$\rightarrow\frac{n(n-4)(n-5)}{6}$$ 따라서 총 삼각형 수는 $3250$,하지만이 사실이이 문제에 어떻게 도움이 될지 잘 모르겠습니다.

누구든지 나를 도울 수 있습니까? 감사합니다.

Answer 1

아무 지점이나 선택하고 부르세요 $A_1$. 시계 반대 방향으로 점에 레이블 지정$A_2,\ldots,A_{30}$ .

두 번째 정점은 $A_5$ ...에 $A_{27}$.

두 번째가 $A_5$, 세 번째 정점은 $A_9$ ...에 $A_{27}$. 그건$19$ 방법.

두 번째가 $A_6$, 세 번째 정점은 $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$ 두 번째 정점이있을 때 점의 수는 먼저 제외됩니다. $A_{k+2}$.

Answer 2

다른 방법은 별과 막대 방법을 사용하는 것입니다.

삼각형 대신 일반화하고 고려할 수 있습니다. $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$ 따라서 최종 솔루션은 다음과 같습니다.

$${n-kd+k-1 \choose k-1}\frac{n}{k}={30-3\cdot4+3-1 \choose 3-1}\frac{30}{3}={20 \choose 2}\frac{30}{3}=1900$$