A long time at the till

There are two possible approaches to this question, other than trial and improvement/computer-based approaches. One is combinatorial with a little arithmetic and does not need a calculator; the other is algebraic with a little combinatorics and needs a calculator. It is unclear as to which is the most efficient: both are quite involved, although they only involve simple steps.

SOLUTION 1

We wish to find four numbers with at most two decimal places which add up to $7.11$ and multiply together to give $7.11$. The decimals seem awkward, so I will work in pence throughout so that everything is a whole number. The problem is now to find four whole numbers A, B, C, D which add up to $S= 711$ and multiply together to give $P=711,000,000=79\times 5^6\times 3^2\times 2^6$. I'll call A, B, C, D the costs (in pence). I need to allocate these 15 factors to the four costs and will build up the costs factor by factor. I'll use the notation $(a, b, c, d)(z)$ to indicate that $a, b, c, d$ are (unordered) factors allocated so far of the four costs and $z$ are the remaining factors to be distributed amongst the four costs in some way. I'll gradually eliminate factor possibilities by considering the form of $S$ and $P$. The plan is that we can check that we reach the answer without a calculator.

As there are many cases to consider, I'll split the proof up into different explorations and intersperse these with the fact which arise.

Fact 1: Clearly each cost must be positive and less than 711.

Fact 2: The factor 79 can be multiplied by at most 8, since $79\times 9=711$.

Exploration 1: Distribution of the factors of 2.

Since $S$ is odd then either $1$ or $3$ of the costs are even. Thus the costs have factors $(2^6, -, -, -)$ or $(2, 2, 2, -)(2^3)$, with no 2s in the places marked $-$.

Fact 3: The 2s are distributed as follows in, with no 2s in the places marked $-$

$$(2^6, -, -, -)\mbox{ or }(2, 2, 2, -)(2^3)$$

Exploration 2: Distribution of the factors of 5.

Consider the $5^6$ factor of $P$. These six 5s must be distributed amongst the four costs. Clearly each cost cannot be a factor of 5, as the sum of the factors would end in a 5 or a 0. Therefore, at most three of the costs are multiples of 5.

No cost can be a multiple of $5^5 = 3125$; this is too large.

No cost can be a multiple of $5^4=625$, since the remaining $5^2$ and $79$ must be factors of the other $3$ costs; the resulting sum would be greater than $625+25+79> 711$.

Therefore we deduce:

Fact 5: The $5$s are distributed amongst the costs as either

$$(5^3, 5^3, -, -)\,, (5^3, 5^2, 5^1, -)\,,\mbox{ or }(5^2, 5^2, 5^2, -)$$

Exploration 3: Distribution of the factors of 10

Case 3.1 All costs are multiples of 10

Clearly if all costs are multiples of 10 then the factor sum cannot be 711. Therefore we deduce Fact 3.1:

Fact 3.1 The four costs are not all multiples of 10

Case 3.2. Exactly 3 costs are multiples of 10

If three of the costs are multiples of 10 then the final cost must end in a 1 to provide the correct sum. The only combination of factors of $P$ which multiply to give a units digit of $1$ is $79\times 3\times 3=711$. However, this cannot be a cost as it is too large. Therefore, three of the costs cannot be a multiple of 10. Therefore:

Fact 3.2 Exactly 0, 1 or 2 of the costs are multiples of 10.

Case 3.3 What if no cost is a multiple of 10

If none of the costs is a multiple of 10 then no cost can have both a factor of 2 and a factor of 5. Combining this with Fact 5 we see that the costs can only contain factors

$$(2^6, 5^3, 5^3, -), (2^6, 5^3, 5^2, 5)\mbox{ or }(2^6, 5^2, 5^2, 5^2)$$

Since the factor 79 can be multiplied by at most $8$ (see Fact 1) these possibilities reduce to

$$

(2^6=64, 5^3=125, 5^2=25, 5\times 79=395)(3^2)

$$

or

$$

(2^6=64, 5^3=125, 5^3=125, 79)(3^2)

$$

The factor sum of the first and second lists, excluding the factors of 3 are 609 and 393 respectively, leaving a slack in the factor sum of 102 and 318 respectively.

Now, since multiplying a factor by $9$ increases the sum by 8 times the factor we see that the factors which are 3 cannot be in the same cost in either case, since neither 102 nor 318 are multiples of 8. Thus, the 3s need to be split which would increase the sum by double the sum of two factors. These two factors would thus need to add to 51 or 159. A quick inspection shows that neither is possible. Thus we find

