$n$을 2 이상의 정수라 하자. 한 변의 길이가 $n$인 정육각형 $ABCDEF$가 있어, 왼쪽 그림처럼 한 변의 길이가 1인 정삼각형들로 분할되어 있다. 정삼각형의 꼭지점들을 이 도형의 꼭지점이라 부르자.

정육각형 $ABCDEF$의 중심에 말이 놓여져있다. 오른쪽 그림처럼 정육각형 $ABCDEF$의 내부(둘레를 포함하지 않는다)에 있는 꼭지점 $P$ 각각에 대해, $P$와 길이 1인 변으로 연결되어있는 6개의 꼭지점들 중 4개의 꼭지점을 향해 화살표가 그려져 있어, 꼭지점 $P$에 말이 놓여져있을 때 그 4방향 중 한 방향으로 말을 움직이는 것이 가능하다. 단, 길이 1인 변 $PQ$에 대해, 꼭지점 $P$에서 꼭지점 $Q$로 말을 움직이는 것이 가능하더라도 꼭지점 $Q$에서 꼭지점 $P$로 말을 움직이는 것이 항상 가능한 것은 아니다.
이 때, 어떻게 화살표가 그려져있다 하더라도 말을 최대 $k$번 움직여서 정육각형 $ABCDEF$의 둘레 위의 꼭지점에 도착하게 하는 것이 가능한 정수 $k$가 존재함을 보이고, 그러한 $k$의 최솟값을 구하여라.