Apples, Oranges, Pears Riddle

I used Python to test out a bunch of cases until I found an answer that worked. I'm hoping someone else has a better method! However, I was able to reduce the number of cases to test by applying the requirements of the problem to the iteration sequence and by introducing a requirement of my own. To begin, the unknowns are the following:

• The 3 prices ( $c_o$ for oranges, $c_a$ for apples, and $c_p$ for pears, in pennies)
• The 3 amounts of fruit that each of the 3 ladies bought ( $n_{ij}$ , with $i$ denoting the lady and $j$ denoting the fruit)

The strategy is to try all possible permutations of $n_{ij}$ and solve for $c_o$ , $c_a$ , and $c_p$ , then determine whether the resulting prices meet the requirements in each case. There are 3 unknowns and 3 equations in each case, so we can solve for the prices using the following system of equations:

$\begin{cases} n_{1o}c_o+n_{1a}c_a+n_{1p}c_p=241\\ n_{2o}c_o+n_{2a}c_a+n_{2p}c_p=241\\ n_{3o}c_o+n_{3a}c_a+n_{3p}c_p=241 \end{cases}$

There are 9!= 362,880 possible permutations of the numbers 1 through 9 that we could potentially try. However, since solving the system of equations is the most computationally expensive step of the process, I organized my code so as to exhaust all the other requirements on each step before doing so. I was able to reduce the number of times a system was solved from 362,880 to 1,368 by applying the following restrictions:

• Discard cases in which the total numbers of each fruit are not mutually coprime. This immediately reduces the number of cases to the 49,248 mutually coprime cases (counted with a separate script out of curiosity).
• Discard cases in which the total number of oranges sold is not greater than the other two or in which the total number of apples is not greater than the pears. This reduces the number of cases by a factor of 3!=6--the number of ways to order the 3 fruits--bringing it down to 8,208.
• Arbitrarily label Lady 1 as the lady who bought the most oranges, Lady 2 as the one who bought the second-most oranges, and Lady 3 as the one who bought the fewest oranges. Ensure that these are in the correct order; other orders will be repeats of the same solution. This reduces the number of cases by a factor of 6 again, for the final number of 1,368 cases.

To check for coprimeness, we can find the prime factors of each sum $n_{1j}+n_{2j}+n_{3j}$ and make sure they have none in common. To find the prime factors, we only have to check for divisibility by primes up to 23 because the maximum sum that can occur is the sum of the 3 largest numbers of fruit purchased: 7+8+9=24.

Finally, after the prices have been found in each case, the following additional requirements must be checked. If they are all met, we have a solution!

• The prices must all be non-negative.
• Pears must be the most expensive, followed by oranges, then apples.
• The prices must be in whole pennies.

Putting this all together, my script gave the output below in about 3 seconds. The script tests all cases even if a solution is found, but it would be faster if it stopped after finding a solution. The script itself is posted below in a comment on a comment because I don't want it to take up too much space.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

cases tested: 1368
found on case #: 213
solutions found: 1

price of an orange: 16 pennies
price of an apple: 14 pennies
price of a pear: 19 pennies
sum: 49

number of oranges sold: 19
number of oranges sold: 15
number of oranges sold: 11

*confirm amounts paid*
lady 1: 241
lady 2: 241
lady 3: 241

*confirm coprime*
prime factors of 19: {19}
prime factors of 15: {3, 5}
prime factors of 11: {11}

We will assume the following interpretations:

• each kind of fruit has a fixed price per piece which is a positive integer number of pence.
• 'all amounts' refers to the three sales amounts per type of fruit.

I will do some linear algebra in fruit space. Let fruit space have three dimensions, one for each kind of fruit, therefore a fruit vector assigns a number to each kind of fruit. Each of the ladies' selection of fruits is a fruit vector $\vec{v_i}$ and also the three prices of the fruits form a fruit vector $\vec{p}$ . Note that all coordinates of these four vectors must be positive integers. Remark: For the time being I leave the question open as to which coordinate corresponds to which fruit.

