Denote $U$ as the set of $20$ diagonals of the regular polygon $P_1P_2P_3P_4P_5P_6P_7P_8$. Find the number of sets $S$ which satisfies the following conditions. 1. $S$ is a subset of $U$. 2. If $P_iP_j \in S$ and $P_j P_k \in S$, and $i \neq k$, $P_iP_k \in S$.
Problem
Source: 2017 KMO Problem 1
Tags: combinatorics, polygon, diagonals, counting
S.C.B.
12.11.2017 13:15
Well, you upload them very quickly! I tried to post them but it seems you uploaded all of them.
MarkBcc168
12.11.2017 13:33
rkm0959 wrote: 2. If $P_iP_j \in S$ and $P_j P_k \in S$, and $i \neq k$, $P_iP_k \in S$. Since $P_iP_{i+1}\notin S$, therefore there are not exist $i, j$ such that $P_iP_j\in S$ and $P_{i+1}P_j\in S$ right?
rkm0959
12.11.2017 13:40
People around me told that that is indeed correct. I misread the question (included $P_i P_{i+1}$ in $U$ as well) and got $B_8 = 4140$. Darn.. This problem is quite bashy, after one proves the obvious lemma that each connected component is a complete graph. Almost everyone got different answers, so I would like to know the answer.
S.C.B.
12.11.2017 18:09
I gave up this problem after several minutes (I'm quite horrible at bashing). The students next to me speculated the answer is 715 or something similar.
PARISsaintGERMAIN
12.11.2017 21:46
Yeah the answer is 715
darij grinberg
15.11.2017 08:11
So you want to count the equivalence relations on the set $\left\{P_1, P_2, \ldots, P_8\right\}$ such that no $P_i$ is equivalent to $P_{i+1}$ (where $P_9$ is understood to mean $P_1$). In other words, you want to count the set partitions of the set $\left\{P_1, P_2, \ldots, P_8\right\}$ such that no $P_i$ belongs to the same block as $P_{i+1}$ (because choosing an equivalence relation is the same as choosing the equivalence classes it partitions the set into). This has recently appeared on the arXiv: ยง5 in Richard Ehrenborg, Alex Happ, Dustin Hedmark, Cyrus Hettle, Box polynomials and the excedance matrix, arXiv:1708.09804v1. The main results for us are: - Lemma 5.2. Fix $n \in \mathbb{N}$, and let $\left[n\right]$ be the set $\left\{1,2,\ldots,n\right\}$. The set partitions of $\left[n\right]$ such that no $i$ belongs to the same block as $i+1$, nor does $n$ belong to the same block as $1$, are in bijection with the set partitions of $\left[n\right]$ having no singleton blocks. - The number of the latter set partitions satisfies a nice recurrence and is Sequence A000296 in the OEIS. Yes, the value for $n = 8$ is $715$.
PARISsaintGERMAIN
26.12.2017 18:55
When we allow the $8$ edges of a regular octagon, it turns out to divide the $8$ vertices into few unlabelled group and making the complete graph for each group.
Here, since the points are labeled, but groups are not, we need Stirling numbers of the second kind.
Let $S(n)$ be the number of ways to divide $n$ labeled vertices into few unlabeled-nonempty groups.
Then, $S(n)=\sum_{k=1}^n S(n,k)$ where $S(n,k)$ is the Stirling numbers of second kind.
We know that $S(n,k)=S(n-1,k-1)+kS(n-1,k)$ by easy combinatorial argument with $n$th vertives.
By using this identity, we can calculate the first few(?) numbers of the Stirling number of the second kind.
\begin{tabular}{|c|l|l|l|l|l|l|l|l|}
\hline
(k,n) & n=1 & n=2 & n=3 & n=4 & n=5 & n=6 & n=7 & n=8 \\ \cline{1-9}
k=1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \cline{1-9}
k=2 & & 1 & 3 & 7 & 15 & 31 & 63 & 127 \\ \cline{1-9}
k=3 & & & 1 & 6 & 25 & 90 & 301 & 966 \\ \cline {1-9}
k=4 & & & & 1 & 10 & 65 &350 & 1701 \\ \cline{1-9}
k=5 & & & & & 1 & 15 & 140 & 1050 \\ \cline{1-9}
k=6 & & & & & & 1 & 21 & 266 \\ \cline{1-9}
k=7 & & & & & & & 1 & 28 \\ \cline{1-9}
k=8 & & & & & & & & 1 \\ \cline{1-9}
S(n) & 1 & 2 & 5 & 15 & 52 & 203 & 877 & 4140 \\ \cline{1-9}
\hline
\end{tabular}
Now, since we cannot use our edges of octagon originally, we should use PIE in order to exclude the sets using the edges.
Regardless of what edge we use, as we use one edge, we can just consider as one vertex disappearing. Thus, when we use $i$ edges of octagon, there are $S(8-i)$ ways to construct such set.
Hence, our answer is $4140-\binom{8}{1}\cdot 877 +\binom{8}{2}\cdot 203-\binom{8}{3}\cdot 52+\binom{8}{4}\cdot 15-\binom{8}{5}\cdot 5 +\binom{8}{6}\cdot 2 -\binom{8}{7}\cdot 1 +1=\boxed{715}$
shmoon
23.07.2018 18:35
PARISsaintGERMAIN wrote:
When we allow the $8$ edges of a regular octagon, it turns out to divide the $8$ vertices into few unlabelled group and making the complete graph for each group.
Here, since the points are labeled, but groups are not, we need Stirling numbers of the second kind.
Let $S(n)$ be the number of ways to divide $n$ labeled vertices into few unlabeled-nonempty groups.
Then, $S(n)=\sum_{k=1}^n S(n,k)$ where $S(n,k)$ is the Stirling numbers of second kind.
We know that $S(n,k)=S(n-1,k-1)+kS(n-1,k)$ by easy combinatorial argument with $n$th vertives.
By using this identity, we can calculate the first few(?) numbers of the Stirling number of the second kind.
\begin{tabular}{|c|l|l|l|l|l|l|l|l|}
\hline
(k,n) & n=1 & n=2 & n=3 & n=4 & n=5 & n=6 & n=7 & n=8 \\ \cline{1-9}
k=1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \cline{1-9}
k=2 & & 1 & 3 & 7 & 15 & 31 & 63 & 127 \\ \cline{1-9}
k=3 & & & 1 & 6 & 25 & 90 & 301 & 966 \\ \cline {1-9}
k=4 & & & & 1 & 10 & 65 &350 & 1701 \\ \cline{1-9}
k=5 & & & & & 1 & 15 & 140 & 1050 \\ \cline{1-9}
k=6 & & & & & & 1 & 21 & 266 \\ \cline{1-9}
k=7 & & & & & & & 1 & 28 \\ \cline{1-9}
k=8 & & & & & & & & 1 \\ \cline{1-9}
S(n) & 1 & 2 & 5 & 15 & 52 & 203 & 877 & 4140 \\ \cline{1-9}
\hline
\end{tabular}
Now, since we cannot use our edges of octagon originally, we should use PIE in order to exclude the sets using the edges.
Regardless of what edge we use, as we use one edge, we can just consider as one vertex disappearing. Thus, when we use $i$ edges of octagon, there are $S(8-i)$ ways to construct such set.
Hence, our answer is $4140-\binom{8}{1}\cdot 877 +\binom{8}{2}\cdot 203-\binom{8}{3}\cdot 52+\binom{8}{4}\cdot 15-\binom{8}{5}\cdot 5 +\binom{8}{6}\cdot 2 -\binom{8}{7}\cdot 1 +1=\boxed{715}$
I believe $S(n)$ implies number of ways to partition a set of $n$ elements. Because not using a certain vertex is also possible, I think you need to choose the certain set among the $k$sets that will not make a complete graph, but stay as vertexes. Since I know Dawon is pretty famous academy, which means the solution you suggested is reliable, I am positive that I am just confused and obsessed by a weird logic. Would you please help me understanding it?