Problem 314: The Mouse on the Moon

Detailed mathematical approach

Problem Summary

A country owns a \(500\) by \(500\) metre square of lunar ground with \(501^2=251001\) posts at \(1\) metre spacing, and keeps only the land it walls in. The wall must be a closed sequence of straight lines from post to post, and we maximise the enclosed area divided by the wall length. We call it \(\rho\); it is a length in metres. The statement gives three walls: the square, with \(\rho=250000/2000=125\); the inscribed circle, which the rules forbid, with \(\rho=\pi\cdot250^2/(\pi\cdot500)=125\) too; and the square with corner triangles of legs \(75\) cut off, of area \(238750\) and wall \(1400+300\sqrt2\) metres, so \(\rho=130.87469\ldots\), rounded there to \(130.87\). The answer wants eight decimals. ^[1]

The whole solution in one sentence: a best wall may be taken convex, and a wall symmetric about both mid-lines is fixed by a quarter of its boundary — a convex chain of lattice steps from the top midpoint to the right midpoint — so the best such quarter is found by a dynamic programme over the steps sorted by slope, run a few times with a price \(\lambda\) per metre of wall until the price equals the ratio it earns.

Mathematical Approach

1. Two walls that tie, and a family that beats them

The two reference walls that give \(125\) are no coincidence. Round the four corners by arcs of radius \(r\), \(0\le r\le250\): each corner loses a square of side \(r\) and regains a quarter disc, while the wall trades two straight pieces of length \(r\) for a quarter circle, so with \(s=500\)

$$\begin{aligned}A(r)&=s^2-(4-\pi)r^2,\\ P(r)&=4s-2(4-\pi)r.\end{aligned}$$

At \(r=0\) this is the square and at \(r=250\) the inscribed circle, and both ends give \(A/P=s/4=125\). In between the quotient is larger: the statement is inviting us to round the corners, not to cut them.

2. The wall may be assumed convex

Take the convex hull of the posts of any legal wall: for a finite planar set that hull is a convex polygon whose vertices belong to the set, so its boundary is a legal wall too. The region it enclosed lies inside the hull, so the area does not shrink, and the hull boundary is the shortest closed curve containing the wall, so the length does not grow. ^[2] So \(\rho\) does not decrease: an optimal wall may be taken convex, which also disposes of self-crossing walls.

3. One cut per corner: the best octagon

Cut all four corners by triangles with legs \(t\), as the statement does with \(t=75\). Writing \(c=8-4\sqrt2\),

$$A(t)=250000-2t^2,\qquad P(t)=2000-c\,t.$$

At a maximum of \(A/P\) the derivative vanishes, so \(A'P=AP'\), here \(cA=4tP\); dividing by \(P\) gives the identity

$$\rho=\frac{4t}{c}=\frac{t}{2-\sqrt2}.$$

Substituting \(A\) and \(P\) turns \(cA=4tP\) into \(2ct^2-16st+cs^2=0\), whose root in range is \(t^{*}=76.6664035\ldots\) with \(\rho=130.8777374\ldots\); the best octagon with posts for corners takes \(t=77\) and reaches \(130.87761512\). The statement's \(t=75\) was thus almost the best single cut per corner: polishing it buys \(0.003\), so something else is needed.

4. Rounded corners, and where the answer must lie

The same calculation for the family of Section 1 gives

$$\begin{aligned}(4-\pi)r^2-4sr+s^2&=0,\\ r^{*}&=\frac{s(2-\sqrt\pi)}{4-\pi}=132.5397260\ldots\end{aligned}$$

and this time the analogous identity is \(\rho=r\): the best quotient equals the radius of the corner arcs. A wall on posts cannot follow a circle but can zigzag close to one, so we expect an answer a little below \(132.54\) and well above the \(130.88\) of the octagons.

A weaker but proved bound confirms this. For a convex region of area \(A\) and perimeter \(P\), the Minkowski–Steiner formula gives the area of the points within distance \(r\) as \(A+Pr+\pi r^2\). ^[3] That set lies in the corresponding set for the square, of area \(s^2+4sr+\pi r^2\), so \(A+Pr\le s^2+4sr\); with \(r=\rho\) and \(P\rho=A\) that is \(2A\le s^2+4s\rho\). The isoperimetric inequality \(4\pi A\le P^2\) ^[4] with \(P=A/\rho\) gives \(A\ge4\pi\rho^2\), so \(8\pi\rho^2-4s\rho-s^2\le0\):