The amount that lady i pays then is the inner product $(\vec{v_i}| \vec{p})$ . Since each lady pays the same amount, we have that $((\vec{v_i}-\vec{v_j})| \vec{p})=0$ . Therefore the plane spanned by the vectors $\vec{v_1}-\vec{v_2}$ and $\vec{v_1}-\vec{v_3}$ must be perpendicular to the price vector $\vec{p}$ .

This means that we can find the direction of the price vector $\vec{p}$ using the outer product:

$\vec{p} = c (\vec{v_1}-\vec{v_2}) × (\vec{v_1}-\vec{v_3})= c (\vec{v_1}× \vec{v_2} + \vec{v_2}× \vec{v_3} + \vec{v_3} × \vec{v_1})$

It follows that for any of the i: $(\vec{v_i}|\vec{p})= c \det (V)$

Here I use a matrix V in which coefficient $v_{ij}$ is the amount of fruit j, bought by lady i.

We know the paid amount is 241d (d is the pre-decimal penny, in the days of Sherlock 1£=20s=240d). Setting $c=\frac{a}{b}$ ( c must be a rational number because all other numbers are integers) we now have

$241b = a \det (V)$

Since 241 is a prime number we either have $241|\det(V)$ or $241|a$ . But in the latter case we will get too large prices.

And since multiples of 241 are too large to be the determinant of 3×3-matices consisting of the 9 different digits 1...9, we will look for such matrices with determinant $\pm 241$ , and set $c=\pm1$ (so just forget about a and b).

Writing out the coordinates, we can always find the coordinates of p, once V and c are known:

$p_1=c(v_{12}v_{23}- v_{13}v_{22} + v_{22}v_{33}- v_{23}v_{32} + v_{32}v_{13}- v_{33}v_{12})$ $p_2=c(v_{13}v_{21}- v_{11}v_{23} + v_{23}v_{31}- v_{21}v_{33} + v_{33}v_{11}- v_{31}v_{13})$ $p_3=c(v_{11}v_{22}- v_{12}v_{21} + v_{21}v_{32}- v_{22}v_{31} + v_{31}v_{12}- v_{32}v_{11})$

Using Excel I did a search for 3×3 matrices with coefficients 1...9 and determinant $\pm241$ , and tried them out, for example:

$V_{fail} = \left| \begin{array}{ccc} 1 & 6 & 4 \\ 2 & 3 & 9 \\ 7 & 8 & 5 \end{array} \right|$ The determinant is +241, so c=+1 and the prices are calculated as above: $p_1=6×9-4×3 +3×5-9×8+8×4-5×6=-13$ , and similarly we find $p_2=29$ and $p_3=20$ .

But here we see that one of the prices is negative, so we discard this solution. There are various reasons to discard solutions, because they have to meet these conditions:

• the determinant is $\pm241$
• the price for each type of fruit is a positive integer
• each price is different
• sales amounts are pairwise coprime
• the least sold fruit is the most expensive, the price of the most sold fruit is between the other prices.

Apart from row or column interchangements, only one matrix meets them all, this matrix is: $V_{success} = \left| \begin{array}{ccc} 1 & 9 & 6 \\ 7 & 2 & 5 \\ 3 & 4 & 8 \end{array} \right|$

which has det=-241, so c=-1, and leads to $\vec{q} = (11, 15, 19)$ and $\vec{p} = (19, 14, 16)$

So that we have our answer: $11+15+19 = \boxed{49}$

In words:

• pears: sold 11 pieces for 19d each
• apples sold 15 sold pieces for 14d each
• oranges: sold 19 pieces for 16d each.

Bonus:

• Lady 1 bought 1 pear, 9 apples and 6 oranges
• Lady 2 bought 7 pears, 2 apples, 5 oranges
• Lady 3 bought 3 pears, 4 apples, 8 oranges.