Fact 3.3 At least 1 cost is a multiple of 10

Case 3.4: What if exactly one of the costs is a multiple of 10

Recall that either 1 or 3 of the costs are even. Look at these distinct cases separately

Case 3.4.1 What if exactly 1 cost is even and exactly one cost is a multiple of 10

If we have exactly 1 even cost then this must also be the only multiple of 10. The possible factor list is therefore

$$(64\times 5=320, -, -, -)(5^53^279)$$

Since the 64 can be multiplied by at most one $5$ we see that this is only compatible with the $(5^3, 5^2, 5, -)$ distribution of 5s, giving

$$(320, 125, 25, -)(3^279)$$

It is easy to see that the 79 would have to occur in the final cost, leaving as a possibility

$$(320, 125, 25, 79)(3^2)$$

Since the 79 can be multiplied by at most one 3 the digit sum mod 5 will be either $9$ mod $5 = 4$ or $(9\times 3)$ mod $5 = 2$, which means that the sum cannot be 711.

Fact 3.4.1: We cannot have exactly 1 even cost and exactly one multiple of ten.

Case 3.4.2: What if exactly one of the costs is a multiple of 10 and exactly 3 of the costs are even

Clearly we need exactly one of the even factors also to have a factor which is 5. The possible combinations of multiples of 2 and 5 are therefore permutations of $(2,2 ,2 , -)(125, 125, - - )$, since three costs having a factor of 5 and three costs having a factor of 2 would lead to at least two multiples of 10.

This reduces the possibilities to

$$

(250, 125, 2, 2)(2^33^279) \mbox{ with no additional evens or powers of 10}

$$

The factor of $79$ can in principle be multiplied by $2, 4, 6$ or $8$, however only 2 and 4 are small enough when combined with the 250. This leaves two possibilities to consider:

$$

(250, 125, 2\times2^33^2 =144, 158), (250, 125,2\times2^23^2=72 , 316)

$$

Neither of these sum to 1 mod 5, thus neither is possible. Thus, we cannot have exactly one even cost and exactly 3 multiples of 10. Combining this with fact 3.4.1 allows us to deduce that

Fact 3.4.2 We cannot have exactly one cost being a multiple of 10.

Case 3.5 :What if exactly two costs are multiples of 10

In this case we would require at least two factors to be multiples of 2. Therefore we can consider $(2, 2, 2, -)$ combined with either $(125, 125, -, -), (125, 25, 5, -)$ or $(25, 25, 25,-)$. For exactly two multiples of 10 these must combine to give:

$$

(250, 250, 2, -), (250, 50, 5, 2), (250, 25, 10, 2), (125, 50, 10,2)  \mbox{ or }(50, 50, 25, 2)

$$

In each case we still need to distribute the remaining factors $2^33^279$ without creating additional even numbers or multiples of 10.

Consider these two sub cases:

Case 3.5.1: What if only two costs are multiples of 5

The first of these possibilities, which only has two costs which are multiples of 5, must therefore be $(250, 250, 16, 79)(3^2)$. As $79$ cannot be multiplied by $9$ the only possibilities are $(250, 250, 16\times 3, 79\times 3)$ and $(250, 250, 16\times 9, 79)$. The resulting mod 5 sums are $(6+9)\times 3 =0$ mod 5 and $(6\times 9 + 9)= 3$ mod 5; neither, therefore, works.

Fact 3.5.1: There cannot be exactly two multiples of 10 and exactly two multiples of 5.

Case 3.5.2: Exactly three costs are multiples of 5

If exactly three costs are multiples of 5 then the final cost must equal 1 mod 5 to have a chance of giving the correct factor sum. The four remaining lists in question are

$$

(250, 50, 5, 2), (250, 25, 10, 2), (125, 50, 10, 2) \mbox{ or }(50, 50, 25, 2)

$$

The factor $79$ can only appear with the factors 2 or 5 from these lists. Consider these two cases separately.

Case 3.5.2.1 One of the costs is a multiple of $2\times 79$

The cost containing a factor $2\times 79$ might contain additional factors up to $2^33^2$. Since $(2\times 79)$ mod$ 5= 3$ the additional factors in this cost must have product equal to 2 mod 5, so that the overall mod 5 factor will be 1. The possibilities to consider are therefore $2, 7, 12, 17, 22, 27, 32, 37, 42, 47, 52, 57, 62, 67, 72, \dots$. Using three 2s and 2 3s we can only make $2, 12= 2^23, 72$  from this list. Since the $79$ can be multiplied by at most $8$, we can discard all but this first of these possibilities, which we must pick to give a factor of $4\times 79 = 316$. We therefore have four possible factor lists:

 