$$\rho\le\frac{s\left(1+\sqrt{1+2\pi}\right)}{4\pi}=147.1680980\ldots$$

5. Both mid-lines: the symmetric family

Put the centre of the square \(S\) at the origin, so the posts are the integer points of \([-250,250]^2\). Reflection in either mid-line maps posts to posts, so a legal convex wall \(K\) has a legal mirror image \(K'\). Their Minkowski sum \(K+K'\), the set of all sums of a point of each, is the convex polygon whose edges are those of \(K\) and \(K'\) merged by direction, so its perimeter is \(2P(K)\), and Brunn–Minkowski ^[5] gives \(\sqrt{A(K+K')}\ge2\sqrt{A(K)}\). The mirror-symmetric average \(M=\tfrac12(K+K')\) therefore has the perimeter of \(K\), at least its area, and lies in \(S\) since \(\tfrac12(S+S)=S\). Symmetrising about both mid-lines in turn thus costs nothing — except that the halvings move corners off the post grid, to half-metre points after the first and quarter-metre points after the second. So the argument covers walls free to turn there, not walls on the posts; for those it is a restriction of the search that we check by computation, and none of the squares checked below, up to \(150\) by \(150\), loses anything by it.

A wall of the family meets the positive \(y\)-axis at some \((0,h)\) and the positive \(x\)-axis at some \((w,0)\), and is described by its part in the first quadrant, a chain from \((0,h)\) to \((w,0)\). What it encloses there lies under that chain, so the whole area and wall are four times the chain's: the quarter has the same \(\rho\) as the wall.

6. The area and the length of one step

Write \(G=250\). As the wall is convex and symmetric about the \(x\)-axis, its upper boundary is the graph of a concave function, which the other symmetry makes even and so non-increasing on \([0,w]\). A step therefore leads from a post \((x,y)\) to \((x+u,y-v)\) with \(u,v\ge0\). The area under it is a trapezium with parallel sides \(y\) and \(y-v\) and width \(u\), and its length is the distance between its ends:

$$\Delta A=u\left(y-\frac v2\right),\qquad \Delta L=\sqrt{u^2+v^2}.$$

Summing over a chain gives its \(A\) and \(L\). Nothing is approximate: \(A\) is a multiple of \(\tfrac12\) and \(L\) a sum of square roots.

7. The chain reaches the side midpoints

Here the endpoints need not be guessed. Let a chain run from \((0,h)\) to \((w,0)\) with \(1\le w,h\le G\), not both \(G\); translate it by \((G-w,G-h)\), prepend the horizontal segment from \((0,G)\) and append the vertical one to \((G,0)\). The result is convex, on posts, and has

$$\begin{aligned}\tilde A&=A+G^2-wh,\\ \tilde L&=L+2G-w-h.\end{aligned}$$

The added area per added length is

$$\begin{aligned}q&=\frac{G^2-wh}{2G-w-h},\\ q-w&=\frac{(G-w)^2}{2G-w-h}\ge0,\end{aligned}$$

and likewise \(q\ge h\), so \(q\ge\max(w,h)\). The chain itself stays in the rectangle \([0,w]\times[0,h]\) and its ends are \(\sqrt{w^2+h^2}\) apart, so \(A\le wh\) and \(L\ge\sqrt{w^2+h^2}\), whence \(A/L\le\min(w,h)\lt q\). Attaching a piece whose own ratio beats the current one raises the ratio, so the best chain of the family runs from the top midpoint to the right midpoint, \(h=w=G\).

8. Primitive steps, and convexity as a sorting rule

If \(\gcd(u,v)=d\ge2\), the step passes through the \(d-1\) posts \((x+ku/d,\,y-kv/d)\), so it splits into \(d\) copies of \((u/d,-v/d)\) of the same total length and area. Only primitive steps, those with \(\gcd(u,v)=1\), are therefore needed, used as often as we like; the axis steps are primitive too. The number of primitive \((u,v)\) with \(1\le u,v\le G\) is \(2(\varphi(1)+\cdots+\varphi(G))-1\), with \(\varphi\) Euler's totient function; ^[6] at \(G=250\) they sum to \(19024\), so the list, with the two axis steps, has \(38049\) entries.

A convex chain is exactly one whose step slopes \(v/u\) never decrease, with \(0\) for a horizontal step and \(\infty\) for a vertical one; the mirror images then meet it convexly on the axes. Equal slopes may only sit next to each other, so a chain is nothing but a multiset of primitive steps with \(\sum u_i=\sum v_i=G\): the slopes force the order. There are about \(2.1\cdot10^{43}\) such multisets at \(G=250\), so they need a dynamic programme, not an enumeration.

9. A complete example: the \(4\) by \(4\) square

Take \(G=2\), a square of side \(4\) with \(25\) posts. The chains from \((0,2)\) to \((2,0)\) are the five multisets of primitive steps with \(\sum u_i=\sum v_i=2\), each evaluated by Section 6:

• \((1,0),(1,0),(0,1),(0,1)\): \(A=4\), \(L=4\), \(A/L=1\) — the whole square;
• \((1,0),(1,1),(0,1)\): \(A=3.5\), \(L=2+\sqrt2\), \(A/L=1.0251262658\ldots\);
• \((1,0),(1,2)\): \(A=3\), \(L=1+\sqrt5\), \(A/L=0.9270509831\ldots\);
• \((2,1),(0,1)\): \(A=3\), \(L=1+\sqrt5\), the same \(0.9270509831\ldots\);
• \((1,1),(1,1)\): \(A=2\), \(L=2\sqrt2\), \(A/L\approx0.7071067812\) — the diamond.

The winner is the second: mirroring its quarter cuts a triangle of legs \(1\) from each corner, leaving area \(16-2=14\) and wall \(8+4\sqrt2\), and \(14/(8+4\sqrt2)=3.5/(2+\sqrt2)\) is indeed the quarter's \(A/L\). An exhaustive search over all \(33041\) convex lattice polygons in that square finds nothing better.

10. Maximising a ratio: the price of a metre of wall

A dynamic programme adds things up, and \(A/L\) is not a sum. The standard repair is Dinkelbach's method for fractional programming. ^[7] For a price \(\lambda\) per metre put

$$F(\lambda)=\max_{c}\bigl(A(c)-\lambda L(c)\bigr),$$

the maximum over the finitely many chains \(c\). Each \(A(c)-\lambda L(c)\) is a strictly decreasing affine function of \(\lambda\), so \(F\) is convex, decreasing and piecewise linear. And \(A(c)-\lambda L(c)\ge0\) says exactly \(A(c)/L(c)\ge\lambda\), so \(F(\lambda)\ge0\) precisely when \(\lambda\le\rho^{*}\), the best ratio in the family; hence \(F(\rho^{*})=0\), and the sign of \(F\) says which side of \(\rho^{*}\) a price lies on.

That gives the algorithm. Let \(c\) attain \(F(\lambda)\) and put \(\lambda'=A(c)/L(c)\). Then

$$\lambda'-\lambda=\frac{F(\lambda)}{L(c)},$$

so \(\lambda'\gt\lambda\) exactly while \(F(\lambda)\gt0\), and \(\lambda'\le\rho^{*}\) always, being the ratio of an admissible chain. From any \(\lambda\le\rho^{*}\) the prices increase and stay below \(\rho^{*}\); from above, the first step lands at or below it. This is Newton's method on the convex \(F\), using its supporting line at the current price; as \(F\) has finitely many linear pieces the prices stop changing after finitely many rounds, and then \(F(\lambda)=0\), so \(\lambda=\rho^{*}\).

This also explains the \(\rho=r\) of Section 4: moving a free piece of boundary outwards gains area in proportion to its length and costs length in proportion to its curvature, so at the fair price the trade balances only where the boundary curves with radius \(\lambda\).

11. The dynamic programme for one price

Fix \(\lambda\). To start the chain at a corner, substitute \(j=G-y\): it then runs from \((0,0)\) to \((G,G)\), a step becomes \((x,j)\to(x+u,j+v)\), and

$$\Delta A=u\left(G-j-\frac v2\right).$$

Let \(D[x,j]\) be the largest \(A-\lambda L\) over convex chains from \((0,0)\) to \((x,j)\) using only the steps treated so far, with \(D[0,0]=0\) and all else unreachable. Take the primitive steps by increasing slope and, for each, apply

$$\begin{aligned}D[x+u,j+v]\gets\max\bigl(&D[x+u,j+v],\\ &D[x,j]+\Delta A-\lambda\Delta L\bigr)\end{aligned}$$

at every reachable state, in place and in the direction of the step. One number per state suffices: two chains reaching the same state at the same stage have the same continuations, each adding the same area and length to both, so the weaker may be dropped. A state just filled by the current step is a source again later in the same sweep, so a step may repeat any number of times — an unbounded knapsack sweep — while the slope order keeps the chain convex. After the last step \(D[G,G]\) is \(F(\lambda)\), and if the best chain's area and length travel with the score, the new price is read off.

How the Code Works

The C++ program ^[8] keeps the states in one flat array addressed by idx(x, y) = x * DIM + y, GRID = 250 and DIM = GRID + 1. build_vectors builds the step list of Section 8: \((1,0)\) with slope \(0\), every \((u,v)\) with \(1\le u,v\le250\) and std::gcd(u, v) == 1 with its length and slope \(v/u\), and \((0,1)\) with the stand-in slope 1e100; sorting by slope leaves the \(38049\) steps counted above.

solve_for_lambda is the sweep of Section 11. Three arrays score, area and length of \(251^2\) doubles are refilled at each call, score with the sentinel kNeg except at the start state. For a step \((u,v)\) it precomputes base_area = u * (GRID - 0.5 * v), which is \(\Delta A\) at \(j=0\), and base_score = base_area - lambda * len, then walks the source rows \(i\le250-u\) and, inside each, \(j\le250-v\), subtracting \(u\) from area_gain and score_gain after every \(j\): that is the \(-ju\) of \(u(G-j-v/2)\), so the inner loop multiplies nothing, and row pointers spare it the row offsets. A target is overwritten when the candidate beats the stored score by more than kEps, taking its area and length from the source plus the step's contributions — that is how the best chain's \(A\) and \(L\) reach the end state. As rows and \(j\) both run upwards, the in-place repetition works for every step.

main starts from lambda = 132.0 — a guess, as Section 10 shows any positive start converges — runs at most \(40\) rounds, each time setting lambda to res.area / res.len at the end state, and stops when the price moves by less than \(10^{-12}\) or the score is within \(10^{-11}\) of zero; it prints with std::fixed and setprecision(8). Section 10 proves convergence for exact fixed-price maxima, which these are not: the program works in floating point and ignores gains of at most kEps, so its stopping tests are numerical rather than certified, and had all \(40\) rounds been used it would print the last price silently.

The Java version mirrors it: an explicit gcd loop, Double.compare on the slope, the same three flat double[] arrays, and String.format(Locale.US, "%.8f", …) so the decimal separator is fixed. It adds a rowMax array of the best score per row and skips a source row while that row is unreachable, which cannot change the result: a row is marked exactly when one of its states is written. The Python file is not a second implementation but a bridge: it compiles the C++ source with clang++ or g++ at -O2 into a cached binary, reusing it unless that source is newer, runs it and reads the value with parse_output. None of the three needs big integers: coordinates, step components and indices are ordinary ints, the areas, lengths, slopes, scores and prices doubles.

Complexity and Verification

One call of solve_for_lambda touches \((G+1-u)(G+1-v)\) states per step \((u,v)\), exactly \(603\,301\,000\) inner-loop updates: the step list has \(\Theta(G^2)\) entries, each sweeping \(O(G^2)\) states, so one price costs \(O(G^4)\) time, here \(0.154\,G^4\). Building and sorting the list is a once-only \(O(G^2\log G)\), and the arrays need \(3\cdot251^2\) doubles, some \(1.5\) MB. The outer loop takes three rounds from the built-in price, four or five from distant ones: \(1.1\) seconds in C++, \(3.1\) in Java on the machine used here. The list is more generous than needed: the \(85\) steps with \(\max(u,v)\le11\), and \(5.1\) million updates, already give the same eight decimals; \(\max(u,v)\le8\) does not.

The following was checked for this article. The statement's three reference values follow from the formulas of Sections 1 and 3, and Section 9's five chains were enumerated by hand and by machine alike. Section 7's extension was checked on all \(648\) chains with endpoints between \(1\) and \(G\) for \(G\le5\), and at full size the programme with free endpoints returns the chain through the midpoints. An exhaustive enumeration of every convex lattice polygon in a small square (\(33041\) for side \(4\), \(3\,300\,820\) for side \(6\)) gives the same optimum as a second, unrestricted dynamic programme that assumes no symmetry; and that programme agrees with the symmetric quarter-chain one for every even side up to \(16\) and for \(20,24,30,40,100\) and \(150\). The prices \(0.5,50,125,140,200\) and \(1000\) all converge to the same eight decimals, as does a rerun in \(80\)-bit arithmetic with the identical chain. The C++ and Java programs print the same line, which the Python bridge reproduces by running the C++ one.

The winning quarter is worth a look: \(286\) primitive steps in \(29\) maximal edges and \(29\) directions, all with \(\max(u,v)\le11\) — a horizontal run of \(122\) metres from \((0,250)\), then \(27\) short edges turning the corner from \((122,250)\) to \((250,122)\), then \(122\) metres straight down to \((250,0)\). The multiset of those \(27\) edges is unchanged when each step \((u,v)\) becomes \((v,u)\), so the winner is symmetric about the diagonals too, though the search never asked that. The whole wall is a strictly convex lattice polygon with \(112\) corners and four straight sides of \(244\) metres, and its corner edges stay between the distances \(125.88\) and \(128\) from \((122,122)\): the rounded shape of Section 4, though not its stationary radius \(r^{*}\). Rebuilding that polygon and recomputing its area by the shoelace formula and its perimeter from the \(112\) sides reproduces the printed value — an independent check of the bookkeeping.

Footnotes and References

The references below supply the background facts used above. The convexity reduction, the step formulas, the two identities for \(\rho\), the endpoint argument of Section 7, the bound of Section 4 and the convergence proof of Section 10 are derived explicitly here; the double-symmetry reduction is proved only for walls free to leave the post grid and is otherwise a tested restriction of the search.

1. Project Euler 314 — The Mouse on the Moon. The official statement gives every country a 500 m by 500 m square with 251001 posts at 1 m spacing, requires the wall to be a closed series of straight lines from post to post, and asks for the largest enclosed-area/wall-length ratio to eight decimal places. It supplies the three reference walls quoted above, of ratios 125, 125 and 130.87.
2. Wikipedia — Convex hull. The hull lies in every convex set containing the given set; for a finite planar point set it is a convex polygon whose extreme points belong to the set; and for a bounded planar set its boundary is the simple closed curve of minimum perimeter containing it. Section 2 uses all three.
3. Wikipedia — Minkowski–Steiner formula. For a convex compact set the measure of the parallel body at distance δ is a polynomial in δ whose coefficients are the measure, the boundary measure and the unit ball volume; in the plane, area + perimeter · δ + πδ², the form used in Section 4.
4. Wikipedia — Isoperimetric inequality. A closed plane curve of length L encloses at most the area L²/(4π), with equality only for a circle; Section 4 uses it as 4πA ≤ P².
5. Wikipedia — Brunn–Minkowski theorem. For non-empty compact sets in n dimensions, the nth root of the measure of A + B is at least the sum of the nth roots of those of A and B; in the plane the square root of the area is superadditive under Minkowski addition, as Section 5 needs.
6. OEIS A018805. The number of pairs (x, y) with 1 ≤ x, y ≤ n and gcd(x, y) = 1 is 2(φ(1) + ⋯ + φ(n)) − 1, also the sum of μ(k)⌊n/k⌋², and asymptotically 6n²/π²; Section 8 uses the totient form at n = 250.
7. W. Dinkelbach, On Nonlinear Fractional Programming, Management Science 13(7), 1967, 492–498. The paper gives the algorithm that maximises a ratio by solving the parametric problem for a fixed parameter and then updating it, resting on Jagannathan's theorem linking fractional and parametric programming; Section 10 proves what the method needs here.
8. C++ — Euler314.cpp. The linked immutable revision, byte for byte the published file, holds build_vectors, solve_for_lambda and the loop over prices. It is the implementation record for this article; the exhaustive and unrestricted searches above were written separately.