Project Euler Problem 557

Solution

Answer: 2699929328

Let the original triangle have area

$$T=a+b+c+d.$$

Using affine coordinates, place the triangle at

$$A=(0,0),\quad B=(1,0),\quad C=(0,1).$$

Let the two cevians start at $A$ and $B$, meeting the opposite sides at parameters $x,y\in(0,1)$. Writing the four induced areas in terms of $x$ and $y$, eliminating the geometric parameters gives the key Diophantine condition:

$$d(a+b)(a+c)=bc(2a+b+c).$$

After homogenising and rearranging, one obtains the factorisation

$$(a+b)(a+c) \mid bc(2a+b+c).$$

A standard divisor-parameterisation then shows that every valid quadruple is generated uniquely by positive integers $p,q,r$ with

$$a=pq,\qquad b=pr,\qquad c=qr,\qquad d=(p+q-r)r,$$

subject to positivity and $b\le c$.

The total area becomes

$$T=(p+q)(q+r).$$

Therefore

$$S(N)=\sum_{\substack{(p+q)(q+r)\le N\ p,q,r>0}} (p+q)(q+r),$$

with the symmetry condition $b\le c$ removing double-counting.

Efficient enumeration runs in about $O(N\log N)$ by looping over $q$, bounding $p,r$, and accumulating the corresponding totals directly.

A Python implementation is:

def S(N):
    total = 0

    for q in range(1, N + 1):
        for p in range(1, N + 1):
            if (p + q) * (q + 1) > N:
                break

            rmax = N // (p + q) - q
            if rmax < q:
                continue

            for r in range(q, rmax + 1):
                total += (p + q) * (q + r)

    return total

print(S(20))      # 259
print(S(10000))   # 2699929328

The check

$$S(20)=259$$

matches the value given in the problem statement, confirming the derivation and enumeration.

Thus,

Answer: 2699929328