(a) Let's assign to each lattice point $P$ the number $f(P)$ which is the sum of the distances from $P$ to the $n$ constant vertices. We will use a few lemmas to solve this problem. Lemma 1. If $ABCD$ is a rhombus of side length $1$, where $A, B, C, D$ are lattice points so that $\angle BAC = \angle BDC = 60$, then we have $f(A) + f(C) \ge f(B) + f(D).$ Proof . It suffices to show this when there is only one $A_i$, then sum over all $A_i$'s. This is not hard to show by casework on where the $A_i$ is. $\blacksquare$ Lemma 2. If $A, B, C$ are three collinear lattice points so that $AB = BC = 1$, then $f(A) + f(C) \ge 2 f(B).$ Proof. This is proven in the same way as Lemma $1.$ $\blacksquare$ Lemma 3. If $ABCD$ is a parallelogram so that $A, B, C, D$ are lattice points, its sides are parallel to the gridlines of the triangular lattice, and $\angle BAC = 60$, then we have $f(A) + f(C) \ge f(B) + f(D).$ Proof. Sum Lemma $1$ over all "sub-rhombi" of $ABCD$ which have parallel sides to $ABCD$ and are of length $1.$All interior points and lattice points on the perimeter of $ABCD$ appear an equal number of times on either side of the $\ge$ sign, except for $A, C$ which appear once each to the left of the $\ge$ sign, and $B, D$ which appear once each to the right of the $\ge $sign. This implies the lemma. $\blacksquare$ Lemma 4. If $A, B, C, D$ are four lattice points so that $AD = t, AB = 1, BC = t-1, CD = t-1$ for some $t \ge 3$ and $AD$ lies entirely on some gridline, then $f(A) + f(D) \ge f(B) + f(C).$ Proof. Our strategy will be to use Lemma $2$ repeatedly. Let's label the lattice points on $AD$ $P_0, P_1, \cdots, P_t$ in the obvious manner, with $A = P_0$ and $D = P_t.$ Notice that by Lemma $2$ we have: $$f(P_0) - f(P_1) \ge f(P_1) - f(P_2) \ge f(P_2) - f(P_3) \ge \cdots \ge f(P_{t-1}) - f(P_t).$$ This implies the lemma. $\blacksquare$ From here, we're ready to solve the problem. Suppose that our process ended at $A$, where $f(A)$ is less than or equal to $f$ of all its neighbors. Assume that $A$ is not the point where $f(A)$ is minimized, for contradiction. Let $B$ be the point closest to $A$ such that $f(B)$ (where "closeness" is measured in any sensible manner). We consider two cases. Case 1. $AB$ lies on a gridline. Then, since $AB$ is clearly not $1$, we can consider points $C, D$ on segment $AB$ so that $AC = DB = 1.$ Then Lemma $4$ implies that $2 f(A) > f(A) + f(B) \ge f(C) + f(D)$, and so one of $f(C), f(D) < f(A).$ But $C, D$ are both closer to $A$ than $B$, contradiction. Case 2. $AB$ doesn't lie on a gridline. Then, there are points $C, D$ so that $ACBD$ is a parallelogram with $\angle CAD = \angle CBD = 60.$ Lemma $3$ then implies that $f(C) + f(D) \le f(A) + f(B) < 2f(A)$, so one of $f(C), f(D) < f(A).$ But $C, D$ are both closer to $A$ than $B$, contradiction. As we've derived a contradiction in all cases, the problem is finished. $\square$ (b) No, we can construct a counterexample as follows. Our vertices will be $P_1, P_2, A_1, A_2, A_3, A_4, A_5, B_1, B_2, B_3, B_4, B_5.$ Start by connecting $P_2$ to all the $B_i$'s and $P_1$ to all the $A_i$'s. Now, for each $1 \le i \le 5$, connect $A_i$ to $B_i.$ Let $B_1, B_2, \cdots, B_5$ be the five constant points. Define $f$ similarly as in part (a). Then we have that $f(P_1) = 10$, $f(P_2) = 5$, $f(A_i) = 13$, and $f(B_i) = 8$ for all $1 \le i \le 5.$ If we begin our algorithm at $P_1$, then since all neighbors of $P_1$ have larger $f$ value (they all have $13$), our algorithm will tell us that $A$ is the global minimum of $f.$ However, that's actually $B$, which attains $5.$ $\square$

In the following triangular lattice distance of two vertices is length of the shortest path between them. Let $ A_{1},A_{2},\dots,A_{n}$ be constant vertices of the lattice. We want to find a vertex in the lattice whose sum of distances from vertices is minimum. We start from an arbitrary vertex. At each step we check all six neighbors and if sum of distances from vertices of one of the neighbors is less than sum of distances from vertices at the moment we go to that neighbor. If we have more than one choice we choose arbitrarily, as seen in the attached picture. Obviusly the algorithm finishes a) Prove that when we can not make any move we have reached to the problem's answer. b) Does this algorithm reach to answer for each connected graph?