2018년 3월 교육청 나형 21번은 [대수학]의 cycle가 포함되어 있었다.
이것은 동영상 주소 고요
Problem
Adam, Benin, Chiang, Deshawn, Esther, and Fiona have internet accounts. Some, but not all, of them are internet friends with each other, and none of them has an internet friend outside this group. Each of them has the same number of internet friends. In how many different ways can this happen?
Solution
Note that if is the number of friends each person has, then
can be any integer from
to
, inclusive.
Also note that one person can only have at most 5 friends.
Also note that the cases of and
are the same, since a map showing a solution for
can correspond one-to-one with a map of a solution for
by simply making every pair of friends non-friends and vice versa. The same can be said of configurations with
when compared to configurations of
. Thus, we have two cases to examine,
and
, and we count each of these combinations twice.
For , if everyone has exactly one friend, that means there must be
pairs of friends, with no other interconnections. The first person has
choices for a friend. There are
people left. The next person has
choices for a friend. There are two people left, and these remaining two must be friends. Thus, there are
configurations with
.
For , there are two possibilities. The group of
can be split into two groups of
, with each group creating a friendship triangle. The first person has
ways to pick two friends from the other five, while the other three are forced together. Thus, there are
triangular configurations.
However, the group can also form a friendship hexagon, with each person sitting on a vertex, and each side representing the two friends that person has. The first person may be seated anywhere on the hexagon without loss of generality. This person has choices for the two friends on the adjoining vertices. Each of the three remaining people can be seated "across" from one of the original three people, forming a different configuration. Thus, there are
hexagonal configurations, and in total
configurations for
.
As stated before, has
configurations, and
has
configurations. This gives a total of
configurations, which is option
.
Note
We can also calculate the triangular configurations by applying (Because choosing
,
and
is the same as choosing
,
and
.
For the hexagonal configurations, we know that the total amount of combinations is . However, we must subtract the number of cases for rotation and reflection.
~Zeric Hang
관련된 미국 문제도 올립니다.[실제로 미국에서 출제된 문제 랍니다.]