Solution

Answer: 123/59

Let

$A_i$ = number supplied by supplier A for product $i$,
$B_i$ = number supplied by supplier B,
$a_i$ = spoiled items for A,
$b_i$ = spoiled items for B.

The table is:

$$\begin{array}{c|cc} & A & B\\hline 1 & 5248 & 640\ 2 & 1312 & 1888\ 3 & 2624 & 3776\ 4 & 5760 & 3776\ 5 & 3936 & 5664 \end{array}$$

Define the common factor $m>1$ such that every per-product spoilage rate for B is worse than A by factor $m$:

$$\frac{b_i}{B_i}=m\frac{a_i}{A_i}$$

and simultaneously the overall spoilage rate for A is worse than B by the same factor:

$$\frac{\sum a_i}{\sum A_i} = m\frac{\sum b_i}{\sum B_i}.$$

We must find the largest possible rational value of $m$.

1. Mathematical analysis

From

$$\frac{b_i}{B_i}=m\frac{a_i}{A_i},$$

we obtain

$$b_iA_i = m,a_iB_i.$$

Write

$$m=\frac{u}{v}$$

in lowest terms. Then

$$v,b_iA_i = u,a_iB_i.$$

For integer solutions, define

$$g_i=\gcd(uB_i,;vA_i).$$

Then the general integer solution is

$$a_i=\frac{vA_i}{g_i}k_i,\qquad b_i=\frac{uB_i}{g_i}k_i,$$

for positive integers $k_i$.

The overall condition is

$$\frac{\sum a_i}{\sum A_i} = \frac{u}{v}\frac{\sum b_i}{\sum B_i}.$$

Since

$$\sum A_i = 18880,\qquad \sum B_i = 15744,$$

substituting the formulas for $a_i,b_i$ gives

$$15744,v^2 \sum_i \frac{A_i}{g_i}k_i = 18880,u^2 \sum_i \frac{B_i}{g_i}k_i.$$

Equivalently,

$$\sum_i \left( 15744,v^2\frac{A_i}{g_i} - 18880,u^2\frac{B_i}{g_i} \right)k_i =0.$$

So for each candidate reduced fraction $u/v$, we only need to determine whether there exist positive integers $k_i$ satisfying this linear equation and the bounds

$$1\le k_i \le \frac{g_i}{u}.$$

Bounding $m$

The product ratios are

$$\frac{B_i}{A_i}= \left( \frac5{41}, \frac{59}{41}, \frac{59}{41}, \frac{59}{90}, \frac{59}{41} \right).$$

From the overall equation,

$$m^2 = \frac{\sum B_i}{\sum A_i} \cdot \frac{\sum a_i}{\sum a_i(B_i/A_i)}.$$

Since the weighted average of $B_i/A_i$ lies strictly above the minimum $5/41$,

$$m^2 < \frac{246/295}{5/41} = \frac{10086}{1475},$$

hence

$$m<2.615.$$

This gives a finite search.

2. Python implementation

from fractions import Fraction
from math import gcd

A = [5248, 1312, 2624, 5760, 3936]
B = [640, 1888, 3776, 3776, 5664]

SA = sum(A)   # 18880
SB = sum(B)   # 15744

values = set()
best = Fraction(0, 1)

# m < sqrt(10086/1475) < 2.615
LIMIT = 2.615

for v in range(1, 5000):

    max_u = int(LIMIT * v) + 2

    for u in range(v + 1, max_u):

        # reduced fraction only
        if gcd(u, v) != 1:
            continue

        # g_i = gcd(u*B_i, v*A_i)
        g = [gcd(u * B[i], v * A[i]) for i in range(5)]

        # need k_i >= 1 and k_i <= g_i/u
        max_k = [gi // u for gi in g]

        if min(max_k) < 1:
            continue

        # coefficients of the linear equation
        coeff = [
            SB * v * v * A[i] // g[i]
            - SA * u * u * B[i] // g[i]
            for i in range(5)
        ]

        # Meet-in-the-middle search for:
        # sum(coeff[i] * k_i) = 0

        left = set()

        for k1 in range(1, max_k[0] + 1):
            for k2 in range(1, max_k[1] + 1):
                left.add(coeff[0] * k1 + coeff[1] * k2)

        found = False

        for k3 in range(1, max_k[2] + 1):
            for k4 in range(1, max_k[3] + 1):

                partial = coeff[2] * k3 + coeff[3] * k4

                for k5 in range(1, max_k[4] + 1):

                    if -(partial + coeff[4] * k5) in left:
                        found = True
                        break

                if found:
                    break

            if found:
                break

        if found:
            m = Fraction(u, v)
            values.add(m)

            if m > best:
                best = m

print(len(values))
print(best)

3. Code walkthrough

Step 1

We loop through all reduced fractions

$$m=\frac{u}{v}$$

with $1<m<2.615$.

Step 2

For each product:

g = gcd(u * B[i], v * A[i])

This produces the general integer solution

$$a_i=\frac{vA_i}{g_i}k_i,\qquad b_i=\frac{uB_i}{g_i}k_i.$$

Step 3

We derive the linear constraint from the overall spoilage condition.

The coefficients are:

coeff[i] =
SB * v^2 * A[i] / g[i]
-
SA * u^2 * B[i] / g[i]

and we search for positive integers $k_i$ satisfying

$$\sum coeff_i,k_i = 0.$$

Step 4

A meet-in-the-middle search makes the computation fast.

The program finds exactly:

35
123/59

matching the statement that there are exactly 35 possible values.

4. Final verification

We obtained

$$m=\frac{123}{59}\approx 2.08474576.$$

This is safely below the theoretical upper bound $2.615$, and the program confirms:

exactly 35 valid values of $m$,
largest value $=123/59$.

So the computation is consistent with every condition in the problem.

Answer: 123/59

Project Euler Problem 236