MathDB

2

Part of 2015 Japan MO Finals

Problems(1)

moving pieces in hexagonal grid

Source: 2015 Japan MO Finals p2

10/22/2022
Let nn be an integer greater than or equal to 22. There is a regular hexagon ABCDEFABCDEF with side length nn, which is divided into equilateral triangles with side length 11 as shown in the left figure. We simply call the vertices of an equilateral triangle as vertex. A piece is placed in the center of a regular hexagon ABCDEFABCDEF. For each of the vertices PP inside ABCDEFABCDEF (not including the perimeter), an arrow is drawn toward 44 vertices four of the six vertices connected to PP by an edge of length 11. When a piece is placed on the vertex PP, this piece can be moved to any of the four vertices which the arrow is drawn. Regarding side PQPQ, even if a piece can be moved from vertex PP to vertex QQ, it is not necessarily possible to move a piece from vertex QQ to vertex PP. Then, show that there exists an integer kk such that it can be moved the piece to vertices on the perimeter of the regular hexagon ABCDEFABCDEF in kk moves regardless of how the arrows are drawn and find the smallest possible value of kk.
[asy] unitsize(0.3 cm);
pair[] A, B, C, D, E, F; int i; pair trans = (18,-4);
A[0] = 8*dir(120); B[0] = 8*dir(180); C[0] = 8*dir(240); D[0] = 8*dir(300); E[0] = 8*dir(0); F[0] = 8*dir(60);
for (i = 1; i <= 7; ++i) { A = interp(A[0],B[0],i/8); B = interp(B[0],C[0],i/8); C = interp(C[0],D[0],i/8); D = interp(D[0],E[0],i/8); E = interp(E[0],F[0],i/8); F = interp(F[0],A[0],i/8); }
draw(A[0]--B[0]--C[0]--D[0]--E[0]--F[0]--cycle);
for (i = 0; i <= 5; ++i) { draw(rotate(60*i)*(A[0]--(A[0] + 3*dir(-60)))); draw(rotate(60*i)*(A[1]--(A[1] + 3*(1,0)))); draw(rotate(60*i)*(A[1]--(A[1] + 3*dir(300)))); draw(rotate(60*i)*(A[2]--(A[2] + 4*(1,0)))); draw(rotate(60*i)*(F[6]--(F[6] + 4*dir(240)))); draw(rotate(60*i)*(F[7]--(F[7] + 3*dir(240)))); draw(rotate(60*i)*(F[7]--(F[7] + 3*dir(300)))); draw(rotate(60*i)*((A[1] + 3*(1,0))--(A[1] + 6*(1,0))), dotted); draw(rotate(60*i)*((A[2] + 4*(1,0))--(A[2] + 6*(1,0))), dotted); }
for (i = 0; i <= 2; ++i) { draw(rotate(60*i)*(3*dir(60)--3*dir(240))); }
for (i = 0; i <= 5; ++i) { draw(rotate(60*i)*(((2,0) + dir(60))--((-2,0) + dir(120)))); draw(rotate(60*i)*((3,0)--(5,0)), dotted); draw(rotate(60*i)*(((2,0) + dir(60))--((4,0) + dir(60))), dotted); draw(rotate(60*i)*(((2,0) + dir(-60))--((4,0) + dir(-60))), dotted); }
label("AA", A[0], NW); label("BB", B[0], W); label("CC", C[0], SW); label("DD", D[0], SE); label("EE", E[0], dir(0)); label("FF", F[0], NE);
draw(shift(trans)*scale(1.3)*((-3,0)--(9,0))); draw(shift(trans)*scale(1.3)*((-3*dir(60))--(9*dir(60)))); draw(shift(trans)*scale(1.3)*(((6,0) + 3*dir(-60))--((6,0) + 9*dir(120)))); draw(shift(trans)*scale(1.3)*(3*dir(120)--3*dir(300))); draw(shift(trans)*scale(1.3)*((6*dir(60) + (-3,0))--(6*dir(60) + (3,0)))); draw(shift(trans)*scale(1.3)*(((6,0) + 3*dir(60))--((6,0) - 3*dir(60)))); draw(shift(trans)*scale(1.3)*((-2,0)--(2,0)), linewidth(1.5*bp), Arrows(4)); draw(shift(trans)*scale(1.3)*(2*dir(60)--2*dir(240)), linewidth(1.5*bp), Arrows(4)); draw(shift(trans)*scale(1.3)*((6,0)--(8,0)), linewidth(1.5*bp), Arrow(4)); draw(shift(trans)*scale(1.3)*((6,0)--((6,0) + 2*dir(60))), linewidth(1.5*bp), Arrow(4)); draw(shift(trans)*scale(1.3)*((6,0)--((6,0) + 2*dir(240))), linewidth(1.5*bp), Arrow(4)); draw(shift(trans)*scale(1.3)*((6,0)--((6,0) + 2*dir(300))), linewidth(1.5*bp), Arrow(4)); draw(shift(trans)*scale(1.3)*(6*dir(60)--(6*dir(60) + (2,0))), linewidth(1.5*bp), Arrow(4)); draw(shift(trans)*scale(1.3)*(6*dir(60)--(6*dir(60) + 2*dir(120))), linewidth(1.5*bp), Arrow(4)); draw(shift(trans)*scale(1.3)*(6*dir(60)--(6*dir(60) + (-2,0))), linewidth(1.5*bp), Arrow(4)); draw(shift(trans)*scale(1.3)*(6*dir(60)--(6*dir(60) + 2*dir(240))), linewidth(1.5*bp), Arrow(4)); [/asy]
combinatorics