$(250, 50, 5, 316)(2^23^2)$,

$(250, 25, 10, 316)(2^23^2)$,

$(125, 50, 10, 316)(2^23^2)$,

$(50, 50, 25, 316)(2^23^2)$,

with the understanding that the final cost in each of these lists is fixed and that we introduce no more multiples of 10.

Case 3.5.2.1.1Consider the two lists with a cost of 250 .

Since we cannot have a cost of 500 and a cost of 316 these lists must reduce to

$$

(250, 200, 5, 316)(3^2)\mbox{ and }(250, 25, 40, 316)(3^2)

$$

The sum of the factors for the first of these lists of costs is too large even without the inclusion of the factors of 3. The second of these lists has factor sum 631 without the inclusion of the factors of 3; we need to increase this by 80 to give 711. A quick inspection shows that this is impossible. Therefore the two lists with a cost of 250 are invalid.

Case 3.5.2.1.2 Consider the list of costs with two 50s

Look at the list of costs with two 50s: $(50, 50, 25, 316)(2^23^2)$. The 2s must combine with the 50s to give either $(200, 50, 25, 316)(3^2)$ or $(100, 100, 25, 316)(3^2)$. The factor sums of these lists without including the two factors which are 3 are 591 and 541 respectively, requiring an increase of 120 and 170 respectively to meet the target $S=711$. These are both clearly impossible to meet using factors of $(50, 25)$ and $(100, 25)$ respectively. Thus, these two lists are also invalid.

Case 3.5.2.1.3 Consider the list with a single 50

There is one list left to consider for the case of exactly two 10s: $(125, 50, 10, 316)(2^23^2)$. The factor sum without considering the additional factors of 2 and 3 is 501; thus we need an additional contribution to the factor sum of 210. The 125 cannot be multiplied by 3, as this would increase the sum by 250, which is too large; neither can it be multiplied by 2, as this would introduce an additional even number. Thus, the additional 2s and 3s must be distributed between the 50 and the 10. Inclusion of the factors which are 3s must lead to an increase of 210. To obtain an increase of 210 we can multiply the 50 by $n$ and the 10 by $m$ for the cases

$$

(n, m) = (1, 22), (2, 17), (3, 12), (4, 7), (5, 2)

$$

We are able to create precisely one of these possibilities using the factors $2^23^2$, namely $(3=3, 12= 2^2\times 3)$.

We have therefore, on the very final possibility for the whole problem, found a solution: $(125, 50\times 3, 10\times 12, 316)$. (This was how the solution actually evolved in reality, so it was something of a surprise when it finally arrived!)

In terms of the original problem, this corresponds to the four costs:

$$

3.16, 1.50, 1.25, 1.20

$$

The search was complete and there are, therefore, no other solutions.

SOLUTION 2

In this solution I first eliminate as many of the big number possibilities as I can before moving on to an alternative approach for the smaller numbers. I made heavy use of a calculator.

Upon first trying this problem I first considered the factors of 5 which can be listed as above like

$$X=(125, 125, -, -), Y=(125, 25, 5, -), Z=(25, 25, 25, -)$$

The remaning factors are six factors of 2, two factors of 3 and a factor of 79.

Consider the large factor of 79. This can be multiplied by either 2, 3, 4, 5, 6, or 8 using the available remaining factors.

Therefore, one of the costs, D, say, must be one of the numbers

$$

158, 237, 316, 395, 474, 632

$$

 

Case 1: 632

This case is easy to eliminate as a possibility by considering the possible configurations of 5s.

Case 2: 474

We can also quickly eliminate the case of 474 as follows:

1. Since $474+250> 711$ case $X$ is impossible

2. Consider $Y$ and $474 = 79\times 6$. We need to distribute a factor of 3 and five factors of 2. $711 -125-25-5-474 = 82$. We clearly can't increase by this amount using only multiples of $5$, so case $Y$ must also be impossible.

3. Consider $Z$ and $474$. We find that $711 - 474 - 25-25-25 = 162$.We clearly can't increase by this amount using only factors of 25, so this case is also impossible.

 

Case 3: 395

Using similar reasoning as used for 474, we can quickly see that the case 395 is also impossible.

Case 4: 158, 237 and 316 

The search space is thus reduced to one of the costs being

$$

