Project Euler Problem 768

Solution

Let the 360 candleholders correspond to the 360th roots of unity.

A configuration is perfectly balanced iff the vector sum of the chosen roots is zero.

Write the chosen set as a vanishing sum of distinct 360th roots of unity.

Because

$$360 = 2^3\cdot 3^2\cdot 5$$

and the number of candles is $20$, which is not divisible by 3, the Lam–Leung classification of vanishing sums implies that every balanced configuration must decompose into disjoint unions of:

antipodal pairs (size $2$), and/or
regular pentagons (size $5$).

No other primitive vanishing configurations can occur.

Define the regular pentagons

$$P_r={r,r+72,r+144,r+216,r+288} \qquad (0\le r<72).$$

Notice:

$P_r$ and $P_{r+36}$ are opposite pentagons.
Together they form a “decagon block” containing 10 vertices.
Inside one block there are exactly 5 antipodal pairs.

So the 360 vertices split into $36$ independent blocks.

For one block, the possible balanced selections are:

choose $k$ antipodal pairs ($0\le k\le 4$):

$$\binom{5}{k}x^{2k}$$

choose one pentagon:

$$2x^5$$

choose the whole decagon:

$$x^{10}$$

(Choosing all 5 antipodal pairs gives the same set as choosing both opposite pentagons, so it must be counted only once.)

Hence the generating polynomial for one block is

$$F(x)=1+5x^2+10x^4+2x^5+10x^6+5x^8+x^{10}.$$

Since the 36 blocks are independent,

$$f(360,20)=[x^{20}]F(x)^{36}.$$

Python code:

from collections import defaultdict

# generating polynomial for one 10-vertex block
F = {
    0: 1,
    2: 5,
    4: 10,
    5: 2,
    6: 10,
    8: 5,
    10: 1
}

# DP for coefficient extraction
dp = {0: 1}

for _ in range(36):
    nd = defaultdict(int)

    for a, va in dp.items():
        for b, vb in F.items():
            if a + b <= 20:
                nd[a + b] += va * vb

    dp = nd

print(dp[20])

This produces

$$7631085872322540.$$

Checks:

For $f(12,4)$, the same method gives $15$.
For $f(36,6)$, it gives $876$.

Both match the problem statement.

Therefore,

Answer: 7631085872322540