And it’s a tricky one this week. Yesterday I went shopping and picked up four items. When I got to the till, the cashier added the price of the four items together and the bill was £7.11. I then noticed that I would get exactly the same total if I were to multiply the four prices. How much did each of the items cost?

As ever, please do NOT post your answer, but do say if you have solved it and how long it took. Solution on Monday!

1. If we allow rounding to the nearest pence, then I’ve found an answer in 3 minutes. If not, then I’m still stumped.

This is the kind of thing that people who go on Countdown do when they’re bored, isn’t it?

1. Richard says:

I was on Countdown & am bored. That’s why I start thinking about the fact that the sum and the product are in different units (\$ vs \$^4).

Now to work out the answer assuming pure numbers.

2. MikeT says:

I got an answer but 2 of the prices were imaginary numbers, so it might not be right! 🙂

1. Anonymous says:

I love imaginary numbers!! 😉

2. Marion says:

I love imaginary numbers!! lol 😉

3. Kitty says:

TBH it would make shopping much more interesting.

3. Emily says:

I found this really easy so I’m not entirely sure of my answer. I used very simple algebra.

4. codifier says:

To my embarrassment, I’ve spent 30 minutes scratching on a piece of paper and now I’m giving up in disgust.

5. Quincy says:

Wait, just double checking the question – where you say ” the same total if I were to multiple the four prices”, do you mean the product of the 4 prices is the same as the sum of the 4 prices?

1. Quincy says:

Can’t find any solution that satisfy the question since the question specified that the product is “exactly the same”. I’m thinking that an exact solution possibly doesn’t exist if each item’s price have at most 2 digits after the decimal point and is a positive real number. (I’m pretty certain as I’ve gone through an exhaustive search of all possible permutations of digits…)

Found 980 solutions if rounding is permitted.

6. Marion says:

I looked at this puzzle and thought about it for a bit- and then gave up, I’ve got holiday packing to do and my brain really isn’t working today. (Although I think I may have had a glimmer if inspiration during my musing.)

7. Nick Sharratt says:

8. carlos says:

I found the answer with 15 lines of programming… is there any way to solve it “manually” without inequations?

9. Simon says:

There’s a an infinite number of solutions….
They form 2 disconnected sets on a 2d plane.

1. haydoni says:

Presumably you mean 2 connected sets, 1 disconnected set.

2. Kris says:

There is a finite number of solutions if you assume that no items are priced in fractions of a cent.

3. Simon says:

You’re both right.
And given other peoples comments I approached the problem completely differently and found the unique, exact solution that does not require any rounding.

10. About two minutes because I had to do it in my head; the result is unique.

1. Simon says:

Unique? Why?

2. My bad: I misread a detail and found the answer to the wrong problem. Now I’m embarrassed but I’ll keep thinking.

11. “I then noticed that I would get exactly the same [B]total[/B] if I were to multiple the four prices”

Richard you will not get a “Total”, but a “Product” by multiplying. Is it the catch?!!

12. No, rounding should not be permitted (“exactly the same total”).

So no, there is NO solution. Mr. Wiseman will prove on Monday that he performed some kind of cheating. The way the problem is put, there is no solution.

With integer, if we need to have a+b+c+d = 711 and also a*b*c*d = 711, there is a no-go, because 711 = 79*3*3*1 and that’s all. This is NOT a solution whatsoever.

Besides, multiplying prices is so ambiguous. Multiplying prices in pounds with decimals CAN’T lead to 7.11. And counting in pence (as above) gives no solution either.

I hate tricky phrasing putting people on a wild goose chase…

1. Will says:

With integer, if we need to have a+b+c+d = 711 and also a*b*c*d = 711000000

According to my calculations there is one unique set of four numbers that meets this condition.

2. I agree with Béranger. There is no solution as the only solution for the equation:

a+b+c+d = a*b*c*d is {1, 1, 2, 4}

and that gives a total of 8.

So unfortunately this must be a trick question involving the wording, making it so ambiguous as to be pointless.

3. I have a working answer which uses four numbers with only two decimal places which have the same product and total.

That said, I had to brute force it, I am not up to determining this in an algebraic fashion any more.

4. Simon says:

What Will says is completely correct.

13. Ed says:

@Béranger: There is no cheating – there is one actual solution, where all four prices are an exact number of pence and the multiplication works exactly.

But yes, the multiplication is done in pounds. So if you express the numbers in pence then
A+B+C+D = 711
AxBxCxD = 711000000