158, 237, 316

$$

We need to take a different approach for these smaller numbers due to the rapid proliferation of possibilities.

 

 

First case 158: 

Take the first of these, 158. Our conditions on the sum and product reduce to new equations

$$

A+B+C = 711 -158 = 553 \,, ABC = 711, 000, 000/158 =4,500,000

$$

We could suppose that C were fixed at some value and A, B vary. We would then have two equations in two unknowns

$$

A+B = 553 - C\,, AB = 4,500,000/C

$$

Eliminating B gives

$$

A(553-C-A) = 4,500,000/C

$$

Tidying up gives

$$

A^2-(553-C)A+4,500,000/C = 0

$$

This is a quadratic equation in A, with standard solution

$$

A = \frac{(553-C)\pm\sqrt{(553-C)^2-18\times 10^6/C}}{2}

$$

Now, for integer solutions we would require that the part inside the square root (which we can call $\Delta(C)$) is a perfect square and for any real solution at all it must be non-negative.

$$

\Delta(C) = (553-C)^2-18\times 10^6/C= \frac{C^3-1106C^2 + 305809C - 18\times 10^6}{C}

$$

For positive $C$ the denominator of $\Delta(C)$ is obviously positive, whereas the numerator, $N(C)$, of $\Delta(C)$ might not be.

Let us next consider when $N(C)$ is positive.

Note that for large $C$ we have $N(C)> 0$ and for $C=0$ we have $N(C)< 0$.

Clearly we must have $C< 711-158 = 553$ and $N(553)< 0$.Furthermore $N(100)> 0$. Therefore, there is a root of $N(C)=0$ for $C> 100$ and a root of $N(C)=0$ for $C< 100$.

A quick binary search shows that these roots lie in the ranges $(80,90)$ and $(310, 320)$.

Since there is nothing special about the factor $C$, the smallest possible cost $A, B, C$in the problem must be greater than 80 and the largest less than 320.Which combinations of powers of factors $5^63^22^5$ lie in this range? We can make a table of possible values with $1, 2, 4, 8, 16, 32$ along one side and $3, 5, 9, 15, 25, 45, 75, 125, 225$ along the otherside.

We soon find that possibilities for $C$ are

$$

90, 100, 120, 125, 144, 150, 180, 200, 225, 240, 250, 300

$$

A similar argument shows that $A$, $B$ must also take values in this list. Furthermore, $A$, $B$ and $C$ must add to $711-158 =553$, which is impossible. Therefore $D$ is not 158. (Instead of applying this logic, you could also just evaluate $\Delta(C)$ for these 12 cases to see that none gives rise to whole number solutions.)

Next case 237

Note that $711-237 = 474$ and $4\times 711000000/237 = 12,000,000$.

We can easily construct the discriminant of interest:

$$

\Delta(C) = (474-C)^2-12,000,000/C= \frac{C^3-948C^2 + 224676C - 12000000}{C}

$$

A binary search shows that non-negative solutions lie in the range $75< C< 275$. This gives a similar list to the previous case:

$$80, 90, 100, 120, 125, 144, 150, 180, 200, 225, 240, 250$$

The sum $A+B+C$ must equal $711-237=474$. We must therefore include 144 in the sum to have a chance of this working, as we must match the units digit in 474.

This gives

$$

\Delta(144) = \frac{3681600}{144}

$$

This is not a perfect square, so there is no solution with the value $D=237$.

Final case 316

Note that $711-316= 395$ and $4\times 711000000/316 = 9,000,000$.

We can easily construct the discriminant of interest:

$$

\Delta(C) = (395-C)^2-9,000,000/C= \frac{C^3-790C^2 + 156025C - 9000000}{C}

$$

The search for non-negative solutions very quickly takes us to values of $C$ in the range $100< C< 175$. The only possibilities for $C$ in this range are $120, 125, 144, 150$. Symmetry arguments imply that each of $A, B$ must also take these values.

Since $711 - 316 = 395$ we must have $A+B+C=395$, which precludes the possibility of 144. Thus the only possibility to check is $(A, B, C) = (120, 125, 150)$. This clearly works, but we can check that the algebra works if we like. Choose $C=120$, for example. This gives:

$$

\Delta(120) = 625

$$

This is a perfect square, yielding

$$

A = \frac{(395-120)\pm\sqrt{(395-120)^2-9000000/120}}{2}= \frac{275\pm 25}{2} = 150, 1 25

$$

These are the other two possibilities implied by the algebra.

 

Phew!