폴리매스

어느 부분에서 문제를 잘못 이해했다고 생각하셨는지 더 말씀해주실 수 있나요? 5 이상의 n에 대하여 을 구하는 것이 문제입니다!

그리고 순환그래프는 정다각형 그래프가 맞습니다! 다른 질문 있으시면 댓글 부탁드릴게요^^

다인 멘토 드림

저는 5이상에서도 계속 5가 나오는데요..?

그니까 육각형을 예로 들자면 한 변으로부터 인접한 두 변과 그 변과 연결되어있는 두 변, 총 5개인 것 같아요

5일 때는 5 맞고 6이상일 때는 임의의 두 원소에 대해서 거리가 2 이상이면 안 되므로 3 맞는듯요.

6 이상일 때 w(Cn) 값이 4 이상이면 반드시 거리가 2 이상인 두 변이 생기거든요.

@Scubed

정육각형을 예로 들자면

서로 마주보는 면은 가까운 면이 아니니

기껏해야 한 면 + 꼭짓점으로 맞닿아 있는 두 면 해서 w(C_6)이 3이 나오는 것 같습니다

좀 더 엄밀하게 이야기해 보겠습니다.

n = 5일 때는 C5 전체가 가까운 변의 집합이므로 답은 5입니다.

n >= 6일 때 연속한 3개를 잡아보면 이는 가까운 변의 집합입니다. 이것이 최댓값임을 보이기 위해 w(Cn)의 값이 4 이상인 집합 S가 존재한다고 가정해봅시다. 고립된 변이 있으면 가까운 변의 집합일 수 없으며, Cn은 정다각형 그래프이므로 집합 S는 일직선 형태일 것입니다. 이때, 집합 S의 모든 변을 일직선 순서대로 E1, E2, E3, E4, ...라고 합시다.

E1, E4의 거리는 두 방향에서 잴 수 있는데, 그 길이는 2와 n-4입니다. 그런데 이 두 수는 모두 2 이상이므로 가까운 변의 집합이 될 수 없습니다. 따라서 w(Cn)의 값은 4 이상일 수 없으며, 답은 3입니다.

답 : n = 5이면 5, n >= 6이면 3

@222

고렇네요 제가 실수했네요 ㅠㅠ

책은 저는 딱히 못 봤고 그냥 이런 문제들을 계속 풀어볼려고 노력하면서 좀 더 가까워진 거 같아요

그래프에서 한 점에 연결된 변의 수를 차수라고 하는데, 모든 점에 대해서 가장 높은 차수를 최고차수라고 합니다.

예시로 문제에 나와있는 그래프에서는 차수는 2,2,2,2,3,3이고 최고차수는 3이 되겠지요.

으아닛! 감사합니다! 이미 진리를 찾아서님은 진리를 찾으신 것 같군요!

잘 풀었습니다!

우아아ㅏ아아아아아ㅏ아아아아아아아ㅏ아아아아아아

대한수학회 문제푼거 첨이에요!!!

감사합니다 멘토님!!

제 생각에는 아마 n을 제곱하라는 것 같습니다. 왜냐하면 그래프를 제곱한다는 말은..들어본 적이 없거든요.

오오 그럼 저 이 문제에대해서 감 잡았는데 이 문제에 대하여 같이 토론하고 풀어보실래요??

오 그럽시다

오 밑에 새로운 댓글 달았어요 거기서 한번 이 문제 자체를 같이 푸러봅시다

+추가로 이 문제는 한붓그리기와 연관이 있는 것 같습니다. 확실합니다!

@진리를 찾아서

잘 푸셨습니다.

다음과 같은 방법으로 서술할 수도 있습니다.

let n = 2m

다음과 같은 그래프 G를 잡자.

V(G)={(a,b) : 1 <= a <= m, 1<= b <= 5}

E(G)={{(a,b),(c,d)} : b-d가 mod5로 1 or -1}

let f(v) = v의 두 번째 index in mod5.

각각의 점은 f(v)값이 1 차이나는 점과 연결되고 차수 2n.

한편, {v1,v2}, {v3,v4}가 이웃하지 않다면 v1,v2는 v3,v4와 연결되지 않고 일반성을 잃지 않고 f(v1)=0, f(v2)=1일 때, f(v3)=f(v4)=3이고 모순.

따라서 모든 변이 이웃하고 w(G)=|E(G)|=5m^2

와!!! 축하드려요!!! 다음엔 시간 날 때 같이 문제 풀어봐요!!!

유태영 멘토님, pure math님 모두 감사합니다!