Which has rather more factors to try!

14. No, no, no!

He said: “exactly the same total”.

Which is 711. Not 711000000.

Hence no solution OR tricky phrasing. I cannot accept “711000000 is exactly the same as 711”.

1. Will says:

To convert to integer you are multiplying each number by 100 so you need to adjust the equations accordingly, so

a*100+b*100+c*100+d*100 = 7.11*100
a*100*b*100*c*100*d*100 = 7.11*100*100*100*100

15. OK, Will, you’ve got me. But I still can’t see the solution and no, I won’t make a script to brute-force it (or would I?).

1. Will says:

16. Will says:

Perhaps we should say how long our bruit-force attacks took, my c# code cracked it in 3.29 seconds, I’m sure someone can do better.

1. Simon says:

One line in Mathematica… 10.12 seconds

17. Julia says:

“I would get exactly the same total if I were to multiple the four prices. ”

That doesn’t sound like correct English to me. Everyone else seems to be assuming that ‘multiple’ = ‘scale or multiply with each other’. Is that correct? Seems a bit too easy if that’s the case.

1. gussnarp says:

Yeah, multiple is not a verb where I come from, so I don’t understand the question in the least.

18. watching you guys work it out is way more fun than actually doing it 🙂
I am wondering if some where you can still get half/penny chews…

19. Ed says:

@Will: I also used thoroughly brutal force, also with C#.

My way took 0.09 sec to find the solution for the first time, and 1.52 sec to be happy that there were no other solutions.

20. Joao Pedro Afonso says:

I’m throwing out the towel for now. My weirdometer is up the roof in terms of the solutions I already tried and still I don’t have any answer. My admiration for the ones that got it (sorry, but I’m not going to read anything until find something).

And out of here, I go!…

21. Markus says:

Took me about 10 minutes to write a program that found the answer; i first made the error to look for (a*b*c*d)/1000000 == 711, instead of a*b*c*d=711000000, and got lots of wrong answers.

22. A bit of reasoning and a few minutes of trial and error win the day. Many people are being tripped up by ignoring the decimals when they multiply.

(PS: I never cared for math as a student, only going so far as geometry in high school. I managed somehow to test out of math in college. In other words, I neither know advanced math nor needed any to solve this.)

23. Rod says:

0.82 seconds with my Delphi code

24. DonS says:

1.43 seconds in Python.

25. Would the exchange rate to the only form of currency I know…us dollar….. mess with the out come? I can’t think….so I’m throwing a copy of this puzzle, paper, pen, calculator, flash light and banana juice into Richards box filled with his monkey and hope for the best…..monkey should come up with the answer!

1. Just checked in with the monkey….and he has failed me…..someone slipped him a bottle of tequila, a blender, ice and fruit…. all he has done is leave me a list and of all the drinks he could make with what was given him…..I may just join him in the box…….lol….

26. Unbelievable! The solution actually exists, it’s unique and in full pence!

27. Hints: one of the four prices is a multiple of 0.79. And they were all bought in a “seven-eleven” (7-11) store 😉

28. *** Related, but simpler puzzle! ***

«When Jack went back for a late-night snack, he bought three items off the rack.

Zack rang up the snacks and said, “That would be £5.70, Jack.”

“Multiply, add, who cares? It still comes out the same. Pay up.”

What the hack is going on there? What were the prices of Jack’s three items?»

So yes, there are 3 prices in pounds and full pence, that added or multiplied give the same value of 5.70.

Google the first phrase for the solution, and select the 2nd result.

29. slightly_skeptical says:

Brute force, 5 minutes to write and debug C++ code, code did take a long time to get result, several minutes, very inefficient brute force algorithm. Spent another 5 minutes on a new and improved algorithm to get results faster exploring all possible search space in 0.35 seconds. 24 identical permutations returned. First result took 0.135 seconds. Thought I’d share since other wrote code for this.

1. I’d like to see the resulted code. My brute-force 7-lines code is only too slow (~1 minute?).

2. slightly_skeptical says:

I’ll post it on Monday (hopefully I remember). The number of lines of code should be close to what you have – I have some timing and std output code in there that makes it a little larger though. I won’t explain the algorithm (i.e. assumptions made – all valid though) but you should be able to figure it out from the code.

3. slightly_skeptical says:

OK, couldn’t wait, and I don’t think this will spoil the puzzle for anyone – they’d have to write and run this code to get the answer to the puzzle. Here’s my algorithm. Runs in about 0.35 seconds, this solution will generate all 24 identical permutations:

#define NUM 711
for (int i = 1; i < NUM-2; i++)
for (int j = 1; i+j < NUM-1; j++)
for (int k = 1; i+j+k < NUM; k++)
if (i*j*k*(NUM-i-j-k) == NUM * 1000000)
cout << "i = " << i << " j = " << j << " k = " << k << " l = " << NUM-i-j-k << endl;

Now, since all the permutations are all identical, do they all need to be generated? The algorithm could be reduced further by avoiding this repetition yet still covering the entire solution space. This following new solution (slightly modified from the one before) runs in 0.056 seconds:

#define NUM 711
for (int i = 1; i < NUM-2; i++)
for (int j = i; i+j < NUM-1; j++)
for (int k = j; i+j+k < NUM; k++)
if (i*j*k*(NUM-i-j-k) == NUM * 1000000)
cout << "i = " << i << " j = " << j << " k = " << k << " l = " << NUM-i-j-k << endl;

As mentioned it doesn't report all the permutations, but I do believe it covers the entire search space, with the assumption of not duplicating what has already been discovered by the algorithm

4. Kevin says:

You can get it running a LOT faster than that 🙂 Don’t want to spoil things until Monday, but I can post code then if you’re interested.

5. slightly_skeptical says:

I’m interested. I don’t think it will spoil the puzzle for folks since we’re not providing the answer unless they run this code, the brute force approach has already been described and optimizing code that will get you the answer was never part of the puzzle. I think it’s OK.

30. Will says:

I think my c# code is down to 0.024 seconds for a result and 0.026 to complete the search

1. slightly_skeptical says:

WoW. Impressive, I’d like to see the algorithm on Monday if you’re willing, I’ll be posting my solution then.

2. Kris says:

It’s not that difficult if you only search values of x_n∈{x|x<711 – (3 – n) and x≥711/(4-n)} where x_0+x_1+x_2+x_3=711. The only snagging point is that I don't recall the CLR's performance being that good.

3. Kris says:

Sorry, I meant x_n∈{x|x<711 – (3 – n) and x≥(711-∑_{i=0}^{n-1}x_i})/(4-n)}, obviously…

4. slightly_skeptical says:

Not sure I understand your description (not sure what the n in 3-n refers to?), anyhow, here’s my algorithm. Runs in about 0.35 seconds, this solution will generate all 24 permutations:

#define NUM 711
for (int i = 1; i < NUM-2; i++)
for (int j = 1; i+j < NUM-1; j++)
for (int k = 1; i+j+k < NUM; k++)
if (i*j*k*(NUM-i-j-k) == NUM * 1000000)
cout << "i = " << i << " j = " << j << " k = " << k << " l = " << NUM-i-j-k << endl;

Since all the permutations are identical, do they all need to be generated? The algorithm could be reduced further. This following new solution (slightly modified from the one before) runs in 0.056 seconds:

#define NUM 711
for (int i = 1; i < NUM-2; i++)
for (int j = i; i+j < NUM-1; j++)
for (int k = j; i+j+k < NUM; k++)
if (i*j*k*(NUM-i-j-k) == NUM * 1000000)
cout << "i = " << i << " j = " << j << " k = " << k << " l = " << NUM-i-j-k << endl;

As mentioned it doesn't report all the permutations, but I believe covers the entire search space. Not sure if this is similar to the approach you were describing.

5. Kris says:

I believe that has roughly the same result as the method I suggested, though it does cover a significant number of permutations twice. I started from the top, rather than the bottom, which is a bit messier, but it cuts out most of the per-loop calculations and doesn’t result in multiple permutations of the (one) solution. http://pastebin.com/pbbTQ951

6. Kevin says:

A hint for improving those algorithms: once two of the values have been fixed, we have two unknowns and two equations. So no need to iterate more than two levels deep, at the expense of some math. Doing that improved my solving time at least 4x.

7. Will says:

@slightly_skeptical
if you are only looking for the permutation with values in ascending order then I think i need not go above NUM/4 and j need not go above (NUM-i)/3 etc

8. Kris says:

@Kevin, I considered that, but I’d decided to keep to basic mathematics. If I were to resort to algebra, I would have gone a lot further than your suggestion.

9. slightly_skeptical says:

Kris, thanks for the algorithm, very fast and elegant coding style, I clocked it at .035 seconds on my machine. I haven’t fully investigated your code, but I don’t think it’s covering the entire solution space. If you try the number 756 you will notice that some solutions are missing. For example if you use 756 instead of 711 one solution 125,125, 378, 128 is not provided by your algorithm as a valid solution. I think there are more solutions missing but one should be enough.

10. Kevin says:

It’s not very clean, but here’s mine: http://pastebin.com/Ehjyt6ta

The timing stuff is mac specific but is easy enough to change.

solve4() is the optimized routine. Runs in 0.0011 seconds now on this machine.

11. Kris says:

I wouldn’t go that far… It was really quick and dirty. But you’re right. I’m really not awake enough to write this kind of thing, so I won’t gurantee that it’s 100% correct, but changing the condition to >= rather than > (as in the above equation) generates the missing result that you specified.

12. slightly_skeptical says:

Kris, Perfect, that fixed it.

13. slightly_skeptical says:

Kevin I just finished running through your code but it only provides one solution for the case where the value is 7.56. There are 5 unique solutions for that one. The 7.11 problem was solved in .024 seconds on this machine, very fast. Note I uncommented the printf the solution to compare apples to apples between yours, Kris’s and my solutions.

Very fast, but like I said only prints out one solution for the 7.56 problem.

Note I used floor instead of roundl since I couldn’t find it in my math.h, hopefully that didn’t screw things up.

14. slightly_skeptical says:

Oops, 4 not 5 solutions.

15. Kevin says:

@slightly_skeptical: That’s odd, when I run the variant that runs through every possible total, I’m seeing 4 solutions for 7.56:

The total \$7.56 has 4 unique solutions

Replacing the round with a floor can indeed cause problems 🙂 For example the floating point representation of the number 1.2 could “really” be 1.1999999999. Round brings it back to the correct value, floor chops off nearly the entire integer value (floor really does nothing in this particular case because we are assigning to an integer so the compiler floors for us).

16. Kevin says:

… and if you really want to compare apples to apples, I’d keep the console output suppressed and run each solver a couple hundred times at least then get an average 🙂

17. slightly_skeptical says:

Kevin, perfect, the floor was the problem, changed it to floor (x+0.5) to be equivalent to roundl(x), got the 4 solutions. Your method seems the fastest, mine’s the slowest and Kris’s is in the middle. I won’t run multiple runs, pretty clear yours is faster. Thanks, and good work to both of you. Cheers.

18. Kris says:

@slightly_skeptical If you want to use floorl, you need to define _XOPEN_SOURCE=600 before you include math.h (or alternatively, depending on your compiler, set the c99 flag). You also might tweak your optimizer settings. Mine runs 4 times as fast with moderate optimization enabled.

31. Piers Cooper says:

I think a lot of people are thinking far too hard about this. It took me under a minute to see the answer.

32. Easy. It’s a lateral thinking, not an algebraic answer. And this is the first Friday Puzzle I’ve ever got 🙂

33. Whilst I accept that there is a typo ‘multiple’ and an error ‘total’ I cannot see what lateral thinking there can be, unless we are saying that the bill is the same, even if we multiply the numbers together, because us doing some maths does not affect the bill.

It’s a simple (or, in fact, bloody hard) algebraic problem with a single unique answer, as far as I can tell.

34. Jerry says:

Slight typo in the wording [“multiple” instead of “multiply”], but I understand the problem and will work on it this weekend.

35. I thought I’d try out Excel’s goalseek, and it’s actually a pretty crappy method for something like this (probably why you can only use it for 1 value in the first place). Writing the code took all of about 3 minutes. Debugging it and making goalseek work right took another 5. But I’m getting multiple answers, too.

36. Ouch. Took about two hours of off and on working and the front and back of a piece of paper, but I got an answer I feel is correct

37. Allowing rounding I get 31296 solutions (well, different permutations of 1304 solutions), but I can’t find any solutions without allowing rounding, even if I do tricky things like allowing for negatively-priced items or whatever.

1. Kris says:

Then you’ve done something wrong. Are you, by chance, using floating point numbers rather than rational integers? Remember that binary floating point can’t accurately represent every base ten decimal value.

38. Kevin says:

Easily solved in code. Only took a minute or two for a simple coded solution, but that was slow and no fun (9.6 seconds). A simple optimization got the time down to 0.42 seconds, a non-trivial further optimization got the time down to 0.016 seconds, and a fairly complicated solution got the time down to only 0.0041 seconds (of course those times depend on the machine you’re using, but they show the different relative times of the various algorithms). This would be an interesting problem to use when teaching about algorithm optimization in computer science courses.

To those people getting multiple answers above: you’re just getting different permutations of the same set of four numbers, right? Just restrict your solutions so that a <= b <= c <= d and consider that your canonical solution. If you're still getting different solutions then I think you're doing something wrong :p

39. Kevin says:

Just for fun I wanted to check how special £7.11 was. Checked all combinations of 4 numbers that had this property for totals between £0.00 and £10.00. There were surprisingly many of them… 105 to be precise. The smallest is £6.44, the largest £9.99. Many of the totals have multiple solutions too (the most was £8.10 with 5 solutions).

40. mickeyd says:

After some glasses of whiskey it took me five second but not sure the answer is right…

41. Rob says:

Anyone tried the math after the removal of 17.5% VAT 😉

42. Sam42 says:

Well, if it’s a buy 1 get 3 free deal, I have an answer.

43. Jon d says:

Got there by a very bad brute force program. I’d like to think there was a lateral thinking solution I’ve missed so I’ll be tuning in on Monday.

44. I think I have it but only after another poster gave me a clue.ha ha.

45. katie says:

Is it even possible for a person to figure this out? I mean, it seems like everybody who found an answer only found it because they asked a computer to do the problem for them. I don’t know any of the programming languages people are using, so does that mean this puzzle isn’t for me?

1. Kris says:

I’ve never seen Richard post a puzzle that’s meant to be solved by computer. Some of the above posters seem to have found ‘lateral thinking’ methods, but the only way I can think of is a directed guess, check, and revise. Since that’s no fun for me, I just used the computer.

2. I worked out the highest and lowest possible numbers first, then played at guess and revise for a bit. I have to say, it was a deeply unsatisfying problem and I ended up giving up on doing it by hand, it was like doing a suduko puzzle – always achievable, so long as one spends enough time trying, but no fun at all.

3. Cuneiform says:

I initially thought of using some C++ code to let the computer guess the answer for me, but I then went after quite some thinking for an algebraical way. I still had to use a calculator for that.

My solution has a small rounding error. I am curious regarding an exact solution.

4. @Katie I don’t do the math genius bit myself so I think their must be more to it and I just didn’t feel up to it…..but I may just give it a try now!

And @LordManley….I love sudoku very much thank you kindly….lol…

5. Never mind I was right the first time…..I don’t know the answer or even where to start…..this one has the better of me…..oh well there will be more……

46. Jon d says:

Having seen the answers from my program I’m trying to work out if I could have got to them by a satisfying lateral thinking method. And that hasn’t happened for me yet either.
Bah!

1. David Wiley says:

Ditto. I thought I had some clever approaches to the problem, but none of them took me all the way. Then brute-forced the answer with a computer to see if I was barking up the right tree. I wasn’t. I’m interested what Richard and some of the lateral thinkers have to say for themselves on Monday. I’ll probably be kicking myself.

47. Captain says:

I gave up manual solving immediately and wrote a little brute force Python program to find out the answer. I have just started learning Python, so this was a perfect little programming task. 🙂

48. Neil2Russell says:

Had to work out the ballpark range of possible answers first which can be done pretty quickly then look at those most likely to be part of the solution (an earlier post gave a heavy clue). After I realised I’d made a stupid aassumption solved it by hand with an exact (non-rounded) solution in about 10 mins. Would love to know if there is a general principle to solving these though rather than what was effectively trial and error.

49. Joao Pedro Afonso says:

Okay, I still didn’t saw any other comment but I think I might quit. Serves me well for saying Richard’s puzzles has been simple. I even resort to the old pound system… to no avail. I got one solution which in one operation result is 7.11, in another is 7.12… hardly a sum exactly equal to the product. With decimal pounds, the results are worst. I’ll do a last try, but I have no hope. I believe I’m doing the things right… my trials goes now by the millions number… let’s see what cames out Monday.

50. Joao Pedro Afonso says:

Okay, I got it, finally, right before the Bell. Is exactly like Richard said, exact sums and products. I quit from being smart, and did an almost brute-force approach. The solution runs in only 0.08 seconds. Plus one hour for the program. Plus half a day in other stupid clever tries that got me in nothing.

1. Kris says:

2. Joao Pedro Afonso says:

Kris, only now I saw your request. I’ll publish my code in the Monday thread.

3. Joao Pedro Afonso says:

Nice use of defines, by the way. 🙂